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

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

S -> Aaa
A -> a | ε

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

S -> aaA
A -> a | ε

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

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

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

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


parsing grammar lr
person Dennis    schedule 08.07.2019    source источник
comment
Этот вопрос носит чисто теоретический характер, и поэтому я считаю, что он принадлежит сайту Computer Science SO.   -  person sophros    schedule 08.07.2019

Ответы (2)


arrow_upward
0
arrow_downward

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

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

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

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

person rici    schedule 08.07.2019

arrow_upward
0
arrow_downward

Во-первых, я бы сказал: «Грамматика определяет, является ли последовательность предложением языка. Затем вы говорите, что преобразованная грамматика создает недопустимое дерево синтаксического анализа. Я бы сказал, что он строит другое дерево синтаксического анализа, которое может или не может быть полезным. Но на ваш вопрос о построении дерева синтаксического анализа из не- Грамматика LR. Рассмотрим следующую грамматику, которая не является LR (k) ни для какого k, потому что она неоднозначна:

E -> E + E | E * E | number

Например:

7 * 4 + 3

Есть два различных дерева синтаксического анализа, которые вы можете построить из этого предложения именно из-за двусмысленности в грамматике (на самом деле это определение неоднозначной грамматики). Итак, ответ на ваш вопрос - я бы не знал, как это сделать в общем случае.

person Booboo    schedule 04.09.2019
comment
Да, я знаю, что генераторы парсеров позволяют добавлять правила устранения неоднозначности, и поэтому вы можете уйти от написания грамматик, подобных приведенной выше, и построить дерево синтаксического анализа. Но это обман для целей данного обсуждения. - person Booboo; 04.09.2019