试对输入串 (id+id)*id 进行自下而上分析
时间: 2023-09-16 13:13:12 浏览: 35
使用自下而上的分析方法,可以采用移进-规约分析法(shift-reduce parsing)进行分析。
初始状态为 $S$,输入串为 $(id+id)*id$,分析栈为 $S$。
第一步:移进 $(id$,分析栈变为 $S(id$。
第二步:移进 $+$,分析栈变为 $S(id+$。
第三步:移进 $id$,分析栈变为 $S(id+id$。
第四步:规约 $F\rightarrow id$,分析栈变为 $S(F+id$。
第五步:规约 $T\rightarrow F$,分析栈变为 $S(T+id$。
第六步:规约 $E\rightarrow T$,分析栈变为 $S(E+id$。
第七步:移进 $*$,分析栈变为 $S(E+id*$。
第八步:移进 $id$,分析栈变为 $S(E+id*id$。
第九步:规约 $F\rightarrow id$,分析栈变为 $S(E+F*id$。
第十步:规约 $T\rightarrow T*F$,分析栈变为 $S(E+T*F$。
第十一步:规约 $E\rightarrow E+T$,分析栈变为 $S(E$。
第十二步:规约 $E\rightarrow (E+F)$,分析栈变为 $S(E$。
第十三步:规约 $F\rightarrow id$,分析栈变为 $S(F$。
第十四步:规约 $T\rightarrow F$,分析栈变为 $S(T$。
第十五步:规约 $E\rightarrow T$,分析栈变为 $S(S$。
因此,输入串 $(id+id)*id$ 经过自下而上分析后,可以得到相应的语法分析树。
相关问题
(id+id)*id的自下而上分析
假设我们有一个输入符号串 "(id+id)*id",我们可以使用自下而上分析(也称为移进-归约分析)来构建语法分析树。
首先,我们需要一个空的栈和一个指向输入符号串开头的指针。我们将指针从左往右移动,并将遇到的每个符号压入栈中,直到我们可以应用一个产生式来归约栈顶部的符号。
以下是分析的过程:
| 分析栈 | 剩余输入 | 动作 |
|--------|----------|------|
| | (id+id)\*id$ | 初始化栈 |
| id | (+id)\*id$ | 移进id |
| +, id | (id)\*id$ | 移进+ |
| +, id, id | (*id)$ | 移进id |
| +, id, *, id | id$ | 移进* |
| +, id, *, id, id | $ | 归约id |
| +, id, *id | $ | 归约id |
| (id+id)\*id | $ | 归约\* |
因此,我们得到了如下语法分析树:
```
*
/ \
+ id
/ \
id id
```
给出A:=B*(-C+D)的自下而上语法制导翻译过程
下面是A:=B*(-C+D)的自下而上语法制导翻译过程:
1. 对于非终极符E,其属性值为E.val
2. 对于终极符,其属性值为终极符本身的值或者空值
3. 产生式S->E,S.val=E.val
4. 产生式E->E1+T,E.val=E1.val+T.val
5. 产生式E->T,E.val=T.val
6. 产生式T->T1*F,T.val=T1.val*F.val
7. 产生式T->F,T.val=F.val
8. 产生式F->(E),F.val=E.val
9. 产生式F->-F1,F.val=-F1.val
10. 产生式F->num,F.val=num.val
11. 产生式F->id,F.val=id.val
按照以上语法制导翻译的规则,对于A:=B*(-C+D),可以按照以下步骤生成中间代码:
1. 将B赋给临时变量t1,即t1=B
2. 将-C赋给临时变量t2,即t2=-C
3. 将t2与D相加并赋给临时变量t3,即t3=t2+D
4. 将t1与t3相乘并赋给A,即A=t1*t3
最终生成的三地址代码为:
```
t1 = B
t2 = -C
t3 = t2 + D
A = t1 * t3
```
相关推荐
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![](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)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)