编译原理总复习题

第一章引论1.编译程序分几个阶段，每个阶段的任务是什么？五个阶段：词法分析、语法分析、语义分析、中间代码生成、优化、目标代码生成词法分析任务：输入源程序；扫描、分解字符串，识别出一个个单词（记号—Token。

定义符、标识符、运算符、界符、常数）。

同时查词法错误，进行标识符登记——符号表管理。

语法分析任务：在词法分析基础上，将单词符号串转化为语法单位（语法范畴）（短语、子句、句子、程序段、程序），并确定整个输入串是否构成语法上正确的程序。

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

代码优化任务：对于代码（主要是中间代码）进行加工变换，以期能够产生更为高效（省时间和空间）的目标代码。

目标代码生成任务：将中间代码变换成特定机器上的低级语言代码2.表格管理和出错处理：编译各阶段均须维持表格并进行表格管理，建表的技术支持是数据结构，表格的分类、结构、处理方法决定于语言及机器，还有优化措施。

一个好的编译程序应该：全，最大限度发现错误；准，准确指出错误的性质和发生地点；局部化，将错误的影响限制在尽可能小的范围内。

源程序中的错误通常分为：语法错误，不符合语法（或词法）规则的错误，如单词拼写错误、括号不匹配 ...语义错误，不符合语义规则的错误，如说明错误、作用域错误、类型不匹配 ...3.前端、后端：编译前端主要由与源语言有关，但与目标机无关的那些部分组成。

编译后端包括编译程序中与目标机有关的那些部分。

4.遍：根据系统资源的状况、运行目标的要求……等，可以将一个编译程序设计成多遍扫描的形式，在每一遍扫描中，完成不同的任务。

遍可以和阶段相对应，也可无关。

单遍代码不太有效。

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

5.“运算符与运算对象类型不符”属于语义错误6.算法逻辑上的错误属于语义错误第二章高级语言及其语法描述1. 程序语言是由语法和语义两方面定义的。

2.上下文无关文法的定义：四个组成部分：一组终结符号、一组非终结符号、一个开始符号、一组产生式。

一个上下文无关文法G是一个四元式（VT,VN,S, P ），其中:VT：是非空有限集，它的每个元素是终结符号；VN：是非空有限集，它的每个元素是非终结符号，VT∩VN=Φ，VT∪VN=V;S：S∈VN，称为开始符号；P ：产生式集合（有限），每个产生式形式是{ P->α| P∈VN，α∈(VT∪VN)*，S至少一次为P }；3.推导、最左推导、最右推导：1、推导：如两个串u0、un，存在一个串序列u0=>u1=>…=>un，则我们称这个序列是从u0到un 的一个推导。

U1un：表示从u0出发，经一步或若干步，可推导出un.U1un：表示从u0出发，经0步或若干步，可推导出un.最左推导是指，任何一步α=>β都是对α中的最左非终结符进行替换的。

最右推导是指，任何一步α=>β都是对α中的最右非终结符进行替换的。

4.语法树：在编译中产生语法树是为了语法分析。

5、什么是句型？什么是句子？什么是语言？假定G是一个文法，S是它的开始符号。

如果S=> α，则称α是一个句型。

仅含终结符的句型是一个句子。

文法G所产生的句子的全体是一个语言。

语言是由句子组成的集合，是由一组记号所构成的集合。

6.乔姆斯基把文法分成4种类型，即0型文法、1型文法、2型文法和3型文法。

0型文法也称为短语文法。

1型文法也称为上下文有关文法。

2型文法也称为上下文无关文法。

3型文法也称为正规文法。

与程序语言语法有关的文法是上下文无关文法。

第三章词法分析1.状态转换图：使用状态转换图是设计词法分析程序的一种好途径，状态转换图是一张有限方向图。

在状态转换图中，结点代表状态，用圆圈表示。

一个状态转换图可用于识别（或接受）一定的字符串。

2.确定的有限自动机（DFA）、非确定有限自动机（NFA）。

五元式：有限状态集合、有穷字母表、转换函数、唯一的初始状态、终止状态集合。

一个确定有限自动机（DFA）M是一个五元式：M ＝(S,∑,δ,s0 ,F) ，其中S是一个有限集，它的每个元素称为一个状态，∑是一个有穷字母表，它的每个元素称为一个输入字符，δ是一个从S×∑至S的单值部分映射。

δ(s,a)=s´意味着：当现行状态为、输入字符为a时，将转换到下一状态s´。

我们称s´为s的一个后继状s0∈S是唯一的初态F 是一个终态集（可空）。

一个非确定有限自动机（NFA）M是一个五元式：M ＝(S,∑,δ,S0 ,F) ，其中S是一个有限集，它的每个元素称为一个状态，∑是一个有穷字母表，它的每个元素称为一个输入字符，δ是一个从S×∑*至S的子集的映射，即δ：S×∑* →2s，S0∈S是唯一的初态，F是一个终态集（可空）。

3.设有确定的有限自动机DFA M = ({0,1,2,3},{a,b},δ,0,{3})，其中δ为:δ(0,a)=1 δ(0,b)=2 δ(1,a)=3 δ(1,b)=2 δ(2,a)=1 δ(2,b)=3 δ(3,a)=3 δ(3,b)=3请画出状态转换矩阵和状态转化图。

相应的状态转换矩阵如下表：对应的状态转换图4.设计一个DFA,要求能够识别∑={0,1}上能被5整除的二进制数。

5.词法分析的流程第四章语法分析——自上而下分析1.语法分析器的功能：识别语法成分,并作语法检查.2.自上而下语法分析方法遇到的主要问题是回溯和左递归。

3.把一个文法改造成任何非终结符的所有候选式首符集两两不相交的方法是提取公共左因子。

4.LL（1）分析法中，第一个L表示从左到右扫描输入串，第二个L表示最左推导。

1表示分析时每步只需向前看一个符号。

5.LL（1）文法的条件：1文法不含左递归2）FIRST(α)∩FIRST(β) = φ3）对文法中的每个非终结符A，若它存在某个候选首符集包含ε，则FIRST（A）∩FOLLOW（A）=Φ。

6. 对下文法，计算每个非终结符的FIRST集合和FOLLOW集合。

E→TE’E’→+E|εT →FT’T’→T|εF→PF’F’→*F’|εP→(E)|a|b|∧First(E)= First(T)= First(F)={(,a,b, ∧}First(E’)={+, ε} ,First(T’)={(,a,b, ∧, ε}First(F’)={*, ε} ,Follow(E)= Follow(E’)={#, )}Follow(T)= Follow(T’)={+,#, )}Follow(F)= Follow(F’)={(,a,b, ∧,+,),#}Follow(P)={*, (,a,b, ∧,+,),#}7.两种实现方法：递归下降分析法、预测分析程序。

第五章语法分析——自下而上分析1. 简述自下而上的语法分析方法:就是从输入串开始，逐步进行“规约”，直至规约到文法的开始符号；或者说从语法树的树叶开始，逐步向上规约，直至规约到根节点。

2.一个句型的句柄是该句型的最左直接短语。

3.规范规约是指最右推导的逆过程。

4.算符优先分析法1）特别适应于表达式分析的方法2）算符优先分析法中，优先表中存储的是优先关系3）算符优先分析法的可规约串是句型的最左素短语。

5.LR分析法:1）LR（K）文法是从左到右分析，每次向貌似句柄的符号串后看K个输入符号的一种编译方法2）四种分析表3）LR(0)项目的含义4）例给定文法：S→AS|b A→SA|a 要求列出这个文法的所有LR(0)项目。

S→.AS S→A.S S→AS. S→.b S→b. A→.SA A→S.A A→SA.A→.a A→a.5）写出LR(0)分析表的构造步骤:①确定G的LR(0)项目②以LR(0)项目为状态,构造一个能识别文法G的所有活前缀的NFA③利用子集法,将NFA确定化,成为以项目集合为状态的DFA根据④利用上述DFA可直接构造出LR分析表。

6）比较LR(0)、SLR（1）、LR（1）、LALR（1）分析表的优缺点:这4种分析表都能识别对应文法的全部句子，其共同特征就是用规范规约的方法寻找句柄进行规约。

在这4种方法中，LR（0）分析表对文法的要求较高，其构造方法是其它表构造方法的基础；SLR（1）分析表对文法的要求有所降低，容易实现，因而很有实用价值；LR（1）分析表对文法的要求最低，适用于一大类文法，故其分析能力最强，但其实现代价过高；LALR（1）分析表的分析能力介于SLR（1）和LR（1）之间，实现代价比LR（1）低。

第六章属性文法和语法制导定义1.语法制导翻译法就是在语法分析的过程中,随分析的过程,根据为每个产生式添加的语义动作进行翻译的方法。

2.写出产生式、语义规则和语义子程序之间的关系。

①产生式:一个产生式描述了一个语法单位,但它只说明了该语法单位能产生的符号串,并未指明所产生的符号串有什么实际意义,即该符号串究竟要做什么。

②语义规则:一个产生式的语义规则描述了该产生式的具体的动作意义,即该产生式产生的符号串要做什么。

③语义子程序:按照产生式的语义规则生成某种中间代码,实现相应的动作。

3.对于文法的每个产生式都配备了一组属性的计算规则，称为属性。

4.文法符号的属性有两种，一种称为综合属性，一种称为继承属性。

综合属性传递信息的方向是自下而上。

继承属性传递信息的方向是自上而下。

5. 在分析树中，一个结点的综合属性值是从其子结点的属性值计算出来的。

一个结点的继承属性由此结点的父结点或兄弟结点的某些属性确定。

6.为文法S →( L ) | a L →L , S | S写一个语法制导定义，它输出括号的对数。

S’→S print (S. num)S →( L ) S. num := L.num + 1S →a S. num := 0L →L1 , S L. num :=max{ L1. num , S. num}L →S L. num := S.num7.为文法S→( L ) | a L →L , S | S写一个翻译方案，它输出每个a的嵌套深度。

例如，对于( a , ( a , a) )，输出的结果是1 2 2。

S’→{S. depth := 0 } SS→{L. depth := S. depth + 1 } ( L )S →a {print (S. depth) }L →{L1. depth := L. depth }L1 , {S. depth := L. depth }SL→{S. depth := L. depth }S8.S-属性文法：只含有综合属性。

可借助于LR分析器实现。

采用自底向上分析，例如LR 分析，首先给出S-属性定义，然后，把S-属性定义变成可执行的代码段，这就构成了翻译程序。