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

作业评讲 Chapter 3.词法分析 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) CH.3.练习题7(P64.) 7. (1) 1(0|1)*101 构造DFA。 解1: 正规式对应的NFA: (1) 正规式 1(0|1)*101 (1) 正规式 1(0|1)*101 CH.3.练习题7(P64.) 7. 构造下列正规式相应的DFA。 (1) 1(0|1)*101 解2: 正规式对应的NFA: 7. 构造下列正规式相应的NFA。(P64.) (2) 1(1010*|1 (010)*1)*0 7. 构造下列正规式相应的NFA。(P64.) (2) 1(1010*|1 (010)*1)*0 7. (2) 1(1010*|1 (010)*1)*0的NFA。 CH.3.练习题14(P64.) (1) 正规式: (10|0)* (2) NFA: 确定化: CH.3.练习题14(P64.) (1) 正规式: (10|0)* (2) NFA: 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,8,9}+ ={0?9数字构成的所有数字串，可以0开头} (2) 给出句子0127、34和568的最左和最右推导。 注意：1)步骤，?和 ?的区别；2) ?不能写为→ 解：0127的最左推导：N?ND?NDD?NDDD?DDDD ?0DDD?01DD?012D?0127 0127的最右推导：N?ND?N7?ND7?N27?ND27 ?N127?D127?0127 CH.2.练习题8(P36.) 8. 令文法为 E → T|E+T|E-T T → F|T*F|T/F F → (E)|i CH.2.练习题8(P36.) 8. 令文法为 E → T|E+T|E-T T → F|T*F|T/F F → (E)|i CH.2.练习题9(P36.) 9. 证明下面的文法是二义的： S → iSeS|iS|i 证明: 因为存在句子 iiiei，它对应两棵不同的语法树,如右图: 所以该文法是二义文法。 说明：按定义只要能给出一个反例即可，iiiei不是唯一的反例。 Chapter 5.自下而上语法分析 CH.5.练习题1(P133.) 1.令文法G1为：E→E+T|T T→T*F|F F→(E)|i 证明E+T*F是它的一个句型,指出这个句型的所有短语、直接短语和句柄。 CH.5.练习题1(P133.) 1.令文法G1为：E→E+T|T T→T*F|F F→(E)|i 证明E+T*F是它的一个句型,指出这个句型的所有短语、直接短语和句柄。 CH.5.练习题2(P133.) 2.考虑下面的表格结构文法G2： S→a|?|(T) T→T,S|S (1)给出(a,(a,a))的最左和最右推导。 CH.5.练习题2(P133.) 2.(2)指出(a,(a,a))的规范归约及每一步的句柄。根据这个规范归约，给出“移进-归约”的过程，并给出它的语法树自下而上的构造过程。 CH.5.练习题2(P133.) 2.(2).给出(a,(a,a))“移进-归约”的过程。 CH.5.练习题2(P133.) 2.(2).给出(a,(a,a))“移进-归约”的过程。 CH.5.练习题2(P133.) 2.(2).给出(a,(a,a))“移进-归约”的过程。 CH.5.练习题2(P133.) 2.(2).给出(a,(a,a))的语法树自下而上构造过程。 CH.5.练习题3(P133.) 3.(1) 计算练习2文法G2的FIRSTVT和LASTVT。 S→a|?|(T) T→T,S|S CH.5.练习题3(P133.) 3.(2)计算文法G2的优先关系,G2是一个算