parsing - 如何找到递归语法的第一组

Question

我有一个语法：

S → SL | ε
L → A; | E; | C;
E → (EBE) | N | V
A → let V =E
C → while E do S | while E do S else S
B → + | - | * | >
V → x | y | z
N → ND | N0 | D
D → 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 

我正在尝试为我构建解析表，以便能够证明它不是 LL(1) 语法。我目前无法找到 S 的 FIRST 集合。我一直在集合中获得 S，无法到达 G 的终端。 FIRST(SL) 会是什么？

当我执行 FIRST(SL) 时，我会不断回到 FIRST(S)，然后 FIRST(SL) ⋃ FIRST(ε) = FIRST(S) ⋃ {ε}，然后 FIRST(S) 会重复一遍和结束。

标签： parsingcompiler-constructiongrammarcontext-free-grammar

Answer 1

大写字母代表非终结符。小写字母代表终端。

First 和 Follow 是在终结符或非终结符之前或之后的 TERMINAL 符号（在分析树的前序遍历中）。

For all A -> xYZ
First (A) = {x}
For all A-> Xyz
First (A) = First(X)
For all A-> εYZ
First (A) = First(Y)

取所有这些终端符号的并集。