Стандартный алгоритм токенизации строки, сохранения разделителей (в PHP)

Question

Я хочу разбить арифметическое выражение на токены, чтобы преобразовать его в RPN.

Java имеет StringTokenizer, который может содержать разделители. Таким образом, я мог бы использовать операторы в качестве разделителей. К сожалению, мне нужно сделать это в PHP, в котором есть strtok, но он отбрасывает разделители, поэтому мне нужно самому что-то приготовить.

Это звучит как классический пример учебника для Compiler Design 101, но я боюсь, что мне здесь не хватает формального образования. Можете ли вы указать мне стандартный алгоритм?

Другие мои варианты - прочитать Lexical Analysis или свернуть что-нибудь быстрое и грязное с доступными строковыми функциями.

Answer 1

Это может помочь.

Практическое использование токенизатора

Answer 2

Как часто, я бы просто использовал для этого регулярное выражение:

<code>$expr = '(5*(7 + 2 * -9.3) - 8 )/ 11';
$tokens = preg_split('/([*\/^+-]+)\s*|([\d.]+)\s*/', $expr, -1,
        PREG_SPLIT_DELIM_CAPTURE | PREG_SPLIT_NO_EMPTY);
$tts = print_r($tokens, true);
echo "<pre>x=$tts

";

Требуется немного больше работы, чтобы принимать числа с показателем степени (например, -9.2e-8).

Answer 3

ОК, спасибо PhiLho, мой последний код такой, если кому-то это понадобится. Это даже не очень грязно. : -)

static function rgTokenize($s)
{
    $rg = array();

    // remove whitespace
    $s = preg_replace("/\s+/", '', $s);

    // split at numbers, identifiers, function names and operators
    $rg = preg_split('/([*\/^+\(\)-])|(#\d+)|([\d.]+)|(\w+)/', $s, -1, PREG_SPLIT_DELIM_CAPTURE | PREG_SPLIT_NO_EMPTY);

    // find right-associative '-' and put it as a sign onto the following number
    for ($ix = 0, $ixMax = count($rg); $ix < $ixMax; $ix++) {
        if ('-' == $rg[$ix]) {
            if (isset($rg[$ix - 1]) && self::fIsOperand($rg[$ix - 1])) {
                continue;
            } else if (isset($rg[$ix + 1]) && self::fIsOperand($rg[$ix + 1])) {
                $rg[$ix + 1] = $rg[$ix].$rg[$ix + 1];
                unset($rg[$ix]);
            } else {
                throw new Exception("Syntax error: Found right-associative '-' without operand");
            }
        }
    }
    $rg = array_values($rg);

    echo join(" ", $rg)."\n";

    return $rg;
}