为给定的CFG生成LL(1)解析表

Question

粮安委的情况如下：

S -> SD|SB
B -> b|c
D -> a|dB

我尝试的方法如下：

我通过左因式分解方法从第一个产品(S->SD|SB)中删除了不确定性。

因此，应用左保理后的CFG如下：

S -> SS'
S'-> D|B
B -> b|c
D -> a|dB

我需要为生产找到第一个S，即S -> SS'，以便进一步进行。有人能帮忙或建议吗？

Answer 1

您不能通过这种方式将此语法转换为LL(1)解析器:语法为https://stackoverflow.com/q/16165352/67579，因此必须执行https://en.wikipedia.org/wiki/LL_parser#Left_recursion_removal.5B4.5D。关键是您可以执行以下技巧:由于S的唯一规则是S -> SS'和S -> (epsilon)，这意味着您只需颠倒顺序，从而引入规则S -> S'S。所以现在语法是：

S -> S'S
S'-> D|B
B -> b|c
D -> a|dB

现在我们可以先构造:第一(B)={ b，c}，第一(D)={a，d}，第一(S‘)={a，b，c，d}和第一(S)={a，b，c，d}。