《编译原理期末复习题(作业)(2012)》由会员分享，可在线阅读，更多相关《编译原理期末复习题(作业)(2012)（23页珍藏版）》请在金锄头文库上搜索。
1、1. P36 第第 6 题：令文法题：令文法G6为为ND|ND D0|1|2|3|4|5|6|7|8|9 (1) G6的语言的语言L(G6)是什么是什么? (2) 给出句子给出句子 0127、34 和和 568 的最左推导和最右推导的最左推导和最右推导 解：(1) G6的语言L(G6)为： L(G6)=x|x为可带前导 0 的正整数 或 L(G6)=x|x为数字串 或 L(G6)=(0|1|2|3|4|5|6|7|8|9)+ (2)分析：最左推导：任何一步 = 都是对 中的最左非终结符进行替换 最右推导：任何一步 = 都是对 中的最右非终结符进行替换 句子 0127、34 和 568 的最左推
2、导如下： N=ND=NDD=NDDD=DDDD=0DDD=01DD=012D=0127 N=ND=DD=3D=34 N=ND=NDD=DDD=5DD=56D=568 句子 0127、34 和 568 的最右推导如下： N=ND=N7=ND7=N27=ND27=N127=D127=0127 N=ND=N4=D4=34 N=ND=N8=ND8=N68=D68=568 2. P36 第第 7 题：写一个文法，使其语言是奇数集，且每个奇数不以题：写一个文法，使其语言是奇数集，且每个奇数不以 0 开头开头 解： 如：GS=，VT=0,1,2,3,4,5,6,7,8,9；VN=S,A,B,C,D 其中 P
3、 为:SAB|B AAC|D B1|3|5|7|9 C0|D D1|2|3|4|5|6|7|8|9 3. P36 第第 8 题：令文法为：题：令文法为： ET|E+T|E-T TF|T*F|T/F F(E)|i (1) 给出给出 i+i*i、i*(i+i)的最左推导和最右推导的最左推导和最右推导 (2) 给出给出 i+i+i、i+i*i 和和 i-i-i 的语法树的语法树 1解：(1)最左推导： E=E+T=T+T=F+T=i+T=i+T*F=i+F*F=i+i*F=i+i*i E=T=T*F=F*F=i*F=i*(E)=i*(E+T)=i*(T+T)=i*(F+T)=i*(i+T) =i*(
4、i+F)=i*(i+i) 最右推导： E=E+T=E+T*F=E+T*i=E+F*i=E+i*i=T+i*i=F+i*i=i+i*i E=T=T*F=T*(E)=T*(E+T)=T*(E+F)=T*(E+i)=T*(T+i)=T*(F+i) =T*(i+i)=F*(i+i)=i*(i+i) (2)i+i+i、i+i*i 和 i-i-i 的语法树分别见图 3-1,3-2 和 3-3 图 3-1 图 3-2 图 3-3 4. P36 第第 9 题：证明下面的文法是二义的：题：证明下面的文法是二义的：SiSeS|iS|i 解： 分析：要证明一个文法具有二义性，方法有两个： 找到该文法的某个句子，对该
5、句子存在两个不同的最左(右)推导 例如：存在句子 iiiei，它存在两个不同的最左推导 S=iSeS=iiSeS=iiieS=iiiei S=iS=iiSeS=iiieS=iiiei 找到该文法的某个句子，它对应两棵不同的语法树 例如：存在句子 iiiei，它对应了两棵不同的语法树 由于该文法的句子 iiiei 存在两个不同的最左推导，因此该文法是二义文法 25. P36 第第 11 题：给出下面语言的相应文法题：给出下面语言的相应文法 L1=anbnci|n1,i0 L2=aibncn|n1,i0 L3=anbnambm|n,m0 L4=1n0m1m0n|n,m0 解：G1S:SAB AaA
6、b|ab BBc| G2S:SAB AAa| BbBc|bc G3S:SAB AaAb| BaBb| G4A:A1A0|0B1| B0B1| 6. P64 第第 8 题：给出下面正规表达式：题：给出下面正规表达式： (1) 以以 01 结尾的二进制数串结尾的二进制数串 (2) 能被能被 5 整除的十进制整数整除的十进制整数 解：(1)(0|1)*01 (2)(1|2|9)(0|1|2|9)*)*(0|5) 7. P64 第第 7 题：构造下列正规式相应的题：构造下列正规式相应的 DFA (1) 1(0|1)*101 (2) 0*10*10*10* 解：(1) 1(0|1)*101，先构造NFA
7、 3确定化： 0 1 1 - 2,3,4 2,3,4 3,4 3,4,5 3,4 3,4 3,4,5 3,4,5 3,4,6 3,4,5 3,4,6 3,4 3,4,5,7 3,4,5,7 3,4,6 3,4,5 0 1 1 - 2 2 3 4 3 3 4 4 5 4 5 3 6 6 5 4 DFA 的状态转换图如下： 附：最小化的 DFA： (2) 0*10*10*10*，先构造NFA 确定化： 40 1 1,2,3 2,3 4,5,6 2,3 2,3 4,5,6 4,5,6 5,6 7,8,9 5,6 5,6 7,8,9 7,8,9 8,9 10,11,12 8,9 8,9 10,11,1
8、2 10,11,12 11,12 - 11,12 11,12 - 0 1 1 2 3 2 2 3 3 4 5 4 4 5 5 6 7 6 6 7 7 8 - 8 8 - DFA 的状态转换图如下： 附：最小化的 DFA 如下： 8. P64 第第 12 题：将图题：将图 3.18 的的(a)确定化，将确定化，将(b)最少化最少化 （1）将图）将图 3.18 的的(a)确定化确定化 解： a b 0 0,1 1 0,1 0,1 1 1 0 - a b 0 1 2 1 1 2 2 0 - 确定化之前 确定化之后 另附最少化： 将终态集和非终态集作为基本分划：0,1、2 5考虑0,1：由于0,1a
9、=1,10,1 0,1b=2,22 因此0,1不可再分；最终分划为：0,1、2 分别用状态 0、2 代表上述集合，且包含原终态的子集对应的状态为新终态 （2）将图）将图 3.18 的的(b)最少化最少化 解：将终态集和非终态集作为基本分划：0,1 2,3,4,5 考虑0,1：由于0,1a=10,1 0,1b=2,42,3,4,5 因此0,1不可再分； 考虑2,3,4,5：2,3,4,5a=1,3,0,5落在当前分划的两个字集中 因此将2,3,4,5一分为二： 由于2,4a=0,1 3,5a=3,5 2,4b=3,5 3,5b=2,4 因此将2,3,4,5划分为2,4和3,5。 当前分划为0,1
10、、2,4、3,5 再分别考虑上述三个子集，均不可再分。最终分划为：0,1、2,4、3,5 分别用状态 1、2、3 代表上述集合，且包含原终态的子集对应的状态为新终态 最小化的 DFA 如下： 9. P65 第第 14 题题 构造一个构造一个 DFA，它接受，它接受 =0,1上所有满足如下条件的字符串：每个上所有满足如下条件的字符串：每个 1 都 有都 有 0 直接跟在右边。直接跟在右边。 解答： （0|10）*NFA 如下： 状态转换表如下： 6I I0I11,2,4 2,4 3 2,4 2,4 3 3 2,4 - 0 1 1 2 3 2 2 3 3 2 - DFA 如下： 化简： (1) 基
11、本分划：1,2，3 (2) 1,20=2,21,2 1,21=3,33 无需再分 (3) 最后分划为：1,2，3 10. P64 第第 15 题：给定右线性文法题：给定右线性文法 G: S0S|1S|1A|0B A1C|1 B0C|0 C0C|1C|0|1 求出一个与求出一个与 G 等价的左线性文法等价的左线性文法 解答：右线性文法=有限自动机 7有限自动机=左线性正规文法 GF：FA1|B0|C0|C1 AA1 BB0 CC0|C1 SS0|S1|0|1 11. P81 第第 1 题：考虑下面文法题：考虑下面文法G1: Sa|(T) TT,S|S (1) 消去消去G1的左递归的左递归 (2)
12、 经改写后的文法是否是经改写后的文法是否是 LL(1)的？给出它的预测分析表的？给出它的预测分析表 解： (1) Sa|(T) TST T,ST| (2) 改写后的文法是 LL(1)的，因为： 1）改写后的文法不含左递归 2）对于产生式 Sa|(T)： FIRST(a)=a FIRST()= FIRST(T)=（ FIRST(a)FIRST()FIRST(T)=； 对于产生式 T,ST|： FIRST(,ST)=， FIRST() = FIRST(,ST)FIRST() = 83）对文法中的非终结符 T，其某个候选首符集包含 ， 但 FIRST(T)= ,， FOLLOW(T)=） FIRST
13、(T)FOLLOW(T)= 因此，改写后的文法是 LL(1)的。 FIRST(S)=a，( FOLLOW(S)=# FIRST(T)=a，( FOLLOW(T)=） FIRST(T)=,， FOLLOW(T)=） 预测分析表： a ( ) , # S Sa S S (T) T TST TST TST T T T,ST 12. P81 第第 2 题：对下面的文法题：对下面的文法 G: ETE E+E| TFT TT| FPF F*F| P(E)|a|b| (1) 计算该文法每个非终结符的计算该文法每个非终结符的 FIRST 和和 FOLLOW (2) 证明该文法是证明该文法是 LL(1)的的 (
14、3) 构造它的预测分析表构造它的预测分析表 解： (1) 文法 G 的每个非终结符的 FIRST 为： FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)=(,a,b, FIRST(E)=+, FIRST(T)=(,a,b, FIRST(F)=*, 文法 G 的每个非终结符的 FOLLOW 为： FOLLOW(E)=FOLLOW(E)=#,) FOLLOW(T)=FOLLOW(T)=+,#,) FOLLOW(F)=FOLLOW(F)=(,a,b,#,+,) FOLLOW(P)=*,(,a,b,#,+,) (2) 证明该文法是 LL(1)文法 分析：判定一个文法是LL(1)文法的充要条件是：对形如：A1|2|n的产生式，有下述条件成立： 9 FIRST(1)FIRST(2)FIRST(n)= 若存在i，i=1,2,n，则有FIRST(A)FOLLOW(A)= 该文法形如A1|2|n的产生式有： E
