Как алгоритм yacc / bison LALR (1) обрабатывает «пустые» правила?

Question

В синтаксическом анализаторе LALR (1) правила в грамматике преобразуются в таблицу синтаксического анализа, которая фактически говорит: «Если у вас есть этот вход до сих пор, и токен предпросмотра - X, то перейдите в состояние Y или уменьшите наrule R ".

Я успешно сконструировал синтаксический анализатор LALR (1) на интерпретируемом языке (ruby), не используя генератор, но вычисляя таблицу синтаксического анализа во время выполнения и оценивая ввод, используя эту таблицу синтаксического анализа.Это работает на удивление хорошо, и генерация таблиц довольно тривиальна (что меня несколько удивило), поддерживая правила самоссылки и лево-правую ассоциацию.

Однако мне сложно понять, как yacc/ bison концептуально обрабатывает пустые определения правил.Мой синтаксический анализатор не может их обработать, поскольку при создании таблицы он рекурсивно просматривает каждый символ в каждом правиле, и «пустой» не является чем-то, что исходит от лексера и не уменьшается правилом.Так как же тогда парсеры LALR (1) обрабатывают пустое правило?Они рассматривают это специально или это «естественная» концепция, с которой действующий алгоритм должен просто работать, даже не имея особой осведомленности о такой концепции?

Скажем, правило, которое может соответствовать любомуколичество парных скобок без середины:

expr:   /* empty */
      | '(' expr ')'
      ;

Ввод, подобный следующему, будет соответствовать этому правилу:

((((()))))

Это означает, что при прочтении '(' и просмотре ')'в маркере упреждения парсер выбирает:

1. Сдвиг ')' (невозможно)
2. Уменьшить ввод в соответствии с другим правилом (невозможно)
3. Что-то еще ...

не совсем вписывается в основной алгоритм "смещения" или "уменьшения".Парсер фактически должен ничего не сдвигать в стек, уменьшать «ничто» до expr, затем сдвигать следующий токен ')', давая '(' expr ')', что, конечно, уменьшает до expr и т. Д.

Меня смущает "сдвиг ничто".Как таблица разбора передает такую ​​концепцию?Также учтите, что должна быть возможность вызвать некоторое семантическое действие, которое возвращает значение до $$ при уменьшении пустого значения, так что довольно упрощенное представление просто пропустить это из таблицы разбора и сказать, что '(' в стеке и ')' в предвкушении должно просто переводить в смену, не будет действительно производить последовательность '(' expr ')', а просто будет производить последовательность '(' ')'.

Answer 1

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

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

В случае пустого правила вам не нужно считать, что «пустой» - это даже концепция. Таблица разбора просто должна включать в себя переход, который говорит: «дано '(' в стеке и« все, что не '(' в прогнозе, уменьшите по «пустому» правилу ». Теперь, когда пустое правило имеет размер нулевых компонентов, удаление нуля из стека означает, что стек не изменяется, а затем, когда результат уменьшения ничего не перемещается в стек, вы смотрите на то, что действительно появляется в грамматика и все становится ясно.

Stack       Lookahead    Remaining Input      Action
--------------------------------------------------------------
$           (            ())$                 Shift '('
$(          (            ))$                  Shift '('
$((         )            )$                   Reduce by /* empty */
$((expr     )            )$                   Shift ')'
$((expr)    )            $                    Reduce by '(' expr ')'
$(expr      )            $                    Shift ')'
$(expr)     $                                 Reduce by '(' expr ')'
$expr                                         Accept

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

Answer 2

Другой способ, возможно, завершить отличный ответ d11wtq, если это возможно:

Правило, допускающее обнуление (которое выводит ϵ), учитывается при построении синтаксического анализатора под функциями FOLLOW(X) и FIRST(X).Например, если у вас есть A -> B x, а B может вывести ϵ, то мы должны включить x в набор, вычисленный как FIRST(A).А также в наборе FOLLOW(B).

Кроме того, пустые правила легко представлены в канонических LR(1) наборах элементов.

Одна полезная вещь - представить, что существует дополнительный нетерминальный символ$, который представляет конец файла.

Давайте возьмем грамматику:

S -> X | ϵ
X -> id

Для первого канонического набора LR(1) элементов мы можем взять первый набор LR(0) элементови добавьте заголовок с символом '$':

S -> . X   , '$'
S -> .     , '$'
X -> . id  , '$'

Тогда у нас есть один для заголовка: id:

S -> . X   , 'id'
S -> .     , 'id
X -> . id  , 'id'

Теперь давайте посмотрим на FIRST и FOLLOW sets:

S -> . X   , '$'

Это не пункт "точка-финал", поэтому здесь нужно смещаться, но только если набор FIRST(X) содержит наш прогнозный символ $.Это неверно, поэтому мы не заполняем запись в таблице.

Далее:

S -> .     , '$'

Это элемент «точка-финал», поэтому его нужно уменьшить.Чтобы проверить контекст для сокращения, мы смотрим на FOLLOW(S): может ли грамматический символ, который мы хотим уменьшить, сопровождаться тем, что находится в поле зрения?Определенно да.$ всегда в FOLLOW(S), потому что начальный символ по определению сопровождается концом ввода.Так что да, мы можем уменьшить.И так как мы уменьшаем символ S, уменьшение на самом деле является действием accept: синтаксический анализ заканчивается.Мы заполняем запись таблицы действием accept.

Аналогичным образом мы можем повторить для следующего набора элементов с lookahead id.Давайте перейдем к правилу S-производного-пустого:

S -> .     , 'id'

Может ли S сопровождаться id?Едва.Так что это сокращение не подходит.Мы не заполняем запись таблицы анализатора.

Таким образом, вы можете видеть, что пустое правило не создает проблем.Он немедленно превращается в точечный LR(0) или LR(1) элемент (в зависимости от метода построения синтаксического анализатора) и обрабатывается так же, как и любой другой точечный конечный элемент, с учетом рассмотрения и заполнения таблиц.