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