编译原理考试习题及答案.ppt

《编译原理考试习题及答案.ppt》由会员分享，可在线阅读，更多相关《编译原理考试习题及答案.ppt（65页珍藏版）》请在优知文库上搜索。

1、程程 序序 设设 计计 语语 言言 Chapter 3.Chapter 3.词法分析词法分析22023-4-13CH.3.CH.3.练习题练习题8(8(P64.)P64.)n8.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)32023-4-13CH.3.CH

2、.3.练习题练习题7(7(P64.)P64.)n7.7. (1) 1(0|1)*101 构造构造DFADFA。解解1: 正规式对应的正规式对应的NFA:XY34511011210 I I0 I1X 1,3,2 1,3,2 3,2 3,4,2 3,2 3,2 3,4,2 3,4,2 3,5,2 3,4,2 3,5,2 3,2 3,Y,4,23,Y,4,23,5,2 3,4,2 I I0 I1初初0 1 1 2 3 2 2 3 3 4 3 4 2 5终终5 4 3 (1) 正规式正规式 1(0|1)*101DFA:x3,Y,4,23,4,23,5,211011,3,23,20100101 I I0

3、 I1X 1,3,2 1,3,2 3,2 3,4,2 3,2 3,2 3,4,2 3,4,2 3,5,2 3,4,2 3,5,2 3,2 3,Y,4,23,Y,4,23,5,2 3,4,2 I I0 I1初初0 1 1 2 3 2 2 3 3 4 3 4 2 5终终5 4 3 (1) 正规式正规式 1(0|1)*101DFA: I I0 I1X 1,3,2 1,3,2 3,2 3,4,2 3,2 3,2 3,4,2 3,4,2 3,5,2 3,4,2 3,5,2 3,2 3,Y,4,23,Y,4,23,5,2 3,4,2 I I0 I1初初0 1 1 2 3 2 2 3 3 4 3 4 2 5

4、终终5 4 30534110112010010162023-4-13CH.3.CH.3.练习题练习题7(7(P64.)P64.)n7.7. 构造下列正规式相应的构造下列正规式相应的DFADFA。 (1) 1(0|1)*101 解解2: 正规式对应的正规式对应的NFA:04123110110 I I0 I10 初初01 11 11 11,2 21,2 21,3 31,2 21,3 31 11,2,4 41,2,4终终4 1,3 31,2 210423110110010DFA:72023-4-13n7.7. 构造下列正规式相应的构造下列正规式相应的NFANFA。( (P64.)P64.) (2)

5、1(1010*|1 (010)*1)*0XY201131010*1 (010)*1XY201136451100*7811(010)*82023-4-13n7.7. 构造下列正规式相应的构造下列正规式相应的NFANFA。( (P64.)P64.) (2) 1(1010*|1 (010)*1)*0XY201136451100*7811(010)*XY2011364511007811910010XY2011364511007811910010XY201136451100781191001211017.7. (2) 1(1010*|1 (010)*1)*0的的NFANFA。102023-4-13CH.

6、3.CH.3.练习题练习题14(14(P64.)P64.)n(1) 正规式正规式: (10|0)* (2) NFA: 确定化确定化:YX1001201001012 I I0 I1X,1,Y 1,Y2 1,Y1,Y2 21,Y I I0 I1初终初终0 1 2 终终 1 1 2 2 1 DFA:112023-4-13CH.3.CH.3.练习题练习题14(14(P64.)P64.)n(1) 正规式正规式: (10|0)* (2) NFA:YX1001201001012DFA:构造一个构造一个DFA，它接受，它接受 S0,1上所有满足如下条件上所有满足如下条件的字符串：每个的字符串：每个1都有都有0

7、直直接跟在右边。接跟在右边。10010DFA:(最简最简)程程 序序 设设 计计 语语 言言 Chapter 2.Chapter 2.高级语言及高级语言及其语法描述其语法描述13CH.2.CH.2.练习题练习题6(6(P36.)P36.)n6.6.令文法令文法G6G6为为: : N D|ND D 0|1|2|3|4|5|6|7|8|9N D|ND D 0|1|2|3|4|5|6|7|8|9n(1) (1) G6G6的语言的语言L(G6)L(G6)是什么是什么? ?n注意注意：集合的写法不正确：集合的写法不正确n解：解：L(G6)=0,1,2,3,4,5,6,7,8,9L(G6)=0,1,2,3

8、,4,5,6,7,8,9+ + =0=0 9 9数字构成的所有数字串，可以数字构成的所有数字串，可以0 0开头开头 n(2) (2) 给出句子给出句子01270127、3434和和568568的最左和最右推导。的最左和最右推导。n注意注意：1)1)步骤，步骤，和和 的区别的区别；2) 2) 不能写为不能写为n解：解：01270127的最左推导：的最左推导：N NNDNDNDDNDDNDDDNDDDDDDDDDDD 0DDD0DDD0101DDDD012012D D01270127 0127 0127的最右推导：的最右推导：N NNDNDN7N7ND7ND7N27N27ND27ND27 N127

9、N127D127D12701270127+14CH.2.CH.2.练习题练习题8(8(P36.)P36.)n8.8. 令文法为令文法为 E T|E+T|E-TE T|E+T|E-T T F|T T F|T* *F|T/FF|T/F F (E)|i F (E)|i (1) 给出给出 i+i*i、i*(i+i)的最左推导的最左推导和最右推导。和最右推导。解解：此处仅以：此处仅以 i*(i+i) 为例给出答案为例给出答案最左推导最左推导E E T T T T* *F F F F* *F F i i* *F F i i* *(E) (E) i i* *(E+T)(E+T) i i* *(T+T)(T+

10、T) i i* *(F+T)(F+T) i i* *(i+T)(i+T) i i* *(i+F )(i+F ) i i* *(i+i)(i+i) 最右推导最右推导E E T T T T* *F F T T* *(E) (E) T T* *(E+T) (E+T) T T* *(E+F)(E+F) T T* *(E+i) (E+i) T T* *(T+i) (T+i) T T* *(F+i)(F+i) T T* *(i+i)(i+i) F F* *(i+i)(i+i) i i* *(i+i)(i+i) 15CH.2.CH.2.练习题练习题8(8(P36.)P36.)n8.8. 令文法为令文法为 E

11、 T|E+T|E-TE T|E+T|E-T T F|TT F|T* *F|T/FF|T/F F (E)|i F (E)|iEE - TE - TTF F iF iii-i-i i-i-i 的语法树的语法树(2) 给出给出 i+i+i、i+i*i和和i-i-i的语法树。的语法树。EE + TE + TTF F iF iii+i+i i+i+i 的语法树的语法树i+ii+i* *i i 的语法树的语法树EE + TTTF F iF ii*n注意注意：树枝和符号均不可随意增减！：树枝和符号均不可随意增减！162023-4-13CH.2.CH.2.练习题练习题9(9(P36.)P36.)n9.9. 证

12、明下面的文法是二义的：证明下面的文法是二义的： S iSeS|iS|iS iSeS|iS|in证明证明: : 因为存在句子因为存在句子 iiieiiiiei，它对应两棵不同的语法树它对应两棵不同的语法树, ,如如右图右图: : 所以该文法是二义文法。所以该文法是二义文法。n说明说明：按定义只要能给出一：按定义只要能给出一个反例即可，个反例即可，iiieiiiiei不是唯一不是唯一的反例。的反例。S i S i S e SiiiSi S e S i Si程程 序序 设设 计计 语语 言言 Chapter 5.Chapter 5.自下而上自下而上语法分析语法分析182023-4-13CH.5.CH

13、.5.练习题练习题1(1(P133.)P133.)n1.1.令文法令文法G1G1为：为：EE+T|T TTEE+T|T TT* *F|F F(E)|i F|F F(E)|i 证明证明E+TE+T* *F F是它的一个句型是它的一个句型, ,指出这个句型的所有短指出这个句型的所有短语、直接短语和句柄。语、直接短语和句柄。n证明证明1: 存在从开始符号存在从开始符号E出发到出发到E+T*F的推导：的推导： E E+T E+T*F E+T*F是是G1的一个句型。的一个句型。短语短语: E+T*F是句型相对于非终结符是句型相对于非终结符E的短的短语语; T*F是句型相对于非终结符是句型相对于非终结符T

14、的短语的短语。直接短语直接短语: T*F是句型相对于规则是句型相对于规则TT*F的的直接短语直接短语句柄句柄: T*FEE + TT * F语法树语法树192023-4-13CH.5.CH.5.练习题练习题1(1(P133.)P133.)n1.1.令文法令文法G1G1为：为：EE+T|T TTEE+T|T TT* *F|F F(E)|i F|F F(E)|i 证明证明E+TE+T* *F F是它的一个句型是它的一个句型, ,指出这个句型的所有短指出这个句型的所有短语、直接短语和句柄。语、直接短语和句柄。n证明证明2: 可构造出可构造出E+T*F的的语法树，如右语法树，如右图所示图所示， E+T

15、*F是是G1的一个句型。的一个句型。n证明证明3: (也可用归约来证明也可用归约来证明)（概念熟悉后，短语、直接短语和句柄可直接列出（概念熟悉后，短语、直接短语和句柄可直接列出而不用说明）而不用说明） 短语短语: E+T*F，T*F 直接短语直接短语: T*F 句柄句柄: T*FEE + TT * F语法树语法树202023-4-13CH.5.CH.5.练习题练习题2(2(P133.)P133.)n2.2.考虑下面的表格结构文法考虑下面的表格结构文法G2G2： Sa| Sa| |(T) TT,S|S |(T) TT,S|S (1)(1)给出给出( (a,(a,a)a,(a,a)的最左和最右推导

16、。的最左和最右推导。 n(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) 212023-4-13CH.5.CH.5.练习题练习题2(2(P133.)P133.)n2.(2)2.(2)指出指出( (a,(a,a)a,(a,a)的规范归约及每一步的句柄。的规范归约及每一步的句柄。根据这个规范归约，给出根据这个规范归约，给出“移进移进- -归约归约”的过程，并的过程，并给出它的语法树自下而上的构造过程。给出它的语法树自下而上的构造过程。n(2) 解解: (a,(a,a)的规范归约及每一步的句柄的规范归约及每一步的句柄: ( a ,(a,a) ( S ,(a,a) (T,( a ,a) (T,( S ,a) (T,(T, a ) (T,( T, S ) (T, (T) ) ( T,S ) (T) S.