针对文法:G[E]:E->E+T|T T->T*F|F F->(E)|i 用c++编写程序利用LR(0)分析方法对该文法进行语法分析,构建i+i*i句型分析过程中符号栈的变化过程并输出分析表
时间: 2024-06-09 11:04:52 浏览: 92
首先,我们需要对该文法进行扩展,使其成为一个 LR(0) 文法。我们可以通过引入新的非终结符号 S,将原来的 E 变成 S,并将原来的 E 视为 S 的一种产生式。扩展后的文法为:
```
S -> E
E -> E + T | T
T -> T * F | F
F -> (E) | i
```
接下来,我们需要构建该文法的 LR(0) 分析表。首先,我们需要对文法进行求解项目集。
```
I0:
S' -> .S
S -> .E
E -> .E + T
E -> .T
T -> .T * F
T -> .F
F -> .(E)
F -> .i
I1:
S' -> S.
I2:
S -> E.
E -> E .+ T
T -> .T * F
T -> .F
F -> .(E)
F -> .i
I3:
E -> T.
T -> T .* F
F -> .(E)
F -> .i
I4:
T -> F.
F -> .(E)
F -> .i
I5:
F -> ( .E)
E -> .E + T
E -> .T
T -> .T * F
T -> .F
F -> .(E)
F -> .i
I6:
F -> i.
I7:
E -> E+ .T
T -> .T * F
T -> .F
F -> .(E)
F -> .i
I8:
T -> T*. F
F -> .(E)
F -> .i
I9:
F -> (E.)
I10:
E -> E + T.
I11:
T -> T * F.
I12:
F -> (E).
I13:
E -> E+.T
T -> T*.F
F -> .(E)
F -> .i
I14:
T -> T*F.
I15:
F -> (E).
I16:
S -> E.
```
接着,我们可以根据项目集和文法符号,构建出 LR(0) 分析表。其中,`r` 表示规约操作,`s` 表示移进操作,`acc` 表示接受操作,空格表示错误操作。
```
i + * ( ) $ E T F S
0 s5 - - s4 - - 1 2 3 -
1 - s6 - - - acc - - - -
2 - r2 s7 - r2 r2 - - - -
3 s8 - - s4 - - - 9 10 -
4 - r4 r4 - r4 r4 - - - -
5 - r6 r6 - r6 r6 - - - -
6 s5 - - s4 - - - 11 3 -
7 s5 - - s4 - - - - 12 -
8 s5 - - s4 - - - - 13 -
9 - s6 - - s14 - - - - -
10 - r3 s7 - r3 r3 - - - -
11 - r1 r1 - r1 r1 - - - -
12 - r5 r5 - r5 r5 - - - -
13 - r7 r7 - r7 r7 - - - -
14 s5 - - s4 - - - 15 3 -
15 - r9 r9 - r9 r9 - - - -
```
最后,我们可以利用该分析表进行句型 i+i*i 的语法分析,构建符号栈的变化过程。具体过程如下:
```
符号栈 输入串 动作
0 i+i*i$ 移进 i,转入状态 5
0i5 +i*i$ 移进 +,转入状态 6
0i5+6 i*i$ 移进 i,转入状态 5
0i5+6i5 *i$ 移进 *,转入状态 7
0i5+6i5*7 i$ 移进 i,转入状态 5
0i5+6i5*7i9 $ 规约 F -> i,弹出栈顶符号 i,转入状态 9
0i5+6i5*9 $ 规约 T -> F,弹出栈顶符号 i,转入状态 4
0i5+6i4 $ 规约 E -> T,弹出栈顶符号 i,转入状态 2
0i2 +i*i$ 移进 +,转入状态 6
0i2+6 i*i$ 移进 i,转入状态 5
0i2+6i5 *i$ 移进 *,转入状态 7
0i2+6i5*7 i$ 移进 i,转入状态 5
0i2+6i5*7i9 $ 规约 F -> i,弹出栈顶符号 i,转入状态 9
0i2+6i5*9 $ 规约 T -> F,弹出栈顶符号 i,转入状态 4
0i2+6i4 $ 规约 E -> T,弹出栈顶符号 T,转入状态 1
0i1 $ 规约 S -> E,弹出栈顶符号 E,转入状态 0
0S0 $ 接受
```
阅读全文