Почему ANTLR не уменьшает это выражение?

У меня есть следующая грамматика:

expr : factor op ;
op
    : '+' factor op
    | // Blank rule for left-recursion elimination
    ;

factor 
    : NUM
    | '(' expr ')'
    ;

NUM : ('0'..'9')+ ;

Я задаю 2 + 3, используя expr в качестве начального правила. Результирующее дерево синтаксического анализа от ANTLR правильное; однако я думаю, что неправильно понимаю методы сдвига-уменьшения, которые он использует.

Я ожидаю, что произойдет следующее:

 Step # | Parse Stack   | Lookahead | Unscanned | Action
 1      |               | NUM       | + 3       | Shift
 2      | NUM           | +         | 3         | Reduce by factor -> NUM
 3      | factor        | +         | 3         | Shift a 'null'?
 4      | factor null   | +         | 3         | Reduce by op -> null
 5      | factor op     | +         | 3         | Reduce by expr -> factor op
 6      | expr          | +         | 3         | Shift
 7      | expr +        | NUM       |           | Shift
 8      | expr + NUM    |           |           | Reduce by factor -> NUM
 9      | expr + factor |           |           | ERROR (no production)

Я ожидал, что на шаге 3 произойдет ошибка, когда синтаксический анализатор shift поместит в стек null в качестве предварительного условия для reduce увеличения коэффициента до expr.

Сдвигает ли ANTLR null только тогда, когда это строго «требуется», потому что результирующий reduce будет удовлетворять грамматике?


antlr antlr4 parsing lr
person Adam Kewley    schedule 12.05.2016    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Мне кажется, что ANTLR не использует синтаксический анализатор сдвига-уменьшения; сгенерированные парсеры являются рекурсивным спуском с использованием произвольного количества просмотров вперед.

Шаги парсера будут примерно такими:

Rule          | Consummed | Input
--------------+-----------+------
expr          |           | 2 + 3
..factor      |           | 2 + 3
....NUM       | 2         | + 3
..op          | 2         | + 3
....'+'       | 2 +       | 3
....factor    | 2 +       | 3
......NUM     | 2 + 3     |
....op        | 2 + 3     |
......(empty) | 2 + 3     |

Из того, что я читал об ANTLR, вы можете добиться того же результата со следующими изменениями в исходной грамматике:

expr: factor op*;
op: '+' factor;
...
person Branco Medeiros    schedule 12.05.2016
comment
Разве рекурсивный спуск не является методом синтаксического анализа сверху вниз? Я думал, что ANTLR производит парсеры LR снизу вверх? - person Adam Kewley; 12.05.2016
comment
(меня смущает то, что, когда я читаю статьи о LR, меня направляют к восходящим методам, таким как сдвиг-уменьшение, а когда я читаю о рекурсивном спуске, меня направляют к нисходящим методам синтаксического анализа) - person Adam Kewley; 12.05.2016
comment
Хорошо, я полный идиот, которому нужно прочитать ссылку ANTLR. Он производит парсер LL! - person Adam Kewley; 12.05.2016
comment
Если бы он был восходящим, не было бы необходимости в левом факторе или удалении левой рекурсии. - person rici; 12.05.2016
comment
Для записей «LR» - это «распознавание языка», а не обычное «слева направо, крайнее правое производное». Все название означает «Другой инструмент для распознавания языка»: o) - person Seki; 15.05.2016
comment
В дополнение к Read the F ***** g Manual (RTFM) SO мог бы сделать с Read The F ***** g Acronym (RTFA) ;) - person Adam Kewley; 16.05.2016