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

Question

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

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

Answer 1

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

В общем, процесс ...

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

Answer 2

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

например. в YACC:

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

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

Не уверен, что JavaCC позволяет вам делать.

Answer 3

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

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

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

Answer 4

Вы должны фактически скомпилировать или интерпретировать его в соответствии с тем, что вам нужно ..

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

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

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 в корне дерева.Может потребоваться семантическая проверка (с созданием таблицы символов, если вы планируете иметь переменные или что-то еще).