编译原理复习要点

《编译原理复习要点》由会员分享，可在线阅读，更多相关《编译原理复习要点（1页珍藏版）》请在金锄头文库上搜索。

1、翻译程序:有这样的一个程序，它把用汇 编语言或高级语言编写的程序转换成等 价的机器语言程序，我们把这种执行转换 功能的程序统称为翻译程序。编译：高级语言的翻译程序称为编译程 序。编译程序的输入对象称为源程序,输出对 象称为目标程序。编译程序支持的源程序的执行分为两个 阶段：编译阶段，运行阶段。编译阶段:对整个源程序进行分析，翻译 成等价的目标程序,翻译的同时做语法检 查和语义检查,凡是有错误的源程序均指 出其错误。运行阶段在运行子程序的支持 下执行目标程序。运行子程序是为了支持 目标程序的运行而开发的程序。词法分析：扫描程序的ASCII码序列，识 别出一个个具有独立意义的最小语法单 位，并把每

2、个单词的 ASCII 码序列替换为 所谓的token形式。语法分析:根据程序设计语言的语法规 则，把词法分析的结果分解陈各种语法单 位，同时检查程序中的语法错误。语义分析:对语法分析所识别出的各类语 法范畴，分析其含义，并进行静态语义检 查。中间代码生成:上述过程后，有些编译程 序将程序变成一种内部表示形式，这种表 示形式叫做中间代码中间代码优化:对前阶段产生的中间代码 在不改变源程序的前提下进行加工变化， 使生成的代码更高效，缩短运行时间或节 省存储空间。目标代码生成:把中间代码变换成特定机 器上的机器指令代码或汇编指令代码。 表格管理:编译程序在对源程序的分析过 程中，需要创建和管理一系列

3、的表格，以 登记源程序的各类信息和编译各阶段的 进展情况。错误处理:一个编译程序不仅能对书写正 确的程序进行翻译，而且能对出现在源程 序中的错误进行处理。文法:是用有限的规则表示无穷字符串集 的一种方法O 型文法:也称为短语文法，其产生式具 有形式仪一卩，其中久卩日VyVj*，并且 a至少含一个非终极符；1型文法：也称为上下文有关文法。它是 0型文法的特例。其产生式具有形式:(1) aApayp,AeV 丫 为非空串.或(2)|a| IPI (S是开始符,Sr除外，且S不出现 在任何产生式的右部)2型文法:也称为上下文无关文法。它是 1型文法的特例。其产生式具有形式:A- 卩，A叫卩为非空串.

4、即要求产生式左部 是一个非终极符.3型文法:也称为正则文法。它是2型文 法的特例。其产生式的右部至多有两个符 号，而且具有下面形式之一：A a , A a B,其中A,BeV ，日叫文法描述能力O型文法 ；型文法 2 型文法3型文法文法对应自动机O型文法(短语文法):图 灵机 1 型文法(上下文有关文法) :线性 有界自动机2型文法(上下文无关文法): 下推自动机 3 型文法(正则文法) :有限 自动机句型:如果有S n* a, S是文法的开始符,a e (VTuVN )*，则称a是G的句型 句子:如果有S n+ a, S是文法的开始符,a e VT*，则称a是G的句子 短语：一个句型形如a旳

5、，如果存在一个 句型aAy,而且An+卩，则称卩为句型a旳 的短语； 一个句型形如a旳，如果存在一个句型 a Ay,而且A n p,则称卩为句型apy的简单短语； 句柄:一个句型的简单短语可能有多个， 称最左简单短语为句柄 规范推导：最右推导 每个句子一定有最右(规范)推导，每个句 型不一定有最右(规范)推导 二义性文法:如果文法的一个句子有两棵 或两棵以上不同的语法分析树，则称该文 法为二义性文法。消除文法二义性的常用方法:1、规定符 号的优先级2、规定符号的结合性 文法变换:有些语法分析方法要求被分析 的文法满足一定的约束条件，当被分析的 文法不满足这些条件时，常常要进行文法 变换。文法变

6、换必须保证变换前后的两个 文法G1和G2是等价的,即L(G1) = L(G2) 消除公共前缀A Tap1 | apn| y1|.| ym提取公因子ATaA| y1| ym，At p1| | Pn消除左递归A t A a1 | A an|卩1|.| pm 消除:ATp1A| pmA ， At a1A | . | anA|s百动机:是为研究有限内存的计算过程和 某些语言类而抽象出的一种计算模型。 NFA到DFA的转化思想:将NFA的状态 集当作 DFA 的状态，同时确保转化后的 DFA与原NFA等价DFA化简思想:等价状态：对于DFA中的 两个状态si和s2,如果分别将si和s2 当作开始状态，它

7、们接受的字符串集合相 同，则称si和s2是等价状态；DFA化简的两种方式:合并等价状态;(状 态合并法)分离不等价状态;(状态分离法) DFa 和 NRA 的不同: rDFA1 NFA初始一个初始状态初始状态 集合边/U1 1/不允许允许f (S, a)S or 丄S1实现右曰Snor 丄 有不确定自顶向下语法分析主要思想:是从文法的 开始符号出发，试图为输入串建立一个最 左推到，或者为输入串构造一个语法树。 自顶向下语法分析条件:对任意非终极符 A，A的任意两条产生式predict(Apk)c predict(Apj )=0，k工 j 不满足LL文法条件的情形:文法的产 生式存在左递归或公共

8、前缀。递归下降语法的做法:对文法中每个非终 极符U都编写一个子程序，以完成该非 终极符所对应的语法成分的分析和识别 任务。某个非终极符的语法分析子程序的功能： 用该非终极符的规则的右部符号串去匹 配输入串。递归卜降法优点:程序结构和层次清晰明 了，易于手工实现，就语义加工来说，这 种方法是十分灵活的。缺点：对文法的限 制太严格，频繁调用子程序，分析效率低 LL(1的主要思想:LL的含义是从左到右扫 描输入串，采用最左推导分析句子。数字 1 表示分析句子时需向前看一个输入符 号。LL(1)方法和递归下降法属于同一级别 的自顶向下分析法(分析条件相同)。LL(1)文法的特性:无二义性，无左递归，

9、对于一个非终极符来讲,最多只有一个空 产生式递归下降法与LL(1)的相同点:同属于自 顶向下分析法，分析条件相同。不同点: 递归下降法对每个非终极符产生子程序， 而LL(1)方法则产生LL分析表；递归下降 法能判断每个产生式的结束，而LL(1 )方 法则不能；递归下降法分析法不用符号 栈，而LL(1)方法则用符号栈。自底向上分析主要思想:从输入串出发； 尽可能地找到可归约子串并将其归约成 一个非终极符；直到归约成文法的开始符 或发现语法错误；规范推导：最右推导规范句型：最右推导导出的句型 规范前缀:若有规范句型an，且n是终 极符串或空串，则称a为规范前缀。 规范活前缀:若规范前缀a不含句柄或

10、含 一个句柄并且句柄在a的最右端,则称规 范前缀a为规范活前缀。规约规范活前缀:活前缀a是含句柄的活 前缀，并且句柄在a的最右端，则称活前 缀a为规约规范活前缀。LR方法主要思想:从左至右读入输入串; 每次找到句柄 (归约规范活前缀 )来进行 归约；归约直到得到开始符或报告语法错 误；LR(0)项目:带圆点的产生式，圆点只能出 现在产生式的右部符号串的任意位置LR(0)分析的局限:LR(0)文法仅凭符号栈 里的内容来确定可归约活前缀 , 非常容 易产生冲突；LR(O)文法易于产生冲突的原 因在于在确定分析动作时没有考虑输入 串信息。LR(1)分析基本思想:对于非终极符的每 个不同出现求其后继终

11、极符(follow),称 为展望符；一个非终极符的一个出现的所 有后继终极符构成的集合称为展望符集； 展望符集的作用 : 对于移入型项目 , 不 起作用,但是需要保存；对于归约型项目 , 表示只有当下一个输入符是其中一个展 望符时，才可以进行归约动作 LR(1 )分析存在的问题：为消除冲突，引 入太多的状态，构造分析表的工作量及所 占存储空间较大；LALR(1)分析主要思想：合并文法G的 LR(1)自动机中的同心状态，得到的自动机 称为LALR(1)自动机；若这个得到的 LALR(1 )自动机没有冲突，则称文法G是 LALR(1)文法。分析能力:LR(1)二 LALR(1)二SLR(1)二 L

12、R(0)状态数:LR(1) LALR(1) = SLR(1) = LR(0) 语法:是描述一个合法定义的程序结构的 规则语义：说明一个合法定义的程序的含义 词法分析和语法分析是对源程序形式上 的识别和处理，而语义分析是对源程序的 语义做相应的处理工作。静态语义：编译时可以检查的语义 动态语义:目标程序运行时才能检查的语 义静态语义检査内容:各种条件表达式的类 型是不是 Boolean 型，运算符的分量的类 型是否相容，赋值语句的左右部的类型是 否相容，形参和实参的类型是否相容，下 表表达式的类型是否为所允许的类型等。 符号表:可看作是从标识符名字到它的属 性的映射；用于存储程序中声明的标识符

13、及其属性；为什么在语义分析时需要符号表?从标识 符的Token定义，我们仅仅知道了标识符 的名字，对于其它属性，例如类型，种类 等没有记录，对于标识符的更多信息需要 进行语义分析，从而检查语义错误； 为表示标识符的属性,我们需要建立:标 识符的内部表示，类型的内部表示，值的 内部表示。为什么需要类型的内部表示?类型是标识 符的重要属性；类型检查是语义分析的重 要部分;类型的结构对类型检查很重要； 标识符声明:查找符号表检查标识符是否 已经被声明过；如果是，则重复声明错； 如果不是，则建立标识符的内部表示，将 其放入符号表；标识符使用:查找符号表检查标识符是否 有声明；如果是，则取出标识符的属性

14、进 行语义分析；如果不是，则未声明错； 声明的语义分析:收集被声明的标识符的 属性；建立被声明标识符的内部表示；检查 重复声明错误；将被声明标识符的内部表 示插入符号表； 中间代码生成方法：语法制导的翻译方 法：属性文法和动作文法，基于Token序 列，基于抽象语法树 运行时间坏境:是指目标计算机的寄存器 和内存结构，该结构用于管理内存和维护 目标程序执行时需要的信息.过程活动记录:每当过程/函数被调用时， 为其分配的局部空间的一种统一结构。存 放在栈区的一段连续的存储单元中，由目 标程序进行管理。是过程一次活动的一个 现场记录。过程调用的时候进行填写， 过程返回的时候释放。活动记录通用结构:

15、临时变量 局部变量 返回 返回地址 控制信息 动态链：如果每个AR是等长的则用sp 减去这个长度就可以了，但实际上每个 AR的长度不一定相同，所以在每个AR中 要保存其前一个AR的始地址，于是栈上 的AR被连起来了，这样连起来的AR结 构称之为动态链。 目标代码生成器主要任务: 给变量分配 实际地址，寄存器分配，生成管理AR的指 令和其他指令。奇存器分配应遵循的原则:寄存器优先原 则:即变量的值尽可能的存放在寄存器 中。寄存器活跃原则:即变量的值至少有 下一次的引用时才分配寄存器。寄存器多 载原则:即一个寄存器中可能存放多个变 量的值。典型的例子是通过赋值操作的结 果。源变量和被赋值的变量共用一个寄存 器表达式四元式生成算法(1) 初始化: S1 和 S2 为空；(2) 读 token: tk=ReadOne()；(3) Switch tk of(i) #: if (S1 为空)exit; else while (S1 不为空)op = pop(S1)； (a, b)=pop(2)； t= NewTemp(dir)；GenIR(op, b, a, t)； push(S2, t)；(ii) 操作数:push(tk, S2); goto (2);(iii) 操作符:if (Si为空| tk优先级大 于 Top(S1) push (tk, Si)