《编译原理考试知识点复习》由会员分享，可在线阅读，更多相关《编译原理考试知识点复习（8页珍藏版）》请在金锄头文库上搜索。
1、第一章：编译过程的六个阶段：词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成解释程序：把某种语言的源程序转换成等价的另一种语言程序目标语言程序，然后再执行目标程序。解释方式是接受某高级语言的一个语句输入，进行解释并控制计算机执行，马上得到这句的执行结果，然后再接受下一句。编译程序：就是指这样一种程序，通过它能够将用高级语言编写的源程序转换成与之在逻辑上等价的低级语言形式的目标程序(机器语言程序或汇编语言程序)。解释程序和编译程序的根本区别：是否生成目标代码第三章：Chomsky对文法中的规则施加不同限制，将文法和语言分为四大类：0型文法（PSG） 0型语言或短语结构语言文法
2、的每个产生式中：若*N*, (NT)* ，则 是0型文法，即短语结构文法。1型文法（CSG） 1型语言或上下文有关语言在0型文法的基础上：若产生式集合中所有|，除(空串)外，则是型文法,即：上下文有关文法另一种定义：文法G的每一个产生式具有下列形式：A，其中、V*，AVN，V+；2型文法（CFG） 2型语言或上下文无关语言文法的每个产生式A，若AN ,(NT)*，则是型法，即：上下文无关文法。2型文法1型文法0型文法3型文法3型文法（RG） 3型语言或正则(正规)语言 若、N，T或 e，右线性文法：若产生式为或左线性文法：若产生式为 或都是型文法（即：正规文法）最左（最右）推导在推导的任何一步
3、 ，其中、是句型，都是对中的最左（右）非终结符进行替换规范推导：即最右推导。规范句型：由规范推导所得的句型。句子的二义性（这里的二义性是指语法结构上的。）文法GS的一个句子如果能找到两种不同的最左推导(或最右推导)，或者存在两棵不同的语法树，则称这个句子是二义性的。文法的二义性一个文法如果包含二义性的句子，则这个文法是二义文法，否则是无二义文法。短语若S* A且 A +，则称是句型相对于非终结符A的短语。简单短语（直接短语）若S * A且A，则称是句型相对于非终结符A 的简单短语。句柄一个句型的最左简单短语。（产生式的右部）子树与短语的关系 (1) 短语：子树的末端结点(即树叶)组成的符号串；
4、 (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不是短语不是某棵子树的结果第四章：单词符号的输出形式 二元组：（单词种别，单词自身的值）单词符号的分类关键字，标识符 ，常数，运算符，界符等（
5、这种分类不是唯一的）【例4.2】 令S=a，b， S上的正规式和相应的正规集的例子有: 正规式 正规集a aab a, bab ab(ab)(ab) aa, ab, ba, bba * e, a, aa, 任意个a的串(ab)* e ,a,b,aa,ab 所有由a和b组成的串(ab)*(aabb)(ab)* S*上所有至少含有两个相继的a或两个相继的b组成的串 DFA定义:一个确定的有穷自动机Md是一个五元组：Md=（K, f, S, Z），其中：(1) K：有穷状态集；(2) ：有穷输入字母表； (3) f ：转换函数，K K的单值映射； 即 f (ki , a)=kj ，其中 ki、kjK
6、，a；(4) S ： SK，惟一初态；(5) Z：ZK，是一个终态集，也称可接受状态或结束状态。【例】DFA M=(S,U,V,Q，a,b，f，S，Q)， 其中f定义为：f（S，a）=U，f（V，a）=U f（S，b）=V，f（V，b）=Q f（U，a）=Q，f（Q，a）=Q f（U，b）=V，f（Q，b）=Q DFA的表示（1）用转换函数；（2）状态转换矩阵；（3）状态转换图转换函数 ：DFA M=(0, 1, 2, 3, a, b , f, 0, 3 ) f: f(0,a)=1 f(0,b)=2 f(1,a)3 f(1,b)2 f(2,a)=1 f(2,b)=3 f(3,a)3 f(3,b
7、)3 转换矩阵 状态转换图 NFA M的定义:一个非确定有穷自动机Mn是一个五元组Mn=(K, , f, S, Z )，其中： (1) K、Z的意义与DFA相同；(2) f：从K* K的子集映射；(3) S K，是一个非空初态集。 与DFA的主要区别允许有多个初始状态。允许状态在其输出边上有相同的符号(多值映射)。允许输出边上有空串符号e 。特点:在给定状态和符号的情况下，不能唯一的确定下一个状态。NFA的确定化基本方法 基本方法:e边合并 ,符号合并 (NFA转化成的DFA不是唯一的) 【 例 】 NFA M如右图所示，试将其确定化为DFA M。【解答】（1）用子集法将图所示的NFA M确定
8、化为表1。（2）对表1中的所有子集重新命名得到表2的状态转换矩阵_closure(S0)确定有穷自动机的化简：第五章：语法分析是编译程序的核心部分：在词法分析的基础上，识别单词符号序列是否是给定文法的正确句子（程序）。自上而下分析的前提：消除左递规和消除回溯。自顶向下分析法就是从文法的开始符号出发，试图推导出与输入的单词串完全匹配的句子。如果能够推导出，则该输入串是给定文法的句子。如果不能推导出，则该输入串不是给定文法的句子。自顶向下分析法分两种不确定性分析法：是带有回溯的分析方法，效率低，代 价高，极少使用。确定性分析法：对文法有一定的限制，但实现简单直观，便于手工或自动构造。LL(1)文法
9、的定义一个上下文无关文法是LL(1)文法的充分必要条件是：对每个非终结符A的任两个不同产生式 Aa，A，满足：Select(Aa)Select(A)=,其中：a、不同时推导出e 注：对LL(1)文法进行语法分析时不会产生回溯。LL(1)的含义：(LL(1)文法是无二义的； LL(1)文法不含左递归)第1个L：从左到右扫描输入串 第2个L：生成的是最左推导1 ：向右看1个输入符号便可决定选择哪个产生式某些非LL(1)文法到LL(1)文法的等价变换: 1. 提取公因子 2. 消除左递归 1. 提取左公因子形如: Aa1a2.an 提取左公因子： A a(12.n)改写为： A a A A12.n
10、2. 消除左递归 （如果一个 文法是左递归时，则不能采用自顶向下分析法。）(1)左递归的定义 （含有左递归的文法绝对不是LL（1）文法）一个文法含有下列形式的产生式时， AAb AVN , bV* 直接左递归 ABb B Aa A, BVN , a，b V* 间接左递归(2)直接左递归的消除 （改为右递归）SbS SaS| SSa Sb 形如： A A a|（a非e，不以A打头）改写为： A A A aA | e 形如： AAa1 | Aa2 | . . . | Aan | b1 | b2 | . . . | bm 其中，每个a都不等于e ，b1 , . . . , bm 均不以A开头。改写为
11、： A b1 A | b2 A | . . . | bm A A a1 A | a2 A | . . . | an A | e E T EE + T ET F TT * F TF ( E )i E E + TT T T * FFF ( E )i 预测分析法（又称LL(1)分析法，属于确定的自顶向下分析方法） 基本思想 ：从左到右扫描源程序，直接根据： (1) 当前(需推导)的语法变量; (2) 输入串的当前输入符号; 确定进行分析所需的候选式：使其第一个符号与当前输入符号相同，或该候选式可推导出的第一个符号与当前符号相同。预测分析器构成：预测分析程序，先进后出栈，预测分析表与文法有关第七章对输
12、入串的分析过程（已知文法的分析表）LR分析法：是一种规范规约过程LR(k)含义L ：从左到右扫描输入符号R ：最右推导对应的最左归约(反序完成最右推导)k ：超前读入k个符号，以便确定归约用的产生式LR(0)项目分类移进项目，形如Aa ab，a是终结符,a ,b V* 以下同 【例】 S bBB 待约项目，形如 A a Bb 【例】 Sb BB SbB B 归约项目，形如 A a 【例】 SbBB 接受项目，形如 S S 第八章：一个属性文法包含一个上下文无关文法和一系列语义规则,这些语义规则附在每个产生式上。文法符号的属性:单词的含义，即与文法符号相关的一些信息。如，类型、值、存储地址等。一个属性文法(attribute grammar)是一个三元组A=(G, V, F)G：上下文无关文法。V：属性的有穷集。每个属性与文法的一个终结符或非终结符相连。属性与变量一样，可以进行计算和传递。F：关于属性的断言或谓词(一组属性的计算规则)的有穷集。断言或语义规则与一个产生式相联，只引用该产生式左端或右端的终结符或非终结符相联的属性。综合属性:若产生式左部的单非终结符A的属性值由右部各非终结符的属性值决定, 则A的属性称为综合属性。 继承属性:若产生式右部符号B的属性值是根据左部非终结符的属性值或者右部其它符号的属性值决定的,则B的属性为
