Правильный LL (1) грамматики для арифметических выражений

Question

Это правильная грамматика LL:

Е-> TX

Т -> (Е) Y | Инты

Х -> + E | -E | e

Y -> * E |/E | е

но будет производить то же AST дерева для выражения

INT-ИНТ ИНТ и int- (целое + целое)

э

Sub (Simple (int), Add (Simple (int), Simple (int))

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

Answer 1

Попробуйте грамматику

E -> T E' 
E' -> + T E' | -TE' |epsilon 
T -> F T' 
T' -> * F T' | /FT' |epsilon 
F -> (E) | int 

Answer 2

решили эту проблему, добавив некоторые дополнительные "если-S" по оценке AST. Грамматика остается неизменной.

Answer 3

Анализ синтаксического анализа операторов основан на снижении с понижением вниз parsing. В выражении анализируемые токены переносятся в стек. В подходящее время стек уменьшается, применяя оператор к вершине стека. Это лучше всего иллюстрирует пример.

Мы определяем два стека: opr, для операторов и val, для значений. A '$' обозначает конец ввода или конец стека. Первоначально стеки пусты, и вход содержит выражение для синтаксического анализа. Каждое значение, так как оно встречается, смещается в стек. Когда встречается первый оператор (шаг 2), мы переносим его в стек opr. Второе значение сдвигается к стеку theval на шаге 3. На шаге 4 мы имеем символ «*» в opr и символ «+». Поскольку мы хотим размножаться до того, как мы добавим (предоставляя приоритет умножения), мы уменьшим содержимое val, применяя оператор '*' к вершине val. После уменьшения оператор «+» будет сдвинут на opr на шаге 5. Этот процесс продолжается до тех пор, пока входные данные и opr не будут пустыми. Если все пойдет хорошо, нам следует оставить ответ в вале. В следующей таблице приведены действия, предпринятые как функция ввода и верхняя часть opr:

Когда входной токен равен «+», а «+» - на opr, мы уменьшаем перед переносом нового «+» на opr , Это приводит к тому, что самый левый оператор выполняется первым, и подразумевает, что добавление является лево-ассоциативным. Если бы мы вместо этого переместились, то дополнение было бы право-ассоциативным. Когда входной токен равен «», а «+» - в opr, сдвигаем «» на opr. Позже, при уменьшении, «*» выставляется перед «+», давая преимущество умножению. Правильно указав действия сдвига и уменьшения, мы можем контролировать ассоциативность и приоритет operators в выражении. Когда мы сталкиваемся с оператором во входном потоке и operator уже находится в стеке, выполните следующие действия: Если значения operators отличаются друг от друга, сдвиньте, чтобы дать higher precedence на вход operator. Если operators одинаковы, сдвиг для правильной ассоциативности.для более посещения: operator-precedence-parsing