编译原理及实现课后习题答案绝杀版

2.1 设字母表A={a}，符号串x=aaa，写出下列符号串及其长度：x0,xx,x5以及A+和A*. x=(aaa)=ε | x|=0 xx=aaaaaa |xx|=6 x=aaaaaaaaaaaaaaa | x|=15 A =A∪A∪ ?. ∪A ∪?={a,aa,aaa,aaaa,aaaaa?}

A* = A∪A∪ A ∪ ?. ∪ A ∪?={ε,a,aa,aaa,aaaa,aaaaa?}

2.2 令∑={a，b，c}，又令x=abc，y=b，z=aab，写出如下符号串及它们的长度：xy，xyz，（xy）3 xy=abcb |xy|=4 xyz=abcbaab |xyz|=7 (xy)=(abcb)=abcbabcbabcb | (xy)|=12 2.3

设有文法G[S]：S∷=SS*|SS+|a，写出符号串aa+a*规范推导，并构造语法树。 S => SS* => Sa* => SS+a* => Sa+a* => aa+a*

3

3

3

0

1

2

n

+

1

2

n

5

5

0

0

0

S S S a S a + S a * 2.4 已知文法G[Z]：Z∷=U0∣V1 、 U∷=Z1∣1 、 V∷=Z0∣0 ,请写出全部由此文法描述的只含有四个符号的句子。

Z=>U0=>Z10=>U010=>1010 Z=>U0=>Z10=>V110=>0110 Z=>V1=>Z01=>U001=>1001 Z=>V1=>Z01=>V101=>0101

2.5 已知文法G[S]： S∷=AB A∷=aA︱ε B∷=bBc︱bc , 写出该文法描述的语言。

A∷=aA︱ε描述的语言: {a|n>=0} B∷=bBc︱bc描述的语言：{bc|n>=1} L(G[S])={abc|n>=0,m>=1}

2.6 已知文法E∷=T∣E+T∣E-T 、 T∷=F∣T*F∣T/F 、 F∷=(E)∣i，写出该文法的开始符号、终结符号集合VT、非终结符号集合VN。

nmm

nnn

开始符号：E

Vt={+, - , * , / ,（ , ）, i} Vn={E , F , T}

2.7 对2.6题的文法，写出句型T+T*F+i的短语、简单短语以及句柄。 短语：T+T*F+i T+T*F i i T T*F 简单短语：i T*F T 句柄：T

E E E T + T + T * F T F i 2.8 设有文法G[S]：S∷=S*S|S+S|(S)|a，该文法是二义性文法吗？

S S * S S S + S S + S a a S * S a a a a

根据所给文法推导出句子a+a*a，画出了两棵不同的语法树，所以该文法是二义性文法。 2.9 写一文法，使其语言是奇正整数集合。 A::=1|3|5|7|9|NA N::=0|1|2|3|4|5|6|7|8|9

2.10给出语言{anbm|n,m≥1}的文法。

G[S]: S::=AB A::=aA|a B::=bB|b

3.1 有正则文法G[Z]：Z::=Ua|Vb，U::=Zb|b，V::=Za|a ，画出该文法的状态图，并检查句子abba是否合法。 解：该文法的状态图如下：

句子abba合法。

3.2 状态图如图3.35所示，S为开始状态，Z为终止状态。写出相应的正则文法以及V，Vn和Vt。

解： 左线性文法G[Z]: 右线性文法G’[S]:

Z::=Ab|b S::=aA|b

A::=Aa|a A::=aA|b

V={Z,A,a,b} V={S,A,a,b}

Vn={Z,A} Vt={a,b} 3.3 构造下列正则表达式相应的NFA： 1(1|0)*|0

1(1010*|1(010)*1)*0 解：正则表达式：1(1|0)*|0

正则表达式：1(1010*|1(010)*1)*0

3.4 将右图的NFA M确定化 a

解：

0 a,b a 1 Vn={S,A} Vt={a,b} q0={0} q1={0,1} q2={1} DFA: a {0,1} {0,1} {0} b {1} {1} Φ

3.5 将图3.37的DFA化简。

解： 划分 {0,1} {2,3,4,5} 划分 {0,1} {2,4} {3,5} q0={0,1} q1={2,4} 化简后的DFA：

a {1} {0,1} {3,5} q2={3,5} b {2,4} {3,5} {2,4} a {1} {1,0,3,5} b {2,4} {3,5,2,4}

4.1 对下面文法，设计递归下降分析程序。 S→aAS|(A) , A→Ab|c

解：首先将左递归去掉，将规则A→Ab|c 改成 A→c{b} 非终结符号S的分析程序如下：

非终结符号A的分析程序如下：

4.2 设有文法G[Z]： Z∷=(A) , A∷=a|Bb , B∷=Aab

若采用递归下降分析方法，对此文法来说，在分析过程中，能否避免回溯？为什么？

解：若采用递归下降分析方法，对此文法来说，在分析过程中不能避免回朔。因为规则A∷=a|Bb和规则B∷=Aab构成了间接左递归，不满足实现没有回溯的递归下降分析方法的条件（1）（书P67），且规则 A: := a|Bb，FIRST(a)={a}，FIRST(Bb)={a}，即此规则候选式的首符号集有相交，不满足实现没有回溯的递归下降分析方法的条件（2）（书P67），在分析过程中，将造成回溯。 改写文法可避免回溯：

将规则B∷=Aab代入规则A∷=a|Bb得：A∷=a|Aabb，再转换成：A∷=a{abb}，可避免回溯。

4.3 若有文法如下，设计递归下降分析程序。 <语句>→<语句><赋值语句>|ε <赋值语句>→ID=<表达式>

<表达式>→<项>|<表达式>＋<项>|<表达式>－<项> <项>→<因子>|<项>*<因子>|<项>/<因子> <因子>→ID|NUM|(<表达式>) 解：首先，去掉左递归

<语句>→<语句><赋值语句>|ε改为： <语句>→{<赋值语句>} <表达式>→<项> | <表达式> + <项> | <表达式> - <项> 改为： <表达式>→<项>{（+ | -）<项>}

<项>→<因子> | <项> * <因子> | <项> / <因子> 改为：

本文来源：https://www.bwwdw.com/article/nhpf.html