编译技术复习题答案

第一章：编译系统概述一．单选题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．生成目标代码4．DFA（如图所示）接受的字集为（D）。A．以0开头的二进制数组成的集合B．以0结尾的二进制组成的集合C．含奇数个0的二进制组成的集合D．含偶数个0的二进制组成的集合5．词法分析器的输出结果是（C）。A．单词的种别编码B．单词在符号表中的位置C．单词的种别编码和自身的值D．单词自身值二．填空题：1．描述程序设计语言的词法的机制是（正则表达式），识别机制是（有穷状态自动机）。2．最小状态DFA的含义是（没有多余状态，没有两个状态等价）。3．确定有限自动机DFA是（NFA）的一个特例。4．确定的有穷自动机是一个（五元组），通常表示为（DFA=(S，∑，f,s0Z)）。三、简述题：1．词法分析答：词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位，并转换成统一的内部表示(token)，送给语法分析程序。四．综合应用题：1．设有非确定的有自限动机NFAM=({A，B，C}，{0，1}，，{A}，{C})，其中：(A，0)={C}(A，1)={A，B}(B，1)={C}(C，1)={C}。请画出状态转换距阵和状态转换图。解：状态转换距阵为：01ACA，BBCCC状态转换图为：010YX2．有一台自动售货机，接收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，如图所示：X123Yabababba3．设={0，1}上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。解：构造相应的正规式：(0|1)*1(0|1)NFA:11100确定化：(3分)I0I1I{0,1,2}{1,2}{1,2,3}{1,2}{1,2}{1,2,3}{1,2,3}{1,2,4}{1,2,3,4}{1,2,4}{1,2}{1,2,3}{1,2,3,4}{1,2,4}{1,2,3,4}0AB1C11011012341010001114．构造一个DFA，使其接受={0，1}上0和1的个数都是偶数的字符串。解：5．构造一个字母表{0，1}上的DFA，其接受的串中所含0的数目能被3除尽。解：6．写出在={a,b}上不是a开头的，以aa结尾的的字符串集合的正规表达式，并直接构造与之等价的状态最少的DFA。解：7．写一个文法使其语言为L(G)={anbncm|m，n≥1，n为奇数，m为偶数}。解：文法G(S)：ccCcc|ccCbaaAbb|aAACS8．构造一个DFA，它接受={a，b}上所有包含ab的字符串。解：构造相应的正规式：(a|b)*ab(a|b)*aaabbb确定化：I0I1I{0,1,2}{1,2,3}{1,2}{1,2,3}{1,2,3}{1,2,4,5,6}{1,2}{1,2,3}{1,2}{1,2,4,5,6}{1,2,3,5,6}{1,2,5,6}{1,2,3,5,6}{1,2,3,5,6}{1,2,4,5,6}{1,2,5,6}{1,2,3,5,6}{1,2,5,6}bbba012340123645aaaaabbb最小化：{0，1，2}{3，4，5}{0，2}，1，{3，4，5}第三章程序设计语言的语法描述一．单选题：1．如果文法G是无二义的，则它的任何句子α（A）。A．最左推导和最右推导对应的语法树必定相同B．最左推导和最右推导对应的语法树可能不同C．最左推导和最右推导必定相同D．可能存在两个不同的最左推导，但它们对应的语法树相同2．正规式M1和M2等价是指（C）。A．M1和M2的状态数相等B．M1和M2的有向边条数相等C．M1和M2所识别的语言集相等D．M1和M2状态数和有向边条数相等3．文法G所描述的语言是（D）的集合。A．文法G的字符表V中所有符号组成的符号串。B．文法G的字符表V的闭包V*中的所有符号串。C．由文法的识别符号推出的所有符号串。D．由文法的识别符号推出的所有4．已知语言L={anbbn|n≥1}，则下述文法，（D）可以产生语言L。A．Z→aZb|aAb|bB．A→aAbA→aAb|bA→bC．Z→AbBD．Z→aAbA→aA|aA→aAb|bB→bB|b5．正则表达式的运算符的优先顺序为（C）。A．|*·B．*|·C．*·|D．|·*6.ab3的另一种表示方法是（）。012345baa01b3baA.abbbB.abababC.abbaabD.aaabbb二．填空题：1．如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（二义性的）。2．最右推导亦称为（规范推导），由此得到的句型称为（规范）句型。3．对于文法G，仅含终结符号的句型称为(句子)。4．2型文法又称为（上下文无关）文法；3型文法又称为（正则）文法。5．一个文法G是一个四元式(VT,VN,S,P)组成的。6．文法G产生的（句子）的全体是该文法描述的语言。7．L+可以写成（LL*）。三．简述题1．一个文法是由哪几部分组成的，各部分的功能是什么？解：一个文法G是一个四元式（VT,VN,S,P）其中：VT是一个终结符的非空有限集合，终结符通常用小写字母表示；VN是一个非终结符的非空有限集合，非终结符通常用大写字母表示；S是一个特殊的非终结符（S∈VN），称为开始符号。P是一个产生式（规则）的有限集合，每个产生式的形式是A→α，其中A∈VN，α∈(VT∪VN)*。第四章自上而下的语法分析一．单选题：1．文法G[S]:S→xSx|y所识别的语言是（C）。A.xyxB.(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．一个文法G[Z]，若存在推导序列Z→+…Z…,则称G[Z]是（递归）文法，这类文法所产生的句子有（无数）个。5．描述语言L={ambn|n≥m≥1}的文法是：（Z→aAb、A→Ab|aAb|ε）。三．简述题1．简述自顶向下的语法分析方法。答：所谓自顶向下的语法分析方法就是从文法的开始符开始，根据给定的输入串并按照文法的产生式一步一步的向下进行最左推导，试图推导出文法的，使之与给定的输入串。四．综合应用题：1．试验证如下文法G[E]是LL(1)文法:E→[F]E′E’→E|εF→aF’F’→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’）=φ所以,文法G[E]是LL（1）文法。2．设有文法G[A]的产生式集为:A→BaC|CbBB→Ac|cC→Bb|b试消除G[A]的左递归。解：不妨以A、B、C排序.先将A代入B中，然后消除B中左递归；再将A、B代入C中。再消除C中左递归。最后结果为:G[A]:A→BaC|CbBB→CbBcB'|cB'B'→aCcB'|εC→cB'bC'|bC'C'→bBcB'bC'|ε3.对文法G[S]：S→a|∧|(T)T→T,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)改写文法为：S→aS→∧S→(T)T→SNN→,SNN→ε(3)非终结符First集Follow集S{a,∧,(}{#,,,)}T{a,∧,(}{)}N{,,ε}{)}(4)预测分析表：a∧(),#S→a→∧→(T)T→SN→SN→SNN→ε→,SN（5）对于输入串（a,a）#的分析过程为：栈当前输入符剩余输入符号使用的产生式#S(a,a)#S→(T)#)T((a,a)##)Ta,a)#T→SN#)NSa,a)##)Naa,a)##)N,a)#N→,SN#)NS,,a)##)NSa)#S→a#)Naa)##)N)#N→ε#))###可见输入串（a,a）#是文法的句子。4.对文法G(S)：SSaT|aT|aTTaT|a(1)