Как парсеры LR могут генерировать деревья разбора?

Question

Предположим, у меня есть грамматика:

S -> Aaa
A -> a | ε

Очевидно, что эта грамматика может анализировать только последовательности aa и aaa. Простой анализатор LR (1) (или даже LL) может анализировать их при преобразовании в эквивалентную грамматику:

S -> aaA
A -> a | ε

Хотя эти грамматики эквивалентны, их сгенерированные деревья разбора отличаются. Рассмотрим для последовательности aaa:

    S          S
   / \        / \
  A  aa      aa  A
  |              |
  a              a

Грамматика определяет, является ли последовательность частью языка, вместо предоставления дерева синтаксического анализа, которое представляет ее в языке. Не преобразованная грамматика не может анализировать последовательность (без большего заблаговременного просмотра); Хотя преобразованная грамматика может анализировать ее, но создает недопустимое дерево синтаксического анализа.

Как можно было бы построить дерево разбора для последовательности - чья (не зависящая от контекста) грамматика не может (не преобразована) быть представлена ​​LR-парсером?

Answer 1

Если грамматика не имеет синтаксического анализатора LR (1), вам нужно использовать другой алгоритм разбора. В этом случае вы можете использовать синтаксический анализатор LR (3). Или вы можете (в общем) использовать парсер Earley или GLR, у которого нет ограничений на просмотр.

Я думаю, что ваш вопрос связан с восстановлением исходного синтаксического анализа по результатам анализа с преобразованной грамматикой. Это будет зависеть от алгоритма преобразования.

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

Существует другое преобразование, которое можно использовать для построения грамматики LR (1) из грамматики LR (k), если известно значение k. Это преобразование обратимо. Тем не менее, это обычно не считается практичным, потому что он эффективно кодирует LR (k) машину в правила грамматики, что приводит к огромному взрыву грамматики. Было бы эквивалентно использовать реальный парсер LR (k), который также имеет огромный автомат.