针对文法:G[E]:E->E+T|T T->TF|F F->(E)|i 用c++编写程序利用LR(0)分析方法对该文法进行语法分析,构建i+ii句型分析过程中符号栈的变化过程并输出分析表
时间: 2024-06-09 15:04:51 浏览: 48
基于LR(0)方法的语法分析程序
3星 · 编辑精心推荐
为了方便起见,我们可以将文法转换为如下形式:
```
E -> T E'
E' -> + T E' | ε
T -> F T'
T' -> * F T' | ε
F -> ( E ) | i
```
其中,`ε` 表示空串。
接下来,我们可以使用 LR(0) 分析方法进行语法分析。首先,我们需要构造分析表。构造分析表的过程如下:
1. 对于每一个状态 `S`,找到状态中的每一个项 `A -> α . β`。
2. 如果 `β` 不为空,则对于 `FIRST(β)` 中的每一个终结符号 `a`,将 `ACTION[S, a]` 设为移进操作,移动到状态 `S'`,其中 `S'` 是从 `S` 中通过 `a` 能够得到的状态。
3. 如果 `β` 为空,则对于 `FOLLOW(A)` 中的每一个终结符号 `a`,将 `ACTION[S, a]` 设为规约操作,规约为 `A -> α`。
4. 对于每一个状态 `S`,如果存在 `A -> α .`,则对于 `FOLLOW(A)` 中的每一个终结符号 `a`,将 `ACTION[S, a]` 设为规约操作,规约为 `A -> α`。
5. 对于每一个状态 `S`,如果存在 `S -> α .`,则对于 `FOLLOW(S)` 中的每一个终结符号 `a`,将 `ACTION[S, a]` 设为接受操作。
根据上述过程,我们可以得到如下的 LR(0) 分析表:
| | ( | ) | * | + | i | $ |
|----|----|----|----|----|----|----|
| 0 | s4 | | | s5 | s6 | |
| 1 | | | | | | acc |
| 2 | | r2 | s7 | r2 | r2 | r2 |
| 3 | | r4 | r4 | r4 | r4 | r4 |
| 4 | s4 | | | s5 | s6 | |
| 5 | s4 | | | s5 | s6 | |
| 6 | s4 | | | s5 | s6 | |
| 7 | s4 | | | s5 | s6 | |
| 8 | | s9 | s7 | | | |
| 9 | | r1 | r1 | r1 | r1 | r1 |
其中,`s` 表示移进操作,后面的数字表示移动到的状态的编号;`r` 表示规约操作,后面的数字表示使用哪一个产生式进行规约;`acc` 表示接受操作。
接下来,我们可以使用上述分析表进行语法分析,构建出符号栈的变化过程。
假设我们要分析的字符串为 `i+i*i`。我们从状态 `0` 开始,符号栈的初始状态为:
```
$0
```
其中,`$` 表示输入串的结束符,`0` 表示状态的编号。
接下来,我们读入第一个字符 `i`,并根据分析表中的对应项进行移进操作,移动到状态 `4`。此时符号栈的状态为:
```
$0i4
```
接下来,我们读入第二个字符 `+`,并根据分析表中的对应项进行移进操作,移动到状态 `5`。此时符号栈的状态为:
```
$0i4+5
```
接下来,我们读入第三个字符 `i`,并根据分析表中的对应项进行移进操作,移动到状态 `4`。此时符号栈的状态为:
```
$0i4+i4+5
```
接下来,我们读入第四个字符 `*`,并根据分析表中的对应项进行移进操作,移动到状态 `7`。此时符号栈的状态为:
```
$0i4+i4*7
```
接下来,我们读入第五个字符 `i`,并根据分析表中的对应项进行移进操作,移动到状态 `4`。此时符号栈的状态为:
```
$0i4+i4*7i4
```
接下来,我们读入结束符 `$`,并根据分析表中的对应项进行规约操作,规约为 `F -> i`。此时符号栈的状态为:
```
$0i4+i4*7F2
```
其中,`F2` 表示使用产生式 `F -> i` 进行规约。
接下来,我们根据分析表中的对应项进行规约操作,规约为 `T -> F`,符号栈的状态为:
```
$0i4+T8
```
其中,`T8` 表示使用产生式 `T -> F` 进行规约。
接下来,我们根据分析表中的对应项进行移进操作,移动到状态 `5`。此时符号栈的状态为:
```
$0i4+T8+5
```
接下来,我们根据分析表中的对应项进行规约操作,规约为 `E' -> + T E'`,符号栈的状态为:
```
$0E0
```
其中,`E0` 表示使用产生式 `E -> T E'` 进行规约。
最终,我们可以根据分析表中的对应项进行接受操作,分析完成。
完整的符号栈变化过程为:
```
$0
$0i4
$0i4+5
$0i4+i4
$0i4+i4*7
$0i4+i4*7i4
$0i4+i4*7F2
$0i4+T8
$0i4+T8+5
$0E0
```
阅读全文