Этот блог является продолжением серии моих блогов о JavaCC Установка JavaCC для Mac. Цель этого блога - реализовать очень простой, но расширяемый синтаксический анализатор на основе команд. Команды будут

moveForward()
turnRight()

Вот схема железной дороги для языка

Мы будем использовать генерацию кода JavaCC для создания синтаксического анализатора, передав ему правильную грамматику EBNF.

Грамматика EBNF

CFG - контекстно-свободная грамматика - это набор производственных правил, которые могут применяться независимо от контекста к любому нетерминальному

EBNF - язык метасинтаксиса, основанный на теории CFG и позволяющий анализировать фразы и предложения. По сути, это просто набор вызовов функций Regex и Recursive, которые используются для формирования дерева синтаксического анализа.

Терминалы - все, что не имеет никаких производственных правил. Например. строки «BEGIN» и «END» являются терминалами в программе на Паскале.

Нетерминальные элементы - это что-либо, что может создавать один или несколько нетерминалов. (может даже называть себя)

Токены - это то, что соответствует выражению регулярного выражения. Например. если вы пишете математический калькулятор, числовой жетон будет

<number: [“1”- “9”] ([“0”- “9”])+

Пример программы

FORWARD 20
LEFT 120
RIGHT 40
FORWARD 20

Вывод программы

Call:   Program
  Call:   MoveForward
    Consumed token: <"FORWARD" at line 1 column 1>
    Consumed token: <<DIGITS>: "20" at line 1 column 9>
    Consumed token: <<EOL>: "
" at line 1 column 11>
  Return: MoveForward
Processed Move FORWARD
  Call:   Error
    Consumed token: <<ERROR>: "L" at line 2 column 1>
  Return: Error
  Call:   handleError
*** ERROR: Line 2 after "L"
    Consumed token: <<ERROR>: "E" at line 2 column 2> (in getNextToken)
    Consumed token: <<ERROR>: "F" at line 2 column 3> (in getNextToken)
    Consumed token: <<ERROR>: "T" at line 2 column 4> (in getNextToken)
    Consumed token: <<DIGITS>: "120" at line 2 column 6> (in getNextToken)
    Consumed token: <<EOL>: "
" at line 2 column 9> (in getNextToken)
  Return: handleError
  Call:   TurnRight
    Consumed token: <"RIGHT" at line 3 column 1>
    Consumed token: <<DIGITS>: "40" at line 3 column 7>
    Consumed token: <<EOL>: "
" at line 3 column 9>
  Return: TurnRight
Processed Turn RIGHT
  Call:   MoveForward
    Consumed token: <"FORWARD" at line 4 column 1>
    Consumed token: <<DIGITS>: "20" at line 4 column 9>
    Consumed token: <<EOF> at line 4 column 10>
  Return: MoveForward
Processed Move FORWARD
Return: Program

Как видите, все было успешно проанализировано, а команда LEFT не была включена и пропущена. Теперь нетрудно расширить этот синтаксический анализатор, включив в него столько команд, сколько вы хотите, но чем это вообще может быть полезно? Я согласен с тем, что сам по себе синтаксический анализ не очень полезен, но не намного сложнее придать смысл каждому из этих узлов синтаксического анализа, которые мы только что создали.

В этом разборе вы создали AST, в котором программа является корневым узлом и имеет четырех дочерних узлов. Теперь все, что вам нужно сделать, это пройти по дереву и выполнить соответствующую операцию для каждого узла!

FORWARD 20 <- node 1
Error <- node 2
RIGHT 40 <- node 3
FORWARD 20 <- node 4

В следующем блоге мы попытаемся взять эти узлы и вернуть векторную сумму всех команд.