1、第一章练习 12、典型的编译程序可划分为哪几个主要的逻辑部分？各部分的主要功能是什么？典型的编译程序具有 7 个逻辑部分：第二章练习 2.24.试证明：A+ =AA*=A*A证： A*=A0A+ ，A+=A1A2An得：A*=A0 A1 A2An AA*=A（A0A1A2An）= AA0AA1AA2 A An=AA2A3 An +1= A+同理可得：A*A =(A0A1A2 An)A=A0 AA1AA2A AnA= AA2 A3 An+1= A+因此： A+ =AA*=A*A练习 2.31.设 G标识符 的规则是 ：标识符:=a|b|c|标识符a|标识符 c|标识符0|标识符 1试写出 VT
2、和 VN，并对下列符号串 a,ab0,a0c01,0a,11,aaa 给出可能的一些推导。解：VT =a,b,c,0,1， VN =标识符(1) 不能推导出 ab0,11,0a(2)标识符=a(3)标识符=标识符1=标识符01=标识符c01=标识符0c01= a0c01(4)标识符=标识符a=标识符aa=aaa2写一文法，其语言是偶整数的集合解：G：:= | := + | |:= |:= | 1 | 3 | 5 | 7 | 9:=0 | 2 | 4 | 6 | 84. 设文法 G 的规则是：A :=b| cc试证明：cc, bcc, bbcc, bbbccLG证：（1） A=cc（2） A=b
3、A=bcc（3） A=bA=bbA=bbcc（4） A=bA=bbA=bbb A=bbbcc又cc, bcc, bbcc, bbbccVt*由语言定义，cc, bcc, bbcc, bbbccLG5 试对如下语言构造相应文法：（1） a(bn)a | n=0,1,2,3,其中左右圆括号为终结符。（2） （an） （bn ） | n=1,2,3, 解：（1）文法GS ：S:= a(B)aB:= bB |( 2 ) 文法GS：-错了，两个 n 不等S := (A)(B)A:= aA|aB:= bB|b7.对文法 G3表达式表达式:=项|表达式+项| 表达式-项项:=因子| 项*因子|项 /因子因子
4、:=（表达式 ）| i列出句型表达式+项* 因子的所有短语和简单短语。= + = + * 短语有：表达式+项*因子和项*因子简单短语是：项*因子8 文法 V:= aaV | bc 的语言是什么？解：L（GV）= a2nbc | n=0,1,2,V aaV aaaaV . a2nbc (n 1)V bc (n=0)练习 2.45.已知文法 GE：E:=ET+ | TT:=TF* |FF:=FP |PP:=（E ）| i有句型 TF*PP+，问此句型的短语，简单短语，和句柄是什么？解：此句型的短语有：TF*PP+ ，TF* ，PP，P简单短语有：TF*，P句柄是：TF*8.证明下面的文法 G 是二
5、义的：S:= iSeS | iS | i证：由文法可知 iiiei 是该文法的句子，又由文法可知 iiiei 有两棵不同的语法树。所以该文法是二义性文法。第三章练习 3.11画出下述文法的状态图Z:=BeB :=AfA := e |Ae使用该状态图检查下列句子是否是该文法的合法句子f，eeff，eefe2、有下列状态图，其中 S 为初态，Z 为终态。（1） 写出相应的正则文法：（2） 写出该文法的 V，Vn 和 Vt；（3） 该文法确定的语言是什么？解：（1） ZA1|0 AA0|0（2） V=A,Z,0,1Vn=A,ZVt=0,1（3） L (GS)= 0 或 0n1,n1L (GS)= 0
6、|00*1练习 3.21令 A，B，C 是任意正则表达式，证明以下关系成立：A|A=A（A*） *= A*A*=| AA*（AB）*A = A（BA）*（A|B ）* =（A*B* ）*=（A*|B*）证明：A A xxL(A) 或 xL(A)xxL(A) A（A* ）* （A* ）0（A*）1 （A*）2（A*）n(A0A 1A2An) (A1)A0A 1A2AnA*AA* 所表示的语言是 :LALA*LA0LA（LA0LA1LA2）LA0LA1LA2LA*故 AA* A*(LALB)*LA=(L(A)LBLALBLALB LALBLALBLALB) LA=LALALBLALALBLALBLALALBLALBLALB LA= LA(LBLA LBLALBLA )= LA(LBLA)(AB)*A=A(BA)*三个表达式所描述的语言都是 LALB 中任意组合（A|B ）*=(A*B*)=(A*|B*)*2. 构造下列正则表达式相应的 DFA（1） 1（0|1）*|0（2） 1（1010*|1 （010 ）*1）*04. 5. 构造一 DFA，它接受 =0,1上所有满足如下条件的字符串：每个 1 都有 0 直接跟在右边。
