关于LL(1)文法变换的几个问题

Question

我在把下面的非LL(1)文法转换成LL(1)文法时遇到了一些问题。有可能被改造吗？

> A ::= B | A ; B 

> B ::= C | [ A ]

> C ::= D | C , D

> D ::= x | (C)

其中;，x，(，)，，是终端。

Answer 1

这里的主要问题是产品

A→A；B

和

C→C，D

它们是左递归的。在这两种情况下，这些结果都将生成由某种分隔符(第一种情况下是分号，第二种情况是逗号)分隔的对象字符串，因此您可以像这样重写它们：

A→B；A

C→D，C

这给出了语法

A→B| B；A

B→C|A

C→D| D，C

D→x| (C)

现在的问题是，A和C的结果有一个共同的前缀。但这没什么好担心的:我们可以像这样对它们进行左因子分析：

A→B H

H→ε|；A

B→C|A

C→D i

I→ε|C

D→x| (C)

我相信这个语法现在是LL(1)。