编译原理复习资料习题.doc

编译原理 学习与作业第一章 引论一、填空问题 ①由于计算机只能认识机器语言，所以需要翻译程序将高级语言翻译成计算机可以识别的机器语言②编译程序的工作过程一般主要划分为词法分析，语法分析，中间代码生成，代码优化，目标代码生成等几个基本阶段，同时还会伴有表格处理和出错处理③如果编译程序生成的目标程序是机器代码程序，则源程序的执行分为两个阶段：编译阶段和运行阶段如果编译程序生成的目标程序是汇编语言的程序，则源程序的执行分为三个阶段：编译阶段，汇编阶段和运行阶段二、判断问题①高级语言程序必须经过编译程序的翻译才被计算机识别和执行 错 ）答：对高级语言的翻译，还有解释程序②编译程序的输入是高级语言，输出是机器语言程序错）答：输出还有汇编语言程序③具有优化功能的编译程序的工作效率高错）答：优化是编译程序的的一部分，优化的目的，是提高目标程序的质量和运行效率④有的编译程序可以没有目标代码生成部分错）答：编译程序必须生成目标代码，所以目标代码生成部分是不可缺少的。

第二章 高级语言及其语法描述一、判断题 1、正规文法一定不是二义性的错）答：文法的二义性问题是不可避免和不可判定的，正规文法也可能存在二义性的问题 2、文法的二义性和语言的二义性是两个不同的概念对） 答：可能有两个不同的文法G和G`，其中G是二义性的，但是却有L（G）= L（G`） 3、一个句型对应的一棵语法树，包括了该句型的所有推导错）答：一棵语法树，只能对应一个推导，所以不能包括该句型的所有推导二、选择题 1、文法G所描述的语言是 D 的集合A、文法G的字汇表V中所有符号组成的符号串 B、文法G的字汇表V的闭包V*中的所有符号串C、由文法的开始符号推出的所有符号串D、由文法的开始符号推出的所有终结符号串三、解答题 1、设文法G E®T½E+T½E-T T®F½T*F½T/F F®（E）½I⑴试给出关于（i）与（i+i）/i的推导E Þ T Þ F Þ（E）Þ（T）Þ（F）Þ（i）EÞTÞT/FÞF/FÞ（E）/FÞ（E+T）/FÞ（T+T）/FÞ（F+T）/FÞ（i+T）/FÞ（i+F）/FÞ（i+i）/FÞ（i+i）/i⑵证明E+T*F*i+i是该文法的句型。

EÞE+TÞE+T+TÞE+T*F+TÞE+T*F*F+TÞE+T*F*F+FÞE+T*F*F+iÞE+T*F*i+i因为存在上述推导序列，所以E+T*F*i+i是该文法的句型2、试判断下述文法是否具有二义性： E®i½（E）½EAE A®+½-½*½/该文法是二义性文法，因为该文法给定的句子i+i+i，存在两棵不同的语法树E E E A E E A E E A E + i i + E A E i + i i + i8、把下面的文法改写为无二义性的文法： S®SS½（S）½（） 该文法产生二义性文法的原因就在于产生式S®SS中左部符号在右部连续出现两次，使得对S既可以采用左递归得到（）（）（）又可以采用右递归得到（）（）（），为此改写文法为：S®AS½（S）½（）A®（S）½（） 第三章 词法分析一、填空题1、编译过程中扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位—单词。

2、高级程序设计语言的单词通常分为五类，它们是关键字、标识符、常数、运算符以及界限符3、确定的有限自动机是一个五元组，通常表示为DFA M=（S，S，d，S0，F）4、词法分析的任务是输入源程序，输出单词符号5、确定有限自动机DFA是NFA的一种特例6、若二个正规式所表示的正规集相同，则认为二者是等价的二、判断题1、一些语言，它们能被确定的有限自动机识别，但不能用正规表达式表示 错 ）答：用正规式表示的语言，都能被确定的有限自动机识别2、每一个NFA M都对应有唯一的一个最小化的DFA M 对 ）答：每一个NFA M都可以构造一个DFA M，而DFA M又可以构造一个最小化的DFA M3、一个有限自动机，仅有一个唯一的终态错）答：有限自动机的终态可以有多个4、确定的有限自动机以及不确定的有限自动机都能正确识别正规集对）答：一个有限自动机能识别该正规式，所描述的语言（正规集）5、对任意一个正规文法G，都存在一个DFA M，满足L（G）=L（M）对）答：对每一个正规文法G，都存在一个DFA M，使得L（G）=L（M）三、选择题1、在词法分析中能识别出a，c，e a、关键字 b、四元式 c、运算符 d、逆波兰式 e、常数2、令å={a，b}，则å上所有以b开头，后跟若干个ab的字的全体对应的正规式b，d。

a、b（ab）* b、b（ab）+ c、（ba）*b d、（ba）+b e、b（ba）*3、词法分析所依据的是b a、语义规则 b、词法规则 c、语法规则 d、等价变换规则 4、正规式V1和V2等价是指ca、V1和V2的状态数相等 b、V1和V2的有向弧条数相等c、V1和V2所识别的语言集相等 d、V1和V2状态数和有向弧条数相等5、令å={a，b}，正规式a½b½c代表的正规集b a、{ａ}　　　b、｛ａ，ｂ，ｃ｝ c、｛ａｂｃ｝　　 d、｛ｂ，ｃ｝三、简答题 1、什么是扫描器？扫描器的功能是什么？ 扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析使用四、基本题1、设M=（{x，y}，{a，b}，d，x，{y}）为一个非确定有限自动机，其中d定义如下：d（x，a）={x，y} d（x，b）={y}d（y，a）=f d（y，b）={x，y}试构造相应的确定的有限自动机(DFA M`).解：⑴根据d函数值，先构造NFA M aYX b b a b⑵用子集法构造DFA M的转换矩阵表 I Ia Ib {x} 0 {x，y} 2 {y} 1 {y} 1 {x，y} 2 {x，y} 2 {x，y} 2 {x，y} 2 ⑶确定DFA M`的初态和终态①含有x状态子集为DFA M`的初态结点，所以{x}=0初态结点。

②含有y状态子集为DFA M`的终态结点，所以{y}=1，{x，y}=2为终态结点（因为DFA M`只含有唯一的初态）⑷构造DFA M`20 a1 b b a,b⑸DFA M`的最小化将DFA M`划分成终态集{1，2}和非终态集{0}，采用后继状态等价性的依赖关系，构造DFA M`的最小化因为结点1和结点2输入的字符不同，结点1，2是可分割的，所以确定的有限自动机（DFA M`）不需要化简2、构造下列正规式相应的DFA M最小化 （1½0）*（11½00）*D⑴构造NFA M 1 1 1CZSAB e e e eE 0 0 0⑵用子集法构造DFA M的转换矩阵表I I0 I1{S，A，B，C，Z} S {A，B，C，E，Z} A {A，B，C，D，Z} B{A，B，C，E，Z} A {A，B，C，E，Z} A {A，B，C，D，Z} B{A，B，C，D，Z} B {A，B，C，E，Z} A {A，B，C，D，Z} B ⑶确定DFA M`的初态和终态①含有s，z状态子集为DFA M`的初态和终态，即为S。

②含有z状态子集为DFA M`的终态结点，即为A，B⑷构造DFA M`A2 0 0S 1 0B1 1 1⑸将DFA M`最小化将DFA M`划分成终态集和非终态集因为DFA M`只有终态集，即{S，A，B}采用后继状态等价性的依赖关系，构造DFA M`的最小化又因为输入0均到达A，输入1均到达B，所以S，A，B等价，化简后的DFA M`S 0，1第四章 语法分析—自上而下分析一、填空题1、自上而下语法分析方法的基本思想是：从文法的开始符号出发不断建立直接推导，试图构造一个推导序列，最终由它推导出与输入符号串相同的符号串2、自上而下语法分析方法会遇到的主要问题有回溯和左递归3、在自上而下语法分析中，应先消除文法的间接左递归，再消除文法的直接左递归4、在语法分析中，最常见的两种方法是自上而下分析法，另一种是自下而上分析法二、选择题1、高级语言编译程序常用的语法分析方法中，递归下降分析法属于B分析方法A、自左至右 B、自上而下 C、自下而上 D、自右至左三、解答题 1、已知文法G： A®aAa½e⑴该文法是LL（1）文法吗？为什么？⑵若采用LL（1）方法进行分析，如何得到该文法的LL（1）分析表。

⑶若输入串“aaaa”，请给出语法分析过程解：⑴因为FOLLOW（A）ÈFIRST（a）={a，#} 造成FOLLOW（A）ÇFIRST（A）={a，#}Ç{a，e}¹f 所以该文法不是LL（1）文法⑵若采用ll（1）方法进行语法分析，必须修改该文法因该文法产生偶数（可以为0）个a，所以得到文法G`：A®aaA½e此时 FOLLOW（A）={#}，因此FOLLOW（A）ÇFIRST（A）={#}Ç{a，e}=f所以文法G`是LL（1）文法，该文法的ll（1）分析表：VTVN a # A A®aaA A®e 。