• 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=>SS=>(S)S=>(S+S)S=>(a+a)S=>(a+a)*a	S=>SS=>Sa=>Sa=>(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))

以下均为最左推导语法树

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->+|*