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

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

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

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

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

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

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

((((()))))

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

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

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

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