转换为LL(k)语法

Question

我试图解决一个练习问题，但在尝试将示例答案与我的答案进行比较时遇到了问题。以下是转换前的语法：

E-> S*
S-> SD
S-> D
D-> [D]
D-> x

起始符号是E，而其它非终端符号是S和D。

我的答案是：

E-> S*
S-> DS'
S'-> DS'
S'->
D-> [D]
D-> x

在样本答案中，它们没有S-> DS'，E变成了E-> DS'*。由于书中使用的方法删除左递归，

A -> Aa
A -> b
=>  A -> bA'
    A' -> aA'
    A' ->

应该存在CCD_ 6。我现在对此感到困惑，也许我只是不理解这种方法。有人能给我一些提示吗？你能告诉我这里的星象符号*的含义吗？非常感谢！

Answer 1

你的回答没有错。示例答案只是在转换后简化了语法。

E -> S*
S -> DS'

给定S'和D的规则，并假设S和E不会出现在其他产品中，这部分语法等效于

E -> DS'*

第一次生产中的S被简单地替换为DS'，正如第二次生产中所定义的那样，已经被剥离。

*符号可能是一颗克莱恩星。这意味着S可以发生任何次数（包括零）。但如果没有上下文，就很难判断，它也可能意味着其他东西。