编译原理_练习参考概要.ppt

作业评讲 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 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. 构造下列正规式相应的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 CH.3.练习题14(P64.) (1) 正规式: (10|0)* (2) NFA: 确定化: CH.3.练习题14(P64.) (1) 正规式: (10|0)* (2) NFA: Chapter 4. 自上而下语法分析 CH.4.练习题1(P81.) 1.考虑下面文法G1: S→a|^|(T) T→T，S|S (1) 消去G1的左递归。然后对每个非终结符,写出不带回溯的递归子程序。 CH.4.练习题1(P81.) CH.4.练习题1(P81.) CH.4.练习题1(P81.) CH.4.练习题1(P81.) CH4.1.(3) 给出对符号串(a，^) 的分析过程 CH.4.练习题3(P82.) 3.下面文法中, 哪些是LL(1)的, 说明理由。 (1) S→ABc A→ a|ε B→ b|ε。 CH.4.练习题3(P82.) 3.下面文法中, 哪些是LL(1)的, 说明理由。 (2) S→Ab A→ a|B|ε B→ b|ε。 CH.4.练习题3(P82.) 3.下面文法中, 哪些是LL(1)的, 说明理由。 (3) S→ABBA A→ a|ε B→ b|ε。 CH.4.练习题3(P82.) 3.下面文法中, 哪些是LL(1)的, 说明理由。 (4) S→aSe|B B→bBe|C C→cCe|d。 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 (