《编译原理考试习题与答案》由会员分享，可在线阅读，更多相关《编译原理考试习题与答案（64页珍藏版）》请在金锄头文库上搜索。
1、程 序 设 计 语 言,Chapter 3.词法分析,编译原理参考答案,2018/12/2,CH.3.练习题8(P64.),8. 给出下面的正规表达式。 (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),2018/12/2,CH.3.练习题7(P64.),7. (1) 1(0|1)*101 构造DFA。 解1: 正规式对应的NFA:,(1) 正规式 1(0|1)*101,DFA:,(1
2、) 正规式 1(0|1)*101,DFA:,2018/12/2,CH.3.练习题7(P64.),7. 构造下列正规式相应的DFA。 (1) 1(0|1)*101 解2: 正规式对应的NFA:,0,4,1,2,3,1,1,0,1,1,0,DFA:,2018/12/2,7. 构造下列正规式相应的NFA。(P64.) (2) 1(1010*|1 (010)*1)*0,2018/12/2,7. 构造下列正规式相应的NFA。(P64.) (2) 1(1010*|1 (010)*1)*0,7. (2) 1(1010*|1 (010)*1)*0的NFA。,2018/12/2,CH.3.练习题14(P64.)
3、,(1) 正规式: (10|0)* (2) NFA: 确定化:,DFA:,2018/12/2,CH.3.练习题14(P64.),(1) 正规式: (10|0)* (2) NFA:,DFA:,构造一个DFA，它接受 S0,1上所有满足如下条件的字符串：每个1都有0直接跟在右边。,DFA:(最简),程 序 设 计 语 言,Chapter 2.高级语言及其语法描述,编译原理参考答案,CH.2.练习题6(P36.),6.令文法G6为: N D|ND D 0|1|2|3|4|5|6|7|8|9 (1) G6的语言L(G6)是什么? 注意：集合的写法不正确 解：L(G6)=0,1,2,3,4,5,6,7,
4、8,9+ =09数字构成的所有数字串，可以0开头 (2) 给出句子0127、34和568的最左和最右推导。 注意：1)步骤，和 的区别；2) 不能写为 解：0127的最左推导：NNDNDDNDDDDDDD 0DDD01DD012D0127 0127的最右推导：NNDN7ND7N27ND27 N127D1270127,+,CH.2.练习题8(P36.),8. 令文法为 E T|E+T|E-T T F|T*F|T/F F (E)|i,(1) 给出 i+i*i、i*(i+i)的最左推导和最右推导。,解：此处仅以 i*(i+i) 为例给出答案,最左推导 E T T*F F*F i*F i*(E) i*
5、(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),CH.2.练习题8(P36.),8. 令文法为 E T|E+T|E-T T F|T*F|T/F F (E)|i,i-i-i 的语法树,(2) 给出 i+i+i、i+i*i和i-i-i的语法树。,i+i+i 的语法树,i+i*i 的语法树,注意：树枝和符号均不可随意增减！,2018/12/2,CH.2.练习题9(P36.),9. 证明下面的
6、文法是二义的： S iSeS|iS|i 证明: 因为存在句子 iiiei，它对应两棵不同的语法树,如右图: 所以该文法是二义文法。 说明：按定义只要能给出一个反例即可，iiiei不是唯一的反例。,编译原理参考答案,程 序 设 计 语 言,Chapter 5.自下而上语法分析,2018/12/2,CH.5.练习题1(P133.),1.令文法G1为：EE+T|T TT*F|F F(E)|i 证明E+T*F是它的一个句型,指出这个句型的所有短语、直接短语和句柄。,证明1: 存在从开始符号E出发到E+T*F的推导： E E+T E+T*F E+T*F是G1的一个句型。 短语: E+T*F是句型相对于非
7、终结符E的短语; T*F是句型相对于非终结符T的短语。 直接短语: T*F是句型相对于规则TT*F的直接短语 句柄: T*F,2018/12/2,CH.5.练习题1(P133.),1.令文法G1为：EE+T|T TT*F|F F(E)|i 证明E+T*F是它的一个句型,指出这个句型的所有短语、直接短语和句柄。,证明2: 可构造出E+T*F的语法树，如右图所示， E+T*F是G1的一个句型。 证明3: (也可用归约来证明) （概念熟悉后，短语、直接短语和句柄可直接列出而不用说明） 短语: E+T*F，T*F 直接短语: T*F 句柄: T*F,2018/12/2,CH.5.练习题2(P133.)
8、,2.考虑下面的表格结构文法G2： Sa|(T) TT,S|S (1)给出(a,(a,a)的最左和最右推导。,(1) 解: (a,(a,a)的 最左推导： S (T) (T,S)(S,S) (a,S) (a,(T) (a,(T,S) (a,(S,S) (a,(a,S)(a,(a,a) 最右推导： S (T) (T,S)(T,(T) (T,(T,S) (T,(T,a)(T,(S,a)(T,(a,a) (S,(a,a)(a,(a,a),2018/12/2,CH.5.练习题2(P133.),2.(2)指出(a,(a,a)的规范归约及每一步的句柄。根据这个规范归约，给出“移进-归约”的过程，并给出它的
9、语法树自下而上的构造过程。,2018/12/2,CH.5.练习题2(P133.),2.(2).给出(a,(a,a)“移进-归约”的过程。,(2) 解: (a,(a,a)的“移进-归约”过程: 步骤 符号栈 输入串 动作 句柄 1 # ( a ,(a,a)# a 2 #( a ,(a,a)# 移进 ( 3 #( a ,(a,a)# 移进 a 4 #( S ,(a,a)# 归约 S a S 5 #( T ,( a ,a)# 归约 T S a 6 #( T , ( a ,a)# 移进 , 7 #(T,( a ,a)# 移进 ( 8 #(T,( a ,a)# 移进 a,2018/12/2,CH.5.练
10、习题2(P133.),2.(2).给出(a,(a,a)“移进-归约”的过程。,(2) 解: (a,(a,a)的“移进-归约”过程: 步骤 符号栈 输入串 动作 句柄 9 #(T,( S ,a)# 归约 S a S 10 #(T,(T , a )# 归约 T S a 11 #(T,(T, a )# 移进 , 12 #(T,(T, a )# 移进 a 13 #(T,( T,S )# 归约 S a T,S 14 #(T, (T ) )# 归约 T T,S (T) 15 #(T, (T) )# 移进 ) 16 #( T, S )# 归约 S (T) T,S,2018/12/2,CH.5.练习题2(P1
11、33.),2.(2).给出(a,(a,a)“移进-归约”的过程。,(2) 解: (a,(a,a)的“移进-归约”过程: 步骤 符号栈 输入串 动作 句柄 17 # (T ) # 归约 T T,S (T) 18 # (T) # 移进 ) 19 # S # 归约 S (T) 20 成功,分析结束,接受输入串,2018/12/2,CH.5.练习题2(P133.),2.(2).给出(a,(a,a)的语法树自下而上构造过程。,(2) 解: (a,(a,a)的语法树自下而上构造过程: 用序号表示,2018/12/2,CH.5.练习题3(P133.),3.(1) 计算练习2文法G2的FIRSTVT和LAST
12、VT。 Sa|(T) TT,S|S,(1) 解: （执行相应的算法可求得） FIRSTVT(S)= a, , ( FIRSTVT(T)= , a, , ( LASTVT(S)= a, , ) LASTVT(T)= , , a, , ) ,2018/12/2,CH.5.练习题3(P133.),3.(2)计算文法G2的优先关系,G2是一个算符优先文法吗? Sa|(T) TT,S|S,(2) 解: FIRSTVT(S)= a, , ( FIRSTVT(T)= , , a, , ( LASTVT(S)= a, , ) LASTVT(T)= , , a, , ) 逐一考察 S(T) 和 TT, S 两两
13、相邻的符号，得到算符优先关系, 如右图； G2是算符优先文法 。,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,2018/12/2,3.(4)给出输入串(a,(a,a)的算符优先分析过程。,Sa|(T) TT,S|S,最左素短语,2018/12/2,.,.,.,.,.,.,.,.,.,.,.,.,.,3.(4)给出输入串(a,(a,a)的算符优先分析过程。,Sa|(T) TT,S|S,最左素短语,2018/12/2,5.(1) 考虑文法 SAS|b ASA|a 列出这个文法的所有LR(0)项目。,CH.5.练习题5(P134.),解(1): 拓广文
14、法，加入 SS 拓广文法的LR(0)项目有: S.S SS. S.AS SA.S SAS. S.b Sb. A.SA AS.A ASA. A.a Aa.,2018/12/2,5.(2) 构造文法 SAS|b ASA|a 的LR(0)项目集规范族及识别活前缀的DFA。,1）拓广文法，加入 SS,2）画出 DFA,5.(2) 构造文法 SAS|b ASA|a 的LR(0)项目集规范族及识别活前缀的DFA。,0: S.S S.AS S.b A.SA A.a,5: ASA. SA.S S.AS S.b A.SA A.a,7: SAS. AS.A A.SA A.a S.AS S.b,1: SS. AS.A A.SA A.a S.AS S
