针对文法:G[E]:E->E+T|T T->TF|F F->(E)|i 用c++编写程序利用LR(0)分析方法对该文法进行语法分析,构建i+ii句型分析过程中符号栈的变化过程并输出分析表
时间: 2024-06-05 20:11:57 浏览: 15
首先,对于该文法,我们需要构建它的LR(0)项集族:
I0:
E' -> .E
E -> .E+T
E -> .T
T -> .TF
T -> .F
F -> .(E)
F -> .i
I1:
E' -> E.
I2:
E -> E.+T
T -> .TF
T -> .F
F -> .(E)
F -> .i
I3:
E -> T.
T -> T.F
F -> .(E)
F -> .i
I4:
T -> TF.
F -> .(E)
F -> .i
I5:
T -> T.F.
F -> .(E)
F -> .i
I6:
F -> (.E)
E' -> .E
E -> .E+T
E -> .T
T -> .TF
T -> .F
F -> .(E)
F -> .i
I7:
E -> E+.T
T -> .TF
T -> .F
F -> .(E)
F -> .i
I8:
T -> TF.
F -> (.E)
E -> .E+T
E -> .T
T -> .TF
T -> .F
F -> .(E)
F -> .i
I9:
T -> T.F.
F -> (.E)
E -> .E+T
E -> .T
T -> .TF
T -> .F
F -> .(E)
F -> .i
I10:
F -> (E.)
E -> E.+T
T -> T.F
F -> .(E)
F -> .i
I11:
E -> E+T.
I12:
T -> TF
F -> i
F -> (.E)
接下来,我们需要构建LR(0)分析表。对于该文法,终结符包括:i,+,(,),$,非终结符包括:E,T,F,E'。因此,分析表如下:
| | i | + | ( | ) | $ | E | T | F | E' |
|-----|----|----|----|----|----|----|----|----|----|
| 0 | s5 | | s6 | | | 1 | 2 | 3 | |
| 1 | | | | | acc | | | | |
| 2 | s5 | s7 | | | r3 | | | | |
| 3 | r6 | r6 | r6 | r6 | r6 | | | | |
| 4 | r5 | r5 | r5 | r5 | r5 | | | | |
| 5 | s5 | | s6 | | | 8 | 2 | 3 | |
| 6 | s5 | | s6 | | | | 9 | 3 | |
| 7 | r2 | r2 | r2 | r2 | r2 | | | | |
| 8 | | s7 | | s10 | r1 | | | | |
| 9 | | r4 | s11 | r4 | r4 | | | | |
| 10 | s5 | | s6 | | | | 12 | 3 | |
| 11 | s5 | | s6 | | | | | 13 | |
| 12 | r3 | r3 | r3 | r3 | r3 | | | | |
| 13 | r4 | r4 | r4 | r4 | r4 | | | | |
其中,s表示移进,r表示归约,acc表示接受。
现在,我们可以利用该分析表对句子进行语法分析了。假设我们要分析的句子为:i+i*i。
符号栈初始化为:0(\$)
| Step | Current Token | Action | Symbol Stack | Next State |
|------|---------------|--------|------------------------|------------|
| 1 | i | shift | 0(\$) 5(i) | 5 |
| 2 | + | shift | 0(\$) 5(i) 7(+) | 7 |
| 3 | i | shift | 0(\$) 5(i) 7(+) 5(i) | 5 |
| 4 | * | shift | 0(\$) 5(i) 7(+) 5(i) 6(*) | 6 |
| 5 | i | shift | 0(\$) 5(i) 7(+) 5(i) 6(*) 5(i) | 5 |
| 6 | $ | reduce | 0(\$) 1(E') | acc |
因此,该句子是符合该文法的。
最后,我们可以输出一下该文法的分析表:
| | i | + | ( | ) | $ | E | T | F | E' |
|-----|----|----|----|----|----|----|----|----|----|
| 0 | s5 | | s6 | | | 1 | 2 | 3 | |
| 1 | | | | | acc | | | | |
| 2 | s5 | s7 | | | r3 | | | | |
| 3 | r6 | r6 | r6 | r6 | r6 | | | | |
| 4 | r5 | r5 | r5 | r5 | r5 | | | | |
| 5 | s5 | | s6 | | | 8 | 2 | 3 | |
| 6 | s5 | | s6 | | | | 9 | 3 | |
| 7 | r2 | r2 | r2 | r2 | r2 | | | | |
| 8 | | s7 | | s10 | r1 | | | | |
| 9 | | r4 | s11 | r4 | r4 | | | | |
| 10 | s5 | | s6 | | | | 12 | 3 | |
| 11 | s5 | | s6 | | | | | 13 | |
| 12 | r3 | r3 | r3 | r3 | r3 | | | | |
| 13 | r4 | r4 | r4 | r4 | r4 | | | | |
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)