Как алгоритм yacc/bison LALR(1) обрабатывает "пустые" правила?
В синтаксическом анализаторе LALR(1) правила в грамматике преобразуются в таблицу синтаксического анализа, которая фактически говорит: "Если у вас есть этот ввод до сих пор, и токен предварительного просмотра равен X, то перейдите в состояние Y или уменьшите по правилу R",
Я успешно создал анализатор LALR(1) на интерпретируемом языке (ruby), не используя генератор, но вычисляя таблицу анализа во время выполнения и оценивая ввод, используя эту таблицу анализа. Это работает на удивление хорошо, и генерация таблиц довольно тривиальна (что меня несколько удивило), поддерживая правила самоссылки и лево-правую ассоциацию.
Однако мне сложно понять, как концептуально yacc/bison обрабатывает пустые определения правил. Мой синтаксический анализатор не может их обработать, поскольку при создании таблицы он рекурсивно просматривает каждый символ в каждом правиле, и "пустой" не является чем-то, что исходит от лексера и не уменьшается правилом. Так как же тогда парсеры LALR(1) обрабатывают пустое правило? Они рассматривают это специально или это "естественная" концепция, с которой действующий алгоритм должен просто работать, даже не требуя особой осведомленности о такой концепции?
Допустим, правило, которое может соответствовать любому количеству парных скобок, в середине которых нет ничего:
expr: /* empty */
| '(' expr ')'
;
Ввод, подобный следующему, будет соответствовать этому правилу:
((((()))))
Это означает, что после прочтения '(' и видения ')' в жетоне упреждения парсер выбирает:
- Сдвиньте ')' (невозможно)
- Уменьшите вход в соответствии с некоторым другим правилом (невозможно)
- Что-то другое...
не совсем вписываются в основной алгоритм "смещения" или "уменьшения". Парсер фактически должен ничего не переносить в стек, уменьшать "ничто" до exprзатем сдвиньте следующий токен ')', давая '(' expr ')'что, конечно, сводится к expr, и так далее.
Меня смущает "сдвиг ничего". Как таблица разбора передает такую концепцию? Учтите также, что должна быть возможность вызвать некоторое семантическое действие, которое возвращает значение $$ на уменьшение пустого значения, так что довольно упрощенное представление просто пропустить это из таблицы разбора и сказать, что '(' в стеке и ')' в предвкушении следует просто перевести на смену, не будет действительно производить последовательность '(' expr ')', но будет просто производить последовательность '(' ')',
2 ответа
Несмотря на то, что думали об этом в течение нескольких дней, так как обдумывали это, когда писали вопрос и в последующие минуты, что-то просто поразило меня настолько невероятно очевидным и простым.
Сокращение по всем правилам всегда: извлеките 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
Причина, по которой он "просто работает", заключается в том, что для сокращения по пустому правилу вам нужно всего лишь вытолкнуть ноль элементов из стека.
Другой способ, возможно, завершить отличный ответ 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 наборы:
S -> . X , '$'
Это не пункт "точка окончательный", поэтому здесь нужно сместить, но только если набор FIRST(X) содержит наш прогнозный символ $, Это неверно, поэтому мы не заполняем таблицу.
Следующий:
S -> . , '$'
Это пункт "точка финал", поэтому он хочет уменьшить. Чтобы проверить контекст для сокращения, мы смотрим на FOLLOW(S): может ли грамматический символ, который мы хотим уменьшить, сопровождаться тем, что находится в поле зрения? Определенно да. $ всегда в FOLLOW(S) потому что начальный символ по определению сопровождается концом ввода. Так что да, мы можем уменьшить. И так как мы уменьшаем символ S, снижение на самом деле accept действие: синтаксический анализ заканчивается. Заполняем запись в таблице accept действие.
Точно так же мы можем повторить для следующего набора элементов с lookahead id, Давайте перейдем к правилу S-производного-пустого:
S -> . , 'id'
Можно S сопровождаться id? Едва. Так что это сокращение не подходит. Мы не заполняем таблицу парсера.
Таким образом, вы можете видеть, что пустое правило не создает проблем. Это сразу превращается в точечный финал LR(0) или же LR(1) item (в зависимости от метода построения синтаксического анализатора) и обрабатывается так же, как и любой другой конечный элемент dot, с учетом рассмотрения и заполнения таблиц.