《编译原理_练习参考》由会员分享，可在线阅读，更多相关《编译原理_练习参考（60页珍藏版）》请在金锄头文库上搜索。
1、程 序 设 计 语 言 Chapter 2.高级语言及 其语法描述*2CH.2.练习题6(P36.)n6.令文法G6为:N D|ND D 0|1|2|3|4|5|6|7|8|9n(1) G6的语言L(G6)是什么?n注意：集合的写法不正确n解：L(G6)=0,1,2,3,4,5,6,7,8,9+=09数字构成的所有数字串，可以0开 头n(2) 给出句子0127、34和568的最左和最右推导。n注意：1)步骤，和 的区别；2) 不能写 为n解：0127的最左推导： NNDNDDNDDDDDDD0DDD01DD012D01 270127的最右推导： NNDN7ND7N27ND27N127D1270
2、127+3CH.2.练习题8(P36.)n8. 令文法为E T|E+T|E-TT F|T*F|T/FF (E)|i(1) 给出 i+i*i、i*(i+i)的最左推导 和最右推导。解：此处仅以 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*(i+F ) 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) 4CH.2.练习题8(P36.)n8. 令文法为E T|E+T
3、|E-T T F|T*F|T/FF (E)|iEE - TE - TTFF iFiii-i-i 的语法树(2) 给出 i+i+i、i+i*i和i-i-i的语法树。EE + TE + TTFF iFiii+i+i 的语法树i+i*i 的语法树EE + TTTFF iFii*n注意：树枝和符号均不可随意增减！5CH.2.练习题9(P36.)n9. 证明下面的文法是二义的 ：S iSeS|iS|in证明: 因为存在句子 iiiei ，它对应两棵不同的语法树,如 右图:所以该文法是二义文法。n说明：按定义只要能给出一 个反例即可，iiiei不是唯一的 反例。Si S i S e SiiiSi S e
4、Si SiDate程 序 设 计 语 言 Chapter 3.词法分析*7CH.3.练习题8(P64.)n8. 给出下面的正规表达式。 (1) 以01结尾的二进制数串;正规式 (0|1)*01 (2) 能被5整除的十进制整数; 允许任意0开头：(0|1|2|3|4|5|6|7|8|9)*(0|5)不允许0开头（0本身除外）： (0|5)|(1|2|3|9)(0|1|2|3|9)*(0|5)Date8CH.3.练习题7(P64.)n7. 构造下列正规式相应的DFA。(1) 1(0|1)*101 解2: 正规式对应的NFA:04123110110I I0 I1 0 初01 1 1 11 11,2
5、2 1,2 21,3 31,2 2 1,3 31 11,2,4 4 1,2,4终41,3 31,2 2 10423110110010DFA:Date9n7. 构造下列正规式相应的NFA。(P64.)(2) 1(1010*|1 (010)*1)*0XY201131010*1 (010)*1XY201136451 100*7811 (010)*Date10n7. 构造下列正规式相应的NFA。(P64.)(2) 1(1010*|1 (010)*1)*0XY201136451 1007811910010XY201136451100781191001211017. (2) 1(1010*|1 (010)
6、*1)*0的NFA。Date11CH.3.练习题14(P64.)n(1) 正规式: (10|0)*(2) NFA: 确定化:YX10 012010 01 01 2I I0 I1X,1,Y 1,Y2 1,Y1,Y2 21,Y I I0 I1 初终0 1 2 终 1 1 2 2 1 DFA:Date12CH.3.练习题14(P64.)n(1) 正规式: (10|0)*(2) NFA:YX10 012010 01 01 2DFA:构造一个DFA，它接受 S 0,1上所有满足如下条件 的字符串：每个1都有0直 接跟在右边。10010DFA:(最简)Date程 序 设 计 语 言 Chapter 4.
7、自上而下 语法分析*14CH.4.练习题1(P81.)n1.考虑下面文法G1: Sa|(T)TT，S|Sn(1) 消去G1的左递归。然后对每个非终结符,写 出不带回溯的递归子程序。n解(1) 消左后的文法G1: Sa|(T)TSTT ,ST|Date15CH.4.练习题1(P81.)n解(1) 不带回溯的递归子程序: Sa|(T)Procedure S;Beginif sym=a or sym= then advance else if sym=( thenbegin advance;T;if sym=) then advanceelse errorendelse errorEnd;16CH.
8、4.练习题1(P81.)n解(1) 不带回溯的递归 子程序: nTSTProcedure T;BeginS;Tend;n解(1) 不带回溯的递归 子程序: nT,ST|procedure T;begin if sym=, then begin advance;S;TendEnd;17CH.4.练习题1(P81.)(2) 经改写后的文法是否是LL(1)的? 给出它的预测分析表。消左后的文法G1 : Sa|(T)TST T ,ST| (2) 因为G1 : 文法不含左递归; 对 Sa|(T)FIRST(a)=a, FIRST()=, FIRST( (T) )= ( , 集合互不相交且不含; 对 T,
9、ST|FIRST( ,ST )= , , FIRST()=, 其交集为空。 但FIRST(T)=FIRST( ,ST )FIRST()=，, 然而，FOLLOW(T)= ) FIRST(T)=，, ，两者 不 相交。所以，G1是LL(1)文法。 18CH.4.练习题1(P81.)(2)构造G1的预测分析表: 对Sa|(T) 对TSTFIRST(a)=a FIRST(ST)=a,(FIRST()= 对 T,ST|FIRST(T)=( FIRST(,ST)=, 预测分析表: FOLLOW(T)=) a ( ) , #SSaSS(T)TTSTTSTTSTTTT ,STDate19CH4.1.(3)
10、给出对符号串(a，) 的分析过程步骤 符号栈 输入串 动作, 所用产生式 .0 #S (a,)# 初始；用 S , ( 查表1 #)T( (a,)# S(T), 展开S2 #)T a,)# 匹配(；用 T , a 查表3 #)TS a,)# TST , 展开T; 用 S ,a 查表4 #)Ta a,)# S a, 展开S5 #)T ,)# 匹配a; 用T , , 查表6 #)TS, ,)# T ,ST, 展开T7 #)TS )# 匹配, ；用 S , 查表8 #)T )# S , 展开S9 #)T )# 匹配 ；用 T , )查表10 #) )# T,展 开T11 # # 匹配 )12 # #
11、 分析成功, 结束分析20CH.4.练习题3(P82.)n3.下面文法中, 哪些是LL(1)的, 说明理由。n(1) SABc A a| B b|。n解，因为 FOLLOW(S)=# 文法不含左递归; FIRST(S)=a,b,c 对 Aa|候选式的FIRST集合互不相交; FIRST(A) 但, FOLLOW(A)=b,c FIRST(A)=a, 两者不相交。 Bb|其候选式的FIRST集合互不相交; FIRST(B)但， FOLLOW(B)=c FIRST(B)=b, 两者也不相交。所以，文法是LL(1)文法。21CH.4.练习题3(P82.)n3.下面文法中, 哪些是LL(1)的, 说明理由。n(2) SAb A a|B| B b|。n解(1) 因为 FOLLOW(S)=#对 Aa|B| ; FIRST(S)=a,b FIRST(B)=b,与FIRST()=相交; 所以文法不是LL(1)文法。n 解(2) 对 Aa|因为FIRST(A)= a,b, ，FOLLOW(A)=b, FOLLOW和FIRST两者相交。所以文法不是LL(1)文法。22CH.4.练习题3(P82.)n3.下面文法中, 哪些是LL(1)的, 说明理由。n(3) SABBA A a| B b|。n解，虽然
