编译原理（蒋立源）部分习题答案

、（1）L（G6）={0,1,2,......,9}+ （2）最左推导： N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=>0127 N=>ND=>DD=>3D=>34 N=>ND=>NDD=>DDD=>5DD=>56D=>568 最右推导： N=>ND =>N7=>ND7=>N27=>ND27=>N127=>D127=>0127 N=>ND=>N4=>D4=>34 N=>ND=>N8=>ND8=>N68=>D68=>568 7、Ｇ：S→ABC | AC | C A→1|2|3|4|5|6|7|8|9 B→BB|0|1|2|3|4|5|6|7|8|9 C→1|3|5|7|9 8、（1）最左推导： E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>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=>E+T=>E+T*F=>E+T*i=>E+F*i=>E+i*i=>T+i*i=>F+i*i=>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) (2) 9、证明：该文法存在一个句子iiiei有两棵不同语法分析树，如下所示，因此该文法是二义的。 11、 第3章 词法分析 7、构造下列正规式相应的DFA：1(0|1)*101 解： （1）构造NFA： （2）确定化： 构造状态转换矩阵如下： 重命名： I I0 I1 {X} _ {1} {1} {1} {1,2} {1,2} {1,3} {1,2} {1,3} {1} {1,2,Y} {1,2,Y} {1,3} {1,2} S 0 1 0 1 1 1 2 2 3 2 3 1 4 4 3 2 画出状态转换图： （注：已是最简） 8、（1）（0|1）*01 （2）（0|1|2|3|4|5|6|7|8|9）(1|2|3|4|5|6|7|8|9)*(0|5)|0|5 （3）（10*1|0）*10*|（01*0|1）*01* （4）a*b*c*......z* 9、（1） 正规式（0|1）*（010）（0|1）* NFA: 构造状态转换矩阵： 重命名： I I0 I1 {X} {X,0} {X} {X,0} {X,0} {X,1} {X,1} {X,0,Y} {X} {X,0,Y} {X,0,Y} {X,1,Y| {X,1,Y} {X,0,Y} {X,Y} {X,Y} {X,0,Y} {X,Y} S 0 1 0 1 0 1 1 2 2 3 0 3 3 4 4 3 5 5 3 5 画出DFA： 最少化后： 12、（a）构造状态转换矩阵： 重命名： I Ia Ib {0} {0，1} {1} {0，1} {0，1} {1} {1} {0} —— S a b 0 1 2 1 1 2 2 0 _ 重命名： 画出确定化后的有限自动机： 【编译原理】是计算机科学领域的一个重要分支，主要研究如何将高级编程语言转换为机器可执行的指令。本节内容涉及的是编译原理中的语言分析部分，包括词法分析和语法分析，以及如何处理文法的二义性。 1. **词法分析**：这一部分介绍了如何构造有限自动机（DFA）来识别正规式。例如，正规式`(0|1)*101`对应的状态转换矩阵和最简DFA的构造过程，以及正规式`(0|1)*01`、`(0|1|2|3|4|5|6|7|8|9)(1|2|3|4|5|6|7|8|9)* (0|5)|0|5`和`a*b*c*...*z*`对应的DFA构造。词法分析器的任务是识别输入字符串中的单词（token），并将其分类。 2. **语法分析**：这里提到了最左推导（Leftmost Derivation）和最右推导（Rightmost Derivation），这是上下文无关文法解析的两种常见方法。例如，文法`G`下的句子`iiiei`存在两种不同的最左推导和最右推导，表明该文法是二义的，即对于某些句子，可以生成不止一棵语法分析树，这在设计编译器时是需要避免的。 3. **文法规则与二义性**：证明文法的二义性通常涉及到展示同一个句子可以有多个不同的语法分析路径。例子中，句子`iiiei`在文法`G`下有两棵不同的语法分析树，这表明文法不是无二义的。无二义性是编译器设计中的一个重要目标，因为它能确保语句的唯一解释，从而避免程序的错误。 4. **消除左递归与LL(1)文法**：文法`S→a|^|(T)`和`T→T,S|S`展示了消除左递归的过程，这是构建LL(1)解析器的关键步骤。LL(1)文法意味着左到右扫描输入，并且一次看一个字符（L1），同时决定下一步的移动（L）；它要求每个非终结符的First集和Follow集之间不存在冲突，以避免解析歧义。 总结来说，这部分习题涵盖了编译原理中的核心概念，如词法分析的DFA构造、语法分析的最左推导和最右推导，以及文法的二义性和消除左递归，这些都是编译器设计的基础。理解和掌握这些知识点对于编写编译器或理解编译过程至关重要。