编译原理之路（四）第四章语法分析典型习题解答
• 4.2.1(1-3)，4.2.2(1-5)，4.2.3(1-3)
• 4.3.1
• 4.4.1(1-5)，4.4.3， 4.4.4,
• 4.5.1
• 4.6.2, 4.6.5, 4.6.6,
• 4.7.4，4.7.5
4.2.1（1-3）
| 最左推导 | 最右推导 |
|---|---|
| S=> SS* =>SS+S* =>aS+S*=>aa+S*=>aa+a* | S=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a* |
最左推导语法树如下
4.2.2(1-5) 从文法推导串
这个比较简单，可以通过肉眼看出，对于相对复杂的，也可以拆解串，逆推得到
| 序号 | 最左推导 | 最右推导 |
|---|---|---|
| 1 | S=>0S1=>00S11=>000111 | S=>0S1=>00S11=>000111 |
| 2 | S=>+SS=>+ *SS S=>+*aSS=>+*aaS->+*aaa | S=>+SS=>+Sa=>+ *SS a=>+*Saa=>+*aaa |
| 3 | S=>S(S)S=>S( S(S)S )S=>S( S(S)S (S)S)S=>(()()) | S=>S(S)S=>S( S(S)S )S=>S( S(S) S(S)S)S=>(()()) |
| 4 | S=>SS=>S*S=>(S)*S=>(S+S)*S=>(a+a)*S=>(a+a)*a | S=>SS=>Sa=>S*a=>(S)*a=>(S+S)*a=>(a+a)*a |
| 5 | S=>(L)=>(L,S)=>( L,S ,S)=>(S,S,S)=>((L),S,S)=>((L,S),S,S)=>((S,S),S,S)=>((a,a),S,S)=>((a,a),a,(L))=>((a,a),a,(S))=>((a,a),a,(a) | S=>(L)=>(L,S)=>(L,(L))=>(L,(S))=>(L,(a))=>(L,S,(a))=>(L,a,(a))=>(S,a,(a))=>((L),a,a)=>((L,S),a,a)=>((L,a),a,a)=>((S,a),a,a)=>((a,a),a,(a)) |
以下均为最左推导语法树
2. 
3.(由于画图软件无法打出 ϵ，用null代替)
4
5.
4.2.3(1-3) 从串推导文法
1.S->(0?1)*
"所有"表示文法最外层一定有*
"0后至少有一个1"表示0可有可无
2.S->0S0|1S1|1|0| ϵ
回文一般用递归考虑
3.S->0S1S|1S0S| ϵ
保证递归内部每次插入一个0时必然有1插入，反之亦然
4.3.1 消除左递归
1.提左公因子方法
此文法并没有左公因子，但是我们先将其消除左递归，套公式即可
rexpr->rterm|rexpr’
rexpr’->+rterm rexpr’| ϵ
rterm->rfactor|rterm’
rterm’-> rfactor rterm’| ϵ
rfactor->rprimary|rfactor’
rfactor’->* rfactor’| ϵ
消除完左递归后，是可以自顶向下语法分析的
4.4.1(1-5)
在4.4.4中
4.4.3
求first 通过产生式第一个非终结符最左字符开始添加，如果这个非终结符可以为空，继续找第二个
求follow 找到含有目标非终结符的右部，其follow就是右边第一个非终结符的first,如果右边可以为空，就可以加上左部的follow
S->SS+|SS*|a
first(S)={a}
follow(S)={+,*,$}
4.4.4
预测分析器和预测分析表 与 first和follow集合
方法(这是我自己的简略总结，可能不容易看懂，真正要理解还是要看书做题哦）：
- 提左公因式，消除左递归
- 计算每个非终结符的first(自底向上，追踪连续查找，右部一个非终结符含 ϵ就可以继续添加下一个非终结符的first）,follow（自顶向下，查看右部含目标非终结符的，加上对应first,开始符号一定有一个$)
- 从左到右，按行填表，有first先first,first含 ϵ就找follow,如果自己的first()含 ϵ且follow()含$,还要填到列为$中去
1
S->0S1|01
1.提左公因子
S->0A
A->S1|1
2.消除左递归，带入得
S->0A
A->0A1|1
| first | follow |
|---|---|
| first(S)={0} | first(A)={0,1} |
| follow(S)={$} | follow(A)={$} |
第一列表示非终结符，其他列为输入符
| 非终结符 | 0 | 1 | $ |
|---|---|---|---|
| S | S->0A | ||
| A | A->0A1 | A->1 |
2
S->+SS|*SS|a
无左公因子无左递归
| first | follow |
|---|---|
| first(S)={+,*,a} | follow(S)={$} |
| 非终结符 | + | * | a | $ |
|---|---|---|---|---|
| S | S->+SS | S->*SS | S->a |
3
S->S(S)S| ϵ
消除左递归
S-> ϵ|S’
S’->(S)SS’| ϵ
也就是
S->S’
S’->(S)SS’| ϵ
| first | follow |
|---|---|
| first(S)={(,), ϵ} | follow(S)={$} |
| first(S’)={(,), ϵ} | follow(S’)={$} |
| 非终结符 | ( | ) | $ |
|---|---|---|---|
| S | S->S’ | S->S’ | S->S’ |
| S’ | S->(S)SS’ | ϵ | S’-> ϵ | S’-> ϵ |
4
S->S+S|SS|(S)|S*|a
提左公因子
S->SA|(S)|a
A->+S|S|*
当终结符含两个以上时，用一个非终结符表示
S->SA|T
A->+S|S|*
T->(S)|a
消除左递归
S->TS’
S’->AS’| ϵ
A->+S|TS’|*
T->(S)|a
这个难度比之前要高很多，要多加小心，注意做的顺序是first从下往上填，follow从上往下填，先first再follow
但是求出来follow都一样，感觉有问题……
| first | follow |
|---|---|
| first(S)={(,a} | follow(S)={+,(,),a,*,$} |
| first(S’)={+,(,a,*, ϵ} | follow(S’)={+,(,),a,*,$} |
| first(A)={+,(,a,*} | follow(A)={+,(,),a,*,$} |
| first(T)={(,a} | follow(T)={+,(,),a,*$} |
| 非终结符 | a | + | * | ( | ) | $ |
|---|---|---|---|---|---|---|
| S | S->TS’ | S->TS’ | ||||
| S’ | S’->AS’ | S’->AS’ | S’->AS’ | S’->AS’ | S’-> ϵ | S’-> ϵ |
| A | A->TS’ | A->+S | A->* | A->TS’ | ||
| T | T->a | T->(S) |
5
S->(L)|a
L->L,S|S
消除左递归
S->(L)|a
L->SL’
L’->,SL’| ϵ
| first | follow |
|---|---|
| first(S)={(,a} | follow(S)->{,,),$} |
| first(L)->{(,a} | follow(L)->{)} |
| first(L’)->{, ϵ} | follow(L’)->{)} |
| 非终结符 | ( | , | ) | a | $ |
|---|---|---|---|---|---|
| S | S->(L) | S->a | |||
| L | L->SL’ | L->SL’ | |||
| L’ | L’->,S | L’-> ϵ |
4.5.1
如图所示，在将字符压入栈中，通过移入规约方法转换为文法时，出现在栈顶的符号就是句柄
1如下图 在000111中的第一个1入栈时，弹出01 然后压入S
所以句柄为01
2同理 句柄为0S1
4.6.2
S->SS+|SS*|a
提左公因子，保留，不同的用另一个非终结符替代，一次性提完
S->SSA|a
A->+|*
然后消除左递归，注意这里是SS,套公式，我们把第二个S看着终结符
S->aS’
S’->SAS’| ϵ
A->+|*
此时S与S’循环递归了，我们把一代入二，同时
对于开始符号S，要加一个S’->S，只有这样，才能表示进入接受状态，如果只有S出现，由于左递归，S可以在很多地方出现，所以不表示接受状态，为了与上面的S’区分，我们换成S’’
所以答案为
S’‘->S
S->aS’
S’->aS’AS’| ϵ
A->+|*
4.6.5
判断LL(1)文法的标准
first(AaAb)={A}和first(BaBb)={B}无交集，且不为 ϵ，所以是LL(1)文法
又因为follow(A)=follow(B)={a,b}，当移入a或者b时，就会发生规约冲突所以不是SLR(1)
从另一个角度也可以解释，因为A->. B->. 所以存在规约冲突
4.6.6
有左递归，显然不是LL(1)的
是SLR(1)文法，因为没有找到冲突
4.7.4
从文法中容易看出，当输入符为d时，将发生移入规约冲突
SLR(1)将查看可规约的非终结符的follow，判定规约对象，
S->d.c
follow(A)={a,c)
两者含有c，所以SLR(1)文法不能解决
但是他是LR(1)文法，在SLR(1)基础上增加向前搜索符
项目集变成 {[A->d.,a],[A->d.c,$}，此时已经没有冲突
现在判断是否是LALR(1),即在LR(1)的基础上合并同心集（项目集相同，向前搜索法不同的状态集），如果不产生冲突，就是LALR(1)文法
做出对应的LR项目集，然后画出DFA（图中有一处错误，I4和I2应该合并为一个状态，但是已经画了，就不改了，不影响正确性）
从DFA可以看到，并不存在冗余项，所以他也是LALR（1）文法
4.7.5
先做出对应的LR(1)项集，然后画出DFA
如图所示，发现I5和I9是一样的，但是显然，他们通过不同的路径得到，如果合并的话一定会有冲突，所以不是LALR(1)文法
