Устранить косвенные конфликты «первый-первый» в грамматике LL 1

Question

Я пытаюсь написать генератор синтаксического анализатора LL (1), и у меня возникла проблема с грамматиками, которые я знаю как LL (1), но я не могу их правильно разложить.

Например, рассмотримграмматика:

S -> As Ao
As -> a As
As -> Ɛ
Ao -> a
Ao -> Ɛ

Теперь у этой грамматики есть конфликт «первый за первым» в As, поэтому я выполняю Ɛ исключение и имею:

S -> As Ao
S -> Ao
As -> a As
As -> a
Ao -> a
Ao -> Ɛ

У которого есть конфликты «первый-первый» в S и As. Разрешение конфликта в As приводит к:

S -> As Ao
S -> Ao
As -> a As'
As' -> As
As' -> Ɛ 
Ao -> a
Ao -> Ɛ

, который имеет первый-следующий конфликт в As', который при устранении просто зацикливается. Кроме того, конфликт в S не может быть решен с помощью левой факторизации

Я считаю, что проблема в том, что As Ao == As, если бы я знал, как это доказать, я считаю, что проблема исчезнет, ​​поскольку исходная грамматика может быть преобразованаto:

S -> As
As -> a As
As -> Ɛ

Существуют ли стандартные методы разрешения таких конфликтов?

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

S -> a As Ao
As -> , a AS
As -> Ɛ
Ao -> ,
Ao -> Ɛ

Т.е. разделенный запятыми список a с необязательной конечной запятой.

Answer 1

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

Конечно, вы можете достаточно легко устранить неоднозначности, поскольку язык - это просто «ноль или более a s»:

S  ⇒ As
As ⇒ a As
As ⇒ Ɛ

Но, вероятно, вопрос заключается в упрощении некоторыхболее сложная грамматика, в которой Ao не совпадает с a, но в которой FIRST(As) и FIRST(Ao) имеют некоторый общий элемент.

В общем случае писать LL сложно (1)грамматики для таких языков, и действительно возможно, что такая грамматика не существует для языка. Чтобы ответить на вопрос более подробно, необходимо понять, что подразумевается под утверждением о том, что грамматика известна как LL (1).