编译原理模拟题

现代远程教育《编译原理》课程学习指导书作者：柴玉梅《编译原理》课程指导书第一章编译概述（一）本章学习目标1.正确理解什么是编译程序、编译程序工作的基本过程及其各阶段的基本任务；2.熟练掌握编译程序总框；3.了解编译程序的生成方法和编译技术在软件开发中的应用。（二）本章重点、要点编译程序的概念、编译程序各阶段的划分及任务。（三）本章练习题和思考题1.1编译程序由哪几部分构成？简述各部分功能。1.2简述编译程序工作的基本过程，其各阶段的基本任务是什么？1.3.编译程序的生成方法有哪些？1.4画出编译程序总框。1.5描述词法规则、语法规则、语义规则各使用哪些描述工具？第二章文法和语言的基本知识（一）本章学习目标1.正确理解字母表和符号串的基本概念及其运算2.熟练掌握上下文无关文法的定义；3.熟练掌握形式语言的形式化定义方法；4.直接推导、推导、最左（右）推导、短语、直接短语、句型、句柄、句子及语言等重要概念；5.能为给定语言构造文法；6.能利用推导与语法分析树判断文法的二义性，并进行修改；7.了解文法和语言的分类。（二）本章重点、要点1.上下文无关文法的定义；2.直接推导、推导、句型、短语、直接短语、句柄、句子等重要概念；3.为给定语言构造文法；4.二义文法的判定。（三）本章练习题和思考题2.1写文法G1,G2,分别产生语言:(1)L(G1)={ambn｜m＞0，n.≥0}。(2)L(G2)={bmabm|m≥0}。2.2设文法G为：E→（E）｜abc(1)写出文法G所定义的语言L（G）。(2)判断abc、（（（abc））是否为L（G）的句子，说明理由。(3)画出句型（（E））的语法树，写出其短语、直接短语和句柄。2.3设有文法G[A]:Aa|b|e|A0|A1（1）试问TNvv和分别由哪些符号组成？（2）下列符号串a,a0,a0e01,0a,e111,e0011是否为该文法的句子？（3）写出文法G1[A]产生的语言第三章词法分析与有穷自动机（一）本章学习目标1.理解词法分析器的功能及单词符号及输出单词的形式；2.熟练掌握正规式与有穷自动机的定义形式；3.熟练掌握有NFA到DFA的转换及DFA的确定化；3.熟练掌握正规式与有穷自动机的等价性及其相互转换方法；4.熟练掌握正规文法与有穷自动机的定义形式；5.熟练掌握正规文法与有穷自动机的等价性及其相互转换方法；6.能依据状态转换图编写词法分析程序。（二）本章重点、要点1.词法分析器的功能2.正规式、正规文法与有穷自动机的定义形式；3.NFA到DFA的转换及DFA的确定化；4.正规式、正规文法与有穷自动机的等价性及其相互转换方法；5.词法分析程序的编写方法（三）本章练习题和思考题3.1设正则表达式ba*，(1)所定义的正规集（语言）L是什么？(2)构造识别L的NFA。(3)构造定义L的正则文法。3.2设正则表达式bba*aa，(1)所定义的正规集（语言）是什么？(2)构造识别L的最小DFA。(3)为其构造正则文法。3.3有文法G(S)：SaAcAbA|aA|a(1)给出文法G(S)所对应的正规式。(2)构造G(S)对应的NFA(3)将G(S)对应的NFA确定化(4)将(3)中的DFA最小化第四章语法分析（一）本章学习目标1.理解语法分析程序的功能；2.掌握自上而下语法分析原理；3.熟练掌握确定的自上而下语法分析的前提条件、LL(1)文法的判定及变换；4.熟练掌握LL(1)分析方法5.掌握自下而上语法分析原理；6.熟练掌握算符优先分析方法；7.熟练掌握算符优先文法的判定。8.了解优先函数的构造（二）本章重点、要点1.自上而下和自下而上语法分析的基本原理；2.LL(1)分析表的构造及其分析算法3.算符优先分析表的构造及其分析算法（三）本章练习题和思考题4.1考虑下面文法G1:S→a|∧|(T)T→T,S|S(1)消去G1的左递归，然后对每个非终结符写出不带回溯的递归子程序。(2)经过改写的文法是否是LL（1）的？给出它的预测分析表。4.2下面文法那些是LL（1）文法？（1）S→AbcA→a|εB→b|ε（2）S→AbA→a|B|εB→b|ε（3）S→ABBAA→a|εB→b|ε(4)S→aSe|BB→bBe|CC→cCe|d4.3简述算符优先分析过程。4.4设有表格结构文法G[S]：||(),|SaTTTSS(1)给出（a，（a，a））的最左、最右推导，并画出相应的语法树。(2)计算文法G[S]的FIRSTVT集和LASTVT集。(3)构造G[S]的优先关系表，并判断G[S]是否为算符优先文法。样卷一.(15分)编译程序由哪几部分构成？简述各部分功能。二.(15分)写出产生语言L(G1)的文法G1：L(G1)={ambmcn｜m，n≥0}。三.(25分).设语言L是字母表{0，1}上以0开头、以1结尾的所有序列的集合。（1）写出其正则表达式。（2）构造识别L的NFA。（3）构造识别L的DFA。（4）给出其最小DFA。四.(20分)设有文法G[S]:S→AA→B|AiBS→C|B+CT→A*|(（1）试画出句型C+Ci(的语法树，并给出该句型的短语、直接短语、句柄和素短语。（2）判断其是否为算符优先文法。五.(25分)设有文法G[S]:S→a|b|(T)T→T,S|S（1）计算每个非终结符的FIRSTVT和LASTVT。（2）构造算符优先关系分析表。（3）文法G[S]是算符优先文法吗？如果是，给出优先函数，并给出串(a,(a,a))的算符优先分析过程。附：各章练习题答案第一章1.1编译程序由哪几部分构成？简述各部分功能。参考答案：五个部分词法分析：接收输入源程序串，输出单词序列。语法分析：接收单词序列，识别出各种语法成分，并做语法检查。语义分析与中间代码生成：分析每个语法结构的静态语义，生成某种形式的中间代码。优化：在不改变程序执行结果的前提下，提高中间代码或目标代码的质量。目标代码生成：将中间代码转换成等价的目标代码。1.2简述编译程序工作的基本过程，其各阶段的基本任务是什么？参考答案：词法分析：接收输入源程序串，输出单词序列。语法分析：接收单词序列，识别出各种语法成分，并做语法检查。语义分析与中间代码生成：分析每个语法结构的静态语义，生成某种形式的中间代码。优化：在不改变程序执行结果的前提下，提高中间代码或目标代码的质量。目标代码生成：将中间代码转换成等价的目标代码。1.3编译程序的生成方法有哪些？参考答案：(1)手工编写编译程序(2)自编译(3)自动生成编译程序(4)移植1.4画出编译程序总框。参考答案见教材第4页图1.5。1.5描述词法规则、语法规则、语义规则各使用哪些描述工具？参考答案：描述词法规则工具：DFA、NFA、正规式、正规文法等。描述语法规则使用工具：上下文无关文法。描述语义规则各使用工具：属性文法、操作语义、公理语义、指称语义等。第二章2.1写文法G1,G2,分别产生语言:(1)L(G1)={ambn｜m＞0，n.≥0}参考答案：G1:SABAa|AaB|Bb(2)L(G2)={bmabm|m≥0}参考答案：G2:Sa|bSb2.2设文法G为：E→（E）｜abc(1)写出文法G所定义的语言L（G）。参考答案：L(G)={(ma)m|m≥0}(3)判断abc、（（（abc））是否为L（G）的句子，说明理由。参考答案：abc是L(G)的句子。因为存在推导：Eabc（（（abc））不是L（G）的句子因为不存在任何产生（（（abc）串的推导。(3)画出句型（（E））的语法树，写出其短语、直接短语和句柄。全部短语为：(E)、((E))。直接短语为：(E)。句柄为(E)。2.3设有文法G[A]:Aa|b|e|A0|A1(1)试问TNvv和分别由哪些符号组成？参考答案：VT={a,b,e,0,1}VN={A}(2)下列符号串a,a0,a0e01,0a,e111,e0011是否为该文法的句子？参考答案：a,a0,e111,e0011是该文法的句子。a0e01,0a不是该文法的句子。(3)写出文法G1[A]产生的语言参考答案：L(G1)是以a,b,e开头后跟若干个0或1的串。2.4写出产生语言L(G1)的文法G1：L(G1)={ambmcn｜m，n≥0}。参考答案：G1:SABA|aAbB|BcE(E)(E)第三章3.1设正则表达式ba*，(1)所定义的正规集（语言）L是什么？参考答案：L={bam|m≥0}。(2)构造识别L的NFA。参考答案：ABba(3)构造定义L的正则文法。参考答案：Ab|bBBa|aB3.2设正则表达式bba*aa，(1)所定义的正规集（语言）是什么？参考答案：L={bbamaa|m≥0}。(2)构造识别L的最小DFA。参考答案：BCbaAbDaEa(3)为其构造正则文法。Da3.3有文法G(S)：SaAcAbA|aA|a(1)给出文法G(S)所对应的正规式。参考答案：a(a|b)*ac(2)构造G(S)对应的NFA参考答案：参考答案：AbBBbCCaC|aDABaa,bCaDc(3)将G(S)对应的NFA确定化参考答案：ABaaCbbDac(4)将(3)中的DFA最小化参考答案：AB00C1C10第四章4.1考虑下面文法G1:S→a|∧|(T)T→T,S|S(3)消去G1的左递归，然后对每个非终结符写出不带回溯的递归子程序。(4)经过改写的文法是否是LL（1）的？给出它的预测分析表。参考答案：（1）消去G1的左递归：S→a|∧|(T)T→ST’T’→,ST’|ε递归子程序：PROCEDURES;IFsym=’a’THENADVANCEELSEIFsym=’∧’THENADVANCEELSEIFsym=’(’THENBEGINADVANCET;IFsym=’)’THENADVANCEELSEERRORENDELSEERROR;PROCEDURET;BEGINS;T’END;PROCEDURES;IFsym=’,’THENBEGINADVANCES;T’END;（2）是LL（1）文法。FIRST(S)={a,∧,(}FIRST(T)={a,∧,(}FIRST(T’)={,,ε}FOLLOW(S)={#,,,ε,)}FOLLOW(T)={)}FOLLOW(T’)={)}预测分析表如下：a,∧(）#SS→aS→∧S→(T)TT→ST’T→ST’T→ST’T’T’→,ST’T’→ε4.2下面文法那些是LL（1）文法？（1）S→AbcA→a|εB→b|ε参考答案：没有左递归且FIRST候选集不冲突且FIRST(A)∩FOLLOW(A)={a,ε}∩{b}=ФFIRST(B)∩FOLLOW(B)={b,ε}∩{c}=Ф所以该文法为LL（1）文法（2）S→AbA→a|B|εB→b|ε参考答案：FIRST(B)＝{b,ε}∩FIRST(ε)={ε}≠Ф所以该文法不是LL（1）文法（3）S→ABBAA→a|εB→b|ε参考答案：没有左递归且FIRST候选集不冲突FIRST(A)∩FOLLOW(A)={a,ε}∩{b,#}=ФFIRST(B)∩FOLLOW(B)={b,ε}∩{b,a,#}≠Ф所以该文法不是LL（1）文法(4)S→aSe|BB→bBe|CC→cCe|d参考答案：没有左递归且FIRST候选集不冲突所以该文法为LL（1）文法4.3简述算符优先分析过程。参考答案：算符优先分析法是一种简单、直观、广为使用的自下而上语法分析方法，它是依据算术表达式的四则运算过程而设计的一种方法，也适用于对一般的高级语言程序的分析。算符优先分析法的基本思想是，首先确定运算符（确切地说是终结符）之间的优先关系和结合性质，然后借助这种关系，比较相邻运算符之间的优先级来确定句型的可归约串，并进行归约。值得注意的是，算符优先分析过程虽然是自下而上归约过程，但它的可归约串未必是句柄，而是素短语。也就是说，算符优先分析过程不是一种规范归约。4.4设有表格结构文法G[S]：||(),|SaTTTSS(1)给出（a，（a，a））的最左、