LL(1) 用文法解析table

Question

我正在尝试使用以下语法获取 LL(1) 解析 Table，

S -> ( L ) | a
L -> L , S | S

我认为它因此具有间接左递归，

L -> S

所以我把它改成，

S -> ( L ) | a
L -> L , ( L ) | L , a | ( L ) | a

然后像这样，

S -> ( L ) | a
L -> ( L ) L' | aL'
L' -> , ( L ) L' | ,aL' | epsilon

有了这个，我得到了 FIRSTs 和 FOLLOWs

FIRST(S) = { (, a }          FOLLOW(S) = { $ }
FIRST(L) = { (, a }          FOLLOW(L) = { ) }
FIRST(L') = { , , epsilon}   FOLLOW(L') = { ) }

但是我画LL解析的时候table，它没有去$.

我是不是记错了或者误会了？

Answer 1

（我的解析理论生疏了，所以我可能在这里犯了一些错误。）

L -> S 是间接递归的一部分，但不是左递归。产生式只能"expand"变成L ->+ ( L )或L ->+ a，两者都以终端开头。这里唯一的左递归是在产生式 L -> L , S 中。在 removing this direct left recursion 之后，我得到以下语法：

S -> ( L ) | a
L -> S L'
L' -> , S L' | ε

这样，你计算出的FIRST和FOLLOW集是一样的，除了FOLLOW(S)是不完整的。除了$（因为S是开始状态），FOLLOW(S)必须包括FIRST(L')的所有元素（因为L -> S L'和L' -> , S L'）和FOLLOW(L')（因为 L' -> ε）。我得到 FOLLOW(S) = { $, ,, ), ε }.

我得到的解析table如下：

    |  (     |  a     |  ,       |  )  |  $  |
----+--------+--------+----------+-----+-----+
S   |  L )   |  a     |          |     |     |
L   |  S L'  |  S L'  |          |     |     |
L'  |        |        |  , S L'  |  ε  |     |

我不确定 "it doesn't go to $" 是什么意思。我只能说 $ 列是空的，因为 S 的所有产品都是非空的并且以终端结尾。

LL(1) 用文法解析table

LL(1) Parsing table with grammar

parsing

context-free-grammar