编译原理期末总复习大纲

《编译原理期末总复习大纲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2021/9/61编译器一个编译程序就是一个语言翻译程序，它把一种语言（称作源语言）书写的程序翻译成另一种语言（称作目标语言）书写的等价的程序。第1章编译概述2021/9/62编译的分析-综合模型分析：分析源程序，计算其基本属性，生成源程序的中间表示综合：将源程序的中间表示转换为目标代码第1章编译概述2021/9/63编译的逻辑阶段词法分析语法分析语义分析中间代码生成代码优化目标代码生成第1章编译概述2021/9/64**符号表管理**出错处理第1章编译概述2021/9/65遍对源程序或源程序中间表示的一次扫描，每一遍读入一个

2、文件，执行一个或几个阶段的编译操作，并输出源程序的一个中间表示遍数多：编译器结构清晰，但时间效率不高遍数少：编译速度快，但对机器的内存要求高第1章编译概述2021/9/66语言某个字母表上的符号串的集合第2章程序语言的基本知识2021/9/67文法G—四元组（VT，VN，S，P）：上下文无关文法A→εA→α第2章程序语言的基本知识2021/9/68推导与归约推导是用产生式的右部代替左部，归约是用产生式的左部代替右部，归约是推导的逆过程第2章程序语言的基本知识2021/9/69最左推导与最右推导最右归约与最左归约第2章程序语言的

3、基本知识2021/9/610句型与句子句型：从文法的开始符号出发进行零步或多于零步的推导得到的文法符号串句型可以既包含终结符号又包含非终结符号，只包含终结符号的句型称为句子第2章程序语言的基本知识2021/9/611语言的形式定义文法G推导出的所有句子组成的集合，称为语言，记为L（G）第2章程序语言的基本知识2021/9/612句型的短语、直接短语和句柄如果SαAδ和Aβ，则称β是关于A的，句型αβδ的一个短语（子树的叶子）SαAδβ第2章程序语言的基本知识2021/9/613如果SαAδ和A=>β，则称β是关于A的，句型αβ

4、δ的一个直接短语（只有父子两代的子树的叶子）SαAδβ第2章程序语言的基本知识2021/9/614最左直接短语称为句柄最左性体现在分析树和句型中SαAδβ第2章程序语言的基本知识2021/9/615句型的素短语、最左素短语1、β是关于A的，句型αβδ的一个短语2、β至少含有一个终结符3、β除自身外不含更小的带终结符的短语称β是关于A的，句型αβδ的一个素短语句型最左边的素短语称为最左素短语第2章程序语言的基本知识2021/9/616句子、文法和语言的二义性如果一个文法的句子有两棵或两棵以上的分析树，称此句子是二义的最左（右）推

5、导与分析树一一对应，句子二义说明它有两个或以上最左（右）推导第2章程序语言的基本知识2021/9/617如果一个文法有一个句子是二义的，此文法称为二义文法如果一个语言的所有文法都是二义的，称此语言是二义的第2章程序语言的基本知识2021/9/618正规表达式正规表达式是一个表示字符串格式的模式用来描述单词符号的结构递归定义第3章词法分析2021/9/619有限自动机是具有离散输入与离散输出的一种数学模型输入：字符串输出：是、否它能对输入字符串是否属于某个模式（正规集、正规语言）作出判断第3章词法分析2021/9/620非确定的

6、有限自动机—NFAS—状态集合Σ—输入符号集合move—转换函数（S×Σ→2S）S0—开始状态F—接受状态集合第3章词法分析2021/9/621确定的有限自动机—DFA没有ε边转移一个状态面临一个输入符号时最多只转移到一个状态第3章词法分析2021/9/622NFA-DFA的转换——子集构造法从正规表达式构造NFADFA的化简（最小化）第3章词法分析2021/9/623自顶向下分析：从根到叶子来建立句子的分析树或，给出句子的一个从开始符号出发的推导序列第4章语法分析2021/9/624自底向上分析：从叶子到根来建立句子的分析树

7、或，给出一个从句子出发到开始符号的归约序列第4章语法分析2021/9/625不确定的自顶向下分析：带回溯的分析方法本质上是一种基于穷举原理的试探方法，是个反复使用不同的产生式谋求匹配输入串的过程不确定性体现在每次选择的产生式不一定是正确的第4章语法分析2021/9/626确定的自顶向下分析：基本思想：从文法的开始符号出发，根据当前的输入符号和其它信息，唯一地确定选用哪条产生式往下推导，构造分析树。无论对错，都没有回溯第4章语法分析2021/9/627FIRST集：FOLLOW集：SELECT集构造LL（1）分析表LL（1）文法

8、第4章语法分析2021/9/628提取左因子含有上面产生式的文法不是LL（1）的，因为:SELECT（A→αβ）∩SELECT（A→αγ）≠ф文法中可能含有形如：A→αβ

9、αγ的产生式第4章语法分析2021/9/629A→αβ1

10、αβ2

11、αβ3

12、…

13、αβn┝A→α（β1

14、β2