下载文档原格式
编译原理习题⼀、填空题:1-01.编译程序的⼯作过程⼀般可以划分为词法分析,语法分析,语义分析，之间代码⽣成,代码优化等⼏个基本阶段,同时还会伴有表格处理和出错处理.1-02.若源程序是⽤⾼级语⾔编写的,⽬标程序是机器语⾔程序或汇编程序,则其翻译程序称为编译程序.1-03.编译⽅式与解释⽅式的根本区别在于是否⽣成⽬标代码.1-04.翻译程序是这样⼀种程序,它能够将⽤甲语⾔书写的程序转换成与其等价的⽤⼄语⾔书写的程序. 1-05.对编译程序⽽⾔,输⼊数据是源程序,输出结果是⽬标程序.1-06.如果编译程序⽣成的⽬标程序是机器代码程序,则源程序的执⾏分为两⼤阶段:编译阶段和运⾏阶段.如果编译程序⽣成的⽬标程序是汇编语⾔程序,则源程序的执⾏分为三个阶段:编译阶段,汇编阶段和运⾏阶段.1-07.若源程序是⽤⾼级语⾔编写的，⽬标程序是机器语⾔程序或汇编程序，则其翻译程序称为编译程序。
1-08.⼀个典型的编译程序中，不仅包括词法分析、语法分析、中间代码⽣成、代码优化、⽬标代码⽣成等五个部分，还应包括表格处理和出错处理。
其中，词法分析器⽤于识别单词。
1-09.编译⽅式与解释⽅式的根本区别为是否⽣成⽬标代码。
2-01.所谓最右推导是指：任何⼀步αβ都是对α中最右⾮终结符进⾏替换的。
2-02.⼀个上下⽂⽆关⽂法所含四个组成部分是⼀组终结符号、⼀组⾮终结符号、⼀个开始符号、⼀组产⽣式。
2-03.产⽣式是⽤于定义语法成分的⼀种书写规则。
2-04.设G[S]是给定⽂法，则由⽂法G所定义的语⾔L(G)可描述为：L(G)＝{x│S x,x∈V T*}。
2-05.设G是⼀个给定的⽂法，S是⽂法的开始符号，如果S x（其中x∈V*），则称x是⽂法的⼀个句型。
2-06.设G是⼀个给定的⽂法，S是⽂法的开始符号，如果S x(其中x∈V T*),则称x是⽂法的⼀个句⼦。
3-01.扫描器的任务是从源程序中识别出⼀个个单词符号。
4-01.语法分析最常⽤的两类⽅法是⾃上⽽下和⾃下⽽上分析法。
编译原理试题及答案一、选择题1. 编译器的主要功能是什么？A. 程序设计B. 程序翻译C. 程序调试D. 数据处理答案：B2. 下列哪一项不是编译器的前端处理过程？A. 词法分析B. 语法分析C. 语义分析D. 代码生成答案：D3. 在编译原理中，词法分析器的主要作用是什么？A. 识别程序中的关键字和标识符B. 将源代码转换为中间代码C. 检查程序的语法结构D. 确定程序的运行环境答案：A4. 语法分析通常采用哪种方法？A. 自顶向下分析B. 自底向上分析C. 正则表达式匹配D. 直接解释执行答案：B5. 语义分析的主要任务是什么？A. 检查程序的语法结构B. 检查程序的类型安全C. 识别程序中的变量和常量D. 将源代码转换为机器代码答案：B二、简答题1. 简述编译器的工作原理。
答案：编译器的工作原理主要包括以下几个步骤：词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成。
词法分析器将源代码分解成一系列的词素；语法分析器根据语法规则检查词素序列是否合法；语义分析器检查程序的语义正确性；中间代码生成器将源代码转换为中间代码；代码优化器对中间代码进行优化；最后，目标代码生成器将优化后的中间代码转换为目标机器代码。
2. 什么是词法分析器，它在编译过程中的作用是什么？答案：词法分析器是编译器前端的一个组成部分，负责将源代码分解成一个个的词素（tokens），如关键字、标识符、常量、运算符等。
它在编译过程中的作用是为语法分析器提供输入，是编译过程的基础。
三、论述题1. 论述编译器中的代码优化技术及其重要性。
答案：代码优化是编译过程中的一个重要环节，它旨在提高程序的执行效率，减少资源消耗。
常见的代码优化技术包括：常量折叠、死代码消除、公共子表达式消除、循环不变代码外提、数组边界检查消除等。
代码优化的重要性在于，它可以显著提高程序的运行速度和性能，同时降低程序对内存和处理器资源的需求。
四、计算题1. 给定一个简单的四则运算表达式，请写出其对应的逆波兰表达式。
第一章1、将编译程序分成若干个“遍”就是为了。
a．提高程序得执行效率b．使程序得结构更加清晰c．利用有限得机器内存并提高机器得执行效率d．利用有限得机器内存但降低了机器得执行效率2、构造编译程序应掌握。
a．源程序b．目标语言c．编译方法d．以上三项都就是3、变量应当。
a．持有左值b．持有右值c．既持有左值又持有右值d．既不持有左值也不持有右值4、编译程序绝大多数时间花在上。
a．出错处理b．词法分析c．目标代码生成d．管理表格5、不可能就是目标代码。
a．汇编指令代码b．可重定位指令代码c．绝对指令代码d．中间代码6、使用可以定义一个程序得意义。
a．语义规则b．语法规则c．产生规则d．词法规则7、词法分析器得输入就是。
a．单词符号串b．源程序c．语法单位d．目标程序8、中间代码生成时所遵循得就是- 。
a．语法规则b．词法规则c．语义规则d．等价变换规则9、编译程序就是对。
a．汇编程序得翻译b．高级语言程序得解释执行c．机器语言得执行d．高级语言得翻译10、语法分析应遵循。
a．语义规则b．语法规则c．构词规则d．等价变换规则二、多项选择题1、编译程序各阶段得工作都涉及到。
a．语法分析b．表格管理c．出错处理d．语义分析e．词法分析2、编译程序工作时，通常有阶段。
a．词法分析b．语法分析c．中间代码生成d．语义检查e．目标代码生成三、填空题1、解释程序与编译程序得区别在于。
2、编译过程通常可分为5个阶段，分别就是、语法分析、代码优化与目标代码生成。
3、编译程序工作过程中，第一段输入就是，最后阶段得输出为程序。
4、编译程序就是指将程序翻译成程序得程序。
单选解答1、将编译程序分成若干个“遍”就是为了使编译程序得结构更加清晰，故选b。
2、构造编译程序应掌握源程序、目标语言及编译方法等三方面得知识，故选d。
3、对编译而言，变量既持有左值又持有右值，故选c。
4、编译程序打交道最多得就就是各种表格，因此选d。
5、目标代码包括汇编指令代码、可重定位指令代码与绝对指令代码3种，因此不就是目标代码得只能选d。
第一章1、将编译程序分成若干个“遍”是为了。
b．使程序的结构更加清晰2、构造编译程序应掌握。
a．源程序b．目标语言c．编译方法3、变量应当。
c．既持有左值又持有右值4、编译程序绝大多数时间花在上。
d．管理表格5、不可能是目标代码。
d．中间代码6、使用可以定义一个程序的意义。
a．语义规则7、词法分析器的输入是。
b．源程序8、中间代码生成时所遵循的是- 。
c．语义规则9、编译程序是对。
d．高级语言的翻译10、语法分析应遵循。
c．构词规则二、多项选择题1、编译程序各阶段的工作都涉及到。
b．表格管理c．出错处理2、编译程序工作时，通常有阶段。
a．词法分析b．语法分析c．中间代码生成e．目标代码生成三、填空题1、解释程序和编译程序的区别在于是否生成目标程序。
2、编译过程通常可分为5个阶段，分别是词法分析、语法分析中间代码生成、代码优化和目标代码生成。
3、编译程序工作过程中，第一段输入是源程序，最后阶段的输出为标代码生成程序。
4、编译程序是指将源程序程序翻译成目标语言程序的程序。
一、单项选择题1、文法G：S→xSx|y所识别的语言是。
a. xyxb. (xyx)*c.x n yx n(n≥0) d. x*yx*2、文法G描述的语言L(G)是指。
a. L(G)={α|S+⇒α , α∈V T*}b. L(G)={α|S*⇒α, α∈V T*}c. L(G)={α|S*⇒α,α∈(V T∪V N*)} d. L(G)={α|S+⇒α, α∈(V T∪V N*)}3、有限状态自动机能识别。
a. 上下文无关文法b. 上下文有关文法c.正规文法d. 短语文法4、设G为算符优先文法，G 的任意终结符对a、b有以下关系成立。
a. 若f(a)>g(b)，则a>bb.若f(a)<g(b)，则a<bc. a~b都不一定成立d. a~b一定成立5、如果文法G是无二义的，则它的任何句子α。
a. 最左推导和最右推导对应的语法树必定相同b. 最左推导和最右推导对应的语法树可能不同c. 最左推导和最右推导必定相同d. 可能存在两个不同的最左推导，但它们对应的语法树相同6、由文法的开始符经0步或多步推导产生的文法符号序列是。
编译原理考试题及答案一、选择题（每题5分，共20分）1. 编译器的主要功能是什么？A. 代码优化B. 代码翻译C. 代码调试D. 代码运行答案：B2. 下列哪个选项不属于编译器的前端部分？A. 词法分析B. 语法分析C. 语义分析D. 代码生成答案：D3. 在编译原理中，文法的产生式通常表示为：A. A -> αB. A -> βC. A -> γD. A -> δ答案：A4. 下列哪个算法用于构建语法分析树？A. LL(1)分析B. LR(1)分析C. SLR(1)分析D. LALR(1)分析答案：A二、填空题（每空5分，共20分）1. 编译器的前端通常包括词法分析、语法分析和________。
答案：语义分析2. 编译器的后端主要负责________和目标代码生成。
答案：代码优化3. 编译器中的词法分析器通常使用________算法来识别单词。
答案：有限自动机4. 语法分析中，________分析是一种自顶向下的分析方法。
答案：递归下降三、简答题（每题10分，共30分）1. 简述编译器的作用。
答案：编译器的主要作用是将高级语言编写的源代码转换成计算机能够理解的低级语言或机器代码，以便执行。
2. 解释一下什么是语法制导翻译。
答案：语法制导翻译是一种翻译技术，它利用源语言的语法信息来指导翻译过程，使得翻译过程能够更好地理解源代码的语义。
3. 什么是词法分析器？答案：词法分析器是编译器前端的一部分，它的任务是将源代码文本分解成一系列的标记（tokens），这些标记是源代码的最小有意义的单位。
四、计算题（每题10分，共30分）1. 给定一个简单的文法G(E)：E → E + T | TT → T * F | FF → (E) | id请计算文法的非终结符号E的FIRST集和FOLLOW集。
答案：E的FIRST集为{(, id}，FOLLOW集为{), +, $}。
2. 假设编译器在进行语法分析时，遇到一个语法错误的代码片段，请简述编译器如何处理这种情况。
1、正规文法又称 DA、0型文法B、1型文法C、2型文法D、3型文法2、对于无二义性的文法，规范归约是 BA. 最左推导B. 最右推导的逆过程C.最左归约的逆过程D.最右归约的逆过程。
3、扫描器的任务是从源程序中识别出一个个单词符号。
4、程序所需的数据空间在程序运行前就可确定，称为 A 管理技术。
A 静态存储B 动态存储C 栈式存储D 堆式存储5、编译过程中，语法分析器的任务是（B）。
①分析单词是怎样构成的②分析单词串是如何构成语句和说明的③分析语句和说明是如何构成程序的④分析程序的结构A、②③B、②③④C、①②③D、①②③④6、文法G：E→E+T|T T→T*P|P P→ (E)| i则句型P+T+i的句柄和最左素短语分别为 B 。
A、P+T和iB、P和P+TC、i和P+T+iD、P和P7、四元式之间的联系是通过B实现的A.指示器B.临时变量C.符号表D.程序变量8、程序语言的单词符号一般可以分为保留字、标识符、常数、运算符、界符等等。
9、下列 B 优化方法是针对循环优化进行的。
A．删除多余运算B．删除归纳变量C．合并已知量D．复写传播10、若文法G 定义的语言是无限集，则文法必然是 AA、递归的B、前后文无关的C、二义性的D、无二义性的11、文法G 产生的D的全体是该文法描述的语言。
A、句型B、终结符集C、非终结符集D、句子12、Chomsky 定义的四种形式语言文法中，0 型文法又称为 A文法；1 型文法又称为 C 文法。
A.短语文法B.上下文无关文法C.上下文有关文法D.正规文法A.短语文法B.上下文无关文法C.上下文有关文法D.正规文法13、语法分析最常用的两类方法是自顶向下和自底向上分析法。
14、一个确定的有穷自动机DFA是一个 A 。
A 五元组（K，∑，f, S, Z）B 四元组（V N，V T，P，S）C 四元组（K，∑，f，S）D 三元组(V N,V T,P)A、语法B、语义C、代码D、运行15、 B不属于乔姆斯基观点分类的文法。
编译原理复习题及答案一、选择题1．一个正规语言只能对应(B)A 一个正规文法B 一个最小有限状态自动机2．文法G[A]：A→εA→aB B→Ab B→a是(A)A 正规文法B 二型文法3．下面说法正确的是(A)A 一个SLR（1）文法一定也是LALR（1）文法B 一个LR（1）文法一定也是LALR（1）文法4．一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL（1）文法的(A)A 必要条件B 充分必要条件5．下面说法正确的是(B)A 一个正规式只能对应一个确定的有限状态自动机B 一个正规语言可能对应多个正规文法6．算符优先分析与规范归约相比的优点是(A)A 归约速度快B 对文法限制少7．一个LR（1）文法合并同心集后若不是LALR（1）文法(B)A 则可能存在移进/归约冲突B 则可能存在归约/归约冲突C 则可能存在移进/归约冲突和归约/归约冲突8．下面说法正确的是(A)A Lex是一个词法分析器的生成器B Yacc是一个语法分析器9．下面说法正确的是(A)A 一个正规文法也一定是二型文法B 一个二型文法也一定能有一个等价的正规文法10．编译原理是对(C)。
A、机器语言的执行B、汇编语言的翻译C、高级语言的翻译D、高级语言程序的解释执行11．(A)是一种典型的解释型语言。
A．BASIC B．C C．FORTRAN D．PASCAL12．把汇编语言程序翻译成机器可执行的目标程序的工作是由(B)完成的。
A. 编译器B. 汇编器C. 解释器D. 预处理器13．用高级语言编写的程序经编译后产生的程序叫(B)A．源程序 B．目标程序C．连接程序D．解释程序14．(C)不是编译程序的组成部分。
A.词法分析程序B.代码生成程序C.设备管理程序D.语法分析程序15．通常一个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成等六个部分，还应包括(C)。
A．模拟执行器B．解释器 C．表格处理和出错处理D．符号执行器16．编译程序绝大多数时间花在(D)上。
第三章词法分析练习3.1给出一个正则表达式和自动机，使之表示满足下面条件的0、1序列：1）只包含两个1。
2）不包含连续的1。
3）包含偶数个1。
3.2写出下面符号串集的正则表达式：1）{a,b,c}a偶数出现2）{a,b,c}不包含子串baa3）二进制数，大于1010014)二进制数，4的倍数5)偶数个0奇数个1的0/1串3.3构造识别下列正则表达式定义的NFA：1)(a|(b)+2)(a*|(b*)*3)(a|(bc)*d*4)((0|1)*(2|3)*)|00115)(a|b)*abb(a|b)*3.4为下列正则表达式构造极化的DFA:1)(a|b)*a(a|b)2)(a|b)*a(a|b)(a|b)3.5利用自动机原理构造模式匹配程序，即构造一个程序，使它能识别给定a/b串是不是a i b j a k b m类串：，其中i和j是大于等于0的整数，而k和m是大于0的整数。
3.5将下面不确定自动机NFA转换为确定自动机DFA:3.6将下面不确定自动机NFA转换为确定自动机DFA:3.7试将下面不确定自动机NFA转换为确定自动机DFA:3.8试写出下面确定自动机DFA的正则表达式：3.9设置一个名字表NameL和整数表ConstL，当遇到标识符时，将其字符串送入名字表NameL，并把其名字表地址作为标识符的Value值。
整常数情形也一样，不要求翻译成二进制数。
要求在NameL表和ConstL表中没有相同元素。
试用C语言写一个针对上述单词集的词法分析器。
单词class valuebegin BeginSymbend EndSymbvar VarSymbinteger IntSymbif IfSymbthen ThenSymbelse ElseSymb;SemiSymb:ColonSymb:=AssigSymb<LittleSymb<=LittEquiSymb标识符IdentSymb名字表地址整常数ConstSymb常数表地址3.10实数的语法定义如下面所述：<实数>::=<整数部分><小数部分><指数部分><整数部分>::=<数字>|<整数部分><数字><小数部分>::=ε|.<整数部分><指数部分>::=ε|e<指数符号><整数部分><指数符号>::=ε|+|-试写出实数的非确定自动机。
3.11试写出3.10题中实数的确定自动机；3.12试写出3.10题中实数的正则表达式。
3.13当构造词法分析器时，根据单词的正则表达式定义首先构造NFA，之后将NFA转换成DFA，并用其DFA进行词法分析。
从正则表达式到NFA的转换速度快，而NFA到DFA的转换速度比较慢，因此在某些场合下，用NFA并按NFA到DFA的转换思想进行词法分析可能是很有意思的。
就是说，在NFA的一个状态下，遇到一个字符时，用NFA到DFA时的构造技术确定下一状态。
试写出算法。
第四章语法分析练习4.1将下列正则表达式转换成上下文无关文法：1）((ab *a)|(ba *b))|ε2)((0|1)+"."(0|1)*)|(((0|1)*"."(0|1)+))3)(a|b)*a(a|b)(a|b)4.2我们称如下形式的上下文无关文法叫做ε-正则文法，即其产生式具有下面形式：A→aB 或A→εB 或A→a其中A 和B 是非终极符，a 是终极符。
要求把下面自动机（确定）转换成ε-正则文法,其中A 是初始状态，而C 是接受状态。
确定自动机状态转换矩阵4.3把下面自动机（非确定）转换成上ε-正则文法,其中A 和B 是初始状态，而C 是接受状态。
非确定自动机状态转换矩阵4.4已给定下面ε-正则文法,试将其转换成非确定自动机。
S→εA |εBA→aA |aC |bB |bC|εB B→aA |aC |bB |εC C→aB |aC |ε4.5试将题4.4中给定的ε-正则文法转换成确定自动机。
4.6试将题4.4中给定的ε-正则文法转换成正则表达式。
提示：用消除法消除开始符以外的非终极符。
关键知识：C→aC |α，可转换成C→a *α,4.7试给出将ε-正则文法,转换成确定正则文法，但允许开始符有ε产生式。
这相当于从NFA 到DFA 的转换。
4.8形如A→A α的产生式称为左递归的，类似地称B→βB 的产生式为右递归的。
证明如果一个非终极符既有左递归式，又有右递归式，则文法一定有二义性。
4.9试给出一个算法，它判定文法中有哪些非终极符是不可能出现于任何句型中，称这种非终极符为不可到达符号。
4.10试给出一个算法，它判定文法中有哪些非终极符是不可能导出任何终极符串。
4.11形如A→ε的产生式为空产生式，以例说明任何含空产生式的文法均可转换成无空产生式的等价文法（可能只差一个空句子）。
4.12下列哪些文法是LL(1)文法？ab A A B B C BCCab εA A,C B,CB B A,C BCCB,C1）S→Abc2）S→Ab3）S→ABBA4）S→a S eA→a A→a A→a S→BA→εA→B A→εB→b B eB→b A→εB→b B→CB→εB→b B→εC→c C cB→εC→d4.13对下面文法构造LL(1)分析表：E→-EE→(E)E→Var EtailEtail→-EEtail→εVar→id VtailVtail→(E)Vtail→ε4.14试写出用上述LL(1)分析器分析i--i(i)的过程，其中i是标识符。
4.15试将下列文法转换为LL(1)文法DL→DL;DDL→DD→idL:TypeidL→ididL→idL,idType→StypeType→array(STypeL)of TypeStype→idStype→Bound..BoundBound→Sign IntLiteralBound→idSign→+Sign→-STypeL→STypeL,StypeSTypeL→Stype4.16称一个文法是greibach规范型(GNF)文法，如果每个产生式具有形式A→tβ，其中t是终极符，β是任何符号串。
设G是任一不含空句子的文法，试给出G到GNF的转换算法。
4.17证明下列问题：1)左递归文法不是LL(1)文法。
2)证明LL(1)文法是无二义性文法。
1)若文法G没有空产生式，且每个非终极符的产生式均以不同的终极符打头，则G顶是LL(1)文法。
4.18为下面文法构造LR状态机，并给出相应的goto表。
Prog→Block$Block→begin SL endSL→SL;SSL→SS→BlockS→V:=EV→idV→id[E]E→E+TE→TT→VT→(E)4.19以下文法中哪些不是LR(0)?为什么?1)Q→SL$SL→SL;SSL→SS→null2)Q→SL$SL→S;SLSL→SSL→null3)Q→SL$SL→SL;SLSL→SS→null4)Q→SL$SL→null SLtailSLtail→εSLtail→;SL4.20证明对应LL(1)文法的LR状态机的每个状态的项目集恰有一个基本项目。
4.21为4.18题中给出的文法构造一个LR(1)状态机。
4.22下面的文法中哪一些是LR(1)？LALR(1)？SLR(1)？说明你的理由。
4.23为4.18中的文法构造SLR(1)_ACTION 表。
4.24以4.21中为4.18文法构造的LR(1)状态机为基础，合并同心项，即合并有共同核心的项目，建立LALR(1)状态机。
4.25从为4.18构造的LR(0)状态机出发，利用向前看符号的传播与生成算法，确定LALR(1)向前看符号集，并与4.24中通过合并的方法产生的结果进行比较。
4.26证明任何无ε-产生式的LL(1)文法都是LR(0)文法。
4.27证明存在不是LL(1)的LR(0)文法、SLR 文法和LALR(1)文法。
4.28证明所有LL(1)文法都是LR(1)文法。
第五章语义分析练习5.1试写出下面类型的内部表示：1)array[1..5]of array[1..10]ofrecord i：integer；b：boolean end2)record r：record x：real；y：integer end；a：array[1..10]of booleanend5.2试用C语言描述读数组类型的Token序列并构造其类型树的算法。
5.3试用C语言描述读记录类型的Token序列并构造其类型树的算法。
5.4试用C语言描述读联合类型的Token序列并构造其类型树的算法。
5.5试写出按结构等价概念判定类型等价的程序，其输入是两个类型树的根指针，输出是0或1，0表示不等价，1表示等价。
5.6假设给定数组类型树的根结点（指针），并且假设树结点中没设置记录空间大小的size域。
试写出函数EvaluateArraySize，其输入是数组类型树根结点的指针，而输出是表示大小的整数。
5.7假设给定记录类型树的根结点（指针），并且假设树结点中没设置记录空间大小的size域。
试写出函数EvaluateRecordSize，其输入是记录类型树根结点的指针，而输出是表示大小的整数。
5.8假设给定联合类型树的根结点（指针），并且假设树结点中没设置记录空间大小的size域。
试写出函数EvaluateUnionSize，其输入是联合类型树根结点的指针，而输出是表示大小的整数。
5.9试写出一个过程SearchFieldType,其功能是只要给定记录类型树的根结点Ptr和一个域名fid，则在FPtr中返回fid类型数的结点指针。
5.10设当前层数为L，可用偏移量Offset值为101，且有下面程序，写出本层符号表的内容。
const m=333；n=444；type at=array[1..10]of real；rt=record i,j:integer end；var a,b：at；x,y：real；5.11设当前层数为L，当前偏移量为Offset，且有下面过程首部，试写出符号表内容，其中at见5.2题。
var x,y：at；function f（val a:at；var b:at；var x:real）:nteger；5.12表达式的语义检查都包括哪些内容？5.13赋值语句的语义检查包括哪些内容？5.14hile语句的语义检查包括哪些内容？5.15答如何检查通过goto语句跳入结构语句内部的错误？5.16程调用语句的语义检查包括哪些内容？5.17要说明如何检查实参与形参的相容性。
5.18试用C语言写出标识符表(顺序式)的界面程序（填表,查表），其中标识符属性可定义为一个整数。
