编译原理复习资料习题

编译原理 学习与作业 第一章 引论 一、填空问 ①由于计算机只能认识机器语言，所以需要翻译程序将高级语言翻译成计算机可以识 别的机器语言。 ②编译程序的工作过程一般主要划分为词法，语法分析，中间代码生成，代码优化，目标代码生成等几个基本阶段，同时还会伴有表格处理和出错处理。 ③如果编译程序生成的目标程序是机器代码程序，则源程序的执行分为两个阶段：编译阶段和运行阶段。如果编译程序生成的目标程序是汇编语言的程序，则源程序的执行分为三个阶段：编译阶段，汇编阶段和运行阶段。 二、判断问题 ①高级语言程序必须经过编译程序的翻译才被计算机识别和执行。（ 错 ） 答：对高级语言的翻译，还有解释程序。 ②编译程序的输入是高级语言，输出是机器语言程序。（错） 答：输出还有汇编语言程序。 ③具有优化功能的编译程序的工作效率高。（错） 答：优化是编译程序的的一部分，优化的目的，是提高目标程序的质量和运行效率。 ④有的编译程序可以没有目标代码生成部分。（错） 答：编译程序必须生成目标代码，所以目标代码生成部分是不可缺少的。 第二章 高级语言及其语法描述 一、判断题 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 + i 8、把下面的文法改写为无二义性的文法： S(SS(（S）(（） 该文法产生二义性文法的原因就在于产生式S(SS中左部符号在右部连续出现两次，使得对S既可以采用左递归得到（）（）（）又可以采用右递归得到（）（）（），为此改写文法为： S(AS(（S）(（） A(（S）(（） 第三章 词法分析 一、填空题 1、编译过程中扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位—单词。 2、高级程序语言的单词通常分为五类，它们是关键字、标识符、常数、运算符以及界限符。 3、确定的有限自动机是一个五元组，通常表示为DFA M=（S，(，(，S0，F）。 4、词法分析的任务是输入源程序，输出单词符号。 5、确定有限自动机DFA是NFA的一种特例。 6、若二个正规式所表示的正规集相同，则认为二者是等价的。 二、判断题 1、一些语言，它们能被确定的有限自动机识别，但不能用正规表达式表示。（ 错 ） 答：用正规式表示的语言，都能被确定的有限自动机识别。 2、每一个NFA M都对应有唯一的一个最小化的DFA M。（ 对 ） 答：每一个NFA M都可以构造一个DFA M，而DFA M又可以构造一个最小化的DFA M。 3、一个有限自动机，仅有一个唯一的终态。（错） 答：有限自动机的终态可以有多个。 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等价是指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} 试构造相应的确定的有限自动机(DFA M`). 解： ⑴根据(函数值，先构造NFA M a 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` a 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）* ⑴构造NFA M 1 1 1 ( ( ( ( 0 0 0 ⑵用子集法构造DFA M的转换矩阵表 ⑶确定DFA M`的初态和终态 ①含有s，z状态子集为DFA M`的初态和终态，即为S。 ②含有z状态子集为DFA M`的终态结点，即为A，B。 ⑷构造DFA M` 0 0 1 0 1 1 ⑸将DFA M`最小化 将DFA M`划分成终态集和非终态集 因为DFA M`只有终态集，即{S，A，B}。采用后继状态等价性的依赖关系，构造DFA M`的最小化。又因为输入0均到达A，输入1均到达B，所以S，A，B等价，化简后的DFA M`。 0，1 第四章 语法分析—自上而下分析 一、填空题 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 #A aaaa# A(aaA 2 #Aaa aaaa# 匹配 3 #Aa aaa# 匹配 4 #A aa# A(aaA 5 #Aaa aa# 匹配 6 #Aa a# 匹配 7 #A # A(( 8 # # 接受 2、设文法G： S(SbA(aA B(Sc A(Bc ⑴将此文法改写为LL（1）文法。 ⑵求文法的每一个非终结符号的FIRST集合和FOLLOW集合。 ⑶构造相应的LL（1）分析表。 解： ⑴改写文法为LL（1）文法 S(aAS` S`(bAS`(( B(Sc A(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`eq \o(\s\up 8(* ),\s\do 3(=>))(,并且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。 a b c # S S(aAS` S` S`(bAS` S`(( S`(( A A(Bc B B(Sc 第五章 语法分析—自下而上分析 一、填空题 ⑴对于一文法，如果能够构造一张分析表，使得它的每一个入口均是唯一确定的，则称该文法为LR文法。 ⑵自下而上语法分析法的基本思想是：从待输入的符号串开始，利用文法的产生式步步向上进行直接归约，试图归约到文法的开始符号（识别符号）。 ⑶字的活前缀是指该字的任意首部。 ⑷活前缀是指规范句型的一个前缀，这种前缀不含句柄之后的任何句型。 二、选择题 ⑴若a为终结符，则A((•a(为B项目。 A、归约 B、移进 C、接受 D、待约 ⑵一个LR分析器包括A、D。 A、一个总控程序 B、一个项目集 C、一个活前缀 D、一张分析表 E、一个分析栈 ⑶对LR分析表的构造，有可能存在C、E动作冲突。 A、归约 B、移进 C、移进-归约 D、移进-移进 E、归约-归约 ⑷自上而下的语法分析方法A、C、D、E有。 A、算符优先分析法 B、LL（1）分析法 C、LR（0）分析法 D、SLR（1）分析法 E、LALR（1）分析法 ⑸每一项ACTION[s，a]所规定的动作包括A、C、D、E。 A、归约 B、比较 C、移进 D、接受 E、报错 四、解答题 ⑴考虑文法G S(BB B(aB(b ①列出这个文法的所有LR（0）项目； ②构造这个文法的LR（0）项目及识别活前缀的DFA； ③若是LR（0）文法，构造LR（0）分析表。 解答： ①将文法G拓广为文法G`及LR（0）的项目集规范族： 0、S`(S S`(•S S`(S• 1、S(BB S(•BB S(B•B S(BB• 2、B(aB B(•aB B(a•B B(aB• 3、B(b B(•b B(b• ②用(-CLOSURE办法构造文法G`的LR（0）项目集规范族： I0：S`(•S I1：S`(S• I3：B(a•B I5：B(aB• S(•BB I2：S(B•B B(•aB I6：B(b• B(•aB B(•aB B(•b B(•b B(•b I4：B(b• ③根据转换函数GO构造出G`的DFA。 S ( B B A b a b a B b ④构造LR（0）的分析表 状 ACTION GOTO 态 a b # S B 0 S3 S4 1 2 1 acc 2 S3 S4 5 3 S3 S4 6 4 r3 r3 r3 5 r1 r1 r1 6 r2 r2 r2 ⑵已知文法G S(aS(bS(a ①构造该文法的项目； ②构造识别活前缀的DFA； ③判断该文法是否是SLR（1）文法，并构造其SLR分析表。 解：①将文法G拓广为G`及构造LR（0）项目： 0、S`(S S`(•S S`(S• 1、S(aS S(•aS S(a•S S(aS• 2、S(bS S(•bS B(b•S B(bS• 3、S(a S(•a B(a• ②构造识别活前缀的DFA S a a b a S B S b ③构造其SLR分析表 在I1项目集中存在移进-归约冲突，求FOLLOW（S）={#} 证明： {a，b}(FOLLOW（S）={a，b}({#}=(，所以是SLR（1）文法（或判定分析表中是否有冲突项）。其分析表为： 状 ACTION GOTO 态 a b # S 0 S1 S2 3 1 S1 S2 r3 4 2 S1 S2 5 3 acc 4 r1 5 r2 第七章 语义分析和中间代码生成 一、填空题 1、所谓语法制导翻译，是指在语法规则的制导下，通过计算语义规则，完成输入符号的翻译，即每当使用语法规则进行推导或归约的同时，就是用与其相关的语义规则来进行翻译。 2、编译过程中，常见的中间语言形式有逆波兰式表示、三地址代码（三元式、四元式）和图形表示。 3、语法制导翻译即可以用来产生中间代码，也可以产生目标指令，甚至可用来对输入串进行解释执行。 二、选择题 1、中间代码生成时所依据的是C。 A、语法规则 B、词法规则 C、语义规则 D、等价变换规则 2、终结符具有D属性。 A、传递 B、继承 C、抽象 D、综合 3、在下面的语法制导翻译B、C、D、E中，采用拉练-回填技术。 A、赋值语句 B、布尔表达式的短路计算 C、GOTO语句 D、条件语句 E、循环语句 4、在编译程序中安排中间代码生成的目的是B、D。 A、便于进行存储空间的组织 B、利于目标代码的优化 C、利于编译程序的移植 D、利于目标代码的移植 三、判断题 1、 一个语义子程序描述了一个文法所对应的翻译工作。（错） 答：一个语义子程序描述了一个产生式对应的翻译工作。 2、 程序中的表达式语句在语义翻译时不许要回填技术。（对） 答：表达式语句在语义翻译时程序结构是顺序结构。 3、 对任何一个编译程序来说，产生中间代码是不可缺少的。（错） 答：有的编译程序对目标程序不许要优化，可以直接生成目标程序。 四、解答题 1、什么是语法制导翻译？ 在分析过程中，每当需要使用一个产生式进行归约时，语法分析程序除执行相应的语法分析动作之外，还要执行相应的语义动作或调用相应的语义子程序。 2、什么是语义子程序？ 语义子程序描述了一定的输入和一定的输出之间的对应关系。 3、设某语言的WHILE语句的语法形式为： S(while E do S（1）其语义解释如图所示。 假 真 ● ⑴写出适合语法制导翻译的产生式。 ⑵写出每个产生式对应的语义动作。 解：改写后的产生式如下： W(while A(W E do S(A S（1） 每个产生式对应的语义子程序如下： W(while {W.QUAD:=NXQ;} A(W E do {BACKPATCH(E.TC，NXQ); B.CHAIN:=E.FC; A.QUAD:=W.QUAD} S(A S（1） { BACKPATCH(S（1）.CHAIN，A.QUAD); GEN(j，_，_，A.QUAD); S.CHAIN:=A.CHAIN;} 4、用7.5.1节的办法，把下列语句翻译成四元式序列： while a