kN_编译原理_1

大学期间的笔记补全。编译原理内容太多分几次。
课本《编译原理》第三版，陈火旺等编著。
笔记总目录：
一、引论
二、高级语言及其语法描述
三、词法分析
四、语法分析——自上而下分析
五、语法分析——自下而上分析
六、属性文法和语法制导翻译
七、语义分析和中间代码生成
八、优化
九、目标代码生成

一、引论

1.1 什么叫编译程序

程序语言技术的发展：

机器语言（表示机器实际操作的数字代码）-> 汇编语言（以符号形式给出指令和储存地址）-> 高级语言（类似于数学定义或自然语言的简洁形式编写程序）
程序的两种执行方式
- 解释：边解释边执行源语言程序，不产生目标语言程序
  - 优点：易于查出错误；缺点：效率低，运行速度慢
  - Javascript，Basic
  - 相当于源程序的一个执行系统，生成源程序的执行结果
- 编译：产生目标语言的程序再执行，目标语言程序与源程序逻辑等价
  - 优点：只需要分析和翻译一次；缺点：运行中发现错误必须查找整个程序确定
  - Pascal，C，C++
  - 相当于源程序的一个转换系统，生成源程序的目标代码
  JAVA兼具两者，一次编写，逐句运行 -> 达到跨平台的效果（将硬件的异构转嫁到虚拟机上）
  
  C#也同理（在虚拟机上运行的高级语言均同理）

1.2 编译过程概述

词法分析
- 词法分析程序又称扫描程序（Scanner）
- 读取源程序的字符流、识别单词（符号），并转换成内部形式
- 依循语言的词法规则（正规文法）
  
  终结符：能够查阅的有语法含义的符号
- 有效工具：正规式和有限自动机
  
  并不知道每一个表达式具体的含义，也判断不了变量的数据类型
- 状态转换图
  
  状态转换图中，终态带有""的标志，则表示判断该终态需要多读一个字符，判断结束之后要把这个字符推出*，使之进入下一轮判断。
语法分析
- 语法分析又称识别程序（Parser）
- 读入由词法分析程序识别出的符号，根据给定语法规则识别出各个语法单位（短语、程序段等），并声称另一个内部表示（如语法分析树等）
- 常用上下文无关文法描述
  
  非终结符：自发引入的语法范畴（可以理解为终结符的抽象/规约）
  
  语法分析思路：从上往下做推导（根结点->叶子结点），从下而上做裁剪（叶子结点->根结点）
- 方法：递归子程序法，LR分析法，etc.
语义分析中间代码生成
- 语义分析
  - 对语法分析树或其他内部中间表示进行静态语义检查，正确则进行翻译
  - 按照层次关系和先后顺序，伴随进行类型审查等其他补充、修改操作
- 中间代码生成
  - 中间代码是一种独立于具体硬件的记号系统
  - 形式：四元式、三元式、逆波兰式
    
    四元式：算符、运算对象1、运算对象2、运算结果
    
    由语法分析树生成四元式，中间节点全为算符，每一个算符便构成一条四元式代码（三地址码）
  - 中间代码生成的次序与扫描方向有关。不可人为调整。
优化
- 对代码提供教工，提高效率
- 依靠程序的等价交换原则
目标代码生成
- 把中间代码（优化处理后）变换成特定机器上的低级语言代码
- 与机器相关

1.3 编译程序的结构

结构

编译程序的结构
- 表格管理：符号表——编译程序使用中最重要的表格
- 出错处理：语法错误 & 语义错误
遍(Pass)
- 对源程序或源程序的中间结果从头到尾扫描一次，做相关处理，生成新的中间结果或目标程序的过程
  
  四遍扫描
- 编译程序可由一遍、两遍or多遍完成：
  - 多遍：少占内存，耗时多
  - 一遍：多占内存，耗时少

1.4 编译程序的生成

T形图：源语言S、目标语言T、编译程序实现语言I

典型T形图

如果A机器上已有一个用A机器码实现的某高级语言L1的编译程序，则我们可以用 L1语言编写另一种高级语言L2的编译程序，把写好的L2编译程序经过L1编译程序编译后就可得到A机器代码实现的L2编译程序
可这样理解：
- 用L1写成的 L2 -> A
- 用A写成的 L1 -> A (将源代码为L1的程序(该程序功能为L2 -> A)变为A(程序功能仍为L2 -> A))
- 用A写成的 L2 -> A
组合的T形图

二、高级语言及其语法描述

2.1 程序设计语言的定义

程序语言的内涵：
- 语法：组合规律
- 语义
- 语用：目的

2.2 高级语言的一般特性

2.3 程序语言的语法描述

编译原理 = 形式语言理论 + 编译技术

形式语言
- 通过人们公认的符号、表达方式所描述的一种语言，是一种通用语言。
- 形式语言是某个字母表上的字符串的集合，有一定的描述范围。
文法的形式定义
- 文法G是一个四元组 $G=(V_N, V_T, S, £)$
  - $V_N$ :非终结符的有限集合
  - $V_T$ :终结符的有限集合， $V_N ∩ V_T =Φ$
  - $S$ :开始符号且 $S∈ V_N$
  - $£$ :形式为 $P→α$ 的产生式的有限集合，且 $P∈(V_N∪V_T)^* V_N (V_N∪V_T)^* ，α∈ (V_N∪V_T)^*$
    怎么理解 $P∈(V_N∪V_T)^* V_N (V_N∪V_T)^*$ ？
    1. $P$ 属于 $(V_N∪V_T)$ 的闭包： $P∈(V_N∪V_T)^*$
    2. 但是必须要至少有一个 $V_N$ ： $P∈(V_N∪V_T)^* V_N$
    3. 然而非终结符不一定在最后，也可以在最前： $P∈(V_N∪V_T)^* V_N (V_N∪V_T)^*$
  例子：文法 $G1 =( \{ N \}, \{0, 1\},N, \{N→0N, N→1N, N→0, N→1\})$ 其中:
  - $V_N = \{N\}$ ，[非终结符的有限集合]
  - $V_T = \{0, 1\}$ ，[终结符的有限集合/字母表]
  - $S = N$ ，[起始符]
  - $£ = \{N→0N, N→1N, N→0, N→1\}$ 。[产生式]
- 终结符号 $V_T$ :组成语言字母表中的基本符号，属于个体记号
- 非终结符号 $V_N$ :需要进一步定义的符号，非终结符是一个类(或集合)记号，而不是个体记号。
- 开始符号 $S$ 属于非终结符号，至少在某个产生式的左部出现一次（是研究目标）
- 产生式 $£$ (规则) :定义语法单位的一种书写规则
  
  若干个左部相同的产生式如 $P→α_1 , P→α_2 , P→α_3 , ... , P→α_n$ 可合并成一个,缩写为 $P→α_1|α_2|α_3|…|α_n$ , 其中,每个 $α_i$ 称为是 $P$ 的一个候选式。
- 为了简化，文法表示
  - 只写出产生式部分
  - 约定第一个产生式的左部符号为初始符号或在产生式前写上“G[A]”，其中G为文法名，A为初始符号
  例子：
  
  文法G[N]: N→0N, N→1N, N→0, N→1 => 终结符: {0,1}
  
  文法G[E]: E→E+E│E*E│(E)│i => 终结符: {+, *, (, ), i }
直接推导与归约
- 直接推导
  - 如果A→γ是一个产生式，而 $α，β∈(V_T∪V_N)^*$ ，则将产生式A→γ用于符号串αAβ得到符号串αγβ，记为 αAβ => αγβ，称αAβ直接推出αγβ。
  - 推导: 设 $α_1,α_2,...,α_n (n>0)∈(V_T∪V_N)^*$ ，且有 $α_1$ => $α_2$ =>… => $α_n$ ，则称这个序列是从α1到αn的一个推导。
  - 若存在一个α1到αn的一个推导，则称α1可推导出αn。
  - $α1$ => $^+ α_n$ (经一步或若干步推导)
  - $α_1$ => $^* α_n$ (经0步或若干步推导)
- 归约是推导的逆过程
  - 若存在αAβ => αγβ ，则称αγβ能够直接归约成αAβ 。
- 若在推导关系中，每次最先替换最左(右) 的非终结符，则称为最左(右)推导;
- 若在归约过程中，每次最先归约最左(右) 的非终结符，则称为最左(右)归约。
- 最左推导的逆过程是最右归约。
句型、句子和语言
- 句型：假定G是一个文法，E是它的开始符号，如果E => $^* α$ ，则称 $α$ 是文法G的一个句型。
- 句子：仅由终结符组成的句型称为句子。
- 语言：文法G所产生句子的全体。是一个集合。
Chomsky文法体系
- 相较于普通的形式语言，该体系对产生式的形式做了一些规定，分为四类，即0型、1型、2型、3型文法
- 0型：无限制文法，短语文法
  - 对应的语言:递归可枚举语言
  - 与图灵机等价。
- 1型：也称上下文有关文法(CSG:Context-sensitive Grammar)
  - 限制： $|P| \leq |\alpha|$ (在形式为 $P → \alpha$ 的定义中)
  - 对应的语言:上下文有关语言(CSL:Context-sensitive Language)
  - 若不考虑ε，与线性有界自动机(LBA, Linear Bounded Automaton)等价。
- 2型：也称上下文无关文法(CFG:Context-free Grammar)
  - 在1型的基础上，添加限制 $P∈V_N$
  - 对应的语言:上下文无关语言 (CFL: Context-free Language)
  - 对应的自动机:下推自动机(PDA: Pushdown Automaton)。
- 3型：也称正规文法
  - 右线性文法(Right-linear Grammar):任何产生式为 $A→ωB$ 或 $A→ω$ ，其中 $A、B∈ V_N, ω∈ V_T$ 。
  - 左线性文法(Left-linear Grammar):任何产生式为 $A→Bω$ 或 $A→ω$ ，其中 $A、B∈ V_N, ω∈ V_T$ 。
    
    式子右端有且最多只能有一个非终结符，且其位置固定在边缘一侧。
  - 等价于正规式
  - 对应的语言:正规语言
  - 对应的自动机:有限自动机(Finite Automaton)。
    
    自动机分类：
    
    有限/无限自动机：状态数量有限/无限；
    
    确定/非确定自动机：在某一个状态接收同一输入时，转换到的下一个状态确定/不确定。
语法树：语法树是表示一个句型推导过程的图，是一棵倒立的树。
二义性：如果一个文法的句子(句型)存在两棵语法树，那么，该句子是二义性的。如果一个文法包含二义性的句子,则称这个文法是二义性的; 否则，该文法是无二义性的。

三、词法分析

3.1 对词法分析器的要求

单词符号
- 分类：关键字、标识符、常数、运算符、界符
  - 一个语言的单词符号如何分类，分成几类，怎样编码取决于处理上的方便。
    - 标识符一般统归为一种。
    - 常数则宜按类型（整、实、布尔等）分种。
    - 关键字可视其全体为一种，也可以一字一种。采用一字一种的分法实际处理起来较为方便。
    - 运算符可采用一符一种的分法，但也可以把具有一定共性的运算符视为一类。
    - 至于界符一般用一符一种的分法。
- 表示形式：词法分析器输出的单词符号常表示成二元式：（单词种别，单词符号的属性值）
  - 单词种别是语法分析需要的信息
  - 单词符号属性值则是编译其它阶段需要的信息，简称单词值。
- 属性：单词符号的属性是指单词符号的特征或特性。属性值则是反映特性或特征的值。
语法分析器的实现方式
- 完全独立方式：词法分析程序作为单独一遍来实现。词法分析程序读入整个源程序，它的输出作为语法分析程序的输入。
  - 编译程序结构简洁、清晰和条理化
- 相对独立方式：把词法分析程序作为语法分析程序的一个独立子程序。语法分析程序需要新符号时调用这个子程序。
  - 避免了中间文件生成，可以提高效率。

3.2 语法分析器的设计

分析器结构

分析器的结构

超前搜索：一般在常数，算符和界符需要
状态转换图：一个有限方向图

3.3 正规表达式与有限自动机

词法规则 -> 正规式 -> NFA（非确定有限自动机） -> DFA（确定有限自动机） -> 词法分析器(Scanner)

正规式与正规集

字母表上的正规式和正规集递归定义如下：

（1） $ε$ 和 $φ$ 都是 $∑$ 上的正规式，它们所表示的正规集分别为 $\lbrace ε \rbrace$ 和 $φ$ 。
（2）任意元素 $a∈∑$ ， $a$ 是 $∑$ 上的一个正规式，它所表示的正规集是 ${a}$ ；
（3）假定 $U$ 和 $V$ 都是 $∑$ 上的正规式，它们所表示的正规集记为 $L(U)$ 和 $L(V)$ ，那么 $(U|V)$ ， $(U·V)$ 和 $(U)^*$ 都是正规式，他们所表示的正规集分别记为 $L(U)∪L(V)$ ， $L(U)L(V)$ 和 $(L(U))^*$ 。
（4）仅由有限次使用上述三步而得到的表达式才是 $∑$ 上的正规式，它们所表示的字集才是 $∑$ 上的正规集。
- 运算符：
  - |读为”或”
  - ·读为”连接”
  - *读为”闭包”
  一般地，连接符.可省略不写，在不引起混淆的情况下，括号可省去
- 正规式运算符的优先顺序为：*最高，·次之，|最低。
- 若两个正规式所表示的正规集相同，则认为二者等价，记为U=V。
自动机
- 自动机的定义：
  - 具有离散输入输出的数学模型。
  - 自动机接受一定的输入，执行一定的动作，产生一定的结果。使用状态迁移描述整个工作过程。
    
    状态：一个标识，能区分自动机在不同时刻的状况。有限状态系统具有任意有限数目的内部“状态”。
  可能的状态、运行的规则都是事先确定的。一旦开始运行，就按照事先确定的规则工作，因此叫“自动机”。
  - 自动机的本质
    - 根据状态、输入和规则决定下一个状态
    - 状态＋输入＋规则 ―> 状态迁移
确定有限自动机（DFA）
- DFA是一个五元组 $M=(S,Σ,δ,s_0,F)$
  - $S$ : 有限的状态集合，每个元素称为一个状态；
  - $Σ$ : 有限的输入字母表，每个元素称为一个输入字符；
  - $δ$ : 转换函数(状态转移集合) : $S×Σ→S$ ；
  - $s_0$ : 初始状态， $s_0∈ S$ ；（初始状态只能有一个）
  - $F$ : 终止状态集， $F\subseteq S$ ；
- 状态转移矩阵：一个DFA可用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示的值。
- 状态转换图：一个DFA可以表示成一个（确定的）状态转换图。
- 扩展转移函数：
  - $δ '$ 函数
    - 接收一个字符串的状态转移函数。
    - $δ ' :S×Σ^*→S$
  - 对任何 $s∈ S$ ，定义：
    1. $δ '(s,ε)=s$
    2. 若 $ω$ 是一个字符串, $a$ 是一个字符，定义： $δ '(s,ωa)=δ(δ '(s,ω)a)$
  - 对于DFA： $δ '(s,a)=δ(δ '(s,ε)a)=δ (s,a)$ ，即对于单字符， $δ '$ 和 $δ$ 是相等的。
  - 被DFA接收的字符串 : 输入结束后使DFA的状态到达终止状态。否则该字符串不能被DFA接收。
  - DFA接收的语言 : 被DFA接收的字符串的集合。 $L(M) =\lbrace α|δ’ (s_0,α)∈F \rbrace$
非确定有限自动机（NFA）
- NFA是一个五元组
  - $S,Σ$ : 定义同上；
  - $δ$ : 转换函数 : $S×Σ^*→2^S$ (状态子集) ；对于某个状态 $s∈ S$ 和一个输入字母 $a$ : $δ (s,a)=S'\subseteq S$
  - $S_0$ : $S_0∈ S$ 为非空初态集；
  - $F$ : 终止状态集， $F\subseteq S$ ；
- 状态转移矩阵：状态转换矩阵中的每一项都是一个集合。包含空集。
- 被NFA接收的字符串 : 接受一个字符后NFA进入一个状态集，此集合包含至少一个中的状态。
- NFA接收的语言 : 被NFA接收的字符串的集合。 $L(M) =\lbrace α|δ’ (s_0,α)\bigcap F \neq \phi \rbrace$
DFA和NFA的比较：

比较
- 输入字母
  - DFA的每一个状态对于字母表中的每一个符号都有一个转移函数。
  - NFA中，一个状态对于字母表中的每一个符号可能不存在转移函数或者存在空转换。
- 转移状态
  - DFA中的下一状态是确定的，即唯一的
  - NFA中的下一状态是不确定的，可能存在多个转移状态。
- NFA和DFA的等价性：DFA是NFA的特例，所以NFA必然能接收DFA能接收的语言。
  
  NFA转化DFA_1
  
  NFA转化DFA_2
转换矩阵中的集合内都是等价状态（可经过n个达到）

转换矩阵构成方法：由起始态构造等价状态集，开始推导。直到右侧出现的等价集全部已经被推导过为止。

对于有多个初态的NFA，则可以将这些初态视为等价集（可以在初态前加一个新的初态，通过与所有初态相连）。同理，多个终态也可以视为等价集。
正规式与有限自动机的等价性
- 正规式与有限自动机是等价的。
  1. 对任何FA M，都存在一个正规式V，使得：；
  2. 对任何正规式V，都存在一个FA M，使得：；
- 由NFA构造等价正规式：
  
  NFA构造正轨式
- 从正规式构造等价的NFA：（Thompson算法）
  
  正规式构造NFA_1
  
  正规式构造NFA_2
  
  所有的闭包可化简为自循环。
DFA的化简
- DFA的化简释之寻找一个状态数比M少的DFA M'，使L(M)=L(M')。
  
  状态s和t等价：若任意从状态s出发能读出字α停于终态，则从t出发也能读出α而停于终态；反之,若从状态t出发能读出字α停于终态，则从s出发也能读出α而停于终态。
  
  状态s和t可区别：状态s和t不等价。存在状态s读入α停于终态，但状态t读入α不停于终态。
- 化简思路：将DFA M的状态集划分为不相交的子集，使不同的两个子集的状态可区别，同一个子集的状态都等价。
- 化简步骤
  - 把状态集S划分为两个子集，得初始划分 $∏= \lbrace I^{(1)}, I^{(2)} \rbrace$ ，其中 $I^{(1)}$ 为终态集， $I^{(2)}$ 为非终态集；
  - 设当前 $∏= \lbrace I^{(1)}, I^{(2)}, … ,I^{(m)}\rbrace,$ 检查 $∏$ 中每个 $I^{(k)}$ 是否可以再分
    
    依据为:如果存在一个输入字符 $a$ ，使得 $I^{(k)}_a$ 不全包含在现行 $∏$ 的子集中，就将 $I^{(k)}$ 进行划分。
  - 一般地，如果 $I^{(k)}_a$ 落入现行 $∏$ 的N个子集中，则应将 $I^{(k)}$ 划分成N个不相交的组，使得每个组 $I^{(k_i)}$ 的 $I^{(k_i)}_a$ 都落入 $∏$ 的同一子集。
  - 重复第二步,直至 $∏$ 中子集数不再增长为止。
  步骤举例