编译原理考试知识点复习

第一章：编译过程的六个阶段：词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成解释程序：把某种语言的源程序转换成等价的另一种语言程序——目标语言程序，然后再执行目标程序。解释方式是接受某高级语言的一个语句输入，进行解释并控制计算机执行，马上得到这句的执行结果，然后再接受下一句。编译程序：就是指这样一种程序，通过它能够将用高级语言编写的源程序转换成与之在逻辑上等价的低级语言形式的目标程序(机器语言程序或汇编语言程序)。解释程序和编译程序的根本区别：是否生成目标代码第三章：Chomsky对文法中的规则施加不同限制，将文法和语言分为四大类：0型文法（PSG）0型语言或短语结构语言文法Ｇ的每个产生式α→β中：若α∈Ｖ*ＶNＶ*,β∈(ＶN∪ＶT)*，则Ｇ是0型文法，即短语结构文法。1型文法（CSG）1型语言或上下文有关语言在0型文法的基础上：若产生式集合中所有|α|≤|β|，除Ｓ→ε(空串)外，则Ｇ是１型文法,即：上下文有关文法另一种定义：文法G的每一个产生式具有下列形式：αAδ→αβδ，其中α、δ∈V*，A∈VN，β∈V+；2型文法（CFG）2型语言或上下文无关语言文法Ｇ的每个产生式A→α，若A∈ＶN,α∈(ＶN∪ＶT)*，则Ｇ是２型法，即：上下文无关文法。3型文法（RG）3型语言或正则(正规)语言若Ａ、Ｂ∈ＶN，ａ∈ＶT或，右线性文法：若产生式为Ａ→ａＢ或Ａ→ａ左线性文法：若产生式为Ａ→Ｂａ或Ａ→ａ都是３型文法（即：正规文法）最左（最右）推导在推导的任何一步αβ，其中α、β是句型，都是对α中的最左（右）非终结符进行替换规范推导：即最右推导。规范句型：由规范推导所得的句型。句子的二义性（这里的二义性是指语法结构上的。）文法G[S]的一个句子如果能找到两种不同的最左推导(或最右推导)，或者存在两棵不同的语法树，则称这个句子是二义性的。文法的二义性一个文法如果包含二义性的句子，则这个文法是二义文法，否则是无二义文法。短语若S*αAδ且A+β，则称β是句型αβδ相对于非终结符A的短语。简单短语（直接短语）若S*αAδ且Aβ，则称β是句型αβδ相对于非终结符A的简单短语。句柄一个句型的最左简单短语。（产生式的右部）2型文法1型文法0型文法3型文法子树与短语的关系(1)短语：子树的末端结点(即树叶)组成的符号串；(2)直接短语：简单子树的末端结点组成的符号串；(3)句柄：最左简单子树的末端结点组成的符号串；左图所示的关于句型E+E*i的语法树来说：它有3棵子树，即3个短语分别为i、E*i和E+E*i；直接短语、句柄均为i。从语法树中可以看出，所有树叶的组合就是其相对应的父结点的短语。句型i+i*i的语法树有8棵子树，短语和直接短语如下：直接短语：i1，i2，i3短语：i1，i2，i3，i1*i2，i1*i2+i3句柄：i1注意：i2+i3不是短语不是某棵子树的结果第四章：单词符号的输出形式二元组：（单词种别，单词自身的值）单词符号的分类关键字，标识符，常数，运算符，界符等（这种分类不是唯一的）【例4.2】令={a，b}，上的正规式和相应的正规集的例子有:正规式正规集a{a}ab{a,b}ab{ab}(ab)(ab){aa,ab,ba,bb}a{,a,aa,…任意个a的串}(ab){,a,b,aa,ab…所有由a和b组成的串}(ab)(aabb)(ab){*上所有至少含有两个相继的a或两个相继的b组成的串}DFA定义:一个确定的有穷自动机Md是一个五元组：Md=（K,Σ,f,S,Z），其中：(1)K：有穷状态集；(2)Σ：有穷输入字母表；(3)f：转换函数，K×ΣK的单值映射；即f(ki,a)=kj，其中ki、kj∈K，a∈Σ；(4)S：S∈K，惟一初态；(5)Z：ZK，是一个终态集，也称可接受状态或结束状态。【例】DFAM=({S,U,V,Q}，{a,b}，f，S，{Q})，其中f定义为：f（S，a）=U，f（V，a）=Uf（S，b）=V，f（V，b）=Qf（U，a）=Q，f（Q，a）=Qf（U，b）=V，f（Q，b）=QabSUVUQVVUQQQQ34251X6abababab2YDFA的表示（1）用转换函数；（2）状态转换矩阵；（3）状态转换图转换函数：DFAM=({0,1,2,3},{a,b},f,0,{3})f:f(0,a)=1f(0,b)=2f(1,a)＝3f(1,b)＝2f(2,a)=1f(2,b)=3f(3,a)＝3f(3,b)＝3转换矩阵状态转换图NFAM的定义:一个非确定有穷自动机Mn是一个五元组Mn=(K,Σ,f,S,Z)，其中：(1)K、Σ、Z的意义与DFA相同；(2)f：从K×Σ*K的子集映射；(3)SK，是一个非空初态集。与DFA的主要区别允许有多个初始状态。允许状态在其输出边上有相同的符号(多值映射)。允许输出边上有空串符号。特点:在给定状态和符号的情况下，不能唯一的确定下一个状态。NFA的确定化基本方法基本方法:边合并,符号合并(NFA转化成的DFA不是唯一的)【例】NFAM如右图所示，试将其确定化为DFAM'。【解答】（1）用子集法将图所示的NFAM确定化为表1。（2）对表1中的所有子集重新命名得到表2的状态转换矩阵确定有穷自动机的化简：ε_closure(S0)第五章：语法分析是编译程序的核心部分：在词法分析的基础上，识别单词符号序列是否是给定文法的正确句子（程序）。自上而下分析的前提：消除左递规和消除回溯。自顶向下分析法就是从文法的开始符号出发，试图推导出与输入的单词串完全匹配的句子。如果能够推导出，则该输入串是给定文法的句子。如果不能推导出，则该输入串不是给定文法的句子。自顶向下分析法分两种不确定性分析法：是带有回溯的分析方法，效率低，代价高，极少使用。确定性分析法：对文法有一定的限制，但实现简单直观，便于手工或自动构造。LL(1)文法的定义一个上下文无关文法是LL(1)文法的充分必要条件是：对每个非终结符A的任两个不同产生式A，Aβ，满足：Select(A)∩Select(Aβ)=,其中：、β不同时推导出注：对LL(1)文法进行语法分析时不会产生回溯。LL(1)的含义：(LL(1)文法是无二义的；LL(1)文法不含左递归)第1个L：从左到右扫描输入串第2个L：生成的是最左推导1：向右看1个输入符号便可决定选择哪个产生式某些非LL(1)文法到LL(1)文法的等价变换:1.提取公因子2.消除左递归1.提取左公因子形如:A→aβ1｜aβ2｜...｜aβn｜γ提取左公因子：A→a(β1｜β2｜...｜βn)｜γ改写为：A→aA'｜γA'→β1｜β2｜...｜βn2.消除左递归（如果一个文法是左递归时，则不能采用自顶向下分析法。）(1)左递归的定义（含有左递归的文法绝对不是LL（1）文法）一个文法含有下列形式的产生式时，①
AAAVN,V*直接左递归②ABBAA,BVN,，V*间接左递归(2)直接左递归的消除（改为右递归）形如：A→Aa|β（a非，β不以A打头）改写为：A→βA¢A¢→aA¢|形如：A→Aa1|Aa2|...|Aan|b1|b2|...|bm其中，每个a都不等于，b1,...,bm均不以A开头。改写为：A→b1A¢|b2A¢|...|bmA¢A¢→a1A¢|a2A¢|...|anA¢|SSaSbSbS’S’aS’|εE→E+T｜TT→T*F｜FF→(E)｜iE→TE'E'→+TE'｜εT→FT'T'→*FT'｜εF→(E)｜i预测分析法（又称LL(1)分析法，属于确定的自顶向下分析方法）基本思想：从左到右扫描源程序，直接根据：(1)当前(需推导)的语法变量;(2)输入串的当前输入符号;确定进行分析所需的候选式：使其第一个符号与当前输入符号相同，或该候选式可推导出的第一个符号与当前符号相同。预测分析器构成：预测分析程序，先进后出栈，预测分析表——与文法有关第七章对输入串的分析过程（已知文法的分析表）LR分析法：是一种规范规约过程LR(k)含义L：从左到右扫描输入符号R：最右推导对应的最左归约(反序完成最右推导)k：超前读入k个符号，以便确定归约用的产生式LR(0)项目分类移进项目，形如A→•a，a是终结符,,V*以下同【例】S→•bBB待约项目，形如A→•B【例】S→b•BBS→bB•B归约项目，形如A→•【例】S→bBB•接受项目，形如S’→S•第八章：一个属性文法包含一个上下文无关文法和一系列语义规则,这些语义规则附在每个产生式上。文法符号的属性:单词的含义，即与文法符号相关的一些信息。如，类型、值、存储地址等。一个属性文法(attributegrammar)是一个三元组A=(G,V,F)G：上下文无关文法。V：属性的有穷集。每个属性与文法的一个终结符或非终结符相连。属性与变量一样，可以进行计算和传递。F：关于属性的断言或谓词(一组属性的计算规则)的有穷集。断言或语义规则与一个产生式相联，只引用该产生式左端或右端的终结符或非终结符相联的属性。综合属性:若产生式左部的单非终结符A的属性值由右部各非终结符的属性值决定,则A的属性称为综合属性。继承属性:若产生式右部符号B的属性值是根据左部非终结符的属性值或者右部其它符号的属性值决定的,则B的属性为继承属性。在两种情况下，都说属性b依赖于属性c1,c2,…,ck(1)非终结符既可有综合属性也可有继承属性，但文法开始符号没有继承属性。(2)终结符只有综合属性，没有继承属性，它们由词法程序提供。在计算时：综合属性沿属性语法树向上传递；继承属性沿属性语法树向下传递。语法制导翻译：是指在语法分析过程中，完成附加在所使用的产生式上的语义规则描述的动作。语法制导翻译实现：对单词符号串进行语法分析，构造语法分析树，然后根据需要构造属性依赖图，遍历语法树并在语法树的各结点处按语义规则进行计算。中间代码（中间语言）1、是复杂性介于源程序语言和机器语言的一种表示形式。/2、一般，快速编译程序直接生成目标代码。3、为了使编译程序结构在逻辑上更为简单明确，常采用中间代码，这样可以将与机器相关的某些实现细节置于代码生成阶段仔细处理，并且可以在中间代码一级进行优化工作，使得代码优化比较容易实现。何谓中间代码：源程序的一种内部表示，不依赖目标机的结构，易于代码的机械生成。为何要转换成中间代码逻辑结构清楚；利于不同目标机上实现同一种语言。便于移植，便于修改，便于进行与机器无关的优化。中间代码的几种形式：逆波兰记号，三元式和树形表示，四元式逆波兰记号：把运算分量(操作数)写在前面，把运算符写在后面的表示法，又称后缀表示法。中缀表达式向逆波兰表达式转换postfix(x)=xpostfix(c)=cpostfix(E1opE2)=postfix(E1)postfix(E2)oppostfix((E))=postfix(E)第九章：符号表的一般形式：一张符号表的的组成包括两项，即名字栏和信息栏。信息栏包含许多子栏和标志位，用来记录相应名字和种种不同属性，名字栏也称主栏。主栏的内容称为关键字（keyword）。符号表的功能：（1）收集符号属性在分析语言程序中标识符说明部分时，编译程序根据说明信息收集有关标识符的属性，并在符号表中建立符号的相应属性信息。(2)上下文语义的合法性检查的依据：检查标识符属性在上下文中的一致性和合法性。(3)作为目标代码生成阶段地址分配的依据符号的主要属性及作用：1.符号名2.符号的类型（整型、实型、字符串型等））3.符号的存储类别（公共、私有）4.符号的作用域及可视性（全局、局部）5.符号变量的存储分配信息（静态存储区、动态存储区）6.符号的其它属性数组内情向量(类型、维数、各维的上下界、首地址等)记录结构型的成员信息函数及过程的形参第十章：运行时的存储区为了使目标程序能够运行，编译程序要从操作系统中得到一块存储区，以使目标程序能够在其上运行。运行时的存储区划分目标区：存放目标代码。静