《中国计量学院编译习题解答2.doc》由会员分享，可在线阅读，更多相关《中国计量学院编译习题解答2.doc（9页珍藏版）》请在金锄头文库上搜索。
1、文法GN为： N-D|ND D-0|1|2|3|4|5|6|7|8|9 GN的语言是什么？答案 GN的语言是V+。V=0,1,2,3,4,5,6,7,8,9 N=ND=NDD. =NDDDD.D=D.D已知文法GZ： Z-aZb|ab 写出L(GZ)的全部元素。 答案 Z=aZb=aaZbb=aaa.Z.bbb= aaa.ab.bbb L(GZ)=anbn|n=1令文法GE为: E-E+T|E-T T-T*F|T/F|F F-(E)|I 证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。 答案 此句型对应语法树如右，故为此文法一个句型。或者：因为存在推导序列: E=E+T=
2、E+T*F，所以 E+T*F句型。此句型相对于E的短语有:E+T*F；相对于T的短语有T*F,直接短语为：T*F。句柄为：T*F 。 给出下列文法所对应的正规式： S-0A|1BA-1S|1B-0S|0 答案 解方程组S的解： S=0A|1BA=1S|1B=0S|0将A、B产生式的右部代入S中S=01S|01|10S|10=（01|10）S|（01|10）所以：S= (01|10)*(01|10)为下边所描述的串写正规式，字母表是 a,b. a) 以ab 结尾的所有串b) 包含偶数个b但不含a的所有串c) 包含偶数个b且含任意数目a的所有串d) 只包含一个a的所有串e) 包含ab子串的所有串f
3、) 不包含ab子串的所有串答案 注意 正规式不唯一a) (a|b)*abb) (bb)*c) (a*ba*ba*)*d) b*ab*e) (a|b)*ab(a|b)*f) b*a* 请描述下面正规式定义的串. 字母表S = 0，1. a) 0*(10+)*0*b) (0|1)*(00|11) (0|1)*c) 1(0|1)*0 答案 a) 每个 1 至少有一个 0 跟在后边的串 b) 所有含两个相继的0或两个相继的1的串 c) 必须以 1 开头和0结尾的串 设有文法GA的产生式集为: ABaC|CbB BAc|c CBb|b试消除GA的左递归。 答案 提示：不妨以A、B、C排序.先将A代入B中
4、，然后消除B中左递归；再将A、B代入C中。再消除C中左递归。 最后结果为:GA: ABaC|CbB BCbBcB|cB BaCcB| CcBbC|bC CbBcBbC|设文法G为 S A A BA | B aB | b (1)证明它是LR(1)文法； (2)构造它的LR(1)分析表； (3)给出输入符号串abab的分析过程。 答案(1)拓广文法G: (0) S S (1) S A (2) A BA (3) A (4) B aB (5) B b FIRST(A) = , a, b FIRST(B) = a, b构造的DFA如下:由项目集规范族看出，不存在冲突动作。 该文法是LR(1)文法。 (2
5、) LR(1)分析表 状态 ActionGoto a B # S A B 0 S4 S5 r3 1 2 3 1 acc 2 r1 3 S4 S5 r3 6 3 4 S4 S5 7 5 r5 r5 r5 6 r2 7 r4 r4 r4 (3)输入串abab的分析过程为： 步骤 状态栈 符号栈 当前字符 剩余字符串 动作 (1) 0 # a bab# 移进 (2) 04 #a b ab# 移进 (3) 045 #ab a b# 归约 Bb (4) 047 #aB a b# 归约 BaB (5) 03 #B a b# 移进 (6) 034 #Ba b # 移进 (7) 0345 #Bab # 归约
6、Bb (8) 0347 #BaB # 归约 BaB (9) 033 #BB # 归约 A (10) 0336 #BBA # 归约 ABA (11) 036 #BA # 归约 ABA (12) 02 # A # 归约 SA (13) 01 #S # acc 写出语句 WHILE(AB) DO IF(CD)THEN X:=Y+Z; 的四元式表示 。答案 100 IF AB GOTO 102 101 GOTO 107 102 IF CAa|b A-SB B-ab第1种改写： S-SBa|b B-ab 0) S-b N2 1) N2-B a N2 2) N2- 3) B-a b =| | FIRST
7、| FOLLOW |+-+-+-+| S | b | # |+-+-+-+| B | a | a |+-+-+-+| N2 | ,a | # |=Predicting Analysis Table=| | a | b | # |+-+-+-+-+| S | |-b N2 | |+-+-+-+-+| B |-a b | | |+-+-+-+-+| N2 |-B a N2 | |- |=由预测分析表中无多重入口判定文法是LL(1)的。第2种改写：S-Aa|bA-AaB|bBB-ab 0) S-A a 1) S-b 2) A-b B N3 3) N3-a B N3 4) N3- 5) B-a b=| | FIRST | FOLLOW |+-+-+-+| S | b | # |+-+-+-+| A | b | a |+-+-+-+| B | a | a |+-+-+-+| N3 | a, | a |=
