编译技术复习题答案.doc

第一章：编译系统概述一单选题1编译程序前三个阶段完成的工作是（ C ）。A词法分析、语法分析和代码优化 B代码生成、代码优化和词法分析C词法分析、语法分析、语义分析和中间代码生成 D词法分析、语法分析和代码优化2编译程序绝大多数时间花在（ D ）上。 A出错处理 B词法分析 C目标代码生成 D表格管理3编译程序是对（ C ）。 A汇编程序的翻译 B高级语言程序的解释执行 C高级语言的翻译 D机器语言的执行4在使用高级语言编程时，首先可通过编译程序发现源程序的全部（ A ）错误。 A语法 B语义 C语用 D运行二填空题1编译程序首先要识别出源程序中每个( 单词 )，然后再分析每个( 句子 )并翻译其意义。 2通常把编译过程分为分析前端与后端两大阶段。词法、语法和语义分析是对源程序的( 分析 )，中间代码生成、代码优化与目标代码的生成则是对源程序的 (综合 )。3对编译程序而言，输入数据是( 源程序 )，输出结果是( 目标程序 )。4对下列错误信息，请指出可能是编译的哪个阶段（词法分析、语法分析、语义分析、代码生成）报告的。（1） else 没有匹配的if （语法分析）（2） 数组下标越界 （语义分析）（3） 使用的函数没有定义 （语法分析）（4） 在数中出现非数字字符 （词法分析）5如果编译程序生成的目标程序是机器代码程序，则源程序的执行分为两大阶段： （ 编译阶段 ） 和（ 运行阶段 ）。如果编译程序生成的目标程序是汇编语言程序，则源程序的执行方式分成三个阶段：（ 编译阶段 ）（ 汇编阶段 ）和（ 运行阶段 ）。6编译程序在其工作过程使用最多的数据结构是（ 表 ），它记录着源程序中各种信息，以便查询或修改，在这些（ 表 ）中，尤以（ 符号表 ）最重要，它的生存期最长，使用也最频繁。 三简述题：1编译程序的工作分为那几个阶段?答：词法分析、语法分析和语义分析是对源程序进行的分析(称为编译程序的前端)，而中间代码生成、代码优化和代码生成三个阶段合称为对源程序进行综合(称为编译程序的后端)，它们从源程序的中间表示建立起和源程序等价的目标程序。第二章 词法分析一单选题：1语言是（ A ）。A句子的集合 B产生式的集合 C符号串的集合 D句型的集合2扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即（ B ）。 A 字符 B单词 C句子 D句型3词法分析的任务是（ A ）。 A识别单词 B分析句子的含义 C识别句子 D生成目标代码4DFA（如图所示）接受的字集为（ D ）。 0 1 0YX A以0开头的二进制数组成的集合 B以0结尾的二进制组成的集合 C含奇数个0的二进制组成的集合 D含偶数个0的二进制组成的集合 5词法分析器的输出结果是（ C ）。 A单词的种别编码 B单词在符号表中的位置 C单词的种别编码和自身的值 D单词自身值二填空题：1描述程序设计语言的词法的机制是（正则表达式），识别机制是（有穷状态自动机）。2最小状态DFA的含义是（没有多余状态，没有两个状态等价）。3确定有限自动机DFA是（ NFA ）的一个特例。4确定的有穷自动机是一个（ 五元组 ），通常表示为（ DFA = ( S，f , s0 Z ) ）。三、简述题：1词法分析答：词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位，并转换成统一的内部表示(token)，送给语法分析程序。四综合应用题：1设有非确定的有自限动机NFA M=(A，B，C，0，1，d，A，C)，其中：d (A，0)=C d (A，1)=A，B d (B，1)=C d (C，1)=C。请画出状态转换距阵和状态转换图。解：状态转换距阵为：d01ACA，BBCCC状态转换图为：110112有一台自动售货机，接收1分和2分硬币，出售3分钱一块的硬糖。顾客每次向机器中投放 3分的硬币，便可得到一块糖（注意；只给一块并且不找钱）。（1）写出售货机售糖的正则表达式；（2）构造识别上述正则式的最简DFA。 解：（1）设a = 1, b = 2,，则售货机售糖的正则表达式为：a (b | a (a | b) | b (a | b) 。 （2）画出与正则表达式a (b | a (a | b) | b (a | b)对应的NFA，如图所示： 3设S=0，1上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。解：构造相应的正规式：(0|1)*1(0|1) NFA: 1 110432 e e e e 1 0 0确定化：(3分)I0,1,21,21,2,31,21,21,2,31,2,31,2,41,2,3,41,2,41,21,2,31,2,3,41,2,41,2,3,4 0 143210 0 1 0 0 0 1 1 14构造一个DFA，使其接受S = 0， 1上0和1的个数都是偶数的字符串。解：5构造一个字母表0，1上的DFA，其接受的串中所含0的数目能被3除尽。解：6写出在S = a , b上不是a开头的，以aa结尾的的字符串集合的正规表达式，并直接构造与之等价的状态最少的DFA。 解：7写一个文法使其语言为L(G)=anbncm| m，n 1，n为奇数，m为偶数。解： 文法G(S)：8构造一个DFA，它接受S=a，b上所有包含ab的字符串。解：构造相应的正规式：(a|b)*ab(a|b)*0123645 a a e e a b e e b b确定化：I0,1,21,2,31,21,2,31,2,31,2,4,5,61,21,2,31,21,2,4,5,61,2,3,5,61,2,5,61,2,3,5,61,2,3,5,61,2,4,5,61,2,5,61,2,3,5,61,2,5,6 b b b a543210 a a a a a b b b 最小化：0，1，2 3，4，5 0， 2，1， 3，4，5baa01b3ba第三章 程序设计语言的语法描述一单选题：1如果文法G是无二义的，则它的任何句子 （ A ）。 A最左推导和最右推导对应的语法树必定相同 B最左推导和最右推导对应的语法树可能不同 C最左推导和最右推导必定相同 D可能存在两个不同的最左推导，但它们对应的语法树相同 2正规式 M 1 和 M 2 等价是指（ C ）。 AM1和M2的状态数相等 BM1和M2的有向边条数相等 CM1和M2所识别的语言集相等 DM1和M2状态数和有向边条数相等 3文法G所描述的语言是（ D ）的集合。A文法G的字符表V中所有符号组成的符号串。 B文法G的字符表V的闭包V*中的所有符号串。C由文法的识别符号推出的所有符号串。D由文法的识别符号推出的所有 4已知语言L = anbbn | n 1 ，则下述文法，（ D ）可以产生语言L。 AZ aZb|aAb|b BA aAbA aAb | b A bCZ AbB DZ aAbA aA | a A aAb | bB bB | b 5正则表达式的运算符的优先顺序为（ C ）。 A| * B * | C* | D| * 6. ab3 的另一种表示方法是（ ）。 A. abbb B. ababab C.abbaab D.aaabbb二填空题：1如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（ 二义性的 ）。2最右推导亦称为（规范推导），由此得到的句型称为（规范）句型。3对于文法G，仅含终结符号的句型称为 ( 句子 )。42型文法又称为（上下文无关）文法；3型文法又称为（正则 ）文法。5一个文法G是一个四元式( VT,VN,S,P )组成的。6文法G产生的 （ 句子 ）的全体是该文法描述的语言。7L+ 可以写成 （ LL* ）。三简述题1一个文法是由哪几部分组成的，各部分的功能是什么？解：一个文法G是一个四元式（VT, VN ,S, P）其中：VT是一个终结符的非空有限集合，终结符通常用小写字母表示；VN是一个非终结符的非空有限集合，非终结符通常用大写字母表示；S是一个特殊的非终结符（SVN），称为开始符号。P是一个产生式（规则）的有限集合，每个产生式的形式是A ，其中AVN，(VTVN)*。第四章 自上而下的语法分析一单选题：1文法GS: S xSx|y 所识别的语言是（ C ）。 A.xyx B.(xyx)* C.xnyxn (n 0) D.x*yx* 2 编译过程中，语法分析器的任务是（ ）。 A分析单词是怎样构成的 B分析单词串是如何构成语句和说明的 C分析语句和说明是如何构成程序的 D分析程序的结构3下列关于标识符和名字的叙述中，正确的为（ C ）。 A标识符有一定的含义 B名字是一个没有意义的字符序列C名字有确切的属性 D都不对 二填空题：1编译器常用的语法分析方法有( 自底向上 )和( 自顶向下 )两种。2在LL(1)文法，其中的第一个L代表（ 从左向右扫描输入 ），第二个L表示产生（ 最左推导 ），1代表在决定分析器的每步动作时（ 向前看一个输入符号 ）。3一个上下文无关文法所含四个组成部分是（非终结符有限集合、终结符有限集合、产生式有限集合、开始符）。4一个文法GZ，若存在推导序列Z +Z,则称GZ是（ 递归 ）文法，这类文法所产生的句子有 （ 无数 ）个。 5描述语言L = ambn | n m 1 的文法是：（ Z aAb、A Ab | aAb | ）。三简述题1简述自顶向下的语法分析方法。答：所谓自顶向下的语法分析方法就是从文法的开始符开始，根据给定的输入串并按照文法的产生式一步一步的向下进行最左推导，试图推导出文法的，使之与给定的输入串。四综合应用题：1试验证如下文法 GE 是 LL(1)文法:E F EE E| F aFF aF | 其中E，F，E，F为非终结符解：各非终结符的FIRST 集和FOLLOW 集如下：FIRST（E）= FOLLOW（E）= FIRST（E）= ， FOLLOW（E）= FIRST（F）= a FOLLOW（F）= FIRST（F）= a ， FOLLOW（F）= 对于E E | FIRST(E) FOLLOW（E）= 对于F aF| FIRST（aF） FOLLOW（F）= 所以, 文法GE是LL（1）文法。2设有文法GA的产生式集为:ABaC|CbBBAc|cCBb|b试消除GA的左递归。解：不妨以A、B、C 排序.先将A 代入B 中，然后消除B 中左递归；再将A、B 代入C 中。再消除C 中左递归。最后结果为:GA:ABaC|CbB BCbBcB|cB BaCcB|CcBbC|bC CbBcBbC|3. 对文法GS：Sa|(T)TT,S|S(1) 给出(a,(a,a)的最左推导。(2) 对文法G，进行改写，消除左递归。(3) 对修改后的文法求First和Follow集。(4) 并给出它的预测分析表。(5) 给出输入串(a,a)#的分析过程，并说明该串是否为G 的句子。解：（1）对(a,(a,a)的最左推导为：S= (T) = (T,S)= (S,S) = (a,S) = (a,(T) = (a,(T,S) = (a,(S,S) = (a,(a,S) =(a,(a,a)(2) 改写文法为： Sa S S( T ) TS N N, S N N (3)非终结符First集Follow集S a, , ( #, , , ) T a, , ( ) N , , ) (4) 预测分析表： a(),#Sa( T )TS NS NS NN, S N（5）对于输入串（a,a）#的分析过程为： 栈当前输入符剩余输入符号使用的产生式#S(a,a)#S( T )#) T(a,a)#) Ta,a)#TS N#)NSa,a)#)Naa,a)#)N,a)#N, S N#)NS,a)#)NSa)#Sa#)Naa)#)N)#N#)# 可见输入串（a,a）#是文法的句子。4. 对文法G(S)：S SaT |aT|aTT aT|a(1) 消除该文法的左递归和提取左公因子；(2) 构造各非终结符的FIRST和FOLLOW集合；(3) 构造该文法的LL(1)分析表，并判断该文法是否是LL(1)的。解： （1）消除左递归： S aTS|aTSSaTS|T aT|a提取左公因子：S aTS|aTSSaTS|T aTTT|（2） FIRST(S)=a， FOLLOW(S)=#FIRST(S)=， FOLLOW(S)=#FIRST(T)= FOLLOW(T)=，#FIRST(T)=， FOLLOW(T)=，#（3）LL(1)分析表如下，该文法是LL(1)文法。a#SSaTSSaTSSSaTSSTTaTTTTTT5. 考虑文法G： S a | | ( T ) T T, S | S (1) 消除文法G的左递归。 （2）用类C+语言写出递归下降分析程序。假设由单词种别构成的源文件存放于文件Lex.txt中，如文件内容。 6. 考虑下列文法G（j相当与endif）： S fCtSj | fCtSes | a C i （1）提取文法的左因子。 （2）构造预测分析表。 （3）判断经改写的文法是否是LL(1)文法。 解：（1）S fCtSS| a SeS | j C i (2) char t;ifstrem cinf(lex.txt);void main() cinf t; S();void S() if (t = a) cinf t; else if (t = f) cinf t; C(); if (t = t) cinf t; S(); S(); void S() if (t = e) cinf t; S(); else if (t = j) cinf t;void C() if (t = i) cinf t;（3）first(S) = f,afirst(S) = e, jfirst(C) = iftaeji#SfCtSSaSeSjCi 表不含多重定义，因此该文法是LL(1)文法。第五章 自下而上的语法分析一单选题：1一个句型中称为句柄的是该句型的最左（ D ） A非终结符号 B短语 C句子 D直接短语2若a为终结符，则Aa为（ B ）项目。 A归约 B移进 C接受 D待约3在规范归约中，用（ B ）来刻画可归约串。 A直接短语 B句柄 C最左短语 D短语4若项目集Ik含有A，则在状态K时，仅当面临的输入符号aFollow(A)时，才采用“A”动作的一定是（ D ）。 ALALR文法 BLR（0）文法 CLR（1）文法 DSLR（1）文法5在LR（0）的ACTION子表中，如果某一行中存在标记“rj”的栏，则（ A ）。A该行必定填满rjB该行未填满rjC其他行也有rj Dgoto子表中也有rj二填空题： 1一个LR分析器包括两部分：一个总控程序和（一张分析表 ）。2LR（0）分析法的名字中“L”表示（ 自左至右分析 ），“R”表示（采用最右推导的逆过程即最左归约 ），“0”表示（ 向右查看0个字符 ）。 3如果文法G的开始符是S，那么G的拓广文法G是在G的基础上增加一个新的开始符号 ( S ) 和产生式（ S S ）。4由于存在（ 规约- 移进 ）冲突，使得文法不是LR（0），转换LR（0）为SLR（1）文法，需要计算（ 非终结符的follow集 ）。三简述题；1简述自下而上的分析方法。 答：所谓自下而上分析法就是从输入串开始，逐步进行“归约”，直至归约到文法的开始符号；或者说从语法树的末端开始，步步向上“归约”，直到根节点。四综合应用题：1 对于文法GS：SAB，AAa|bB，Ba|Sb求句型baSb的全部短语、直接短语和句柄？答句型baSb的语法树如图所示。ASBbBSab图五(2) 句型baSb的的语法树短语：baSb、ba、Sb、a直接短语：Sb 、a句柄：a2证明下述文法G：SaSbS|aS|d是二义性文法。解：一个文法，如果存在某个句子有不只一棵语法分析树与之对应，那么称这个文法是二义性文法。句子aadbd有两棵语法树。如下图：SaSSabSdddSSabSSad(1) (2)由此可知，SaSbS|aS|d定义的文法是二义性文法。3对于文法G(S): （1）写出句型b(Ma)b的最右推导并画出语法树。（2）写出上述句型的短语，直接短语和句柄。SbM(TMabL)解：（1） （2）短语: Ma)， (Ma)， b(Ma)b直接短语: Ma)句柄: Ma)4已知文法：AaAd | aAb | 判断该文法是否是SLR(1)文法，若是构造相应分析表，并对输入串ab#给出分析过程。解：文法： AaAd | aAb | 拓广文法为G，增加产生式SA若产生式排序为：（0）S A（1）A aAd（2）A aAb（3）A 由产生式知： First (S ) = ,a First (A ) = ,a Follow(S ) = #Follow(A ) = d,b,#G的LR(0)项目集族及识别活前缀的DFA 如下图所示：在I0 中：A .aAd 和A .aAb 为移进项目，A .为归约项目，存在移进-归约冲突，因此所给文法不是LR(0)文法。在I0、I2 中：Follow(A) a= d，b，# a= 所以在I0、I2 中的移进-归约冲突，可以由Follow 集解决，所以G 是SLR(1)文法。构造的SLR(1)分析表如下：stateActionGoto a d b # A0S2R3R3R311acc2S2R3R3R333S4S54R1E1R15R2R2R2 对于输入ab#分析过程如下； 步骤状态栈符号栈输入符动作10#ab#shift202#ab#reduce3023#aAb#shift40235#aAb#reduce501#A#accept若有定义二进制数的文法如下：SLL|LLLB|BB0|1(1) 试为该文法构造LR 分析表，并说明属哪类LR 分析表。(2) 给出输入串101.110 的分析过程。解：文法：SL.L|LLLB|BB0|1拓广文法为G，增加产生式SS若产生式排序为：（0） S S（1） S L.L（2） S L（3）L LB（4） L B（5） B 0（6） B 1由产生式知：Follow(S ) = #Follow(S ) = #Follow(L ) = .,0,1,#Follow(B ) = .,0,1,#G的LR(0)项目集族及识别活前缀的DFA 如下图所示：在I2 中：B .0 和 B .1 为移进项目，S L.为归约项目，存在移进-归约冲突，因此所给文法不是LR(0)文法。在I2、I8 中：Follow(s) 0，1= # 0，1=所以在I2 、I8 中的移进-归约冲突可以由Follow 集解决，所以G 是SLR(1)文法。构造的SLR(1)分析表如下：stateactiongoto.01#SLB0S4S51231acc2S6S4S5R273R4R4R4R44R5R5R5R55R6R6R6R66S4S5837R3R3R3R38S4S5R17对输入串101.110#的分析过程：步骤状态栈符号栈输入串动作#101.110#shift#101.110#reduce#B01.110#reduce#L01.110#shift#L01.110#reduce#LB1.110#reduce#L1.110#shift#L1.110#reduce#LB.110#reduce#L.110#shift#L.110#shift#L.110#reduce#L.B10#reduce #L.L10#shift#L.L10#reduce#L.LB0#reduce#L.L0#shift#L.L0#reduce#L.LB#reduce#S#accept分析成功,说明输入串101.110#是文法的句子。第六章 语法制导翻译与中间代码生成一单选题：1常用的中间代码形式不含（ D ）。 A三元式 B四元式 C逆波兰式 D语法树2代码生成阶段的主要任务是（ C ）。 A把高级语言翻译成汇编语言 B把高级语言翻译成机器语言 C把中间代码变换成依赖具体机器的目标代码 D把汇编语言翻译成机器语言3四元式之间的联系是通过（ B ）实现的。 A指示器 B临时变量 C符号表 D程序变量4有一语法制导翻译如下所示： S bAb cout ”1” A (B cout “2” A a cout ”3” B A