LL(1)

  • First 可以有 $\varepsilon $ ,Follow 不能有。

考虑如下文法 $G:$ $E \rightarrow A \mid B$ $A \rightarrow$ num $\mid$ id $B \rightarrow(L)$ $L \rightarrow L E \mid E$ (1) 消除该文法中的左递归。 (2) 为改写后的文法中的非终结符号构造 FIRST 集合和 FOLLOW 集合。 (3) 说明改写后的文法是 LL (1) 文法,并构造其 LL (1) 分析表。 (4) 给出输人符号串 (a (b (2))(c)) 的预测分析过程。

(1)消除左递归得到:$L' \to EL' \mid \varepsilon , L = EL'$

$E \rightarrow A \mid B$ $A \rightarrow$ num $\mid$ id $B \rightarrow(L)$ $L' \to EL' \mid \varepsilon $ $L = EL'$

(2)

First
Follow

答:

Symbol Nullable First Set Follow Set
$E \rightarrow A \mid B$ num id ( $ num id (
$A \rightarrow$ num $\mid$ id num id $ num id (
$B \rightarrow(L)$ ( $ num id (
$L' \to EL' \mid \varepsilon $ T num id ( ε )
$L \to EL'$ num id ( )

(3)LL (1) 文法的判断

  1. 根据产生式判断。对任意产生式 $A \to a \mid b$,服从于:
    • $\operatorname{First} ( a ) \cap \operatorname{First} ( b ) = \emptyset $
    • 若 $b$ 可致空,则 $\operatorname {First}(a) \cap \operatorname {Follow}(A) = \emptyset $
  2. 根据分析表判断。如果 LL (1) 分析表无二义性,则文法是 LL (1) 文法。

方法 1 实际上是说:

  • 对于产生式的各个分支,一定能通过第一个词符判断选择哪个分支。
  • 对于含有自指的分支,一定能通过第一个词符判断是否继续自指。

对于本题,

  1. 就 $E \rightarrow A \mid B$ 而言,$A,B$ First Set 交集为空。
  2. 就 $L' \to EL' \mid \varepsilon $ 而言,First (EL') 与 Follow (L') 交集为空。

所以是 LL (1) 文法。

分析表的构造

Symbol num id ( ) $
$E $ $E \to A$ $E \to A$ $E \to B$
$A $ $A \to \text{num} $ $A\to \text{id}$
$B $ $B \to (L)$
$L $ $L \to EL'$ $L \to EL'$ $L \to EL'$
$L'$ $L' \to EL'$ $L' \to EL'$ $L' \to EL'$ $L'\to \varepsilon $
细节

(4)(a (b (2))(c)) 的预测分析过程

Step Stack Input Output Annotation
1 $E (a (b (2))(c))$ $E \to B$ 栈顶是 (,查表,采用 $E \to B$ 规约
2 $B (a(b(2))(c))$ $B \to (L)$
3 $) L ( (a (b (2))(c))$ (L) 从右到左压栈
4 $)L a(b(2))(c))$
5 $)L a(b(2))(c))$ $L \to EL'$
6 $)L'E a(b(2))(c))$ $E \to A$
7 $)L'A a(b(2))(c))$ $A\to \text{id}$
8 $)L'id a(b(2))(c))$
9 $)L' (b(2))(c))$ $L' \to EL'$
10 $)L'E (b(2))(c))$ $E \to B$
11 $)L'B (b(2))(c))$ $B \to (L)$
12 $)L')L( (b(2))(c))$
13 $)L')L b(2))(c))$ $L \to EL'$
14 $)L')L'E b(2))(c))$ $E \to A$
15 $)L')L'A b(2))(c))$ $A\to \text{id}$
16 $)L')L'id b(2))(c))$
17 $)L')L' (2))(c))$
18 $)L')L' (2))(c))$ $L' \to EL'$
19 $)L')L'E (2))(c))$ $E \to B$
20 $)L')L'B (2))(c))$ $B \to (L)$
21 $)L')L')L( (2))(c))$
22 $)L')L')L 2))(c))$
23 $)L')L')L 2))(c))$ $L \to EL'$
24 $)L')L')L'E 2))(c))$ $E \to A$
25 $)L')L')L'A 2))(c))$ $A \to \text{num} $
26 $)L')L')L'num 2))(c))$
27 $)L')L')L' ))(c))$
28 $)L')L')L' ))(c))$ $L' \to \varepsilon $
29 $)L')L') ))(c))$
30 $)L')L' )(c))$ $L' \to \varepsilon $
31 $)L') )(c))$
32 $)L' (c))$ $L' \to EL'$
33 $)L'E (c))$ $E \to B$
34 $)L'B (c))$ $B \to (L)$
35 $)L')L( (c))$
36 $)L')L c))$ $L \to EL'$
37 $)L')L'E c))$ $E \to A$
38 $)L')L'A c))$ $A\to \text{id}$
39 $)L')L'id c))$
40 $)L')L' ))$ $L' \to \varepsilon $
41 $)L') ))$
42 $)L' )$ $L' \to \varepsilon $
43 $) )$
44 $ $

LR(0)

文法:

E'->E
E->E+T
E->T
T->T*F
T->F
F->(E)
F->id

其有限自动机如下:(红底白字为 移进 - 规约冲突的项

image_up_164034658231f655b9.jpg

SLR(1)

可以尝试用 FOLLOW 集消除冲突。对于 I2,I9: 求出 E、T 的 FOLLOW 集,若下一个输入符号属于 E 的 FOLLOW 集,那么就归约为 E,反之则采用移进。

如果通过 Follow 集合消除冲突,则此文法为 SLR 文法。

如果项目的 Follow 集合相同,则无法消除冲突,不是 SLR 文法。

问题在于,SLR 也不是完美的。

考虑 $A \to \alpha $,在 SLR 中,如果 $b \in \operatorname {Follow}(A)$,我们就进行规约。然而实际上这只是必要条件,并不充分。

那么怎么解决呢?为此引入了 LR (1) 分析。

LR(1)

考虑 $G$:

$S \rightarrow L=R$ $S \rightarrow R$ $L \rightarrow * R$ $L \rightarrow \mathbf{i d}$ $R \rightarrow L$

构造其 $LR (1)$ 自动机。

解:

增广文法:我们希望开始符号 $S$ 仅出现在一个产生式的左边,从而使得分析器只有一个接受状态。如果不满足此条件,则需要增加一个 $S'$ 指向 $S$ ,以 $S'$ 作为开始符号。

发现 $S$ 出现在两个产生式的左边。我们改造为增广文法 $G'$:

$S' \to S$ $S \rightarrow L=R$ $S \rightarrow R$ $L \rightarrow * R$ $L \rightarrow \mathbf{i d}$ $R \rightarrow L$

接下来求解 $\operatorname {Follow}$ 集合。

Symbol First Dep First Set Follow Dep Follow Set
$S' \to S$ $S$ * id $S$ = $
$S \to L=R \mid R$ $L,R$ * id $R$ = $
$L\to\star R\mid\text{id}$ * id $R$ = $
$R \to L$ $L$ * id $L$ = $

使用下面的方法构造 $I_0$ 状态

image_up_16407868062d79a62e.jpg

然后输入各种符号,得到如下的表:

image_up_1640791271a0a7b87e.jpg

于是得到分析表:

现态 \ 输入 * id = $ S L R
0 s4 s5 1 2 3
1 r0ACC
2 s6 r5
3 r2
4 s4 s5 8 7
5 r4 r4
6 s11 s12 10 9
7 r3 r3
8 r5 r5
9 r1
10 r5
11 s11 s12 10 13
12 r4
13 r3

*,id,=,$,S,L,R 列表示输入。即 后面的符号。可能是非终结符或终结符,分别对应 ACTION 和 GOTO.

最左侧列代表现态,表格数据代表次态。即 i 行 j 列数据代表:现态是 i,输入 符号 j 后跳转到的状态。

需要注意的是,对于 Follow 集合中出现过的 =, $ 别忘了写它们的规约项。

注意式子的需要是从 0 开始,填表时要小心。不要填 r0,要填 ACC

上面就是 LR (1) 分析表。

LALR(1)

对于 image_up_1640791506b4e031ae.jpg 这样的项,可以简化为 image_up_1640791541c11f0d0c.jpg

如果只有前瞻符号不同,则两个 Item 是同心的。比如是 L -> *R・,$L -> \*R・,=/$ 同心的。

于是我们简化并用虚线框出同心项:

image_up_1640791925b465a23d.jpg

于是可以将其合并,从而减小状态数。缺点:但这样合并后,虽然不产生冲突,但可能会推迟错误的发现。

什么时候不可以合并

考虑状态下面两个状态:

Ii                  Ij
+-------------+     +-------------+
| A -> c ·, d |     | A -> c ·, e |
| B -> c ·, e |     | B -> c ·, d |
+-------------+     +-------------+

我们如果将其合并,则 A,B 都可以归约到 e/d,那到底怎么规约?不知道。所以,会产生规约 - 规约冲突。所以不可合并。(注:合并同心项不可能产生移进规约冲突)