编译原理笔记.docVIP

编译原理

Chapter1编译概述

编译程序：将高级语言的源程序翻译成等价的机器语言或汇编语言的目标程序

编译方式程序运行阶段：编译+运行or编译+汇编+运行（编译程序+汇编程序）

解释方式只有解释执行阶段，根本区别是不生成目标程序

编译程序的构成：词法分析，语法分析，语义分析和中间代码生成，代码优化，目标代码生成，表格管理，出错处理

阶段划分是在逻辑结构上，不是实际执行的顺序，可以把几个不同阶段组织为一遍扫描

代码优化和中间代码生成不是必需的

编译程序与具体的机器和语言有关

目标代码需要有运行系统和初始数据才能进行运行计算

生成编译程序的方法：自编译or移植

Chapter2文法和语言

描述程序设计语言考虑的因素：语法，语义和语用

闭包和正闭包的关系：

只含空串的集合和空集：

形式语言的描述：有穷时用枚举，无穷时用文法

文法：

设计文法时要注意空串是否在形式语言中，以及表达能力是否正确

最右推导为规范推导，最左规约为规范规约

当一个语言是无穷集合时，定义该语言的文法一定是递归的

求短语、直接短语和句柄的格式：句型...中的子串...是（相对于非终结符...）句型...的短语（且为直接短语/句柄）

文法二义性：存在句子有两棵不同的语法树，有两个不同的最右（最左）推导（规约） 语言二义性：不存在无二义性的文法

文法二义性可以通过非形式规则或改写消除

0型无限制文法，1型上下文有关文法，2型上下文无关文法，3型正规文法

多余规则：左部符号不可达or无法推出终结符号串

Chapter3词法分析与有穷自动机

词法分析程序：扫描和分解字符串形式的源程序，识别出具有独立意义的单词符号，并以（单词种别，单词自身的值）得形式输出

单词符号的两种定义方式：正规文法和正规式

正规式与正规集一一对应，描述能力与正规文法等价，无法处理等

正规文法到正规式：联立解正规式方程组，基本型是和

正规式到正规文法：反复添加非终结符，基本型是和

单词符号的识别方式：有穷自动机（也可用来描述正规集，能力相同）

DFA：，f单值函数，初态唯一，终态不唯一

NFA：，f多值函数且允许输入（），初态不唯一

正规式到NFA：化简后分段转化

FA到正规式：添加总初态节点X和总终态节点Y，逐步消去中间节点

NFA到DFA：1）确定化，；

2）最简化，删去多余状态，合并等价（一致性，蔓延性）状态

正规文法与有穷自动机的互相转化

Chapter4语法分析

语法分析程序：输入词法分析后的单词符号串，输出句子的语法树或错误表

自上而下分析：

1）要进行确定分析，则文法必须无左递归和无回溯

2）消除左递归：

消除回溯：提取公共左因子，判断是否为LL(1)文法

3）递归下降分析法：scanner()和error()何时使用，main()的写法

4）预测分析法：预测分析表的构造，反序入栈；

分析表无多重定义元素表明LL(1)，优点是分析表相对小

自下而上分析：

1）可规约串在规范规约分析法中是句柄，在算符优先分析法中是最左素短语；

2）算符优先分析法

算符文法规则右部没有相邻非终结符，算符优先文法非终结符间有唯一优先关系

算符优先关系表的构造：FIRSTVT(A)和LASTVT(A)

素短语：含终结符的直接短语

不考虑非终结符的作用，速度快但可能错误识别文法中不含的句子

3）LR分析法综述

对文法要求最少，可处理大部分无二义性上下文无关文法

LR分析表=分析动作ACTION表+状态转换GOTO表

四种动作：移近s，规约r，接受acc，报错

4）LR(0)分析法

LR(0)项目指明对活前缀的识别状态，分为规约、移近、待约和接受项目；

DFA中每个状态对于若干项目的集合

LR(0)分析表中没有移近-规约冲突和规约-规约冲突则是LR(0)文法

5）SLR(1)分析法

在LR(0)分析法基础上向前查看一个输入符号，避免无脑规约

6）LR(1)分析法

LR(1)项目=[LR(0)项目，有哪些信誉好的足球投注网站符]，规约仅在输入符号是有哪些信誉好的足球投注网站符时进行

Chapter5语法制导翻译技术和中间代码生成

语义分析的任务：静态语义审查，执行真正的翻译（生成中间代码或目标代码）

语法制导翻译法不是形式化方法，使用属性文法描述语义

综合属性自下而上，继承属性自上而下传递信息

常用中间代码：逆波兰式，三元式，四元式，树形表示

简单算术表达式到四元式的翻译

布尔表达式到四元式的翻译

Chapter7代码优化

代码优化的目的：生成高效率（存储空间少，运行时间短）的目标代码

代码优化的分类：

是否涉及具体计算机：与机器有关