编译原理复习提纲

2023/2/11编译器一个编译程序就是一个语言翻译程序，它把一种语言（称作源语言）书写的程序翻译成另一种语言（称作目标语言）书写的等价的程序。第1章编译概述2023/2/12编译的分析-综合模型分析：分析源程序，计算其基本属性，生成源程序的中间表示综合：将源程序的中间表示转换为目标代码第1章编译概述2023/2/13编译的逻辑阶段词法分析语法分析语义分析中间代码生成代码优化目标代码生成第1章编译概述2023/2/14**符号表管理**出错处理第1章编译概述2023/2/15遍对源程序或源程序中间表示的一次扫描，每一遍读入一个文件，执行一个或几个阶段的编译操作，并输出源程序的一个中间表示遍数多：编译器结构清晰，但时间效率不高遍数少：编译速度快，但对机器的内存要求高第1章编译概述2023/2/16语言某个字母表上的符号串的集合第2章程序语言的基本知识2023/2/17文法G—

四元组（VT，VN，S，P）：上下文无关文法A→εA→α第2章程序语言的基本知识2023/2/18推导与归约推导是用产生式的右部代替左部，归约是用产生式的左部代替右部，归约是推导的逆过程第2章程序语言的基本知识2023/2/19最左推导与最右推导最右归约与最左归约第2章程序语言的基本知识2023/2/110句型与句子句型：从文法的开始符号出发进行零步或多于零步的推导得到的文法符号串句型可以既包含终结符号又包含非终结符号，只包含终结符号的句型称为句子第2章程序语言的基本知识2023/2/111语言的形式定义文法G推导出的所有句子组成的集合，称为语言，记为L（G）第2章程序语言的基本知识2023/2/112句型的短语、直接短语和句柄如果SαAδ和Aβ，则称β是关于A的，句型αβδ的一个短语（子树的叶子）SαAδβ第2章程序语言的基本知识2023/2/113如果SαAδ和A=>β，则称β是关于A的，句型αβδ的一个直接短语（只有父子两代的子树的叶子）SαAδβ第2章程序语言的基本知识2023/2/114最左直接短语称为句柄最左性体现在分析树和句型中SαAδβ第2章程序语言的基本知识2023/2/115句型的素短语、最左素短语1、β是关于A的，句型αβδ的一个短语2、β至少含有一个终结符3、β除自身外不含更小的带终结符的短语称β是关于A的，句型αβδ的一个素短语句型最左边的素短语称为最左素短语第2章程序语言的基本知识2023/2/116句子、文法和语言的二义性如果一个文法的句子有两棵或两棵以上的分析树，称此句子是二义的最左（右）推导与分析树一一对应，句子二义说明它有两个或以上最左（右）推导第2章程序语言的基本知识2023/2/117如果一个文法有一个句子是二义的，此文法称为二义文法如果一个语言的所有文法都是二义的，称此语言是二义的第2章程序语言的基本知识2023/2/118正规表达式正规表达式是一个表示字符串格式的模式用来描述单词符号的结构递归定义第3章词法分析2023/2/119有限自动机是具有离散输入与离散输出的一种数学模型输入：字符串输出：是、否它能对输入字符串是否属于某个模式（正规集、正规语言）作出判断第3章词法分析2023/2/120非确定的有限自动机—NFAS—

状态集合Σ—

输入符号集合move—

转换函数（S×Σ→2S）S0

—

开始状态F—

接受状态集合第3章词法分析2023/2/121确定的有限自动机—DFA没有ε边转移一个状态面临一个输入符号时最多只转移到一个状态第3章词法分析2023/2/122NFA-DFA的转换——

子集构造法从正规表达式构造NFADFA的化简（最小化）第3章词法分析2023/2/123自顶向下分析：从根到叶子来建立句子的分析树或，给出句子的一个从开始符号出发的推导序列第4章语法分析2023/2/124自底向上分析：从叶子到根来建立句子的分析树或，给出一个从句子出发到开始符号的归约序列第4章语法分析2023/2/125不确定的自顶向下分析：带回溯的分析方法本质上是一种基于穷举原理的试探方法，是个反复使用不同的产生式谋求匹配输入串的过程不确定性体现在每次选择的产生式不一定是正确的第4章语法分析2023/2/126确定的自顶向下分析：基本思想：从文法的开始符号出发，根据当前的输入符号和其它信息，唯一地确定选用哪条产生式往下推导，构造分析树。无论对错，都没有回溯第4章语法分析2023/2/127FIRST集：FOLLOW集：SELECT集构造LL（1）分析表LL（1）文法第4章语法分析2023/2/128提取左因子含有上面产生式的文法不是LL（1）的，因为:SELECT（A→αβ）∩SELECT（A→αγ）≠ф文法中可能含有形如：A→αβ|αγ的产生式第4章语法分析2023/2/129A→αβ1|αβ2|αβ3|…|αβn┝A→α（β1|β2|β3|…|βn）┝A→αA’A’→β1|β2|β3|…|βn第4章语法分析2023/2/130消除左递归文法可能含有形如A→Aα|β的产生式或

AAα的推导，称为左递归文法左递归文法不是LL（1）文法，第4章语法分析2023/2/131自底向上分析法，又称为移进-归约法，它的实现思想：对输入符号串自左向右进行扫描，并将输入符逐个移入一个先进后出栈中，边移进边分析，一旦栈顶符号串形成某个句型的可归约串时，就用相应产生式的左部非终结符代替此可归约串。重复这一过程，直到归约到栈中只剩下文法的开始符号时分析成功。第4章语法分析2023/2/132算符优先分析的基本思想：利用算符优先关系来寻找可归约串算符优先分析第4章语法分析2023/2/133LR（k）分析技术：L指从左至右扫描输入符号串R指构造一个最右推导的逆过程（最左归约）k指在作出分析决定前要向前看的输入符号个数，通常为0或1LR分析技术是功能最强的（自底向上）语法分析技术，适用文法广，效率高，分析能力强第4章语法分析2023/2/134LR分析过程中的性质与特点：栈中的文法符号串并上剩余的输入串构成一个右句型（规范句型）当该右句型的句柄出现在栈顶时，归约，否则，移进栈中的文法符号串是当前句型的前缀，该前缀不包含句型句柄后面的符号，称之为活前缀第4章语法分析2023/2/135语义分析阶段分析源程序的含义，并作相应的处理，语义分析的基本功能：确定类型类型检查产生中间代码语义分析的主流技术——

语法制导翻译技术第5章语法制导翻译2023/2/136文法符号的属性： 1、综合属性：属性值是分析树中该结点的子结点的属性值的函数 2、继承属性：属性值是分析树中该结点的父结点和/或兄弟结点的属性值的函数第5章语法制导翻译2023/2/137语法制导定义：为每一条产生式（Aα）引入一套语义规则规则形式：b:=f(c1,c2,…,ck)第5章语法制导翻译2023/2/138语法制导翻译:根据语法分析中产生式对应的语义规则进行翻译的方法称为语法制导翻译。第5章语法制导翻译2023/2/139S-属性定义只含有综合属性的语法制导定义第5章语法制导翻译2023/2/140L-属性定义是一种语法制导定义对于产生式A→X1X2…Xn右部Xj的继承属性，它依赖于：

1、X1，X2，…，Xj-1（Xj左边的文法符号）的属性

2、A的继承属性**L-属性定义包含S-属性定义第5章语法制导翻译2023/2/141翻译模式：将语义规则放到{}中，并插入到产生式右部的适当位置，以反映语义规则的计算顺序，这种书写形式称之为翻译模式第5章语法制导翻译2023/2/142从L-属性定义出发，构造一个满足要求的翻译模式

将计算产生式右边某文法符号的继承属性的语义规则插入到此符号之前将计算产生式左边非终结符号综合属性的语义规则放在产生式右端的末尾第5章语法制导翻译2023/2/143L-属性定义—

深度优先翻译—

两遍扫描S-属性定义—

自底向上翻译—

一遍扫描第5章语法制导翻译2023/2/144三地址代码一般形式：x:=yopz一般含三个地址（名字、常数、临时变量），两个操作数，一个运算结果中间代码第7章中间代码生成2023/2/145根据给定语法制导定义，翻译赋值语句、布尔表达式、控制流语句等，得到中间代码参考例子，掌握方法第7章中间代码生成2023/2/146代码优化编译时刻为改进目标程序的质量而进行的各项工作与机器相关的优化与机器无关的优化第9章代码优化2023/2/147根据优化范围局部优化

——

针对程序基本块循环优化

——

针对循环体全局优化

——

针对整个程序第9章代码优化2023/2/148名字的联编名字的左值—

内存地址，存储名字的瞬时值名字的右值—

名字的瞬时值名字的联编

—

将一个内存地址与一个名字联系起来在程序的一次运行中，一个名字右值（瞬时值）可能会经常改变，一个名字也可能被联编到多个地址（如递归调用中）第6章运行时刻环境的组织2023/2/149运行时刻内存的典型划分操作系统收到运行目标程序的指令，分配一块连续的内存空间使目标程序在其上运行栈：支持过程的递归调用堆：支持动态内存申请第6章运行时刻环境的组织代码静态数据栈堆2023/2/150活动记录是一段连续的存储区，用以存放过程的一次执行所需要的信息，如局部数据第6章运行时刻环境的组织2023/2/151第6章运行时刻环境的组织参数域、状态域、数据域返回的值临时变量实在参数控制链（可选择的）存取链（可选择的）保存的机器状态局部数据TOPTOP_SP2023/2/152静态存储分配动态存储分配栈式分配

和堆式分配第6章运行时刻环境的组织2023/2/153栈式存储分配的思想：在运行空间中划分一块存