下载文档原格式
编译原理复习题及答案一、选择题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)上。
编译原理期末总结复习（经典版）编制人：__________________审核人：__________________审批人：__________________编制单位：__________________编制时间：____年____月____日序言下载提示：该文档是本店铺精心编制而成的，希望大家下载后，能够帮助大家解决实际问题。
文档下载后可定制修改，请根据实际需要进行调整和使用，谢谢!并且，本店铺为大家提供各种类型的经典范文，如公文写作、报告体会、演讲致辞、党团资料、合同协议、条据文书、诗词歌赋、教学资料、作文大全、其他范文等等，想了解不同范文格式和写法，敬请关注!Download tips: This document is carefully compiled by this editor. I hope that after you download it, it can help you solve practical problems. The document can be customized and modified after downloading, please adjust and use it according to actual needs, thank you!In addition, this shop provides you with various types of classic sample essays, such as official document writing, report experience, speeches, party and group materials, contracts and agreements, articles and documents, poems and songs, teaching materials, essay collections, other sample essays, etc. Learn about the different formats and writing styles of sample essays, so stay tuned!编译原理期末总结复习编译原理期末总结复习（精选3篇）编译原理期末总结复习篇1一、简答题1.什么是编译程序？答：编译程序是一种将高级语言程序(源程序)翻译成低级语言(目标程序)的程序。
编译原理总复习总复习■第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→αβ|αγ提取左因⼦。
1》编译程序的框架图与功能块：（1）画出编译程序的总体结构，并简述各部分的主要功能：七个部分（2）编译程序的结构分为几个阶段，各阶段的任务是什么？答编译程序总框架（1）词法分析器，又称扫描器，输入源程序，进行词法分析，输出单词符号。
（2）语法分析器，简称分析器，对单词符号串进行语法分析（根据语法规则进行推导或规约），识别出各类语法单位，最终判断输入串是否构成语法上正确的“程序”。
（3）语义分析与中间代码产生器，按照语义规则对语法分析器归约出（或推导出）的语法单位进行语义分析并把它们翻译成一定形式的中间代码。
（4）优化器，对中间代码进行优化处理。
（5）目标代码生成器，把中间代码翻译成目标程序。
（6）表格管理，登记源程序的各类信息，编译各阶段的进展状况。
（7）出错管理，把错误信息报告给用户。
编译程序的结构分为五个阶段：（1）词法分析.任务是：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词（亦称单词符号或简称符号），如基本字，标识符，常熟，算符和界符。
（2）。
语法分析，任务是：在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位（语法范畴）。
（3）语义分析与中间代码产生。
任务：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。
（4）优化。
任务在于对前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效（省时间和空间）的目标代码。
（5）目标代码生成。
任务是：把中间代码（或优化出理之后）变换成特定机械上的低级语言代码。
2》．重要概念：a. 编译程序：是指能够把源语言程序转换成逻辑上等价的目标语言程序的一个程序。
b. 单词符号：是语言的基本组成成分，是人们理解和编写程序的基本要素，是语言中具有独立意义的最基本结构，它一般包括：基本字、标识符、常数、运算符和界符等c. 中间代码：是一种含义明确，便于处理的记号系统，它通常独立于具体的硬件。
《编译原理》总复习-07级第一章编译程序的概述（一）内容本章介绍编译程序在计算机科学中的地位和作用，介绍编译技术的发展历史，讲解编译程序、解释程序的基本概念，概述编译过程，介绍编译程序的逻辑结构和编译程序的组织形式等。
（二）本章重点编译（程序），解释（程序），编译程序的逻辑结构。
（三）本章难点编译程序的生成。
（四）本章考点全部基本概念。
编译程序的逻辑结构。
（五）学习指导引论部分主要是解释什么是编译程序以及编译的总体过程。
因此学习时要对以下几个点进行重点学习：翻译、编译、目标语言和源语言这几个概念的理解；编译的总体过程：词法分析，语法分析、语义分析与中间代码的生成、代码优化、目标代码的生成，以及伴随着整个过程的表格管理与出错处理。
第三章文法和语言课外训练（一）内容本章是编译原理课程的理论基础，主要介绍与课程相关的形式语言的基本概念，包括符号串的基本概念和术语、文法和语言的形式定义、推导与归约、句子和句型、语法分析树和二义性文法等定义、文法和语言的Chomsky分类。
（二）本章重点上下文无关文法，推导，句子和句型，文法生成的语言，语法分析树和二义性文法。
（三）本章难点上下文无关文法，语法分析树，文法的分类。
（四）本章考点上下文无关文法的定义。
符号串的推导。
语法分析树的构造。
（五）学习指导要构造编译程序，就要把源语言用某种方式进行定义和描述。
学习高级语言的语法描述是学习编译原理的基础。
上下文无关文法及语法树是本章学习的重点。
语法与语义的概念；程序的在逻辑上的层次结构；文法的定义，文法是一个四元组：终结符号集，非终结符号集，开始符号、产生式集；与文法相关的概念，字符，正则闭包，积（连接），或，空集，产生式，推导，直接推导，句子，句型，语言，最左推导，最右推导（规范推导）；学会用文法来描述语言及通过文法能分析该文法所描述的语言；语法树及二义性的概念、能通过画语法树来分析一个文法描述的语言是否具有二义性；上下文无关文法的定义和正规文法的定义，能判断一个语言的文法是哪一类文法。
附训练试题：1：试构造生成语言L={a n b n c i|n≥1, i ≥0}的文法解：2：已知语言L={a n bb n| n ≥1}, 写出产生L的文法。
3：已知文法G=({A,B,C},{a,b,c},A,P)其中产生式P由以下组成：A →abc A →aBbcBb→bB Bc →CbccbC →Cb aC →aaBaC →aa问：此文法表式的语言是什么？4请给出描述语言={a2m+1 b m+1 | m>=0}∪{a2m b m+2| m>=0}的文法5已知文法G[S]为：S→dABA→aA|aB→Bb |εG[S]产生的语言是什么？G[S]能否改写为等价的正则文法？6：试写一文法，使其描述的语言L(G) 是能被5整除的整数集合。
7：已知语言L={x | x∈{a,b,c}*,且x重复排列是对称的（aabcbaa,aabbaa,等）写出该语言的文法。
第四章词法分析课外训练（一）内容本章介绍编译程序的第一个阶段词法分析的设计原理和设计方法，包括源程序输入与词法分析程序输出、正则文法及其状态转换图、确定的有限自动机（DFA）、不确定的有限自动机（NFA）、正则表达式与正规集。
（二）本章重点词法分析器的逻辑结构与功能，状态转换图，正规表达式与正规集、DFA、NFA及其等价转换，NFA的确定化，DFA的最小化。
（三）本章难点正则式与自动机的应用，NFA的确定化，DFA的最小化。
（四）本章考点正规式到NFA的转换。
NFA的确定化。
DFA的最小化。
（五）学习指导掌握正规文法、状态转换图、DFA、NFA、正规表达式和正规集的基本概念和词法分析器的设计与程序编写。
词法分析的任务是对源语言所编写的代码进行从左到右的扫描，产生一个个的单词符号（token），由这些单词符号形成的中间程序是后续语法分析输入。
在理论上词法分析器的构造是根据一种语言的正规文法描述形成相应的状态转换图（DFA），若输入字符串能够被该DFA接受，则认为当前输入是语言中的一个单词符号。
因此，DFA的构造是本章学习的重点。
附训练试题：1写出能被5整除的十进制整数的文法及正规表达式。
2：已知有限自动机如图(1)以上状态转换图表示的语言有什么特征？(2)写出其正规式与正规文法.(3)构造识别该语言的确定有限自动机DFA.3请构造与正规式R=(a*b)*ba(a|b)*等价的状态最少的DFA（确定有限自动机）4设字符集∑={ a, b } ,请写出不以a开头的但以aa结尾的字符串集合的正规表达式，并构造与之等价的状态最少的DFA。
第五章自顶而下语法分析方法课外训练（一）内容本章介绍编译程序的第二个阶段语法分析的第一种设计方法和实现原理即自上而下分析的原理及无回朔的递归下降分析、 LL(1)分析法和相应程序构造。
（二）本章重点自上而下分析的思想，LL(1)文法，LL(1)预测分析，递归下降分析程序的构造。
（三）本章难点消除左递归，预测分析表的构造，求First集和Follow集，预测分析中的出错处理。
（四）本章考点LL（1）文法的判定。
递归下降分析程序的构造。
预测分析程序的构造与分析方法。
（五）学习指导理解自上而下分析面临的问题，理解递归下降分析、LL(1)文法，掌握无回朔的递归下降分析方法的设计和程序实现、LL(1)分析表的构造与分析方法。
语法分析是在词法分析的基础上判定程序的语法结构是否符合语法规则的过程。
词法分析器的构造技术是编译器的主要技术。
词法分析分为自上而下的分析（LL（K））和自下而上的分析（算符优先、LR（K））。
本章先学习在逻辑概念上易于接受的自上而下的分析，即从文法开始符号出发，自上而下地为输入串建立一棵语法树，或者说为输入串寻找一个最左推导。
LL（1）分析法是本章的学习重点。
附训练试题：1试构造与下列文法G[S]等价的无左递归文法。
G[S]: S→Sa|Nb|c (1)N →Sd|Ne|f2：文法G的规则集为;P →begin d : X endX →d : X | sYY→: sY | e做出该文法LL(1)分析表。
3 设有以下文法：G[S]: S→eEfGh | gE→FSG | hF→SE c | cG | εG→Sh |ε（1）求出该文法每一个非终结符的FOLLOW集。
（2）它是LL(1)文法吗？为什么？4：给出语言L={1n a0n1m a0m|n>0, m>=0} 的LL(1)文法G[S]并说明其理由。
5 设有文法：G[S]:S→aBc | bABA→aAb | bB→b | ε构造其LL(1)分析表，并分析符号串baabbb是否是该文发的句子。
6将G[V]改造为LL(1)文法G[V] : V→N | N[E]E→V | V+EN→i7有文法G[S]:S→ BAA→BS | dB→aA | bS | c（1）证明文法为LL(1)文法。
（2）构造LL(1)分析表。
（3）写出句子adccd的分析过程8 考虑下面文法G1:S→a|∧| (T)T→T, S | S(1) 消去G1的左递归。
然后对每一个非终结符，写出不带回溯的递归子程序。
(2) 经改写后的文法是否是LL(1)文法？给出它的预测分析表。
9下面文法中那些是LL(1)文法，说明理由。
（1） 1、S→Abc2、A→a|ε3、B→b|ε（2）S→AbA→a | B|εB→b | ε(3)S→ ABBAA→a | εB →b | ε（4）S→aSe |BB→bBe | CC→c Ce | d第六章自底而上优先分析法课外训练（一）内容本章介绍编译程序的第二个阶段语法分析的第二种设计方法和实现原理即自下而上分析的原理，包括一些基本概念、简单优先分析法、算符优先分析法。
（二）本章重点自下而上分析的思想，算符优先文法及其分析。
（三）本章难点句柄的定义，优先关系的定义，求FIRSTVT集和LASTVT集，优先分析表的构造（四）本章考点基本概念的定义（短语、直接短语、句柄、最左素短语、规范归约等）。
算符优先分析法。
（五）学习指导理解最左素短语的基本概念；掌握算符优先分析方法。
自下而上分析法就是从输入串开始，逐步进行“归约”，直至归约到文法的开始符号，从输入串的语法树上直观地看就是沿着语法树的底部向上分析归约，最终能到达根结点的就认为当前的输入串能被接受。
算符优先分析（OPG）是自下而上分析中针对运算表达式较为常用的易于理解的分析算法。
附训练试题：1已知文法G[S]为算符优先文法，其规则为：S→SaF|FF →FbP|PP →c|d 求优先关系表2 对下列文法G:S’→ #S# P →S|iS →D(R) D →iR → R; P|P求:出每个非终结符的FIRSTVT集和LASTVT集，并构造算符优先关系矩阵。
3 考虑下面文法G2:S→ a| ∧ | (T)T→ T, S | S（1）给出（a,(a, a)）和(((a,a), ∧ ,(a)),a)的最左和最右推导。
（2）给出串（a, (a, a)）的算符优先分析过程。
第七章 LR分析法课外训练（一）内容本章介绍编译程序的第二个阶段语法分析的第二种设计方法和实现原理即自下而上分析的原理，包括一些基本概念、LR分析法。
（二）本章重点自下而上分析的思想，LR分析器逻辑结构和功能，LR(0)文法及其分析、SLR(1)文法及其分析、LR(1)、LALR(1) 文法及其分析。
（三）本章难点句柄的定义，LR项目及活前缀识别自动机，四种LR文法的差别。
（四）本章考点基本概念的定义（短语、直接短语、句柄、规范归约等）。
LR（0）、SLR（1）分析。
（五）学习指导理解有效项目的基本概念；掌握LR(0)、SLR（1）文法的判断及LR(0)、SLR（1）分析表的构造与分析方法。
自下而上分析法就是从输入串开始，逐步进行“归约”，直至归约到文法的开始符号，从输入串的语法树上直观地看就是沿着语法树的底部向上分析归约，最终能到达根结点的就认为当前的输入串能被接受。
大部分现代的编译器都采用LR分析作为语法分析的方式。
因此本章的学习重点是学习如何构造LR分析表。
OPG分析可以作为自下而上分析算法的切入点要求重点掌握。
附训练试题：1、对于文法G[S]S→ ( L) | aS |aL→ L, S | S（1）画出句型( S ,(a))的语法树（2）写出上述句型的所有短语，直接短语，句柄.2、设有文法G[S]:S→L=RS →RL →*RL →iR →L为构造拓广文法，增加新的非终结符S’，得到规则S’ →S，则：closure ( { [S’ →.S, # ]} )=________3、设文法G(S’)S’→A A →aA | b构造识别文法G(S’)的所有活前缀的DFA.4、求文法（1）S’→A（2） A →aA（3）A → bLR(0)分析表：5、设文法G，试构造G的LR(0)分析表G: 1) S→CC2) C →cC3) C →d6、对于文法A→aA|a构造SLR(1)分析表7、设有文法G(S’)为1）S’→S2) S →L=R3) S →R4) L →*R5) L →i6) R →L构造文法G(S’)的LR(1)分析表：8、设有文法G(A）1) A’→ A2) A →BB3) B →aB4) B → b构造LALR(1)分析表第八章语法制导翻译和中间代码的生成课外训练（一）自学内容本章内容围绕语义分析展开，主要介绍属性文法，语法制导翻译与翻译模式的计算，抽象语法树、带注释的语法树。
