grammar - 转换为 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' ->

应该有一个S-> DS'。我现在对此感到困惑，也许我只是不明白这种方法。任何人都可以给我任何提示吗？还有你能告诉我这里星号的含义*吗？非常感谢！

Answer 1

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

E -> S*
S -> DS'

S'给定and的规则D，并假设SandE不会出现在其他产生式中，这部分语法等价于

E -> DS'*

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

该*符号可能是Kleene 星。这意味着S可以发生任意次数（包括零次）。但如果没有上下文，就很难说，它也可能意味着别的东西。