已知文法为: S->a|^|(T) T->T,S|S 构造它的 LR(0)分析表
时间: 2024-05-21 20:17:01 浏览: 253
首先,我们需要构造该文法的所有项集。项集的构造可以使用 LR(0) 项集族算法(LR(0) Canonical Collection Algorithm)。
LR(0) 项集族算法:
1. 从初始项 S' -> .S 加入项集 I0。
2. 重复以下步骤,直到没有新的项集可以加入
1. 对于每个已经存在的项集 Ii 和文法符号 X,求出所有形如 A -> α.Xβ 的项 A -> α.X.β,并对于每个这样的项,加入到一个新的项集中。
2. 对于每个新的项集,计算它的闭包,即对于每个形如 B -> γ 的项 B -> .γ,将所有形如 B -> .γ 的项加入到该项集中。
根据上述算法,我们可以得到该文法的所有项集:
I0:
S' -> .S
S -> .a
S -> .^
S -> .(T)
I1:
S' -> S.
I2:
T -> .T,S
T -> .S
I3:
T -> T.,S
I4:
S -> (.T)
T -> .T,S
T -> .S
I5:
T -> T,.S
I6:
S -> a.
T -> T,.S
I7:
S -> ^.
T -> T,.S
I8:
S -> (.T)
T -> T,.S
T -> T,S.
I9:
T -> T,S.
接下来,我们需要使用这些项集构造 LR(0) 分析表。
LR(0) 分析表构造算法:
1. 对于每个项集 Ii,对于每个终结符 a,在 ACTION[i, a] 中加入“shift j”,其中 j 为项集 Ij 中包含 a 后继的项集编号。
2. 对于每个项集 Ii,对于每个非终结符 A,如果 GOTO(Ii, A) = Ij,则将 GOTO[i, A] 中加入“j”。
3. 对于每个项集 Ii,如果包含项 A -> α.,且 A != S',则将 FOLLOW[A] 中的所有终结符加入到 ACTION[i, a] 中,其中 a 为 FOLLOW[A] 中的一个终结符。
4. 如果项集 Ii 包含项 S' -> S.,则将 $ 加入到 ACTION[i, $] 中。
5. 如果存在冲突,则该文法不是 LR(0) 文法。
根据上述算法,我们可以得到该文法的 LR(0) 分析表:
| | a | ^ | ( | ) | $ | S | T |
|---|---|---|---|---|---|---|---|
| 0 | S3| S2| S4| | | 1 | |
| 1 | | | | |acc| | |
| 2 | | | | | | | |
| 3 | S6| S7| S4| | | | 5 |
| 4 | | | | |r2 | | |
| 5 | r3| r3| r3| r3| r3| | |
| 6 | S6| S7| S4| | | | 8 |
| 7 | R2| R2| R2| R2| R2| | |
| 8 | | | | S9| | | |
| 9 | | | | | r1| | |
其中,S 表示移进,R 表示规约,数字表示对应项集的编号。
阅读全文