编译原理复习提纲

1、2022-3-161n编译器编译器n一个编译程序就是一个语言翻译程序，它把一种语言（称作源语言）书写的程序翻译成另一种语言（称作目标语言）书写的等价的程序。第第1章章 编译概述编译概述2022-3-162n编译的分析编译的分析-综合模型综合模型n分析：分析源程序，计算其基本属性，生成源程序的中间表示n综合：将源程序的中间表示转换为目标代码第第1章章 编译概述编译概述2022-3-163n编译的逻辑编译的逻辑阶段阶段n词法分析词法分析n语法分析语法分析n语义分析语义分析n中间代码生成中间代码生成n代码优化代码优化n目标代码生成目标代码生成第第1章章 编译概述编译概述2022-3-164n* 符号

2、表管理n* 出错处理第第1章章 编译概述编译概述2022-3-165n遍遍n对源程序或源程序中间表示的一次扫描，每一遍读入一个文件，执行一个或几个阶段的编译操作，并输出源程序的一个中间表示n遍数多：编译器结构清晰，但时间效率不高n遍数少：编译速度快，但对机器的内存要求高第第1章章 编译概述编译概述2022-3-166n语言语言n某个字母表上的符号串的集合第第2章章 程序语言的基本知识程序语言的基本知识2022-3-167n文法文法 G 四元组（四元组（VT，VN，S，P）：）：n上下文无关文法上下文无关文法nA nA 第第2章章 程序语言的基本知识程序语言的基本知识2022-3-168n推导与

3、归约推导与归约n推导推导是用产生式的右部代替左部，归约归约是用产生式的左部代替右部，归约是推导的逆过程第第2章章 程序语言的基本知识程序语言的基本知识2022-3-169n最左推导与最右推导最左推导与最右推导n最右归约与最左归约最右归约与最左归约第第2章章 程序语言的基本知识程序语言的基本知识2022-3-1610n句型句型 与与 句子句子n句型：从文法的开始符号出发进行零步或多于零步的推导得到的文法符号串n句型可以既包含终结符号又包含非终结符号，只包含终结符号的句型称为句子第第2章章 程序语言的基本知识程序语言的基本知识2022-3-1611n语言语言的形式定义的形式定义n文法 G 推导出的

4、所有句子组成的集合，称为语言语言，记为 L（G）第第2章章 程序语言的基本知识程序语言的基本知识2022-3-1612n句型的短语、直接短语和句型的短语、直接短语和句柄句柄n如果S A和A ，则称是关于A的，句型的一个短语短语（子树的叶子）*SA第第2章章 程序语言的基本知识程序语言的基本知识2022-3-1613n如果S A和 A =，则称是关于 A的，句型的一个直接短语直接短语（只有父子两代的子树的叶子）*SA第第2章章 程序语言的基本知识程序语言的基本知识2022-3-1614n最左直接短语称为句柄句柄n最左性体现在分析树和句型中SA第第2章章 程序语言的基本知识程序语言的基本知识202

5、2-3-1615n句型的素短语、最左素短语1、是关于A的，句型的一个短语2、至少含有一个终结符3、除自身外不含更小的带终结符的短语称是关于A的，句型的一个素短语素短语n句型最左边的素短语称为最左素短语最左素短语第第2章章 程序语言的基本知识程序语言的基本知识2022-3-1616n句子、文法和语言的二义性句子、文法和语言的二义性n如果一个文法的句子有两棵或两棵以上的分析树，称此句子是二义句子是二义的n最左（右）推导与分析树一一对应，句子二义说明它有两个或以上最左（右）推导第第2章章 程序语言的基本知识程序语言的基本知识2022-3-1617n如果一个文法有一个句子是二义的，此文法称为二义文法二

6、义文法n如果一个语言的所有文法都是二义的，称此语言是二义的语言是二义的第第2章章 程序语言的基本知识程序语言的基本知识2022-3-1618n正规表达式正规表达式n正规表达式是一个表示字符串格式的模式n用来描述单词符号的结构n递归定义递归定义第第3章章 词法分析词法分析2022-3-1619n有限自动机有限自动机n是具有离散输入与离散输出的一种数学模型n输入：字符串n输出：是、否n它能对输入字符串是否属于某个模式（正规集、正规语言）作出判断第第3章章 词法分析词法分析2022-3-1620n非确定的有限自动机非确定的有限自动机 NFAnS 状态集合状态集合n 输入符号集合输入符号集合nmove

7、 转换函数（转换函数（S 2S）nS0 开始状态开始状态nF 接受状态集合接受状态集合第第3章章 词法分析词法分析2022-3-1621n确定的有限自动机确定的有限自动机 DFAn没有边转移n一个状态面临一个输入符号时最多只转移到一个状态第第3章章 词法分析词法分析2022-3-1622nNFA-DFA 的转换的转换 子集构造法子集构造法n从正规表达式构造从正规表达式构造 NFAnDFA 的化简（最小化）的化简（最小化）第第3章章 词法分析词法分析2022-3-1623n自顶向下分析：自顶向下分析：n从根到叶子来建立句子的分析树n或，给出句子的一个从开始符号出发的推导序列第第4章章 语法分析语

8、法分析2022-3-1624n自底向上分析：自底向上分析：n从叶子到根来建立句子的分析树n或，给出一个从句子出发到开始符号的归约序列第第4章章 语法分析语法分析2022-3-1625n不确定的自顶向下分析：不确定的自顶向下分析：n带回溯的分析方法n本质上是一种基于穷举原理的试探方法一种基于穷举原理的试探方法，是个反复使用不同的产生式谋求匹配输入串的过程n不确定性体现在每次选择的产生式不一定是每次选择的产生式不一定是正确的正确的第第4章章 语法分析语法分析2022-3-1626n确定的自顶向下分析：确定的自顶向下分析：n基本思想：从文法的开始符号出发，根据当前的输入符号输入符号和其它信息其它信息

9、，唯一地确定选用哪条产生式往下推导，构造分析树。n无论对错，都没有回溯第第4章章 语法分析语法分析2022-3-1627nFIRST集：集：nFOLLOW集：集：nSELECT集集n构造构造LL（1）分析表）分析表nLL（1）文法）文法第第4章章 语法分析语法分析2022-3-1628n提取左因子提取左因子n含有上面产生式的文法不是 LL（1）的，因为: SELECT（ A ） SELECT（ A ） n文法中可能含有形如：A | 的产生式第第4章章 语法分析语法分析2022-3-1629A 1 | 2 | 3 | | n A （1 | 2 | 3 | | n） A A A 1 | 2 | 3

10、 | | n第第4章章 语法分析语法分析2022-3-1630n消除左递归消除左递归n文法可能含有形如 A A | 的产生式或 A A的推导，称为左递归文法左递归文法n左递归文法不是 LL（1）文法，第第4章章 语法分析语法分析2022-3-1631n自底向上分析法自底向上分析法，又称为，又称为移进移进-归约法归约法，它的实现思想：它的实现思想：n对输入符号串自左向右进行扫描，并将输入符逐个移入一个先进后出栈中，边移进移进边分析，一旦栈顶符号串形成某个句型的可归约可归约串串时，就用相应产生式的左部非终结符代替此可归约串。重复这一过程，直到归约到栈中只剩下文法的开始符号时分析成功。第第4章章 语

11、法分析语法分析2022-3-1632n算符优先分析的基本思想：算符优先分析的基本思想：n利用算符优先关系来寻找可归约串n算符优先分析算符优先分析第第4章章 语法分析语法分析2022-3-1633nLR（k）分析技术：）分析技术：nL 指从左至右扫描输入符号串nR 指构造一个最右推导的逆过程（最左归约）nk 指在作出分析决定前要向前看的输入符号个数，通常为 0 或 1nLR 分析技术是功能最强的（自底向上）语法分析技术，适用文法广，效率高，分析能力强第第4章章 语法分析语法分析2022-3-1634nLR分析过程中的性质与特点：分析过程中的性质与特点：n栈中的文法符号串并上剩余的输入串构成一个右

12、句型（规范句型）n当该右句型的句柄出现在栈顶时，归约，否则，移进n栈中的文法符号串是当前句型的前缀，该前缀不包含句型句柄后面的符号，称之为活前缀活前缀第第4章章 语法分析语法分析2022-3-1635n语义分析阶段分析源程序的含义，并作相语义分析阶段分析源程序的含义，并作相应的处理，语义分析的基本功能：应的处理，语义分析的基本功能：n确定类型确定类型n类型检查类型检查n产生中间代码产生中间代码n语义分析的主流技术语义分析的主流技术 语法制导翻译语法制导翻译技术技术第第5章章 语法制导翻译语法制导翻译2022-3-1636n文法符号的属性：文法符号的属性：1、综合属性综合属性：属性值是分析树中该

13、结点的子结点的属性值的函数 2、继承属性继承属性：属性值是分析树中该结点的父结点和和/或或兄弟结点的属性值的函数第第5章章 语法制导翻译语法制导翻译2022-3-1637n语法制导定义：语法制导定义：n为每一条产生式（A ）引入一套语义规则n规则形式：b := f (c1,c2,ck)第第5章章 语法制导翻译语法制导翻译2022-3-1638n语法制导翻译语法制导翻译:n根据语法分析中产生式对应的语义规则语义规则进行翻译的方法称为语法制导翻译语法制导翻译。第第5章章 语法制导翻译语法制导翻译2022-3-1639nS -属性定义属性定义n只含有综合属性的语法制导定义第第5章章 语法制导翻译语法

14、制导翻译2022-3-1640nL -属性定义属性定义n是一种语法制导定义n对于产生式 AX1X2Xn 右部 Xj 的继承属性，它依赖于：1、 X1，X2，Xj-1 （ Xj左边的文法符号）的属性2、A 的继承属性n* L-属性定义包含 S-属性定义第第5章章 语法制导翻译语法制导翻译2022-3-1641n翻译模式：翻译模式：n将语义规则放到 中，并插入到产生式右部的适当位置，以反映语义规则的计算顺序，这种书写形式称之为翻译模式翻译模式第第5章章 语法制导翻译语法制导翻译2022-3-1642n从 L-属性定义出发，构造一个满足要求的翻译模式n 将计算产生式右边某文法符号的继承属性的语义规则

15、插入到此符号之前n将计算产生式左边非终结符号综合属性的语义规则放在产生式右端的末尾第第5章章 语法制导翻译语法制导翻译2022-3-1643nL-属性定义 深度优先翻译 两遍扫描nS-属性定义 自底向上翻译 一遍扫描第第5章章 语法制导翻译语法制导翻译2022-3-1644n三地址代码三地址代码n一般形式：x := y op zn一般含三个地址（名字、常数、临时变量），两个操作数，一个运算结果n中间代码中间代码第第7章章 中间代码生成中间代码生成2022-3-1645n根据给定语法制导定义，翻译赋值语句、根据给定语法制导定义，翻译赋值语句、布尔表达式、控制流语句等，得到中间代布尔表达式、控制流

16、语句等，得到中间代码码n参考例子，掌握方法第第7章章 中间代码生成中间代码生成2022-3-1646n代码优化代码优化n编译时刻为改进目标程序的编译时刻为改进目标程序的质量质量而进行的各而进行的各项工作项工作n与机器相关的优化与机器相关的优化n与机器无关的优化与机器无关的优化第第9章章 代码优化代码优化2022-3-1647n根据优化范围根据优化范围n局部优化 针对程序基本块基本块n循环优化 针对循环体n全局优化 针对整个程序第第9章章 代码优化代码优化2022-3-1648n名字的联编n名字的左值左值 内存地址，存储名字的瞬时值n名字的右值右值 名字的瞬时值n名字的联编联编 将一个内存地址与

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