消除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，如果我知道如何证明这一点，我相信问题会消失，因为最初的语法可以转换为：

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

是否有解决此类冲突的标准方法？

编辑：我意识到上面的语法是模棱两可的。我对解析真正感兴趣的语法是：

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）的主张的含义。