编译原理期末总复习大纲.ppt

2019/8/6,1,编译器,一个编译程序就是一个语言翻译程序，它把一种语言（称作源语言）书写的程序翻译成另一种语言（称作目标语言）书写的等价的程序。,第1章 编译概述,2019/8/6,2,编译的分析-综合模型,分析：分析源程序，计算其基本属性，生成源程序的中间表示,综合：将源程序的中间表示转换为目标代码,第1章 编译概述,2019/8/6,3,编译的逻辑阶段,词法分析,语法分析,语义分析,中间代码生成,代码优化,目标代码生成,第1章 编译概述,2019/8/6,4,* 符号表管理,* 出错处理,第1章 编译概述,2019/8/6,5,遍,对源程序或源程序中间表示的一次扫描，每一遍读入一个文件，执行一个或几个阶段的编译操作，并输出源程序的一个中间表示,遍数多：编译器结构清晰，但时间效率不高,遍数少：编译速度快，但对机器的内存要求高,第1章 编译概述,2019/8/6,6,语言,某个字母表上的符号串的集合,第2章 程序语言的基本知识,2019/8/6,7,文法 G 四元组（VT，VN，S，P）：,上下文无关文法,A ,A ,第2章 程序语言的基本知识,2019/8/6,8,推导与归约,推导是用产生式的右部代替左部，归约是用产生式的左部代替右部，归约是推导的逆过程,第2章 程序语言的基本知识,2019/8/6,9,最左推导与最右推导,最右归约与最左归约,第2章 程序语言的基本知识,2019/8/6,10,句型 与 句子,句型：从文法的开始符号出发进行零步或多于零步的推导得到的文法符号串,句型可以既包含终结符号又包含非终结符号，只包含终结符号的句型称为句子,第2章 程序语言的基本知识,2019/8/6,11,语言的形式定义,文法 G 推导出的所有句子组成的集合，称为语言，记为 L（G）,第2章 程序语言的基本知识,2019/8/6,12,句型的短语、直接短语和句柄,如果S A和A ，则称是关于A的，句型的一个短语（子树的叶子）,S,A,第2章 程序语言的基本知识,2019/8/6,13,如果S A和 A =，则称是关于 A的，句型的一个直接短语（只有父子两代的子树的叶子）,S,A,第2章 程序语言的基本知识,2019/8/6,14,最左直接短语称为句柄 最左性体现在分析树和句型中,S,A,第2章 程序语言的基本知识,2019/8/6,15,句型的素短语、最左素短语,1、是关于A的，句型的一个短语,2、至少含有一个终结符,3、除自身外不含更小的带终结符的短语,称是关于A的，句型的一个素短语,句型最左边的素短语称为最左素短语,第2章 程序语言的基本知识,2019/8/6,16,句子、文法和语言的二义性,如果一个文法的句子有两棵或两棵以上的分析树，称此句子是二义的,最左（右）推导与分析树一一对应，句子二义说明它有两个或以上最左（右）推导,第2章 程序语言的基本知识,2019/8/6,17,如果一个文法有一个句子是二义的，此文法称为二义文法,如果一个语言的所有文法都是二义的，称此语言是二义的,第2章 程序语言的基本知识,2019/8/6,18,正规表达式,正规表达式是一个表示字符串格式的模式,用来描述单词符号的结构,递归定义,第3章 词法分析,2019/8/6,19,有限自动机,是具有离散输入与离散输出的一种数学模型,输入：字符串,输出：是、否,它能对输入字符串是否属于某个模式（正规集、正规语言）作出判断,第3章 词法分析,2019/8/6,20,非确定的有限自动机 NFA,S 状态集合, 输入符号集合,move 转换函数（S 2S）,S0 开始状态,F 接受状态集合,第3章 词法分析,2019/8/6,21,确定的有限自动机 DFA,没有边转移,一个状态面临一个输入符号时最多只转移到一个状态,第3章 词法分析,2019/8/6,22,NFA-DFA 的转换 子集构造法,从正规表达式构造 NFA,DFA 的化简（最小化）,第3章 词法分析,2019/8/6,23,自顶向下分析：,从根到叶子来建立句子的分析树,或，给出句子的一个从开始符号出发的推导序列,第4章 语法分析,2019/8/6,24,自底向上分析：,从叶子到根来建立句子的分析树,或，给出一个从句子出发到开始符号的归约序列,第4章 语法分析,2019/8/6,25,不确定的自顶向下分析：,带回溯的分析方法,本质上是一种基于穷举原理的试探方法，是个反复使用不同的产生式谋求匹配输入串的过程,不确定性体现在每次选择的产生式不一定是正确的,第4章 语法分析,2019/8/6,26,确定的自顶向下分析：,基本思想：从文法的开始符号出发，根据当前的输入符号和其它信息，唯一地确定选用哪条产生式往下推导，构造分析树。,无论对错，都没有回溯,第4章 语法分析,2019/8/6,27,FIRST集：,FOLLOW集：,SELECT集,构造LL（1）分析表,LL（1）文法,第4章 语法分析,2019/8/6,28,提取左因子,含有上面产生式的文法不是 LL（1）的，因为:,SELECT（ A ） SELECT（ A ） ,文法中可能含有形如：A | 的产生式,第4章 语法分析,2019/8/6,29,A 1 | 2 | 3 | | n, A （1 | 2 | 3 | | n）, A A A 1 | 2 | 3 | | n,第4章 语法分析,2019/8/6,30,消除左递归,文法可能含有形如 A A | 的产生式或 A A的推导，称为左递归文法,左递归文法不是 LL（1）文法，,第4章 语法分析,2019/8/6,31,自底向上分析法，又称为移进-归约法，它的实现思想：,对输入符号串自左向右进行扫描，并将输入符逐个移入一个先进后出栈中，边移进边分析，一旦栈顶符号串形成某个句型的可归约串时，就用相应产生式的左部非终结符代替此可归约串。重复这一过程，直到归约到栈中只剩下文法的开始符号时分析成功。,第4章 语法分析,2019/8/6,32,算符优先分析的基本思想：,利用算符优先关系来寻找可归约串,算符优先分析,第4章 语法分析,2019/8/6,33,LR（k）分析技术：,L 指从左至右扫描输入符号串,R 指构造一个最右推导的逆过程（最左归约）,k 指在作出分析决定前要向前看的输入符号个数，通常为 0 或 1,LR 分析技术是功能最强的（自底向上）语法分析技术，适用文法广，效率高，分析能力强,第4章 语法分析,2019/8/6,34,LR分析过程中的性质与特点：,栈中的文法符号串并上剩余的输入串构成一个右句型（规范句型）,当该右句型的句柄出现在栈顶时，归约，否则，移进,栈中的文法符号串是当前句型的前缀，该前缀不包含句型句柄后面的符号，称之为活前缀,第4章 语法分析,2019/8/6,35,语义分析阶段分析源程序的含义，并作相应的处理，语义分析的基本功能：,确定类型,类型检查,产生中间代码,语义分析的主流技术 语法制导翻译技术,第5章 语法制导翻译,2019/8/6,36,文法符号的属性：,1、综合属性：属性值是分析树中该结点的子结点的属性值的函数,2、继承属性：属性值是分析树中该结点的父结点和/或兄弟结点的属性值的函数,第5章 语法制导翻译,2019/8/6,37,语法制导定义： 为每一条产生式（A ）引入一套语义规则,规则形式：b := f (c1,c2,ck),第5章 语法制导翻译,2019/8/6,38,语法制导翻译: 根据语法分析中产生式对应的语义规则进行翻译的方法称为语法制导翻译。,第5章 语法制导翻译,2019/8/6,39,S -属性定义,只含有综合属性的语法制导定义,第5章 语法制导翻译,2019/8/6,40,L -属性定义,是一种语法制导定义,对于产生式 AX1X2Xn 右部 Xj 的继承属性，它依赖于： 1、 X1，X2，Xj-1 （ Xj左边的文法符号）的属性 2、A 的继承属性,* L-属性定义包含 S-属性定义,第5章 语法制导翻译,2019/8/6,41,翻译模式：,将语义规则放到 中，并插入到产生式右部的适当位置，以反映语义规则的计算顺序，这种书写形式称之为翻译模式,第5章 语法制导翻译,2019/8/6,42,从 L-属性定义出发，构造一个满足要求的翻译模式,将计算产生式右边某文法符号的继承属性的语义规则插入到此符号之前,将计算产生式左边非终结符号综合属性的语义规则放在产生式右端的末尾,第5章 语法制导翻译,2019/8/6,43,L-属性定义 深度优先翻译 两遍扫描,S-属性定义 自底向上翻译 一遍扫描,第5章 语法制导翻译,2019/8/6,44,三地址代码,一般形式：x := y op z,一般含三个地址（名字、常数、临时变量），两个操作数，一个运算结果,中间代码,第7章 中间代码生成,2019/8/6,45,根据给定语法制导定义，翻译赋值语句、布尔表达式、控制流语句等，得到中间代码,参考例子，掌握方法,第7章 中间代码生成,2019/8/6,46,代码优化,编译时刻为改进目标程序的质量而进行的各项工作,与机器相关的优化,与机器无关的优化,第9章 代码优化,2019/8/6,47,根据优化范围,局部优化 针对程序基本块,循环优化 针对循环体,全局优化 针对整个程序,第9章 代码优化,2019/8/6,48,名字的联编,名字的左值 内存地址，存储名字的瞬时值,名字的右值 名字的瞬时值,名字的联编 将一个内存地址与一个名字联系起来,在程序的一次运行中，一个名字右值（瞬时值）可能会经常改变，一个名字也可能被联编到多个地址（如递归调用中）,第6章 运行时刻环境的组织,2019/8/6,49,运行时刻内存的典型划分,操作系统收到运行目标程序的指令，分配一块连续的内存空间使目标程序在其上运行,栈：支持过程的递归调用,堆：支持动态内存申请,第6章 运行时刻环境的组织,代码,静态数据,栈,堆,2019/8/6,50,活动记录,是一段连续的存储区，用以存放过程的一次执行所需要的信息，如局部数据,第6章 运行时刻环境的组织,2019/8/6,51,第6章 运行时刻环境的组织,参数域、状态域、数据域,返回的值,临时变量,实在参数,控制链（可选择的）,存取链（可选择的）,保存的机器状态,局部数据,TOP,TOP_SP,2019/8/6,52,静态存储分配,动态存储分配,栈式分配 和 堆式分配,第6章 运行时刻环境的组织,2019/8/6,53,栈式存储分配的思想：,在运行空间中划分一块存储空间作为栈区,程序运行时每当调用一个过程，就将该过程的活动记录压入栈中，过程执行完毕将它的活动记录从栈中弹出,第6章 运行时刻环境的组织,2019/8/6,54,非局部名字,最近嵌套的作用域规则,第6章 运行时刻环境的组织,2019/8/6,55,C 语言,符号表组织与非局部名字的访问,第6章 运行时刻环境的组织,2019/8/6,56,Pascal 语言,符号表组织,非局部名字的访问（