Реализация на PHP одного примера из старой книги

Книга "Автоматический синтаксический анализ", автор Дж. Фостер, 1970 год.

В параграфе 4.1 рассматривается алгоритм разбора "сверху вниз" для грамматики
$$
S\ \mapsto\ T\ |\ S+T,
$$
$$
T\ \mapsto\ ид\ |\ ид\times T.
$$

Здесь "ид" -- это идентификатор (как имя переменной). Мы будем предполагать, что он может состоять из букв, цифр и знаков нижнего подчёркивания, и обязан начинаться с буквы.

Функция tokenizer() строит по входной строке массив с последовательностью слов.

Фунция parser() строит по этому массиву бинарное дерево. Может находить места синтаксических ошибок.

Функция processor() показывает, зачем нужно это дерево. Вычисляет значение разобранного выражения.

<?php

/**
 * Даны три типа слов: идентификаторы, знак умножения "*" и знак
 * сложения "+". Идентификаторы могут состоять из букв, цифр и знаков
 * нижнего подчёркивания, но идентификатор обязан начинаться с буквы.
 * 
 * Входная строка также может содержать разделители -- последовательности,
 * состоящие из следующих символов: пробел " ", "\n",
 * "\r" или "\t".
 * 
 * S --> T | T + S
 * T --> ид | ид * T
 */

const ADD_SYMBOL = '+';
const MUL_SYMBOL = '*';

function tokenizer($inputString)
{
    $spaceSymbols = [" ", "\n", "\r", "\t"];
    $opsSymbols   = [ADD_SYMBOL, MUL_SYMBOL];
    $wordsArray = [];

    $identifier = '';
    $inputStringLength = mb_strlen($inputString);

    for ($i = 0; $i < $inputStringLength; $i++) {

        $char = $inputString[$i];

        if (in_array($char, $spaceSymbols)) {
            continue;
        } elseif (in_array($char, $opsSymbols) ) {
            $wordsArray[] = $char;
        } elseif (ctype_alpha($char)) {
            $identifier = $char;
            while
                (
                    $i+1 < $inputStringLength           &&
                    (
                        ctype_alpha($inputString[$i+1]) ||
                        ctype_digit($inputString[$i+1]) ||
                        $inputString[$i+1] === '_'
                    )
                ) {
                $identifier .= $inputString[++$i];
            }
            $wordsArray[] = $identifier;
        }
    }
    
    return $wordsArray;
}

function isIdentifier($string)
{
    return ctype_alpha($string[0]);
}

function report_error($first, $second, $offset)
{
    echo "Syntax error! $first expected but $second found.\nSee the word number $offset\n";
    die();
}

// Применить шаблоны класса T
function T_handler(&$fork, $offset, $T_postion)
{
    global $wordsArray, $wordsArrayLength;
    
    if (
        $offset + 2 < $wordsArrayLength         &&     //  id * T
        isIdentifier($wordsArray[$offset])      &&
        $wordsArray[$offset + 1] === MUL_SYMBOL &&
        isIdentifier($wordsArray[$offset + 2])
        )
    {
        $fork[$T_postion] = ['T', null, null];
    } elseif (
        $offset < $wordsArrayLength             &&      // id
        isIdentifier($wordsArray[$offset]) 
        )
    { 
        if (
            $offset + 1 < $wordsArrayLength         &&
            $wordsArray[$offset + 1] === MUL_SYMBOL &&
            (
                empty($wordsArray[$offset + 2])         ||
                !isIdentifier($wordsArray[$offset + 2])
            )        
        ) {
            report_error('Identifier', $wordsArray[$offset + 2] ?? 'nothing', $offset + 2);
        } elseif (
            $offset + 1 < $wordsArrayLength         &&
            $wordsArray[$offset + 1] !== MUL_SYMBOL &&
            $wordsArray[$offset + 1] !== ADD_SYMBOL
            ) {
            report_error(ADD_SYMBOL. ' or '. MUL_SYMBOL, $wordsArray[$offset + 1] ?? 'nothing', $offset + 1);
        } else {
            $fork[$T_postion] = ['T', null];
        }
    } else {
        report_error('Identifier', $wordsArray[$offset] ?? 'nothing', $offset);
    }
    $fork_ref = &$fork[$T_postion];
    return parser($fork_ref, $offset);
}

// Применить шаблоны класса S
function S_handler(&$fork, $offset)
{
    global $wordsArray, $wordsArrayLength;

    if (
        $offset < $wordsArrayLength         &&
        $wordsArray[$offset] === ADD_SYMBOL
        )
    {
        $reminder = array_slice($wordsArray, $offset + 1);
        $fork[2] = in_array(ADD_SYMBOL, $reminder) ? ['S', null, null] : ['S', null];
    } else {
        return report_error(ADD_SYMBOL, $wordsArray[$offset] ?? 'nothing', $offset);
    }
    $fork_ref = &$fork[2];
    
    return parser($fork_ref, $offset + 1);
}

function parser(array &$fork = null, int $offset = 0)
{
    global $wordsArray;
    
    // Признак. Если в предложении есть +, то S --> T + S, иначе S --> T.
    if (is_null($fork)) {
        $fork = in_array(ADD_SYMBOL, $wordsArray) ? ['S', null, null] : ['S', null];
    }
    
    switch ($fork[0]) {
        case 'S':       // S --> T | T + S
            $new_offset = T_handler($fork, $offset, 1);

            if (count($fork) === 3) {   // S --> T + S
                $new_offset = S_handler($fork, $new_offset);
            }
            
            return $new_offset;
        case 'T':
            $fork[1] = ['id', null];
            $fork_ref = &$fork[1];
            $new_offset = parser($fork_ref, $offset);
            
            if (count($fork) === 3) {   // T --> id * T
                $new_offset = T_handler($fork, $offset + 2, 2);
            } 
            return $new_offset;
        case 'id':
            if (isIdentifier($wordsArray[$offset])) {
                $fork[1] = $wordsArray[$offset];
                return $offset + 1;
            } else {
                return report_error('Identifier', $wordsArray[$offset] ?? 'nothing', $offset);
            }
    }
}

function processor($fork)
{
    global $vars_array;
    
    switch ($fork[0]) {
        case 'S':
            if (count($fork) === 3) {
                return processor($fork[1]) + processor($fork[2]);
            } else {
                return processor($fork[1]);
            }
        case 'T':
            if (count($fork) === 3) {
                return processor($fork[1]) * processor($fork[2]);
            } else {
                return processor($fork[1]);
            }
        case 'id':
            return $vars_array[$fork[1]] ?? 0;
    }
}

// Входная строка. Сделаем из неё массив слов.
$inputString = '  ab * c_1 *ddef4+fgrg+ x * y * z';

// Это глобальные переменные для parser().
$wordsArray = tokenizer($inputString);
$wordsArrayLength = count($wordsArray);

  print_r($wordsArray);
  
$fork = null;
parser($fork);

print_r($fork);
  
  
$vars_array = [
    'ab' => 12,
    'c_1' => 24,
    'ddef4' => 266,
    'fgrg' => 232.02,
    'x' => 54,
    'y' => 23,
    'z' => 132.0432,
];

echo processor($fork);
echo "\n";

echo "Тестовое вычисление для сравнения результатов:\n";
$ab = 12;
$c_1 = 24;
$ddef4 = 266;
$fgrg = 232.02;
$x = 54;
$y = 23;
$z =132.0432;

echo   $ab * $c_1 *$ddef4+$fgrg+ $x * $y * $z;

Вывод скрипта:

Array
(
    [0] => ab
    [1] => *
    [2] => c_1
    [3] => *
    [4] => ddef4
    [5] => +
    [6] => fgrg
    [7] => +
    [8] => x
    [9] => *
    [10] => y
    [11] => *
    [12] => z
)
Array
(
    [0] => S
    [1] => Array
        (
            [0] => T
            [1] => Array
                (
                    [0] => id
                    [1] => ab
                )

            [2] => Array
                (
                    [0] => T
                    [1] => Array
                        (
                            [0] => id
                            [1] => c_1
                        )

                    [2] => Array
                        (
                            [0] => T
                            [1] => Array
                                (
                                    [0] => id
                                    [1] => ddef4
                                )

                        )

                )

        )

    [2] => Array
        (
            [0] => S
            [1] => Array
                (
                    [0] => T
                    [1] => Array
                        (
                            [0] => id
                            [1] => fgrg
                        )

                )

            [2] => Array
                (
                    [0] => S
                    [1] => Array
                        (
                            [0] => T
                            [1] => Array
                                (
                                    [0] => id
                                    [1] => x
                                )

                            [2] => Array
                                (
                                    [0] => T
                                    [1] => Array
                                        (
                                            [0] => id
                                            [1] => y
                                        )

                                    [2] => Array
                                        (
                                            [0] => T
                                            [1] => Array
                                                (
                                                    [0] => id
                                                    [1] => z
                                                )

                                        )

                                )

                        )

                )

        )

)
240837.6744
Тестовое вычисление для сравнения результатов:
240837.6744