编译原理习题答案
习题1
1.1翻译程序：把用某种程序设计语言（源语言）编写的程序（源程序）翻译成与
之等价的另一种语言（目标语言）的程序（目标程序）。
编译程序：一种翻译程序，将高级语言编写的源程序翻译成等价的机器语言或
汇编语言的目标程序。
1.2词法分析、语法分析、语义分析和中间代码生成、代码优化、目标代码生成 1.3词法分析：根据语言的词法规则对构成源程序的符号进行扫描和分解，识别出
一个个的单词。
语法分析：根据语言的语法规则，把单词符号串分解成各类语法单位。
语义分析及中间代码生成：对语法分析识别出的语法单位分析其含义，并进 行初步翻译。
代码优化：对中间代码进行加工变换，以产生更高效的目标代码。
目标代码生成：将中间代码变换成特定机器上的绝对指令代码、可重定位的
指令代码或会变指令代码。
以上5个阶段依次执行。
习题2
2.1 （1）有穷非空的符号集合
（2）利用产生是规则A->v将A替换为v时与A的上下文无关。 （3）略
（4）推导是把句型中的非终结符用一个产生是规则的右部开替代的过程； 直接推导是将非终结符的替代结果只用了一次产生式规则。
（5）略
（6）一个句型的最左直接短语
（7）如果一个文法存在某个句子对应两棵不同的语法树或有两个不同的最左
（右）推导，则称这个文法是二义的。
2.2（1）VN =｛Z,A,B｝ VT ={a,b,c,d,e} （2）abbcde,abbbcde是，acde不是。 2.3 （1）L[G]={d （2）
2.4 （1） A=>B=>c=>fAg=>fBg=>fCg=>feg
（2）A=>AaB=>AaC=>Aae=>Bae=>BcCae=>Bceae=>Cceae=>eceae （3）A=>B=>BcC=>BcfAg=>BcfAaBg=>BcfAaCg=>BcfAaeg=>BcfBaeg
=>BcfCaeg=>Bcfeaeg=>Ccfeaeg=>ecfeaeg
（3）中题目有错应为C?fCg|e
|n≥1,m≥0}
2.5 L[G]=｛a?b?c?|aab,n≥2｝
2.6 (1)Z→AB A→Aa|ε B→Bb|ε (2)Z→aZb|ab (3)Z→aAb A→aAb|b
(4)Z→AB A→aAb|ab B→cB|ε
(5)Z→aaAb|ab Z→aaBb|bb A→aaAb|ab B→aaBb|bb
2.7 一位数：Z→2|4|6|8
两位数：Z→AB A→1|2|3|4|5|6|7|8|9 B→0|2|4|6|8 三
位
以
上
：
Z→ACB
A→1|2|3|4|5|6|7|8|9
B→0|2|4|6|8
C→CD
D→0|1|2|3|4|5|6|7|8|9
2.8证明：E=>E+T=>E+T*F
短语：T*F E+T*F 直接短语：T*F 句柄：T*F
2.9 语法树： E 短语：E*T , (E*T) , F↑(E*T) ，F ,E* F↑(E*T) E * F 直接短语：E*T , F T ↑ F 句柄：F F ( E ) E * T 2.10（1）语法树 （2） 直接短语：a , Z Z 句柄：Z ( L ) L , Z Z ( L ) Z a
2.11最左推导：Z=>ZaB=>BaB=>B+AaB=>A+AaB=>(+)Z*aB=>(+)ZaB*aB =>(+)+aB*aB=>(+)+aA*aB=>(+)+a(*aB=>(+)+a(*aA =>(+)+a(*a( 直接短语：（，+ 句柄：(
2.12(1) S=>iSeS=>iiSeS=>iiIeS=>iiIeI S=>iS=>iiSeS=>iiIeS=>iiIeI (2) S=>SaS=>cSaS=>cfaS=>cfaf S=>cS=>cSaS=>cfaS=>cfaf
(3) E=>EOE=>EOEOE=>iOEOE=>i+EOE=>i+iOE=>i+i-E=>i+i-i E=>EOE=>iOE=>i+E=>i+EOE=>i+iOE=>i+i-E=>i+i-i
2.13 Z→aABZ|cCACd A→bAB|aZA|cCC B→bAB|Czb C→cZ|c
习题3
3.1(1)确定的有限自动机
(2)不确定的有限自动机
(3)正规集是一类特殊的单词集合，正规式是正规集的描述工具 3.2 (1) (1|2|3|4|5|6|7|8|9|0)*(1|3|5|7|9) (2) 11(0|1)*00
3.3 证明：b*(a|b)+=｛a,b,ab,ba,aa,bb…｝ (a|b)+=｛a,b,ab,ba,aa,bb…｝ 3.4 (1)
(2)
a ε S0 DA ε Db B εc C ε DZ D
ε Da a S0 DA b b DZ D
(3) (4) a G DF D
b a a S0 Da B b b E Db A b DZ ε D DC a DDb D
a S0 Da a b A Db a B b DZ D
3.5(1) (2)
a Z Db A b a Y D
(3)
*(01|10)
(2) (0(1|00)*)|00 →1AB (2)Z→(0|1)A A→0|1 B→0B →ε )*bb →1B
→0Z|0 →0Z|ε
A Da B Da b C DD D
Sb a 0 X D0 U D1 Z D
1 →AB
→0A|ε
→(0|1)B|ε a 0 aa 3 DD 1 Db b b b b 4 DD
3.6(1) (01|10)
3.7(1) Z A A B B
3.8 r=a(a|b
3.9 Z B Z
3.10 3.11