编译原理复习

第1章引论

编译程序的基本任务是将源语言程序翻译成等价的目标语言程序
编译过程

包括词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成6个阶段，除此之外还有表格管理以及出错处理。
1. 词法分析
  
  任务：从左到右一个字符一个字符的读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个单词。
  
  输入为：源程序
2. 语法分析
  
  任务：在词法分析的基础上将单词序列分解成各类语法短语。
3. 语义分析
  
  任务：审查源程序有无语义错误，为代码生成阶段收集类型信息。
4. 中间代码生成
  
  常用的三种方式：三元式、四元式、逆波兰式。
5. 代码优化
6. 目标代码生成
什么是编译程序

从功能上看，一个编译程序就是一个语言翻译程序。语言翻译程序把一种语言（称为源语言）书写的程序翻译成另一种语言（称作目标语言）的等价程序。

什么是源程序

源语言编写的程序称为源程序

什么是目标程序

目标语言书写的程序称为目标程序

编译阶段的前端、后端

有时把编译的过程分为前端和后端，前端的工作主要依赖于源语言而与目标机无关，前端通常包括词法分析、语法分析、语义分析和中间代码生成这些阶段，某些优化工作也可在前端做，还包括与前端每个阶段相关的出错处理工作和符号表管理工作。

后端指的是那些依赖于目标机而一般不依赖于源语言，只与中间代码有关的那些阶段的工作，即目标代码生成，以及相关出错处理和符号表的操作。

一个编译过程可由一遍、两遍或多遍完成。所谓“遍”，也称为“趟”，是对源程序或其等价的中间语言程序从头到尾扫描并完成规定任务的过程。

解释程序和编译程序的区别

解释程序以源程序作为输入，不产生目标程序，而是边解释边执行源程序本身。
编译程序实现以源语言表示的算法向目标语言表示的算法的等价变换。

第2章文法和语言

直接推导

设α->β是文法G=(V_N,V_T,P,S)的规则(或说是P中的一个产生式)，γ和δ是V^*中的任意符号，若有符号串v、w满足 v = γαδ， w = γβδ 则说v（应用规则α->β）直接产生w，或说w是v的直接推导。

语言

文法G所产生的语言定义为集合{x | S ⇒ x，其中S为文法识别符号，且x∈V_T^* ,推导为星推导}

文法描述的语言是该文法一切句子的集合。

文法的类型

1.设G=(V_N,V_T,P,S)，如果它的每个产生式 α->β 是这样一种结构： α∈(V_N∪V_T)^*

且至少含有一个非终结符，而 β∈(V_N∪V_T)^*，则G是一个0型文法，也叫短语文法。

2.设G=(V_N,V_T,P,S)作为一个文法，若P中的每一个产生式 α->β 均满足 |β| ≥ |α| ，仅仅 S->ε 除外，则文法G是1型或上下文有关的。

3.设G=(V_N,V_T,P,S)，若P中的每一个产生式 α->β 满足：α是一个非终结符， β∈(V_N∪V_T)^* ，则此文法称为2型的或上下文无关的。

4.设G=(V_N,V_T,P,S)，若P中的每一个产生式的形式都是A->aB 或 A->a，其中A和B都是非终结符，a∈V_T^*，则G是3型文法或正规文法。
语法树

描述上下文无关文法的句型推导的直观工具，即语法树，也称推导树。

最左（最右）推导、规范推导

如果在推导的任何一步 α⇒β，其中α、β是句型，都是对α中的最左（最右）非终结符进行替换，则称这种推导为最左（最右）推导。最右推导通常被称为规范推导。

如果一个文法存在某个句子对应两颗不同的语法树，则说这个文法是二义的。

如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。

文法产生的语言是相同的，则他们是等价的。

短语、直接短语、句柄
书上的定义：

我的理解：

一个句型的语法树中任一子树叶结点所组成的符号串都是该句型的短语。

如果子树中不再包含其他的子树，即A只能推导出b，而b不能再推出其他的式子，则b为此句型的直接短语。

直接短语中的最左直接短语为该句型的句柄。

有害规则

所谓有害规则，是指形为U->U的产生式，它对描述语言显然是没有必要的，说它有害是说它会引起文法的二义性。

第3章词法分析

经过编译得到的目标程序是机器语言程序/汇编语言程序

词法分析程序所输出的单词符号可采用以下二元式表示：(单词种别，单词自身的值)

正规文法和正规式的相互转换P46
DFA

一个确定的有穷自动机M是一个五元组：

M = (K,Σ ,f,S,Z)

其中：

（1）K 是一个有穷集，它的每个元素称为一个状态。

（2）Σ 是一个有穷字母表，它的每个元素称为一个输入符号，所以也称 Σ 为输入符号表。

（3）f 是转换函数，是 K×Σ->K 上的映像。例如，f(k1,a)=k2(k1∈K,k2∈K)，就意味着，当前状态为k1，输入字符为a时，将转换到下一个状态k2，把k2称作k1的一个后继状态。

（4）S∈K，是唯一的一个初态。

（5）Z⊆K，是一个终态集，终态也称可接收状态或结束状态。
NFA

一个不确定的有穷自动机M是一个五元组：

M = (K,Σ ,f,S,Z)

其中：

（1）K 是一个有穷集，它的每个元素称为一个状态。

（2）Σ 是一个有穷字母表，它的每个元素称为一个输入符号

（3）f是一个从 K×Σ^*

到 K 的全体子集的映像，即 K×Σ^* -> 2^k,其中2^k表示K的幂集。

（4）S∈K，是一个非空初态集。

（5）Z⊆K，是一个终态集。

状态集合I的ε-闭包，表示为 ε-closure(I) ，定义为一个状态集，是状态集I中的任何状态S经任意条 ε 弧而能到达的状态的集合。

第4章自顶向下语法分析方法

自顶向下分析方法也称面向目标的分析方法，也就是从文法的开始符号出发企图推导出与输入的单词符号串完全相匹配的句子。若输入串是给定文法的句子，则必能推出，反之必然出错。

确定的自顶向下分析方法，是从文法的开始符号开始，考虑如何根据当前的输入符号(单词符号)唯一地确定选用哪个产生式替换相应非终结符以往下推导，或如何构造一颗相应的语法树。

FIRST集 FOLLOW集提取左公共因子消除左递归 LL(1)预测分析

提取左公共因子

A->α(β|γ) 变化为：

A->αA'

A'->β|γ
消除左递归

S->Sa

S->b 变换为：

S->bS'

S'->aS'|ε

第5章自底向上优先分析

实现自底向上分析最常用的技术是移进-归约分析，它的基本思想是对输入符号串自左向右进行扫描，并将输入符号逐个移入一个后进后出栈中，边移进边分析，一旦栈顶符号串形成某个句型的句柄或其他可规约串时就进行规约，规约的结果是将句柄或其他可规约串从栈顶部分弹出，而将相应的非终结符压入栈中。重复这一过程直到归约到栈中只剩文法的开始符号时则为分析成功，也就确认了输入串是文法的句子。

简单优先分析法归约句柄

算符优先分析法归约最左素短语

最左素短语

设有文法G[S]，其句型的素短语是一个短语，它至少包含一个终结符，并除自身外不包含其他素短语，最左边的素短语称最左素短语。

第7章语法制导的语义计算

终结符具有什么属性

综合属性和继承属性
S-属性文法和L-属性文法
只包含综合属性的属性文法称为S-属性文法、L-属性文法既可以包含综合属性，也可以包含继承属性，但要求产生式右端某文法符号的继承属性的计算只取决于该符号左边符号的属性。

第8章静态语义分析和中间代码生成

符号表的作用

1.收集符号（标识符）的属性信息

2.在语义分析中，符号表所登记的内容是进行上下文语义合法性检查的依据。

3.在目标代码生成阶段，符号表是对符号名进行地址分配的依据。
符号表的常见属性

符号的名字、符号的类别、符号的类型、符号的存储类别和存储分配信息、符号的作用域与可见性......
符号表的总体组织方式
1. 属性总类完全相同的符号放在一起
2. 所有语言中的符号都组织在一张符号表中
3. 折中方式，根据符号属性相似程度分类组织成若干表
符号表项的组织传统上采用三种构造方法

1.线性法
2.散列法
3.二分法

关键字域的组织用关键字池

什么是数组内情向量

编译程序对数组说明的主要工作是把数组有关信息汇集在一个叫做“内情向量”的表格中以便以后计算引用这些信息

信息包括：数组的类型，维数，各维的上下界以及数组的首地址

第9章运行时存储组织

运行时存储区域常常划成目标区、静态数据区、栈区、堆区。
存储分配策略

静态存储分配和动态存储分配，动态分为栈式存储分配和堆式存储分配。
嵌套过程定义中非局部量的访问

实现方法有那些？

采用Display表、为活动记录增加静态链域

PS：
这里只总结了部分知识、大题部分也没有叙述

整理这些重点知识的同时还学会了markdown里怎么打上下标...

编译原理复习

第1章 引论

第2章 文法和语言

第3章 词法分析

第4章 自顶向下语法分析方法

第5章 自底向上优先分析

第7章 语法制导的语义计算

第8章 静态语义分析和中间代码生成

第9章 运行时存储组织