Может ли удаление левой рекурсии внести двусмысленность?

Question

Давайте предположим, что у нас есть следующий CFG G:

A -> A b A
A -> a

Который должен производить строкиa, aba, ababa, abababa, и так далее. Теперь я хочу удалить левую рекурсию, чтобы сделать ее пригодной для интеллектуального анализа. Книга Дракона дает следующее правило для удаления немедленных левых рекурсий. Дано

A -> Aa | b

переписать как

A  -> b A'
A' -> a A'
    | ε

Если мы просто применим правило к грамматике сверху, мы получим грамматику G':

A  -> a A'
A' -> b A A'
    | ε

Что выглядит хорошо для меня, но, очевидно, эта грамматика не является LL(1), из-за некоторой неопределенности. Я получаю следующие комплекты First/Follow:

First(A) = { "a" }
First(A') = { ε, "b" }
Follow(A) = { $, "b" }
Follow(A') = { $, "b" }

Из которого я строю таблицу разбора

    |   a          |   b            |  $           |
----------------------------------------------------
A   | A -> a A'    |                |              |
A'  |              | A' -> b A A'   | A' -> ε      |
    |              | A' -> ε        |              |

и есть конфликт в T[A',b]таким образом, грамматика не является LL(1), хотя левых рекурсий больше нет, а также нет общих префиксов производств, так что для этого потребуется левый факторинг.

Я не совсем уверен, откуда возникает двусмысленность. Я думаю, что во время синтаксического анализа стек будет заполняться S', И вы можете в основном удалить его (уменьшить до эпсилон), если он больше не нужен. Я думаю, что это тот случай, если другой S' ниже в стеке.

Я думаю, что LL (1) грамматика G'', которую я пытаюсь получить из оригинальной, будет:

A  -> a A'
A' -> b A
    | ε

Я что-то пропустил? Я сделал что-то не так?

Существует ли более общая процедура удаления левой рекурсии, которая учитывает этот крайний случай? Если я хочу автоматически удалить левые рекурсии, я должен справиться с этим, верно?

Является ли вторая грамматика G 'LL(k) грамматикой для некоторого k > 1?

Answer 1

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

Рассмотрим строку a b a b a, Мы можем получить это двумя способами из исходной грамматики:

A ⇒ A b A
  ⇒ A b a
  ⇒ A b A b a
  ⇒ A b a b a
  ⇒ a b a b a

A ⇒ A b A
  ⇒ A b A b A
  ⇒ A b A b a
  ⇒ A b a b a
  ⇒ a b a b a

Однозначные грамматики, конечно, возможны. Вот правая и левая рекурсивная версии:

A ⇒ a              A ⇒ a
A ⇒ a b A          A ⇒ A b a

(Хотя они представляют один и тот же язык, они имеют разный синтаксический анализ: праворекурсивная версия ассоциируется с правой, а левая рекурсивная - с левой).

Answer 2

Удаление левой рекурсии не может внести двусмысленности. Этот вид трансформации сохраняет неоднозначность. Если CFG уже неоднозначен, результат также будет неоднозначным, а если оригинал - нет, то и результат тоже.