针对文法:G[E]:E->E+T|T T->T*F|F F->(E)|i 用c++编写程序利用LR(0)分析方法对该文法进行语法分析,构建i+i*i句型分析过程中符号栈的变化过程并输出分析表
时间: 2024-06-09 20:04:50 浏览: 8
由于LR(0)分析方法需要构建分析表,因此需要先构建文法的LR(0)自动机,然后根据自动机构建分析表。以下是该文法的LR(0)自动机:
![LR(0)自动机](https://img-blog.csdnimg.cn/20211201174844305.png)
其中,数字表示状态编号,S表示起始状态,接受状态用圆点表示,转移条件用小写字母表示。
根据LR(0)自动机构建分析表,需要计算每个状态的ACTION和GOTO函数。计算ACTION函数时需要分为移进、规约和接受三种情况。计算GOTO函数时需要查看自动机中每个状态的转移条件,从而确定该状态在遇到某个终结符或非终结符时应该转移到哪个状态。
以下是该文法的LR(0)分析表:
| 状态 | + | * | i | ( | ) | $ | E | T | F |
| :--------: | :-------: | :-------: | :-------: | :-------: | :-------: | :-------: | :-------: | :-------: | :-------: |
| 0 | S4(移进)| | S5(移进)| S6(移进)| | | 1 | 2 | 3 |
| 1 | R3(规约)| R3(规约)| R3(规约)| R3(规约)| R3(规约)| R3(规约)| | | |
| 2 | R6(规约)| S7(移进)| R6(规约)| R6(规约)| R6(规约)| R6(规约)| | | |
| 3 | R9(规约)| R9(规约)| R9(规约)| R9(规约)| R9(规约)| R9(规约)| | | |
| 4 | S4(移进)| | S5(移进)| S6(移进)| | | | 8 | 3 |
| 5 | S4(移进)| | S5(移进)| S6(移进)| | | | 9 | 3 |
| 6 | S4(移进)| | S5(移进)| S6(移进)| | | | 10 | 3 |
| 7 | S4(移进)| | S5(移进)| S6(移进)| | | | | 11 |
| 8 | R1(规约)| R1(规约)| R1(规约)| R1(规约)| R1(规约)| R1(规约)| | | |
| 9 | R2(规约)| R2(规约)| R2(规约)| R2(规约)| R2(规约)| R2(规约)| | | |
| 10 | R4(规约)| R4(规约)| R4(规约)| R4(规约)| R4(规约)| R4(规约)| | | |
| 11 | R5(规约)| R5(规约)| R5(规约)| R5(规约)| R5(规约)| R5(规约)| | | |
其中,S表示移进操作,R表示规约操作。
接下来是分析句子i+i*i的分析过程:
| 步骤 | 状态栈 | 符号栈 | 输入串 | ACTION | GOTO |
| :----------: | :------------: | :------------: | :------------: | :------------: | :----------: |
| 0 | 0 | $ | i+i*i$ | S5 | 1 |
| 1 | 0 5 | i | +i*i$ | R9 | - |
| 2 | 0 | F | +i*i$ | S7 | 2 |
| 3 | 0 7 | F+ | i*i$ | S5 | 1 |
| 4 | 0 7 5 | F+i | *i$ | R9 | - |
| 5 | 0 7 10 | T | *i$ | S9 | 3 |
| 6 | 0 7 10 9 | T* | i$ | S5 | 1 |
| 7 | 0 7 10 5 | T*i | $ | R6 | - |
| 8 | 0 7 2 | T | $ | R3 | - |
| 9 | 0 | E | $ | accept | - |
其中,状态栈表示LR(0)自动机中的状态,符号栈表示从输入串中读取的符号。根据分析表中的ACTION和GOTO函数,可以得到每一步的操作:移进、规约或接受。例如,在第1步中,由于状态栈栈顶是0,符号栈栈顶是i,输入串中的下一个符号是+,根据分析表中状态0的ACTION函数,需要移进到状态5,并将+压入符号栈中。在第2步中,状态栈栈顶是0,符号栈栈顶是F,输入串中的下一个符号是+,根据分析表中状态0的GOTO函数和状态7的ACTION函数,需要将F规约为T,然后转移到状态7,并将+压入符号栈中。在最后一步中,由于状态栈栈顶是0,符号栈栈顶是E,输入串中已经没有符号了,根据分析表中状态0的ACTION函数,需要接受该句子。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)