Попытка понять парсеров

Question

Я пытаюсь использовать JavaCC для создания простого калькулятора командной строки, который может обрабатывать различные выражения. Хотя есть много учебников о том, как писать грамматики, ни один из которых я не видел до сих пор, объясняет, что происходит потом.

Теперь я понимаю, что после того, как строка передается в синтаксический анализатор, она разбивается на токены и превращается в дерево синтаксического анализа. Что будет дальше? Прохожу ли я через дерево разбора, проводя кучу сравнения строк if-else по содержимому каждого узла, а затем выполняю соответствующую функцию?

Answer 1

Я настоятельно рекомендую вам посмотреть Scott Stanchfield's ANTLR 3.x tutorials. Даже если вы не закончите использовать ANTLR, который может быть излишним для вашего проекта, но я сомневаюсь в этом, вы узнаете много, наблюдая, как он проходит процесс мышления.

В целом процесс ...

1. Построить лексера, чтобы понять ваши маркеры
2. построить синтаксический анализатор, который может проверить и понять и организовать ввод в абстрактное синтаксическое дерево (AST), который должен представляет собой упрощенный/простой в работу-с версией вашего синтаксиса
3. Выполнить любой расчет на основе AST

Answer 2

Вы должны компилировать или интерпретировать его в соответствии с йо u need ..

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

Конечно, вы могли бы разработать свою собственную виртуальную машину, которая может выполнять набор инструкций, в которых ваш язык компилируется, но это будет излишним в вашем случае. Просто зайдите в дерево разбора. Что-то вроде:

enum Operation { 
    PLUS, MINUS 
} 

interface TreeNode { 
    float eval(); 
} 

class TreeFloat implements TreeNode { 
    float val; 
    float eval() { return val; } 
} 

class TreeBinaryOp implements TreeNode { 
    TreeNode first; 
    TreeNode second; 
    Operation op; 

    float eval() { 
    if (op == PLUS) 
     return first.eval()+second.eval(); 
} 

Тогда вы просто вызываете функцию eval на корень дерева. Может понадобиться семантическая проверка (с построением таблицы символов, если вы планируете иметь переменные или что-то еще).

Answer 3

Пройтись через дерево синтаксического анализа, проводя кучу сравнений строк if-else по содержимому каждого узла, а затем выполните соответствующую функцию?

Нет, нет необходимости строить дерево разбора для реализации калькулятора. В тех частях кода, где вы создадите новый объект узла, просто выполните вычисления и верните число.

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

Answer 4

Некоторые генераторы парсеров (такие как YACC) позволяют помещать действия в грамматику, поэтому, применяя определенную продукцию, вы также можете применить определенное действие во время этого производства.

E.g. в YACC:

E: NUM + NUM  {$$ = $1.value + $2.value}; 

будет добавлять значения NUM и возвращать результат в E-терминал.

Не знаете, что позволяет JavaCC.