首先,构造文法的 LR(0) 自动机如下:

SLR1-1

可以看出,该自动机是 SLR(1) 文法,因为每个状态的移进/归约符号的 Follow 集合都不会包含其他状态的项集中的符号。

接下来,计算每个状态的 LR(0) 闭包和 GOTO 函数:

| 状态 | LR(0) 闭包 | GOTO(E) | GOTO(T) | GOTO(F) | | ---- | --------- | ------- | ------- | ------- | | 0 | E' -> .E | 1 | 2 | 3 | | 0 | E -> .E+T | | | | | 0 | E -> .T | | | | | 0 | T -> .TF | | | | | 0 | T -> .F | | | | | 0 | F -> .(E) | | | | | 0 | F -> .d | | | | | 1 | E' -> E. | | | | | 1 | E -> E.+T | | | | | 1 | T -> .TF | 4 | | 3 | | 1 | T -> .F | 5 | | 3 | | 1 | F -> .(E) | 6 | | 3 | | 1 | F -> .d | 7 | | 3 | | 2 | E -> T. | | | | | 2 | T -> T.F | | 8 | | | 2 | T -> T.F | | 9 | | | 2 | F -> .(E) | 6 | | 10 | | 2 | F -> .d | 7 | | 10 | | 3 | F -> (.E). | | | | | 3 | E -> .E+T | | | | | 3 | E -> .T | | | | | 3 | T -> .TF | | | | | 3 | T -> .F | | | | | 3 | F -> .(E) | | | | | 3 | F -> .d | | | | | 4 | T -> T.F. | | | | | 4 | F -> .(E) | 6 | | 3 | | 4 | F -> .d | 7 | | 3 | | 5 | T -> F. | | | | | 5 | F -> .(E) | 6 | | 11 | | 5 | F -> .d | 7 | | 11 | | 6 | F -> (.E). | | | | | 7 | F -> d. | | | | | 8 | T -> T*.F | | | 12 | | 8 | F -> .(E) | 6 | | 10 | | 8 | F -> .d | 7 | | 10 | | 9 | F -> .(E) | 6 | | 11 | | 9 | F -> .d | 7 | | 11 | | 10 | F -> (.E). | | | | | 11 | F -> d. | | | | | 12 | T -> T*.F. | | | |

然后,计算每个状态的 LR(1) 项目集族和 ACTION/GOTO 表:

| 状态 | LR(1) 项目集 | ACTION(d) | ACTION(+) | ACTION() | ACTION(()) | ACTION()) | ACTION($) | GOTO(E) | GOTO(T) | GOTO(F) | | ---- | ------------ | --------- | --------- | --------- | ---------- | --------- | -------- | ------- | ------- | ------- | | 0 | {E' -> .E,$} | | | | | | | 1 | 2 | 3 | | 0 | {E -> .E+T,$} | | | | | | | | | | | 0 | {E -> .T,$} | | | | | | | | | | | 0 | {T -> .TF,$} | | | | | | | | | | | 0 | {T -> .F,$} | | | | | | | | | | | 0 | {F -> .(E),$} | | | | | | | | | | | 0 | {F -> .d,$} | | | | | | | | | | | 1 | {E' -> E.,$} | | | | | | accept | | | | | 1 | {E -> E.+T,$} | | s5 | | | | | | | | | 1 | {T -> .TF,$} | | | | | | | 4 | | 3 | | 1 | {T -> .F,$} | | | | | | | 5 | | 3 | | 1 | {F -> .(E),$} | | | | s6 | | | | | 3 | | 1 | {F -> .d,$} | | | | s7 | | | | | 3 | | 2 | {E -> T.,$} | s8 | s5 | | | | | | | | | 2 | {T -> T.F,$} | | | s9 | | | | | 8 | 3 | | 2 | {T -> T.F,$} | | | s9 | | | | | 9 | 3 | | 2 | {F -> .(E),$} | | | | s6 | | | | | 10 | | 2 | {F -> .d,$} | | | | s7 | | | | | 10 | | 3 | {F -> (.E).,$} | | | | | | | | | | | 3 | {E -> .E+T,$} | | | | | s11 | | | | | | 3 | {E -> .T,$} | | | | | s11 | | | | | | 3 | {T -> .TF,$} | | | | | s11 | | | | | | 3 | {T -> .F,$} | | | | | s11 | | | | | | 3 | {F -> .(E),$} | | | | s6 | | | | | 12 | | 3 | {F -> .d,$} | | | | s7 | | | | | 12 | | 4 | {T -> T*.F.,$} | | | | | | | | | | | 4 | {F -> .(E),$} | | | | s6 | | | | | 10 | | 4 | {F -> .d,$} | | | | s7 | | | | | 10 | | 5 | {T -> F.,$} | | | | | | | | | | | 5 | {F -> .(E),$} | | | | s6 | | | | | 11 | | 5 | {F -> .d,$} | | | | s7 | | | | | 11 | | 6 | {F -> (.E).,$} | | | | | s13 | | | | | | 7 | {F -> d.,$} | r6 | r6 | r6 | r6 | r6 | r6 | | | | | 8 | {T -> T*.F,$} | | | s9 | | | | | 8 | 12 | | 8 | {F -> .(E),$} | | | | s6 | | | | | 10 | | 8 | {F -> .d,$} | | | | s7 | | | | | 10 | | 9 | {F -> .(E),$} | | | | s6 | | | | | 11 | | 9 | {F -> .d,$} | | | | s7 | | | | | 11 | | 10 | {F -> (.E).,$} | | | | | s14 | | | | | | 11 | {F -> d.,$} | r7 | r7 | r7 | r7 | r7 | r7 | | | | | 12 | {T -> T*.F.,$} | | | | | | | | | |

其中,s表示移进,r表示归约,数字表示对应产生式的编号。

最后,检查 ACTION 表中是否有冲突。可以看出,状态 1 中 ACTION 表的 (d) 和 (+) 项存在移进-归约冲突,因为在状态 5 中存在 F -> d. 和 F -> .(E) 两个 LR(1) 项目。因此,该文法不是 SLR(1) 文法。

SLR1 分析:文法 E->E+T|T,T->T*F|F,F->(E)|d 的分析

原文地址: https://www.cveoy.top/t/topic/f0Jj 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录