编译原理课件整理.pdf

《编译原理课件整理.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第1章编译概述编译器一个编译程序就是一个语言翻译程序，它把一种语言（称作源语言）书写的程序翻译成另一种语言（称作目标语言）书写的等价的程序。2010/6/71第1章编译概述编译的分析-综合模型分析：分析源程序，计算其基本属性，生成源程序的中间表示综合：将源程序的中间表示转换为目标代码2010/6/72第1章编译概述编译的逻辑阶段词法分析语法分析语义分析中间代码生成代码优化目标代码生成2010/6/73第1章编译概述**符号表管理**出错处理2010/6/74第1章编译概述

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

3、约是推导的逆过程2010/6/78第2章程序语言的基本知识最左推导与最右推导最右归约与最左归约2010/6/79第2章程序语言的基本知识句型与句子句型：从文法的开始符号出发进行零步或多于零步的推导得到的文法符号串句型可以既包含终结符号又包含非终结符号，只包含终结符号的句型称为句子2010/6/710第2章程序语言的基本知识语言的形式定义文法G推导出的所有句子组成的集合，称为语言，记为L（G）2010/6/711第2章程序语言的基本知识句型的短语、直接短语和句柄*如果SαAδ和Aβ

4、，则称β是关于A的，句型αβδ的一个短语（子树的叶子）SαAδβ2010/6/712第2章程序语言的基本知识*如果SαAδ和A=>β，则称β是关于A的，句型αβδ的一个直接短语（只有父子两代的子树的叶子）SαAδβ2010/6/713第2章程序语言的基本知识最左直接短语称为句柄最左性体现在分析树和句型中SαAδβ2010/6/714第2章程序语言的基本知识句型的素短语、最左素短语1、β是关于A的，句型αβδ的一个短语2、β至少含有一个终结符3、β除自身外不含更小的带终结符的短语称β是关于A

5、的，句型αβδ的一个素短语句型最左边的素短语称为最左素短语2010/6/715第2章程序语言的基本知识句子、文法和语言的二义性如果一个文法的句子有两棵或两棵以上的分析树，称此句子是二义的最左（右）推导与分析树一一对应，句子二义说明它有两个或以上最左（右）推导2010/6/716第2章程序语言的基本知识如果一个文法有一个句子是二义的，此文法称为二义文法如果一个语言的所有文法都是二义的，称此语言是二义的2010/6/717第3章词法分析正规表达式正规表达式是一个表示字符串格式的模式用来描

6、述单词符号的结构递归定义2010/6/718第3章词法分析有限自动机是具有离散输入与离散输出的一种数学模型输入：字符串输出：是、否它能对输入字符串是否属于某个模式（正规集、正规语言）作出判断2010/6/719第3章词法分析非确定的有限自动机—NFAS—状态集合Σ—输入符号集合Smove—转换函数（S×Σ→2）S0—开始状态F—接受状态集合2010/6/720第3章词法分析确定的有限自动机—DFA没有ε边转移一个状态面临一个输入符号时最多只转移到一个状态2010/6/72

7、1第3章词法分析从正规表达式构造NFANFA-DFA的转换——子集构造法DFA的化简（最小化）2010/6/722第4章语法分析自顶向下分析：从根到叶子来建立句子的分析树或，给出句子的一个从开始符号出发的推导序列2010/6/723第4章语法分析自底向上分析：从叶子到根来建立句子的分析树或，给出一个从句子出发到开始符号的归约序列2010/6/724第4章语法分析不确定的自顶向下分析：带回溯的分析方法本质上是一种基于穷举原理的试探方法，是个反复使用不同的产生式谋求匹配输入串的过程

8、不确定性体现在每次选择的产生式不一定是正确的2010/6/725第4章语法分析确定的自顶向下分析：基本思想：从文法的开始符号出发，根据当前的输入符号和其它信息，唯一地确定选用哪条产生式往下推导，构造分析树。无论对错，都没有回溯2010/6/726第4章语法分析FIRST集：FOLLOW集：SELECT集构造LL（1）分析表LL（1）文法2010/6/727第4章语法分析提取左因子文法中可能含有形如：A→αβ

9、αγ的产生式含有上面产