编译程序总复习——例题

编译原理复习例题(有些内容没有覆盖，比如优化、SLR（1）、LR（1）、LALR（1）等。

但要求至少要按照作业题的范围复习。

)一选择题1．编译的各阶段工作都涉及。

[A]词法分析[B]表格管理 [C]语法分析 [D]语义分析2．型文法也称为正规文法。

[A] 0 [B] 1 [C] 2 [D] 33．文法不是LL(1)的。

[A]递归 [B]右递归 [C]2型 [D]含有公共左因子的4．文法E→E+E|E*E|i的句子i*i+i*i有棵不同的语法树。

[A] 1 [B] 3 [C] 5 [D] 75．文法 S→aaS|abc 定义的语言是。

[A]{a2k bc|k>0} [B]{a k bc|k>0}[C]{a2k-1bc|k>0} [D]{a k a k bc|k>0}6．若B为非终结符，则 A→α.Bβ为。

[A]移进项目 [B]归约项目 [C]接受项目 [D]待约项目7．同心集合并可能会产生新的冲突。

[A]二义 [B]移进/移进 [C]移进/归约 [D]归约/归约8．代码优化时所依据的是。

[A]语法规则 [B]词法规则[C]等价变换规则 [D]语义规则9．表达式a-(-b)*c的逆波兰表示（@为单目减）为。

[A]a-b@c* [B]ab@c*- [C]ab@- [D]ab@c-*10．过程的DISPLAY表是用于存取过程的。

[A]非局部变量[B]嵌套层次 [C]返回地址 [D]入口地址二填空题1．词法分析阶段的任务式从左到右扫描字符流，从而逐个识别一个个的单词。

2．对于文法G[E]：E→T|E+T T→F|T*F F→P^F|P P→(E)|i，句型T+T*F+i的句柄是。

3．最右推导的逆过程称为规范归约，也称为最左归约。

4．符号表的每一项是由名字栏和两个栏目组成。

在目标代码生成阶段，符号表是的依据。

三判断题（认为正确的填“T”，错的填“F”）【】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．产生规则10．测试一个编译程序时使用的测试数据是。

A．源程序B．中间代码C．目标程序D．任意数据11．可以作为目标代码的语言是。

A．高级语言B．中间语言C．低级语言D．程序设计语言12．编译程序检查、处理源程序中的错误具体指的是。

A．词法错误B．语法错误C．语义错误D．以上三项都是13．同正则表达式(a | b)+等价的正则表达式是。

A．(a | b) * B．(a | b) (a | b) *C．(a b)* (a b) D．(a | b)| (a | b)*14．词法分析器的输出结果是。

A．单词自身B．单词的机内符C．单词的词义信息D．单词的词法信息15．如果一个正则表达式所代表的集合是无穷的，则它必含有运算。

A．连接运算：“·”B．或运算：“|”C．闭包运算：“*”D．括弧：“（”和“）”16．称有限自动机A1和A2等价是指。

A．A1和A2都是定义在一个字母表Σ上的有限自动机B．A1和A2状态数和有向边数相等C．A1和A2状态数或有向边数相等D．A1和A2所能识别的字符串集合相同17．DFA同NFA的不同之处是。

编译原理期末总结复习编译原理期末总结复习篇一：一、简答题1.什么是编译程序？答：编译程序是一种将高级语言程序(源程序)翻译成低级语言(目标程序)的程序。

将高级程序设计语言程序翻译成逻辑上等价的低级语言(汇编语言,机器语言)程序的翻译程序。

2.请写出文法的形式定义？答：一个文法G抽象地表示为四元组 G=（Vn,Vt,P,S）–其中Vn表示非终结符号– Vt表示终结符号，Vn∪Vt=Ｖ(字母表)，Vn∩Vt=φ– S是开始符号，–P是产生式，形如：α→β(α∈V+且至少含有一个非终结符号，β∈V*)3.语法分析阶段的功能是什么？答：在词法分析的基础上，根据语言的语法规则，将单词符号串分解成各类语法短语(例：程序、语句、表达式)。

确定整个输入串是否构成语法上正确的程序。

4.局部优化有哪些常用的技术？答：优化技术1—删除公共子表达式优化技术2—复写传播优化技术3—删除无用代码优化技术4—对程序进行代数恒等变换（降低运算强度）优化技术5—代码外提优化技术6—强度削弱优化技术7—删除归纳变量优化技术简介——对程序进行代数恒等变换（代数简化）优化技术简介——对程序进行代数恒等变换（合并已知量）5．编译过程分哪几个阶段？答：逻辑上分五个阶段：词法分析、语法分析、语义分析与中间代码生成、代码优化、目标代码生成。

每个阶段把源程序从一种表示变换成另一种表示。

6. 什么是文法？答：文法是描述语言的语法结构的形式规则。

是一种工具，它可用于严格定义句子的结构；用有穷的规则刻划无穷的集合；文法是被用来精确而无歧义地描述语言的句子的构成方式；文法描述语言的时候不考虑语言的含义。

7. 语义分析阶段的功能是什么？答：对语法分析所识别出的各类语法范畴分析其含义，进行初步的翻译(翻译成中间代码)；并对静态语义进行审查。

8.代码优化须遵循哪些原则？答：等价原则：不改变运行结果有效原则：优化后时间更短，占用空间更少合算原则：应用较低的代价取得较好的优化效果9.词法分析阶段的功能是什么？答：逐个读入源程序字符并按照构词规则切分成一系列单词任务：读入源程序，输出单词符号—滤掉空格，跳过注释、换行符—追踪换行标志，指出源程序出错的行列位置—宏展开，……10.什么是符号表？答：符号表在编译程序工作的过程中需要不断收集、记录和使用源程序中一些语法符号的类型和特征等相关信息。

一、是非题1.设∑为{a，b}，则a，ba，{∑}，Φ都是∑上的正规式。

（）2.对于上下文无关文法G[S]，若 S⇒αAB ⇒αβγ则A →γ一定是一条产生式规则，其中α,β,γ∈（V T∨V N）*。

（）3.对于逆波兰后缀式，无论从哪头开始分析均可得到唯一正确的分解。

（）4.LR（0）分析法是一种规范归约法。

（）5.算符优先分析法只能用来分析算符优先文法。

（）6.解释程序和编译程序一样，生成目标代码。

（）7.编译程序生成的目标代码只能是机器语言。

（）8.等价文法是指两个文法完全相同。

（）9.正规式所确定的语言为正规集。

（）10.对于字母表Σ上的任一NFA M'，必存在Σ上与NFA M' 等价的DFA M。

（）11.词法分析中单词符号是用上下文无关文法描述的，语法分析中语法类是用正则文法描述的。

（）12.算符优先关系表不一定存在对应的优先函数。

（）13.每个文法都能改写为LL(1)文法。

（）14.存在这样一些语言，它们能被确定的有穷自动机识别，但不能用正规表达式表示（）15.不存在正规文法能产生语言：L={a n b n|n>=1}（）16.算符优先分析法每次都是对素短语进行规约。

（）二、简答题1、编译过程一般分为几个阶段？各阶段的输入输出分别为什么？2、文法G为：S→aABA→aB→α|β|γ则判断G为LL（1）文法的条件是：3、文法G=({A, B, S}, {a, b, c}, P, S)其中P为：S→Ac|aBA→abB→bc该文法是二义的吗？说明理由。

4、文法G=({E}, {+, *, i, (, )}, P, E)其中P为：E→iE→E+EE→E*EE→(E)该文法是二义的吗？说明理由。

三、最左、最右推导及语法树1、令文法为E→T|E+T|E-TT→F|T*F|T/FF→（E）|i1）给出i+i*i的最左推导和最右推导；2）E=e+t=e+t*f=e+f*f=t+f*f=f+f*f……. 3）E=e+t=t+t=f+t=f+t*f=f+f*f=…….. 4）给出i+i*i的最左推导语法树。

1》编译程序的框架图与功能块：（1）画出编译程序的总体结构，并简述各部分的主要功能：七个部分（2）编译程序的结构分为几个阶段，各阶段的任务是什么？答编译程序总框架（1）词法分析器，又称扫描器，输入源程序，进行词法分析，输出单词符号。

（2）语法分析器，简称分析器，对单词符号串进行语法分析（根据语法规则进行推导或规约），识别出各类语法单位，最终判断输入串是否构成语法上正确的“程序”。

（3）语义分析与中间代码产生器，按照语义规则对语法分析器归约出（或推导出）的语法单位进行语义分析并把它们翻译成一定形式的中间代码。

（4）优化器，对中间代码进行优化处理。

（5）目标代码生成器，把中间代码翻译成目标程序。

（6）表格管理，登记源程序的各类信息，编译各阶段的进展状况。

（7）出错管理，把错误信息报告给用户。

编译程序的结构分为五个阶段：（1）词法分析.任务是：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词（亦称单词符号或简称符号），如基本字，标识符，常熟，算符和界符。

（2）。

语法分析，任务是：在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位（语法范畴）。

（3）语义分析与中间代码产生。

任务：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。

（4）优化。

任务在于对前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效（省时间和空间）的目标代码。

（5）目标代码生成。

任务是：把中间代码（或优化出理之后）变换成特定机械上的低级语言代码。

2》．重要概念：a. 编译程序：是指能够把源语言程序转换成逻辑上等价的目标语言程序的一个程序。

b. 单词符号：是语言的基本组成成分，是人们理解和编写程序的基本要素，是语言中具有独立意义的最基本结构，它一般包括：基本字、标识符、常数、运算符和界符等c. 中间代码：是一种含义明确，便于处理的记号系统，它通常独立于具体的硬件。

总复习■第1章1、编译程序是一种翻译程序，它将高级语言所写的源程序翻译成等价的机器语言或者汇编语言的目标程序。

2、编译程序是计算机系统中重要的系统软件！3、解释程序与编译程序的主要区别是解释程序在执行过程中不产生目标程序。

4、编译的各个阶段。

答：整个编译过程可以分为5个阶段：词法分析，语法分析，语义分析及中间代码生成，代码优化和目标代码生成。

5、编译程序的结构框图或步骤。

6、遍（趟）：是对源程序或源程序的中间结果从头到尾扫描一遍，并作有关加工处理，生成新的中间结果或目标程序的过程。

■第2章1、符号串的基本运算。

2、简单的说文法由产生式组成；产生式中的符号分为两类：终结符号和非终结符号。

3、推导（最左、最右）、句型、句子、短语、句柄4、乔姆斯基层次中：L3 ⊂ L2 ⊂ L1 ⊂ L0■第2章例题已知文法G[E]：E→T|E+T|E-TT→F|T*F|T/FF→(E)|i（1）该文法的开始符号是什么？（2）请给出该文法的终结符号集合VT和非终结符号集合VN。

（3）找出句型T+T*F+i的所有短语、直接（简单）短语、句柄。

■第3章1、词法分析程序的输出是单词符号序列。

2、DFA的三种表示形式——状态转移图、状态转换表和五元组表示（Q, ∑, f, S, Z ）；3、正规式向DFA的转换：（1）正规式——NFA;（转换原则见下页）（2）NFA——DFA；（3）DFA的最小化。

4、DFA向正规式的转换。

正则式向NFA转换的原则：例：构造与正则表达式R=ba(a|b)*等价的状态最少的DFA，并写出该DFA的五元组形式或状态转换表。

■第4章1、语法分析方法的各种分类；2、LL(1)分析方法。

提示：在此算法中注意First集和Follow集的求法。

并且一定要注意分析过程中步骤要完整。

（分析步骤见下页总结）例：文法：S◊a|^|(T) T◊T,S|S试判断该文法是否是LL(1)文法。

习题4：P100 4.3 4.7 4.9■LL(1)分析方法相关知识总结1、消除文法中的左递归或提取左因子；（1）简单直接左递归的消除A →βA’A →Aα| β→A’ →αA’| ε（2）将文法G：A→αβ|αγ提取左因子。