编译原理已知文法 A→fAa|fAg|b 判断该文法是否是 SLR(1)文法,若是,请构造相应分析表,并对输入串fbg# 给出分析过程。
时间: 2024-05-22 20:11:52 浏览: 12
首先,我们需要构造该文法的 LR(0) 项目集规范族。
初始状态为 {A' → ·A},其中 A' 为增广文法的起始符号。
对该状态进行闭包操作,得到 {A' → ·A},同时加入 {A → ·fAa} 和 {A → ·fAg},因为它们的形式是 A → ·α,在该状态下可以进行移进操作。
对于 {A → ·fAa},进行移进操作得到 {A → f·Aa},然后进行闭包操作,加入 {A → ·fAa} 和 {A → ·fAg},得到状态 {A → f·Aa, A → ·fAa, A → ·fAg}。
对于 {A → ·fAg},进行移进操作得到 {A → f·Ag},然后进行闭包操作,加入 {A → ·a},得到状态 {A → f·Ag, A → ·a}。
对于 {A → ·b},进行移进操作得到 {A → b·},该状态没有其他项目,所以结束。
经过上述操作,得到 LR(0) 项目集规范族:
| 状态 | 项目 |
| :-----: | :--------------: |
| 0 | A' → ·A |
| | A → ·fAa |
| | A → ·fAg |
| 1 | A' → A· |
| 2 | A → f·Aa |
| | A → ·fAa |
| | A → ·fAg |
| 3 | A → fA·a |
| | A → ·a |
| 4 | A → fA·g |
| 5 | A → b· |
接下来,对该文法进行 SLR(1) 分析表的构造。
首先,需要构造文法符号的 FIRST 集和 FOLLOW 集:
- FIRST(A) = {f, b}
- FIRST(a) = {a}
- FIRST(g) = {g}
- FIRST(b) = {b}
- FOLLOW(A) = {$, a}
然后,构造项目集规范族中每个状态的 ACTION 和 GOTO 表项:
| 状态 | ACTION | GOTO |
| :-----: | :------: | :-------------: |
| 0 | shift 1 | 2 |
| | | 3 |
| | | 4 |
| 1 | acc | |
| 2 | shift 5 | 6 |
| 3 | reduce 2| |
| | reduce 3| |
| 4 | reduce 1| |
| 5 | shift 7 | 4 |
| 6 | reduce 0| |
| 7 | reduce 4| |
最后,对输入串 fbg# 进行分析:
初始状态为 0,读入字符 f,根据 ACTION[0, f] = shift 1 进入状态 1,栈中为 0 1。
读入字符 b,根据 ACTION[1, b] = reduce 1 进行规约 A → b,栈中为 0。
读入字符 g,根据 GOTO[0, g] = 4 进入状态 4,栈中为 0 4。
读入字符 #,根据 ACTION[4, #] = reduce 1 进行规约 A → fAg,栈中为 0。
最终,根据 ACTION[0, $] = acc,接受输入串 fbg#。