编译原理复习资料

编译原理学习与作业制作人：李明新共30页第1页20-1-23第一章引论一、填空问题①由于计算机只能认识机器语言，所以需要翻译程序将高级语言翻译成计算机可以识别的机器语言。②编译程序的工作过程一般主要划分为词法分析，语法分析，中间代码生成，代码优化，目标代码生成等几个基本阶段，同时还会伴有表格处理和出错处理。③如果编译程序生成的目标程序是机器代码程序，则源程序的执行分为两个阶段：编译阶段和运行阶段。如果编译程序生成的目标程序是汇编语言的程序，则源程序的执行分为三个阶段：编译阶段，汇编阶段和运行阶段。二、判断问题①高级语言程序必须经过编译程序的翻译才被计算机识别和执行。（错）答：对高级语言的翻译，还有解释程序。②编译程序的输入是高级语言，输出是机器语言程序。（错）答：输出还有汇编语言程序。③具有优化功能的编译程序的工作效率高。（错）答：优化是编译程序的的一部分，优化的目的，是提高目标程序的质量和运行效率。④有的编译程序可以没有目标代码生成部分。（错）答：编译程序必须生成目标代码，所以目标代码生成部分是不可缺少的。第二章高级语言及其语法描述一、判断题1、正规文法一定不是二义性的。（错）答：文法的二义性问题是不可避免和不可判定的，正规文法也可能存在二义性的问题。2、文法的二义性和语言的二义性是两个不同的概念。（对）答：可能有两个不同的文法G和G`，其中G是二义性的，但是却有L（G）=L（G`）。3、一个句型对应的一棵语法树，包括了该句型的所有推导。（错）答：一棵语法树，只能对应一个推导，所以不能包括该句型的所有推导。二、选择题1、文法G所描述的语言是D的集合。A、文法G的字汇表V中所有符号组成的符号串B、文法G的字汇表V的闭包V*中的所有符号串C、由文法的开始符号推出的所有符号串D、由文法的开始符号推出的所有终结符号串三、解答题1、设文法G编译原理学习与作业制作人：李明新共30页第2页20-1-23ETE+TE-TTFT*FT/FF（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）EAEA+-*/该文法是二义性文法，因为该文法给定的句子i+i+i，存在两棵不同的语法树。EEEAEEAEEAE+ii+EAEi+ii+i8、把下面的文法改写为无二义性的文法：SSS（S）（）该文法产生二义性文法的原因就在于产生式SSS中左部符号在右部连续出现两次，使得对S既可以采用左递归得到（）（）（）又可以采用右递归得到（）（）（），为此改写文法为：SAS（S）（）A（S）（）第三章词法分析一、填空题1、编译过程中扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位—单词。2、高级程序设计语言的单词通常分为五类，它们是关键字、标识符、常数、运算符以及界限符。3、确定的有限自动机是一个五元组，通常表示为DFAM=（S，，，S0，F）。4、词法分析的任务是输入源程序，输出单词符号。5、确定有限自动机DFA是NFA的一种特例。6、若二个正规式所表示的正规集相同，则认为二者是等价的。二、判断题1、一些语言，它们能被确定的有限自动机识别，但不能用正规表达式表示。（错）答：用正规式表示的语言，都能被确定的有限自动机识别。编译原理学习与作业制作人：李明新共30页第3页20-1-232、每一个NFAM都对应有唯一的一个最小化的DFAM。（对）答：每一个NFAM都可以构造一个DFAM，而DFAM又可以构造一个最小化的DFAM。3、一个有限自动机，仅有一个唯一的终态。（错）答：有限自动机的终态可以有多个。4、确定的有限自动机以及不确定的有限自动机都能正确识别正规集。（对）答：一个有限自动机能识别该正规式，所描述的语言（正规集）。5、对任意一个正规文法G，都存在一个DFAM，满足L（G）=L（M）。（对）答：对每一个正规文法G，都存在一个DFAM，使得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）*bd、（ba）+be、b（ba）*3、词法分析所依据的是b。a、语义规则b、词法规则c、语法规则d、等价变换规则4、正规式V1和V2等价是指c。a、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}，，x，{y}）为一个非确定有限自动机，其中定义如下：（x，a）={x，y}（x，b）={y}（y，a）=（y，b）={x，y}试构造相应的确定的有限自动机(DFAM`).解：⑴根据函数值，先构造NFAMabbab⑵用子集法构造DFAM的转换矩阵表IIaIb{x}0{x，y}2{y}1{y}1{x，y}2{x，y}2{x，y}2{x，y}2⑶确定DFAM`的初态和终态①含有x状态子集为DFAM`的初态结点，所以{x}=0初态结点。YX编译原理学习与作业制作人：李明新共30页第4页20-1-23②含有y状态子集为DFAM`的终态结点，所以{y}=1，{x，y}=2为终态结点（因为DFAM`只含有唯一的初态）。⑷构造DFAM`abba,b⑸DFAM`的最小化将DFAM`划分成终态集{1，2}和非终态集{0}，采用后继状态等价性的依赖关系，构造DFAM`的最小化。因为结点1和结点2输入的字符不同，结点1，2是可分割的，所以确定的有限自动机（DFAM`）不需要化简。2、构造下列正规式相应的DFAM最小化（10）*（1100）*⑴构造NFAM111000⑵用子集法构造DFAM的转换矩阵表⑶确定DFAM`的初态和终态①含有s，z状态子集为DFAM`的初态和终态，即为S。②含有z状态子集为DFAM`的终态结点，即为A，B。⑷构造DFAM`001011⑸将DFAM`最小化将DFAM`划分成终态集和非终态集因为DFAM`只有终态集，即{S，A，B}。采用后继状态等价性的依赖关系，构造DFAM`的最小化。又因为输入0均到达A，输入1均到达B，所以S，A，B等价，化简后的DFAM`。0，1012SABCZEDII0I1{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}BB1A2SS编译原理学习与作业制作人：李明新共30页第5页20-1-23第四章语法分析—自上而下分析一、填空题1、自上而下语法分析方法的基本思想是：从文法的开始符号出发。不断建立直接推导，试图构造一个推导序列，最终由它推导出与输入符号串相同的符号串。2、自上而下语法分析方法会遇到的主要问题有回溯和左递归。3、在自上而下语法分析中，应先消除文法的间接左递归，再消除文法的直接左递归。4、在语法分析中，最常见的两种方法是自上而下分析法，另一种是自下而上分析法。二、选择题1、高级语言编译程序常用的语法分析方法中，递归下降分析法属于B分析方法。A、自左至右B、自上而下C、自下而上D、自右至左三、解答题1、已知文法G：AaAa⑴该文法是LL（1）文法吗？为什么？⑵若采用LL（1）方法进行分析，如何得到该文法的LL（1）分析表。⑶若输入串“aaaa”，请给出语法分析过程。解：⑴因为FOLLOW（A）FIRST（a）={a，#}造成FOLLOW（A）FIRST（A）={a，#}{a，}所以该文法不是LL（1）文法。⑵若采用ll（1）方法进行语法分析，必须修改该文法。因该文法产生偶数（可以为0）个a，所以得到文法G`：AaaA。此时FOLLOW（A）={#}，因此FOLLOW（A）FIRST（A）={#}{a，}=所以文法G`是LL（1）文法，该文法的ll（1）分析表：⑶对符号串“aaaa”的分析过程：步骤分析栈输入串产生式/动作1#Aaaaa#AaaA2#Aaaaaaa#匹配3#Aaaaa#匹配4#Aaa#AaaA5#Aaaaa#匹配6#Aaa#匹配7#A#A8##接受VTVNa#AAaaAA编译原理学习与作业制作人：李明新共30页第6页20-1-232、设文法G：SSbAaABScABc⑴将此文法改写为LL（1）文法。⑵求文法的每一个非终结符号的FIRST集合和FOLLOW集合。⑶构造相应的LL（1）分析表。解：⑴改写文法为LL（1）文法SaAS`S`bAS`BScABc⑵构造文法每一个非终结符号FIRST和FOLLOW的集合。a、构造文法每一个非终结符号FIRST的集合FIRST（S）={a}FIRST（S`）={b，}FIRST（B）={a}FIRST（A）={a}b、构造文法每一个非终结符号FOLLOW的集合因为SaAS`和BSc，所以FOLLOW（S）={#}FIRST（c）={#，c}因为SaAS`，所以FOLLOW（S`）=FOLLOW（S）={#，c}因为SaAS`，所以FOLLOW（A）=FOLLOW（A）FIRST(S`)\{}={b}又因为S`*=,并且FOLLOW（S）=FOLLOW（S`），最终结果FOLLOW（A）=FOLLOW（A）FOLLOW(S`)={#，c,b}。因为ABc，所以FOLLOW(B)=FOLLOW（B）FIRST（c）={c}⑶判定该文法是否是LL（1）文法因为文法中只含有一个多后选式的定义式S`bAS`，只需证明：FIRST（S`）Follow（S`）={b，}{#，c,}=，该文法是LL（1）文法。⑷构造相应的LL（1）分析表因为FIRST（S）={a}，所以M[S，a]=SaAS`；因为FIRST（S`）={b，}，所以M[S`，b]=S`bAS`，又因为FIRST（S`），则对{b，#}FOLLOW（S`），使得M[S`，b]=S`，M[S`，#]=S`；因为FIRST（B）={a}，所以M[B，a]=BSc；因为FIRST（A）={a}，所以M[A，a]=ABc。abc#SSaAS`S`S`bAS`S`S`AABcBBSc编译原理学习与作业制作人：李明新共30页第7页20-1-23第五章语法分析—自下而上分析一、填空题⑴对于一文法，如果能够构造一张分析表，使得它的每一个入口均是唯一确定的，则称该文法为LR文法。⑵自下而上语法分析法的基本思想是：从待输入的符号串开始，利用文法的产生式步步向上进行直接归约，试图归约到文法的开始符号（识别符号）。⑶字的活前缀是指该字的任意首部。⑷活前缀是指规范句型的一个前缀，这种前缀不含句柄之后的任何句型。二、选择题⑴若a为终结符，则A•a为B项目。A、归约B、移进C、接受D、待约⑵一个LR分析器包括A、D。A、一个总控程序B、一个项目集C、一个活前缀D、一张分析表E、一个分析栈⑶对LR分析表的构造，有可能存在C、