编译原理已知文法 A→fAa|fAg|b 判断该文法是否是 SLR(1)文法,若是,请构造相应分析表,并对输入串fbg# 给出分析过程。
时间: 2024-06-09 22:04:29 浏览: 155
首先,我们需要计算出该文法的 FIRST 集合和 FOLLOW 集合。计算规则如下:
- 对于终结符号,它的 FIRST 和 FOLLOW 集合都是它本身;
- 对于形如 A → α 的产生式,若 α 的左侧第一个符号为终结符号,则将该终结符号加入 A 的 FIRST 集合;若 α 的左侧第一个符号为非终结符号 B,则将 B 的 FIRST 集合中除了 ε 以外的所有符号加入 A 的 FIRST 集合;若 α 可以推导出 ε,则将 FOLLOW(A) 中的所有符号加入 A 的 FIRST 集合;
- 对于形如 B → αAβ 的产生式,将 FOLLOW(B) 中的所有符号加入 A 的 FOLLOW 集合;若 α 可以推导出 ε,则将 FOLLOW(B) 中的所有符号加入 A 的 FOLLOW 集合。
根据上述规则,可以得到该文法的 FIRST 和 FOLLOW 集合如下:
```
FIRST(A) = {f, b}
FIRST(B) = {f, b}
FOLLOW(A) = {#, a, g}
FOLLOW(B) = {a, g}
```
接下来,我们需要构造该文法的 SLR(1) 分析表。首先,我们需要计算出该文法的所有 LR(0) 项集。假设初始项集为 {S' → ·A#},则可以得到如下的所有项集:
```
I0:
S' → ·A#, { $ }
A → ·fAa, { # }
A → ·fAg, { # }
A → ·b, { # }
I1:
A → f·Aa, { # }
A → f·Ag, { # }
I2:
A → ·fAa, { a }
A → ·fAg, { g }
I3:
A → fA·a, { # }
A → fA·g, { # }
I4:
A → b·, { # }
```
接下来,我们需要计算每个 LR(0) 项集的 CLOSURE 和 GOTO 集合。假设我们已经计算得到项集 I0,那么项集 I1 可以通过以下操作得到:
```
CLOSURE(I1) = { A → ·fAa, { # }, A → ·fAg, { # } }
GOTO(I0, f) = I2
```
同样地,我们可以通过对 I2 应用 CLOSURE 和 GOTO 操作得到 I3 和 I4:
```
CLOSURE(I3) = { A → fA·a, { # }, A → fA·g, { # } }
GOTO(I2, a) = I3
GOTO(I2, g) = I3
CLOSURE(I4) = { A → b·, { # } }
```
最终得到所有的 LR(0) 项集如下:
```
I0:
S' → ·A#, { $ }
A → ·fAa, { # }
A → ·fAg, { # }
A → ·b, { # }
I1:
A → f·Aa, { # }
A → f·Ag, { # }
I2:
A → ·fAa, { a }
A → ·fAg, { g }
I3:
A → fA·a, { # }
A → fA·g, { # }
I4:
A → b·, { # }
```
接下来,我们需要计算每个 LR(0) 项集的 FOLLOW 集合。假设我们已经计算得到项集 I0,那么项集 I1、I2 和 I3 的 FOLLOW 集合均为 { #, a, g },项集 I4 的 FOLLOW 集合为 { #, a, g }。
接下来,我们需要计算每个 LR(0) 项集的 ACTION 和 GOTO 函数。对于每个项集 Ii,如果存在一条形如 A → α· 的产生式,并且 A ≠ S',则将 FOLLOW(A) 中的所有符号 a 加入到 ACTION[i, a] 中。如果存在一个项集 Ij,使得 GOTO(Ii, X) = Ij,则将 GOTO[i, X] 设为 j。
根据上述规则,可以得到该文法的 SLR(1) 分析表如下:
```
| f | a | g | b | # |
--+-----+-----+-----+-----+-----+
0 | | S2 | S3 | S4 | |
1 | R4 | | | | R4 |
2 | | S3 | S3 | | |
3 | | R2 | R2 | | R2 |
4 | | | | | acc |
--+-----+-----+-----+-----+-----+
```
其中,S 表示移进操作,R 表示规约操作,$i$ 表示将状态转移至状态 i。
接下来,我们对输入串 fbg# 进行分析:
```
状态栈 | 符号栈 | 输入串 | ACTION | GOTO
------------------+-------------+-------------+-------------+-------------
0 | | fbg# | |
0 S2 | f | bg# | S2 | 2
0 S2 2 | fb | g# | |
2 S3 | fb | g# | S3 | 3
2 S3 3 | fbg | # | |
3 R2 (A → b) | fg | # | R2 |
2 S3 | fg | # | S3 | 3
2 S3 3 | fgg | # | |
3 R2 (A → g) | fg | # | R2 |
2 S3 | fg | # | S3 | 3
2 S3 3 | fga | # | |
3 S4 | fga | # | S4 | 4
3 S4 4 | fgab | # | |
4 R4 (A → b) | fga | # | R4 |
3 S4 | fga | # | S4 | 4
3 S4 4 | fga# | | |
4 accept | | | |
```
最终得到分析栈为 0 S2 2 S3 3 R2 2 S3 3 R2 2 S3 3 S4 4 R4 3 S4 4 accept,因此该输入串符合文法。
阅读全文