Как работает LR Automaton?

Question

В этом LR (0) автомат

Есть переходы для некурящих терминалов, а также, что я не понимаю. Если входной сигнал aab. Затем вы попадете в состояние, которое равно A->a·. Если бы вы визуализировали состояние, которое было достигнуто путем ввода aab или любого другого входа, не было бы переходов между состояниями, у которых нет дуг между ними?

Я не понимаю, почему это отличается от DFA или NFA, где вы начинаете в исходном состоянии, и переходите только по дугам в Automata, пока не достигнете принимающего состояния.

Answer 1

Переходы, помеченные nonterminal, выполняются только после выполнения операции уменьшения. Когда вы сделаете сокращение, вы удалите некоторое количество символов из стека разбора, а затем вставьте нетерминал в стек. В этот момент вы будете следить за переходом, отмеченным этим конкретным нетерминалом.

Автоматический синтаксический анализатор отличается от типичного DFA или NFA тем, что он предназначен для управления стеком. Переходы все соответствуют различным действиям в стеке синтаксического анализа; каждый терминал соответствует сдвигу, завершенные элементы соответствуют сокращениям, а нетерминалы говорят вам, куда идти после выполнения сокращения. Теоретически, LR-автомат является управлением для детерминированного автомата толкания, если это помогает.

Answer 2

В парсинге LR используется стоп-кадр состояний, который в любой точке представляет собой набор не полностью признанных производств в синтаксическом анализе. Когда достигается состояние с полным производством (точка находится в конце, такая как «A -> a.»), это означает, что у стека есть символы с правой стороны этой продукции вверху. Вы выталкиваете их, чтобы вернуться в состояние, которое запустило эту конкретную последовательность переходов, и теперь переходим к не-терминалу в левой части этого производства.

Так что, если вы достигнете 'A -> a.', вам нужно создать резервную копию одного перехода (путь с пометкой «a») и вместо этого принять переход «A». Если вы достигнете «S -> AB.», вам нужно выполнить резервное копирование двух переходов и вместо этого перейти на «S». И так далее.

Нет такого возврата (или соответствующей необходимости поддержания стека) с помощью DFA или NFA.

Answer 3

Автомат LR - это пусковой автомат, который использует стек состояний, а не одно текущее состояние, как с DFA. Действия (shift, reduce и goto) управляются государством, находящимся в верхней части стека, со сдвигом и goto, нажимая новое состояние и уменьшая количество фиксированных состояний на основе уменьшаемого правила. В вашем примере, если мы подсчитаем состояния в столбцах (так что 0 - начальное состояние в верхнем левом углу, 3 - состояние в среднем столбце), мы можем показать, как он анализирует входную строку «ab»:

Action    Stack 
initial state  0 
shift a    0 1 
reduce A->a   0 
goto A    0 3 
shift b    0 3 4 
reduce B->b   0 3 
goto B    0 3 5 
reduce S->AB  0 
goto S    0 2 
accept 

Поскольку это парсер LR (0), каждое состояние имеет либо действие shift/goto, либо одно действие уменьшения, и нет необходимости в поиске, чтобы знать, что делать дальше (хотя сдвиг, который потребляет входной токен, зависят от этого токена, чтобы определить, какое состояние переключиться на).

Для ввода «AAB» процесс только немного дольше:

Action    Stack 
initial state  0 
shift a    0 1 
reduce A->a   0 
goto A    0 3 
shift a    0 3 1 
reduce A->a   0 3 
goto A    0 3 3 
shift b    0 3 3 4 
reduce B->b   0 3 3 
goto B    0 3 3 5 
reduce S->AB  0 3 
goto S    0 3 6 
reduce B->S   0 3 
goto B    0 3 5 
reduce S->AB  0 
goto S    0 2 
accept 

показывает эффект правой возвратных степенных правило, чтобы соответствовать несколько элементов а на входе (B -> S -> AB), что приводит к тому, что все а сдвинуты (нажатие состояний в стеке) до тех пор, пока не будет достигнута окончательная последовательность повторной последовательности, а затем серия действий reduce/goto, чтобы отбросить их. Лучше использовать леворекурсивное правило и использует фиксированное количество пространства стека, чередуя смены и уменьшая.