编译原理

第一章 引言

1.从面向机器的语言到面向人类的语言

汇编指令：用符号表示的指令被称为汇编指令
汇编语言：汇编指令的集合称为汇编语言

2.语言之间的翻译

转换(也被称为预处理)：高级语言之间的翻译，如FORTRAN到ADA的转换
编译：高级语言可以直接翻译成机器语言，也可以翻译成汇编语言，这两个翻译过程称为编译
汇编：从汇编语言到机器语言的翻译被称为汇编
交叉汇编：将一个汇编语言程序汇编成为可在另一机器上运行的机器指令成为交叉汇编
反汇编：把机器语言翻译成汇编语言
反编译：把汇编语言翻译成高级语言

3. 编译器与解释器

（1）语言翻译的两种基本形态

解释器与编译器的主要区别:运行目标程序时的控制权在解释器而不在目标程序.

（2）各自特点

• 编译器:工作效率高,即时间快、空间省；交互性与动态性差,可移植性差.
• 解释器:工作效率低,,即时间慢、空间费；交互性与动态性好,可移植性好.

共同点:均完成对源程序的翻译.
差异:编译器采用先翻译后执行,解释器采用边翻译边执行.

4. 编译器的工作原理与基本组成

（0）通用程序设计语言的主要成份 声明＋操作＝完整定义

（1）以过程为基本结构的程序设计语言的组成

• 声明性语句：提供操作对象的性质，如数据类型、值、作用域等；
• 操作性语句：确定操作的计算次序，完成实际操作。
• 过程定义 = 过程头＋过程体

（2）以阶段划分编译器

注：符号表管理器和出错处理贯穿编译器工作的各个阶段.

（3）编译器各阶段工作

1> 词法分析：词法分析的输入是源程序,输出是识别出的记号流.目的是识别单词. 至少分以下几类：关键字(保留字)、标识符、字面量、特殊符号

2> 语法分析： 输入是词法分析器返回的记号流,输出是语法树.目的是得到语言结构并以树的形式表示.对于声明性语句,进行符号表的查填,对于可执行语句,检查结构合理的表达式运算是否有意义.

3> 语义分析：根据语义规则对语法树中的语法单元进行静态语义检查,如类型检查和转换等,目的在于保证语法正确的结构在语义分析上也是合法的.

4> 中间代码生成(可选)：生成一种既接近目标语言,又与具体机器无关的表示,便于代码优化与代码生成.

(到目前为止，编译器与解释器可以一致)

5> 中间代码优化(可选)：局部优化、循环优化、全局优化等；优化实际上是一个等价变换，变换前后的指令序列完成同样的功能，但在占用的空间上和程序执行的时间上都更省、更有效

6> 目标代码生成：不同形式的目标代码—汇编语言形式、可重定位二进制代码形式、内存形式(Load-and-Go)

7> 符号表管理：合理组织符号,便于各阶段查找\填写等.

8> 出错处理：

动态错误：源程序中的逻辑错误，发生在程序运行的时候。也称为动态语义错误
静态错误：静态错误分为语法错误和静态语义错误.  
<1> 语法错误：有关语言结构上的错误，如单词拼写错误、表达式缺少操作数、begin和end不匹配
<2> 静态语义错误：分析源程序时可以发现的语言意义上的错误，如加法的两个操作数一个是整形变量，另一个是数组名

（4）编译器的分析\综合模式

逻辑上把编译器分为分析(前端)部分和综合(后端)部分.
1> 分析(前端)：语言结构和意义的分析； 从词法分析到中间代码生成各阶段的工作
2> 综合(后端)：语言意义处理；从中间代码生成到目标代码生成的各阶段的工作
3> 编译器和解释器的区别往往是在形成中间代码之后开始的.

5. 编译器扫描的遍数

每个阶段将程序完整分析一遍的工作模式称为一遍扫描。
(将源程序或源程序的某种形式的中间表示完整分析一遍，亦称作一遍扫描)

第二章 词法分析

1. 词法分析中的若干问题

(1) 记号、模式与单词

单词的分类：关键字(保留字)、标识符、字面量、特殊符号
模式（pattern）：产生/识别单词的规则
记号（token）：按照某个模式(或规则)识别出的元素(一组)
单词（lexeme）：被识别出的元素的值(字符串本身) ，也称为词值

(2) 词法分析器的作用与工作方式

词法分析器的作用：

1> 识别记号并交给语法分析器(根据模式识别记号)
2> 滤掉源程序中的无用成分,如注释、空格和回车等
3> 处理与具体平台有关的输入(如文件结束符的不同表示等)
4> 调用符号表管理器和出错处理器，进行相关处理

工作方式：
1.单独一遍扫描
2.作为语法分析器的子程序
3.并行方式

2. 模式的形式化描述

(1) 字符串与语言

语言L是有限字母表∑上有限长度字符串的集合.
定义中强调两个有限，因为计算机的表示能力有限 ：
1> 字母表是有限的，即字母表中元素是有限多个；
2> 字符串的长度是有限的，即字符串中字符个数是有限多个。

(字符串与字符串集合相关的概念与运算,如前缀、后缀、子串、子序列等，字符串的并、交、连接、差、闭包)

(2) 正规式与正规集

令Σ是一个有限字母表，则Σ上的 正规式 及其表示的集合递归定义如下:
    1. ε是正规式，它表示集合  L(ε) = {ε}
    2. 若a是Σ上的字符，则a是正规式，它表示集合L(a)={a}
    3. 若正规式r和s分别表示集合L(r)和L(s)，则
       （a） r|s是正规式，表示集合L(r)∪L(s)，
       （b） rs是正规式，表示集合L(r)L(s)，
       （c） r*是正规式，表示集合(L(r))*，
       （d）(r)是正规式，表示的集合仍然是L(r)。                                   
       括弧用来改变运算的先后次序！

可用正规式描述(其结构)的语言称为 正规语言 或 正规集 。

若运算的优先级和结合性做下述约定:
    1. 三种运算均具有左结合性质；
    2. 优先级从高到低顺序排列为:闭包运算、连接运算、或运算。
则正规式中不必要的括号可以被省略。

若正规式P和Q表示了同一个正规集，则称P和Q是等价的，记为P=Q

(3) 简化正规式描述(主要是简化书写上的复杂)

(a) 正闭包 若r是表示L(r)的正规式，则r+是表示(L(r))+的正规式，且下述等式成立:r+ = rr* = rr，r = r+|ε;
          +与*具有相同的运算结合性和优先级
(b) 可缺省  若r是正规式，则r?是表示L(r)∪{ε}的正规式，且下述等式成立:r? = r|ε
           ? 与 * 具有相同的运算结合性和优先级
(c) 串    若r是若干字符进行连接运算构成的正规式，则:串“r” =  r ，且: ε= “”，   a = “a”（a是Σ的任一字符）
(d) 字符组 若r是若干字符进行|运算构成的正规式，则可改写为  [r’]，其中r’可以有如下两种书写形式：
             枚举:      如  a|b|e|h，可写为 [abeh]：
             分段:   如0|1|2|3|4|5|6|7|8|9|a|b|c|d|e , 可写为： [0-9a-e]
(e) 非字符组 若[r]是一个字符组形式的正规式，则[^r]是表示∑- L([r])的正规式。 

3. 记号的识别——有限自动机

(1) 不确定的有限自动机（NondeterministicFinite Automaton, NFA）

NFA是一个五元组（5-tuple）：M =（S，∑，move，s0，F），其中
（1） S是有限个状态（state）的集合；
（2） ∑是有限个输入字符（包括ε）的集合；
（3） move是一个状态转移函数，move(si，ch)=sj表示，当前状态si下若遇到输入字符ch，则转移到状态sj；
（4） s0是唯一的初态（也称开始状态）；
（5） F是终态集（也称接受状态集），它是S的子集，包含了所有的终态。

<1> 直观的表示方式

① 状态转换图：用一个有向图来直观表示NFA
② 状态转换矩阵：用一个矩阵来直观表示NFA (矩阵中，状态对应行，字符对应列)

<2> NFA(识别记号)的特点
NFA识别记号的最大特点是它的不确定性，即在当前状态下对同一字符有多于一个的下一状态转移。

具体体现：
定义： move函数是1对多的；
状态转换图：从同一状态出发，可通过多于一条标记相同字符的边转移到不同的状态；
状态转换矩阵： M[si,a]是一个状态的集合

<3> NFA识别记号存在的问题

1.只有尝试了全部可能的路径,才能确定一个输入序列不被接受,而这些路径的条数随着路径长度的增长成指数增长
2.识别过程中需要进行大量回朔，时间复杂度升高且算法复杂

(2) 确定的有限自动机（Deterministic Finite Automaton, DFA）

定义: DFA是NFA的一个特例，其中： 
  （1）没有状态具有ε状态转移(ε-transition)，即状态转换图中没有标记ε的边；
  （2）对每个状态s和每个字符a，最多有一个下一状态。
  
特点：与NFA相比，DFA的特征：确定性
    定义：move（si, a)函数都是 1对1 的；
    转换图 从一个状态出发的任2条边上的标记均不同；
    转换矩阵：M[si,a]是一个状态   且字母表不包括ε。
提示：正规式和有限自动机从两个侧面表示正规式。正规式是描述，自动机是识别。

4. 从正规式到词法分析器

构造词法分析器的一般方法和步骤：
1. 用正规式描述模式（为记号设计正规式）；
2. 为每个正规式构造一个NFA，它识别正规式所表示的正规集；
3. 将构造的NFA转换成等价的DFA，这一过程也被称为确定化；
4. 优化DFA，使其状态数最少，这一过程也被称为最小化；
5. 根据优化后的DFA构造词法分析器。

(1) 从正规式到NFA

Thompson 算法

(2) 从NFA到DFA

- smove(S, a)：从状态集S出发，标记为a的下一状态全体。与move(s, a)的唯一区别：用状态集取代状态
- ε-闭包(T)：从状态集T出发，不经任何字符达到的状态全体
- “子集法”构造DFA

(3) 最小化DFA

​ ① 对于任何两个状态t和s，若从一状态出发接受输入字符串ω，而从另一状态出发不接受ω.

或者，② 从t出发和从s出发到达不同的接受状态，则称ω对状态t和s是可区分的.

​ 不可区分的状态位于一个组内，可以合并成一个状态.

主要步骤：
​ 1.初始划分：终态组 ， 非终态组；
​ 2.利用可区分的概念，反复分裂划分中的组Gi，直到不可再分裂；
​ 3.由最终划分构造D'，关键是选代表和修改状态转移；
​ 4.消除可能的死状态和不可达状态。

5. 从DFA构造词法分析器

分类：表驱动型的词法分析器；直接编码的词法分析器
比较：

第三章 语法分析

词法分析：记号的集合，字符串由字母组成，线性结构
语法分析：句子的集合，句子由记号组成，非线性结构（树）

语法分析的双重含义：

• 语法规则：上下文无关文法（子集：LL文法或LR文法）
• 语法分析：下推自动机（LL或LR分析器）、自上而下分析、自下而上分析

1. 语法分析的若干问题

许多编译器，特别是由自动生成工具构造的编译器，往往其前端的中心部件就是语法分析器

（1）语法分析器的作用

• 根据词法分析器提供的记号流，为语法正确的输入构造分析树（或语法树）
• 检查输入中的语法（可能包括词法）错误，并调用出错处理器进行适
  当处理

（2）语法错误的处理原则

源程序中可能出现的错误

语法(包括词法)错误和语义错误(静态语义错误和动态语义错误)

注：跟第一章的分类角度不同，第一章是从静态错误(语法错误，静态语义错误)和动态错误(动态语义错误)分类的，但是殊途同归。

词法错误：指非法字符或拼写错关键字、标识符等
语法错误：指语法结构出错，如少分号、括号不匹配、begin/end不配对等
静态语义错误：如类型不一致、参数不匹配等
动态语义错误(逻辑错误)：如死循环、变量为零时作除数等

2. 上下文无关文法(CFG)

（1）上下文无关文法(Context Free Grammar,CFG)

 CFG是一个四元组G =（N，T，P，S），其中
（1） N是非终结符（Nonterminals）的有限集合；
（2） T是终结符（Terminals）的有限集合，且N∩T=Φ；
（3） P是产生式（Productions）的有限集合，A→α，其中A∈N(左部),α∈(N∪T)*(右部),若α=ε，则称A→ε为空产生式(也可以记为A →);
（4） S是非终结符，称为文法的开始符号（Start symbol）
 注： S ∈ N , N可以出现在产生式左边和右边，T绝不出现在产生式左边.

（2）CFG产生语言的基本方法－推导

CFG（产生式）通过推导的方法产生语言，即（通俗地讲）从开始符号S开始，反复使用产生式：将产生式左部的非终结符替换为右部的文法符号序列(展开产生式，用=>表示)，直到得到一个终结符序列。

1> 直接推导：利用产生式产生句子的过程中，将用产生式A→γ的右部代替文法符号序列αAβ中的A得到αγβ的过程，称αAβ直接推导出αγβ，记作：αAβ=>αγβ

2> 零步或多步推导：若对于任意文法符号序列α1，α2，...αn，有α1=>α2=>...=>αn，则称此过程为零步或多步推导，记为：α1 =*> αn，其中α1=αn的情况为零步推导。

3> 至少一次推导：若α1≠αn，即推导过程中至少使用一次产生式,则称此过程为至少一步推导，记为：α1 =+> αn

(推导具有自反性和传递性)

4> 由 CFGG 所产生的语言L(G)被定义为: L(G) = { ω┃S ωand ω∈T* }，
​ L(G)称为上下文无关语言(Context Free Language, CFL)，ω称为句子。
​ 若S =* > α，α∈(N∪T)*，则称α为G的一个句型。句子一定是句型，反之不是。

5> 在推导过程中，若每次直接推导均替换句型中最左边的非终结符，则称为最左推导，由最左推导产生的句型被称为左句型。 类似的可以定义最右推导与右句型，最右推导也被称为规范推导。

（3）推导、分析树与语法树

1、分析树既反映语言结构的实质，也反映推导过程。

2、对CFGG的句型，分析树被定义为具有下述性质的一棵树。

（1） 根由开始符号所标记；
（2） 每个叶子由一个终结符、非终结符、或ε标记；
（3） 每个内部结点由一个非终结符标记；
（4） 若A是某内部节点的标记，且X1，X2，...，Xn是该节点从左到右所有孩子的标记，则A→X1X2...Xn是一个产生式。若A→ε，则标记为A的结点可以仅有一个标记为ε的孩子。

注：分析树的叶子，从左到右构成G的一个句型。若叶子仅由终结符标记，则构成一个句子。

3、对CFG G的句型，表达式的语法树被定义为具有下述性质的一棵树:

（1） 根与内部节点由表达式中的操作符标记；
（2） 叶子由表达式中的操作数标记；
（3）用于改变运算优先级和结合性的括号，被隐含在语法树的结构中。

• 语法树是表示表达式结构的最好形式

（4）二义性与二义性的消除

二义性：若文法G对 同 一句子产生不止一棵分析树，则称G是二义的.

结论：
1> 一个句子有多于一棵分析树，仅与文法和句子有关，与采用的推导方法无关；
2> 造成文法二义的根本原因：文法中缺少对文法符号优先级和结合性的规定

二义性消除的方法：
① 改写二义文法为非二义文法；
② 规定二义文法中符号的优先级和结合性，使仅产生一棵分析树。

3. 语法与文法简介

（1）正规式与上下文无关文法

• 记号可以用正规式描述，正规式适合描述线性结构，如标识符、关键字、注释等.
• 句子可以用CFG描述，CFG适合描述具有嵌套(层次)性质的非线性结构，如不同结构的句子if-then-else\while-do等

正规式所描述的语言结构均可以用CFG描述，反之不一定.

（2）上下文有关文法CSG

典型的这类语言结构包含：计数问题的抽象、变量的声明与引用、过程调用时形参与实参的一致性检查等.描述它们的文法被称为上下文有关文法(Context Sensitive Grammar，CSG).这些语言结构无法用上下文无关文法CSG来描述.

（3）形式语言与自动机简介

​ 若文法G=(N，T，P，S)的每个产生式α→β中，均有α∈(N∪T)，且至少含有一个非终结符，β∈(N∪T)，则称G为0型文法.

​ 对0型文法施加以下第i条限制，即得到i型文法。

​ 1> G的任何产生式α→β（S→ε除外）满足|α|≤|β|；
​ 2> G的任何产生式形如A→β，其中A∈N，β∈(N∪T)*；
​ 3> G的任何产生式形如A→a或者A→aB(或者A→Ba)，其中A和B∈N，a∈T。

4. 自上而下语法分析

分为：递归下降分析法、预测分析法

基本思想：对任何一个输入序列ω，从S开始进行最左推导，直到得到一个合法的句子或发现一个非法结构。整个自上而下分析是一个试探的过程，是反复使用不同产生式谋求与输入序列匹配的过程。

提前准备——重写文法：1.消除左递归，以避免陷入死循环； 2.提取左因子，以避免回溯.

（1）消除左递归

定义：若文法G中的非终结符A，对某个文法符号序列α存在推导A =+> Aα，则称G是左递归的。若G中有形如A→Aα的产生式，则称该产生式对A直接左递归。

<1> 消除文法的直接左递归

A→Aα|β     替换为     A →βA'
                    A'→αA'|ε

首先，整理A产生式为如下形式：A→ Aα1|Aα2|...|Aαm|β1|β2|...|βn
然后用下述产生式代替A产生式：A→ β1 A'|β2 A'| ...|βn A'
​ A'→ α1 A' | α2 A' | ... | αm A' |ε

<2> 消除文法的左递归

核心思想：将无直接左递归的非终结符展开到其他产生式,然后消除其他产生式中的直接左递归(如果有的话)

若G产生句子的过程中出现A=+A的推导，则无法消除左递归(出现回路)

（2）提取左因子

<1> 提取文法的左因子

左因子产生原因：公共前缀：A → αβ1|αβ2
方法：将 A → αβ1|αβ2|γ
​ 替换为 A→αA'|γ A'→β1|β2

（3）递归下降分析

直接以程序代码（的方式）模拟产生式产生语言的过程:

基本思想：每个非终结符对应一个子程序（函数），过程体中：

• 产生式右部的非终结符：对应子程序调用，
• 产生式右部的终结符： 与输入记号序列进行匹配。

特点：
1> 子程序是递归的（因为文法是递归的）；
2> 程序与文法相关；
3> 它对文法的限制是不能有公共左因子和左递归；
4> 它是一种非形式化的方法，只要能写出子程序，用什么样的方法和步骤均可。

（4）预测分析器

☆ 预测分析器由一张预测分析表、一个符号栈和一个驱动器组成，数学模型是下推自动机。
☆ 对文法的限制是不能有公共左因子和左递归

预测分析器的核心概念：
1> 分析方法：格局与格局变换
2> 分析表+驱动器（模拟算法）
3> 预测分析表的构造
4> LL（文法、语言、分析器）

☆ 开始格局的剩余输入是全部输入序列，而接收格局中剩余输入应该为空，任何其他格局或出错格局中的剩余输入应该是全部输入序列的一个后缀.

☆ 改变格局的动作：

① 匹配终结符： 若top^=ip(但≠#)，则pop且next(ip)；
② 展开非终结符：若top^= X且M[X,ip^]=α(X→α)，则pop且push(α)；
③ 报告分析成功： 若top ^= ip^ = #，则分析成功并结束；
④ 报告出错：其它情况，调用错误恢复例程.

☆ 驱动器算法

☆ 构造预测分析表

步骤：1. 构造文法符号X的FIRST集合和非终结符的FOLLOW集合；2. 根据两个集合构造预测分析表.

通俗地讲，α的FIRST集合就是从α开始可以导出的文法符号序列中的开头终结符。而A的FOLLOW集合，就是从开始符号可以导出的所有含A的文法符号序列中紧跟A之后的终结符.

<1> 计算X的FIRST集合 -----自下而上计算
<2> 计算所有非终结符的FOLLOW集合 —— 自上而下计算
<3> 构造预测分析表
<4> LL(1)文法

文法G被称为是LL(1)文法，当且仅当为它构造的预测分析表中不含多重定义的条目。由此分析表所组成的分析器被称为LL(1)分析器，它所分析的语言被称为LL(1)语言。

☆ 第一个L代表从左到右扫描输入序列，第二个L表示产生最左推导，1表示在确定分析器的每一步动作时向前看一个终结符.

推论3.2 G是LL(1)的，当且仅当G的任何两个产生式A→α|β满足:
1. 对任何终结符a，α和β不能同时推导出以a开始的串；即First(α) ∩ First(β) = ∅
2. α和β最多有一个可以推导出ε；
3. 若β =*> ε,则α不能导出以FOLLOW(A)中终结符开始的任何串. 即First(α) ∩ Follow(A) = ∅

☆ 无论是递归下降子程序法还是非递归的预测分析法，他们都只能处理LL(1)文法.

5. 自下而上语法分析

☆ 自上而下分析采用的是推导;自下而上分析采用的是归约(规范归约—剪句柄—移进/归约分析—SLR(1)分析器).

（1）自下而上分析的基本方法

☆ 基本思想：最左归约.

对于每个输入序列ω：从左到右扫描ω; 从ω开始,反复用产生式的左部替换产生式的右部(即当前句型中的句柄)、谋求对ω的匹配,最终得到文法的开始符号，或者发现一个错误。

☆ 基本概念：

a) > 设αβδ是文法G的一个句型，若存在S=*>αAδ，A=+>β， 则称β是句型αβδ相对于A的"短语".
   > 特别的，若 有A→β，则 称β是句型αβδ相对于产生式A→β的"直接短语".
   > 一个句型的最左直接短语被称为"句柄".

   特征：
    1.  短语：以非终结符为根子树中所有从左到右的叶子；
    2.  直接短语：只有父子关系的子树中所有从左到右排列的叶子（树高为2）；
    3.  句柄：最左边父子关系树中所有从左到右排列的叶子（句柄是唯一的）
    
    
b)最左归约：若 α是文法G的句子且满足下述条件，则称序列αn，αn-1，...，α0是α的一个最左归约。
   1) αn = α
   2) α0 = S（S是G 的开始符号）
   3) 对任何i(0<i<=n)，αi-1是将αi中句柄替换为相应产生式左部非终结符得到的
   
 ☆ 最左归约的逆过程是一个最右推导，分别称最右推导和最左归约为规范推导和规范归约.
 
 c）移进-归约分析器
 1. 工作方式：格局与格局变换
 2. 分析表
 3. 驱动器（模拟算法）
 4. SLR分析表的构造
 5. LR（文法、语言、分析器）

☆ 改变格局的动作：
1. 移进(shift)：当前剩余输入的下一终结符进栈。
2.归约(reduce)：将栈顶句柄替换为对应非终结符(最左归约)
3.接受(accept)：宣告分析成功
4. 报错(error)：发现语法错误，调用错误恢复例程

(2) LR分析

a) LR分析与LR文法
LR分析：允许左递归，但不能有二义

定义3.15 若为文法G构造的移进-归约分析表中不含多重定义的条目，则称G为"LR(k)文法"，分析器被称为是"LR(k)分析器"，它所识别的语言被称为"LR(k)语言"。"L"表示从左到右扫描输入序列，"R"表示逆序的最右推导，"k"表示为确定下一动作向前看的终结符个数，一般情况下k<=1。当k=1时，简称"LR"。             

构造SLR(1)分析器

<1> 活前缀与LR(0)项目

出现在移进-归约分析器栈中的右句型的前缀，被称为文法G的活前缀(viable prefix).
LR(0)项目(简称项目)是这样一个产生式，在它右边的某个位置有一个点"."。对于A→ε，它仅有一个项目A→.。
项目A→α.β显示了分析过程中看到(移进)了产生式的多少。
β不为空的项目称为可移进项目，β为空的项目称为可归约项目.

<2> 拓广文法与识别活前缀的DFA

G' = G ∪ {S' → S}
其中：S' → S是识别S的初态，S' → S. 是识别S的终态. 目的是使最终构造的DFA状态集中具有唯一的初态和终态. ① closure(I)：从项目集I不经任何文法符号到达的项目全体；

② goto(I，x)：所有从I经文法符号x能直接到达的项目全体。

项目[S’→.S]和所有“.”不在产生式右部最左边的项目称为核心项目(kernel items)，
其它“.”在产生式右部最左边的项目(不包括[S’→.S])称为非核心项目(nonkernel items).

核心项目：J=goto(I，X)，S'→.S（作为项目集的代表）
非核心项目：closure(J)-J（特点：可由J某中某项目算得） 

<3> 识别活前缀

定义3.21 若存在最右推导S’=*> αAω => αβ1β2ω，则称项目[A→β1.β2] 对活前缀αβ1有效。

当一个项目集中同时存在：
    1. A→β1.β2和B→β.：既可移进又可归约，移进/归约冲突
    2.A→α.和B→β.：均可指导下一步分析，归约/归约冲突

解决方法：简单向前看一个终结符：
    1. 移进/归约冲突：若FIRST(β2)∩FOLLOW(B)=Φ，冲突可解决
    2. 归约/归约冲突：若FOLLOW(A)∩FOLLOW(B)=Φ，冲突可解决

若冲突可以解决，则称文法为SLR(1)文法，构造的分析表为SLR(1)分析表。
SLR(1)文法：简单向前看一个终结符即可解决冲突
☆ 二义文法不是SLR(1)文法

第四章 静态语义分析

采用语法制导翻译生成中间代码

1. 语法制导翻译简介

（1）语法与语义的关系

语法是指语言的结构、即语言的“样子”；
语义是指附着于语言结构上的实际含意，即语言的“意义”.
一个语法上正确的句子，它所代表的意义并不一定正确.

☆ 语义分析的作用

• 检查结构正确的句子所表示的意思是否合法；
• 执行规定的语义动作，如：表达式求值、符号表的查询/填写、中间代码生成等

☆ 应用最广的语义分析方法是语法制导翻译，他的基本思想是将语言结构的语义以属性的形式赋予代表此结构的文法符号，而属性的计算以语义规则的形式赋予由文法符号组成的产生式.

（2）属性/语义规则的定义

定义4.1 对于产生式A→α，其中α是由文法符号X1X2...Xn组成的序列，它的语义规则可以表示为(4.1)所示关于属性的函数f：
          b := f(c1, c2, ..., ck)                  (4.1)
语义规则中的属性存在下述性质与关系：
      (1)   称(4.1)中属性b依赖于属性c1, c2, ..., ck。
      (2) 若b是A的属性，c1, c2, ..., ck是α中文法符号的属性，或者A的其它属性，则称b是A的综合属性。
      (3) 若b是α中某文法符号Xi的属性，c1, c2, ..., ck是A的属性，或者是α中其它文法符号的属性，则称b是Xi的继承属性。
      (4) 若语义规则的形式如下述(4.2)，则可将其想像为产生式左部文法符号A的一个虚拟属性。属性之间的依赖关系，在虚拟属性上依然存在。
          f(c1, c2, ..., ck)                (4.2)          ■

☆ 继承属性从前辈和兄弟的属性计算得到,综合属性从子孙和自身的其他属性计算得到.

即,继承属性"自上而下,包括兄弟",综合属性"自下而上,包括自身".

（3）语义规则的两种形式

☆ 语义规则的两种形式（忽略实现细节，二者作用等价）

<1> 语法制导定义(Syntax Directed Definition)

用抽象的属性和运算表示的语义规则；(公式，做什么)

<2> 翻译方案(Translation Scheme)

用具体的属性和运算表示的语义规则。(程序段，如何做)

☆ 继承属性是自上而下计算的，综合属性是自下而上计算的.

（4）LR分析翻译方案的设计

☆ LR分析中的语法制导翻译实质上是对LR语法分析的扩充：

1. 扩充LR分析器的功能

当执行归约产生式的动作时，也执行相应产生式对应的语义动作。由于是归约时执行语义动作，

​ 因此限制语义动作仅能放在产生式右部的最右边；

2. 扩充分析栈

​ 增加一个与分析栈并列的语义栈，用于存放分析栈中文法符号所对应的属性值。

☆ 扩充后的LR分析最适合对综合属性的计算，而对于继承属性的计算还需要进行适当的处理.

2. 中间代码简介

☆ 中间代码应具备的特性
1）便于语法制导翻译
2）既与机器指令的结构相近,又与具体机器无关.

使用中间代码的好处:一是便于编译器程序的开发和移植,二是代码进行优化处理.

☆ 中间代码的主要形式：后缀式、树、三地址码等.最基本的中间代码形式是树🌲；最常用的中间代码形式是三地址码，它的实现形式常采用四元式形式。

☆ 符号表是帮助声明语句实现存储空间分配的重要数据结构。

（1）后缀式

操作数在前，操作符紧随其后，无需用括号限制运算的优先级和结合性；便于求值.

（2）三地址码

① 三元式 形式： (i) (op, arg1, arg2)

​ 三地址码：(i):= arg1 op arg2

序号的双重含义：既代表此三元式，又代表三元式存放的结果

存放方式：数组结构，三元式在数组中的位置由下标决定

弱点：给代码的优化带来困难

② 四元式 形式： ( i ) (op，arg1，arg2，result)

​ 所表示的计算： result:= arg1 op arg2

1. 四元式与三元式的唯一区别：将由序号所表示的运算结果改为：用(临时)变量来表示。

2. 此改变使得四元式的运算结果与其在四元式序列中的位置无关.为代码的优化提供了极大方便，因为这样可以删除或移动四元式而不会影响运算结果.

③ 树形表示

1> 语法树真实反映句子结构，对语法树稍加修改（加入语义信息），即可以作为中间代码的一种形式(注释语法树)
2> 树的优化表示－DAG
3> 树与其他中间代码的关系

☆ 树表示的中间代码与后缀式和三地址码之间有内在联系

1. 树 → 后缀式

​ 方法：对树进行深度优先后序遍历，得到的线性序列就是后缀式，或者说后缀式是树的一个线性化序列；

2. 树 → 三元式/四元式

特点：树的每个非叶子节点和它的儿子对应一个三元式或四元式；

方法：对树的非叶子节点进行深度优先后序遍历，即得到一个三元式或四元式序列。

3. 符号表简介

• 符号表的作用：连接声明与引用的桥梁，记住每个符号的相关信息，如作用域和类型等，帮助编译的各个阶段正确有效地工作。
• 符号表的基本目标：有效记录信息、快速准确查找。
• 符号表设计的基本要求：
  • 正确存储各类信息；
  • 适应不同阶段的需求；
  • 便于有效地进行查找、插入、删除和修改等操作；
  • 空间可以动态扩充.

（1）构成名字的字符串

构成名字的字符串的存储方式：直接存储---定长数据(直接将构成名字的字符串放在符号表条目中)和间接存储---变长数据(将构成名字的字符串统一存放在一个大的连续空间内，字符串与字符串之间采用特殊的分隔符隔开，符号表条目中仅存放指向该字符串首字符的指针).

（2）名字的作用域

☆ 程序语言范围的划分可以有两种划分范围的方式：并列和嵌套

☆ 名字的作用域规则：规定一个名字在什么样的范围内应该表示什么意义.

<1> 静态作用域规则（static-scope rule）：编译时就可以确定名字的作用域,即仅从静态读程序就可确定名字的作用域
<2> 最近嵌套规则（most closely nested）：名字的声明在离其最近的内层起作用

（3）线性表

符号表以栈(线性表)的方式组织.

线性表上的操作：查找、插入、删除、修改

查找：从表头(栈顶)开始，遇到的第一个符合条件的名字；插入：先查找，再加入在表头（栈顶）；

关键字 = 名字＋作用域；

（4）散列表

名字挂在两个链上(便于删除操作)：

1. 散列链(hash link)： 链接所有具有相同hash值的元素，表头在表头数组中；
2. 作用域链(scope link)：链接所有在同一作用域中的元素，表头在作用域表中.

☆ 操作：查找、插入、删除

4. 声明语句的翻译

（1）变量的声明

☆ 一个变量的声明应该由两部分来完成：类型的定义和变量的声明

• 类型定义：为编译器提供存储空间大小的信息
• 变量声明：为变量分配存储空间
• 组合数据的类型定义和变量声明：定义与声明在一起，定义与声明分离.

1> 简单数据类型的存储空间是预先确定的，如int可以占4个字节，double可以占8个字节，char可以占1个字节等

2> 组合数据类型变量的存储空间，需要编译器根据程序员提供的信息计算而定.

（2） 过程

1．过程（procedure）：过程头(做什么) ＋  过程体(怎么做)；
   - 函数:  有返回值的过程
   - 主程序:  被操作系统调用的过程/函数

2．过程的三种形式：过程定义、过程声明和过程调用。
   过程定义：过程头+过程体；
   过程声明：过程头；

3. 左值与右值 
   1> 直观上，出现在赋值号左边和右边的量分别称为左值和右值；
   2> 实质上，左值必须具有存储空间，右值可以仅是一个值，而没有存储空间.
   3> 形象地讲，左值是容器，右值是内容.
   
4. 参数传递
   1> 形参与实参
        - 声明时的参数称为形参(parameter或formal parameter)
        - 引用时的参数称为实参(argument或actual parameter)
   2> 常见的参数传递形式：（不同的语言提供不同的形式）
        - 值调用（call by value）---过程内部对参数的修改，不影响作为实参的变量原来的值.
        - 引用调用（call by reference）--- 过程内部对形参的修改，实质上是对实参的修改.
        - 复写－恢复（copy-in/copy-out）--- ① 过程内对参数的修改不直接影响实参，避免了副作用;
                                        ② 返回时将形参内容恢复给实参，实现参数值的返回.
        - 换名调用（call by name）--- 宏调换
   3> 参数传递方法的本质区别： 实参是代表左值、右值、还是实参本身的正文.
   
5. 作用域信息的保存
☆ 能够画出嵌套过程的嵌套关系树(P191 4.33),根据语法制导翻译(P193 4.35)画出分析树,写出推导步骤,构造的符号表

5. 简单算术表达式与赋值句

P197 例4.36 主要是变量类型的转换

6. 数组元素的引用

（1）数组元素的地址计算

• 注意是行主存储还是列主存储

（2）☆数组元素引用的语法制导翻译(考试热点之一)

• P201 例4.37

7. 布尔表达式

布尔表达式的计算有两种方法：数值表示的直接计算和逻辑表示的短路计算

☆ 布尔表达式短路计算的翻译：短路计算的控制流，真出口与假出口，真出口链与假出口链，拉链回填技术(P207 例4.41)（考试热点之一）

8. 控制语句

控制语句的分类：①无条件转移、②条件转移、③循环语句、④分支语句

• 无条件转移(goto)\条件转移(if、while)
• 条件转移的语法制导翻译：P213 例4.42

多看课件PPT，多做题练手