大连理工大学编译原理复习

编译技术命题指导意见教学内容知识点及题型第一章编译器概述A（1）编译的阶段划分[选择题2分][1]编译程序绝大多数时间花在()上。A.出错处理B.词法分析C.目标代码生成D.符号表管理答案：D[2]()和代码优化部分不是每个编译程序都必需的。A.语法分析B.中间代码生成C.词法分析D.代码生成答案：B[3]编译程序前三个阶段完成的工作是()。A.词法分析、语法分析和代码优化B.代码生成、代码优化和词法分析C.词法分析、语法分析和语义分析D.词法分析、语法分析和代码生成答案：C（2）遍的概念[填空题2分][1]编译阶段的活动常用一遍扫描来实现，一遍扫描包括和。答案：读一个输入文件写一个输出文件[2]将编译程序分成若干个“遍”是为了________。答案：使程序的结构更加清晰[3]编译器从逻辑上可以分为7个阶段，其中，可以作为一个后端遍的是___________阶段。答案：代码生成（3）前端和后端的划分[简答题5分][1]什么是前端？[5分]答案：编译器分成分析和综合两大部分。分析部分揭示源程序的基本元素和它们所形成的层次结构，决定它们的含义，建立起源程序的中间表示，分析部分经常被称为前端。[2]什么是后端？[5分]答案：编译器分成分析和综合两大部分。综合部分从源程序的中间表示建立起和源程序等价的目标程序，它经常被称为后端。[3]什么是前端？什么是后端？[5分]答案：编译器分成分析和综合两大部分。分析部分揭示源程序的基本元素和它们所形成的层次结构，决定它们的含义，建立起源程序的中间表示，分析部分经常被称为前端。综合部分从源程序的中间表示建立起和源程序等价的目标程序，它经常被称为后端。第二章2.12.2词法记号的定义及描述B（1）词法分析器的功能[选择题2分][1]词法分析程序的输出结果是（）。A.单词的种别编码B.单词在符号表中的位置C.单词的种别编码和单词属性值D.单词的单词属性值答案：C[2]词法分析器用于识别_____。A.字符串B．语句C．单词D．标识符答案：C[3]扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即（）。A．字符B．单词C．句子D．句型答案：B（2）词法记号概念及属性[填空题2分][1]词法记号是由和构成的二元组。答案：记号名属性值[2]词法单元是源程序中匹配一个的字符序列。答案：记号模式[3]影响语法分析的决策，影响记号的翻译。答案：记号名属性（3）正规式与语言的对应关系[选择题2分][1]下面文法（）和正规表达式a*b描述的语言相同。A.S→ab|aSbB.S→b|aSC.S→a|aSbD.S→a|Sb答案：B[2]最多包含两个a的{a,b}上的语言（）。A.(a|ε)b*(a|ε)B.b*ab*ab*|b*ab*C.b*(a|b*)(a|b*)b*D.b*(a|ε)b*(a|b*)b*答案：D[3]与(a|b)*等价的正规式是（）。A.(a*|b*)*B.(a|b)+C.(ab)*D.a*|b*答案：A第二章2.3.1,2.3.2NFA,DFAC（1）NFA与DFA的概念[选择题2分][1]有如图所示的有穷自动机，与之等价的正规式为（）。A.(0|1)*(000|111)(0|1)B.(0|1)(000|111)(0|1)C.(0|1)*(000|111)(0|1)*D.Ａ，B，C选项都不正确答案：C[2]对于NFA和DFA模型说法错误的是（）。A.DFA是NFA的特殊形式B.DFA与NFA的状态转换完全相同C.都有唯一的开始状态D.都可以有多个接受状态答案：B[3]对于DFA模型，说法错误的是（）。A.DFA从任何状态出发，对于任何输入符号，可有多个转换B.任何状态都没有ε转换C.DFA有唯一的开始状态D.DFA可以有多个接受状态答案：A（2）NFA的构造[简答题10分][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状态转换图为：[2]构造正规式相应的NFA:1(0|1)*101。答案：AB1C11011[3]为（（ε|a）b*）*构造非确定的有限自动机，给出它们处理输入串ababbab的转换序列。答案：输入串ababbab的转换序列：01456789145678789145678910或者0145678914567891236789145678910（3）NFA转化为DFA[简答题10分][1]设={0，1}上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。答案：构造相应的正规式：(0|1)*1(0|1)NFA:确定化：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}、[2]构造正规式1(0|1)*101相应的DFA。答案：先构造NFA：确定化：重新命名，令AB为B、AC为C、ABY为D得：所以，可得DFA为：[3]对于下图所示NFA，回答下列问题：（1）用正规式描述该有限自动机所表示的语言。（2）由NFA转为DFA。（3）构造最简DFA。答案：（1）(a|b)*a(a|b)*（2）（3）（4）DFA的化简[简答题10分][1]已知NFA=（{x,y,z},{0,1},M,{x},{z}），其中：M(x,0)={z},M(y,0)={x,y},M(z,0)={x,z},M(x,1)={x},M(y,1)=φ,M(z,1)={y},构造相应的DFA并最小化。答案：根据题意有NFA图:下表由子集法将NFA转换为DFA：面将该DFA最小化：(1)首先将它的状态集分成两个子集：P1={A,D,E},P2={B,C,F}(2)区分P2:由于F(F,1)=F(C,1)=E,F(F,0)=F并且F(C,0)=C,所以F，C等价。由于F(B,0)=F(C,0)=C,F(B,1)=D,F(C,1)=E,而D，E不等价（见下步），从而B与C，F可以区分。有P21={C,F},P22={B}。(3)区分P1:由于A，E输入0到终态，而D输入0不到终态，所以D与A，E可以区分，有P11={A,E},P12={D}。(4)由于F(A,0)=B,F(E,0)=F,而B，F不等价，所以A，E可以区分。(5)综上所述，DFA可以区分为P={{A}，{B}，{D}，{E}，{C，F}}。所以最小化的DFA如下：[2]给定下列自动机：把此自动机转换为确定自动机DFA。答案：有状态矩阵如图：从而可得DFA如图：[3]（1）将下图中的NFAM确定化为DFAM’。（2）将DFAM’化简。01aaba答案：确定化:ab{0}{0,1}{1}{1}{0}---{0，1}{0,1}{1}状态编号ab01220---112a--aabb未简化的DFA最小化：分为：终态集{0,1}非终态集{2}{0,1}a={1}{0,1}b={2}所以：{0,1}=｛0｝｛2｝=｛1｝a--ba01201第二章2.4,2.5词法分析器的生成器;第二章习题D（1）直接从语言构造DFA[简答题5分][1]写出能产生字母表{x,y}上的不含两个相邻的x,且不含两个相邻的ｙ的全体符号串的有限状态自动机。答案：2210xyxy[2]处于/*和*/之间的串构成注解，注解中间没有*/。画出接受这种注解的DFA的状态转换图。答案：[3]有语言L={w|w∈(0,1)+，并且w中至少有两个1，又在任何两个1之间有偶数个0}，试构造接受该语言的确定有限状态自动机。答案：124start52othersothers/***/（2）Lex的功能[填空题2分][1]Lex是从基于正规式的描述来构造。答案：词法分析器[2]Lex程序包含三部分：、和辅助函数。答案：声明翻译规则[3]由Lex建立的分析器通常作为分析器的一个子程序。答案：词法语法第三章3.1上下文无关文法E（1）上下文无关文法定义[选择题2分]；[1]一个上下文无关文法G包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组（）。A.句子B.句型C.单词D.产生式答案：D[2]文法分为四种类型，即0型、1型、2型、3型。其中2型文法是（）。A.短语文法B.正则文法C.上下文有关文法D.上下文无关文法答案：D[3]文法分为四种类型，即0型、1型、2型、3型。其中0型文法是_____。A.短语文法B.正则文法C.上下文有关文法D.上下文无关文法答案：A（2）最左推导、最右推导[简答题5分]；[1]文法S-a|^|(T)T-T,S|S对(a,(a,a)和(((a,a),^,(a)),a)的最左推导。答案：对(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))对(((a,a),^,(a)),a)的最左推导为：S=(T)=(T,S)=(S,S)=((T),S)=((T,S),S)=((T,S,S),S)=((S,S,S),S)=(((T),S,S),S)=(((T,S),S,S),S)=(((S,S),S,S),S)=(((a,S),S,S),S)=(((a,a),S,S),S)=(((a,a),^,S),S)=(((a,a),^,(T)),S)=(((a,a),^,(S)),S)=(((a,a),^,(a)),S)=(((a,a),^,(a)),a)[2]设文法G[E]:E→RP|PP→(E)|iR→RP+|RP*|P+|P*对i+i*(i+i)的最右推导。答案：ERPR(E)R(RP)R(Ri)R(P+i)R(i+i)RP*(i+i)Ri*(i+i)P+i*(i+i)i+i*(i+i[3]考虑文法S-aSbS|bSaS|ε（a）为句abab构造两个不同的最左推导，以此说明该文法是二义的。（b）为abab构造对应的最右推导。答案：（3）分析树[简答题5分]；[1]考虑文法S-aSbS|bSaS|ε（1）为abab构造对应的分析树。（2）这个文法产生的语言是什么？答案：（1）（2）该文法产生a、b个数相等的ab串（含空串）[2]对于文法G(E):ET|E+TTF|T*FF(E)|i写出句型(T*F+i)的最右推导并画出语法树。答案：（1）ETF(E)(E+T)(E+F)(E+i)(T+i)(T*F+i)（2）语法树如右图。[3]令文法G[S]为：S→ABA→aAb|abB→b,（1）G[S]定义的语言L(G)是什么？（2）给出句子aabbb的最左推导，并给出其语法分析树。答案：（1）SabBabbSaAbBaabbBaabbbSaAbBaaAbbBaaabbbBaaabbbbETF(E)E+TFiTT*F……Sanbm(n=0,m=1)（2）sABaAbBaabbBaabbbb/.（4）二义性概念[选择题2分][1]如果文法G是无二义的，则它的任何句子α（）。A.最左推导和最右推导对应的语法树必定相同B.最左推导和最右推导对应的语法树可能不同C.最左推导和最右推导必定相同D.可能存在两个不同的最左推导，但它们对应的语法树相同答案：A[2]如果一个文法G是无二义性文法，对于任何一个句子，该句子（）。A.可能存在两个不同的最左推导B.可能存在两个不同的最右推导C.最左推导和最右推导不同D.仅存在一个最左推导和一个最右推导答案：D[3]若文法G定义的语言是无限集，则文法必然是（）。A.递归的B.前后文无关的C.二义性的D.无二义性的答案：A第三章3.2语言和文法F（1）消除左递