1 概论

程序设计语言：语法，语义，语用

编译的起源：程序设计语言的发展

低级语言：字位码、机器语言、汇编语言

高级语言从应用角度分类：

基础语言：FORTRAN，COBOL，BASIC，ALGOL
结构化语言：具有很强的过程结构和数据结构能力，PASCAL，C，Ada
专用语言：为特殊应用而设计，APL，Forth

基本概念

源程序：用汇编语言或高级语言编写的程序
目标程序：用目标语言（介于源语言和机器语言之间的语言）所表示的程序

翻译程序：将源程序转换为目标程序

源程序是翻译程序的输入，目标程序是翻译程序的输出

编译程序：一次编译可多次执行

解释程序：对源程序进行解释执行的程序，并不生成目标程序

编译-解释执行：

编译过程和编译程序构造

编译过程

将高级语言程序翻译为等价的目标程序，翻译的实质：语义的等价性

词法分析：分析和识别单词。
语法分析：根据语法规则，识别出各种语法成分
语义分析、生成中间代码：对识别出的各种语法成分进行语义分析，并生成中间代码（介于源语言和目标语言的中间语言形式）
- 便于优化处理，便于编译程序的移植
生成目标程序

错误处理，符号表管理每遍都要

编译程序构造

五个阶段都需要建表和查表和出错处理

遍：对源程序（包括中间形式）从头到尾扫描一遍。

⚠️区分遍与基本阶段的区别：

基本阶段：将源程序翻译为目标程序在逻辑上要完成的工作

遍：指完成上述基本阶段要经过一次或几次扫描处理

可能一次扫描完成多个基本阶段

前端和后端

对源程序的分析，并生成与其等价的中间形式（前端：与源语言有关）
- 词法分析：将字符串形式的源程序分解为具有独立语法意义的单词符号 token
- 语法分析：根据语法规则将单词进一步组合成大的语法类或语法成分，如变量声明、表达式、语句、函数和过程等，生成语法数
- 语义分析：对通过语法分析程序识别出来的语法成分进一步进行语义分析处理（计算），识别他们的含义，同时进行语义检查
生成目标程序（后端：与目标机有关）
- 代码生成：将源程序的中间形式转换为汇编语言或者机器语言
- 代码优化：在确保源代码功能不变的前提下，获得更高效的目标程序
符号表管理：保存每个标识符及其属性信息，在符号表的表项中登录标识符的属性
出错处理：检测错误，向用户报错错误性质和位置，以便用户修改源程序

2 文法和语言

正闭包：

$A^+=A^1\cup A^2\cup ...\cup A^n$

闭包：

$A^*=A^0\cup A^+$

Q：为什么对符号、符号串、符号串集合以及它们的运算感兴趣？

A：把单词看作符号，句子便是符号串。而所有句子的集合就是符号串集合。

文法的非形式定义

对语言结构的定义与描述，也称语法。

语法规则： $:==$ 表示“由…组成”。

由规则推导句子：从一个要识别的符号开始推导，用相应规则的右部替代规则的左部，每次仅用一条，直到所有带<>的非终结符号都被终结符号替代。

最左归约=最右推导=规范推导

推导序列：

最左推导：从最左的语法成分进行推导
最右推导：同理

文法是在形式上对句子结构的定义与描述，未涉及语义

语法推导树：

文法和语言的形式定义

文法

文法：

$G=(V_n,V_t,P,Z)\\ V_n:非终结符号集\\ V_t:终结符号集\\ V=V_n+V_t:文法的字汇表\\ P:产生式或规则的结合\\ Z:开始符号，Z\in V_n$

规则：有序对（U，x）。 $U\rightarrow x$

文法的 BNF 表示（或）：

$U::=x|y|...|z$

推导

直接推导：使用一次规则即可推导出
间接推导：存在一个直接推导序列，
最左/右推导：总是从最左/右的语法成分进行推导
规范推导就是最右推导（ $y\in V_t^*$ 说明 y 一定是终结符号， $U$ 一定是右边第一个非终结符号）

通过若干步推导（可以是 0）：

语言

句型：如果可以通过若干步推导出 x（可以包含终结符，也可以包含非终结符，也可以是空串）
句子：不包含终结符的句型
语言：由文法 G 生成的所有句子集合

形式语言理论证明以下两点：

（1） $G\rightarrow L(G)$ ：已知文法，求语言，通过推导

（2） $L(G)\rightarrow G_1,G_2,...,G_n$ ：已知语言，构造文法，凭经验

已知语言，构造文法： $\{ab^na |n\geq1\}$

$G_1[Z]:Z\rightarrow aBa,B\rightarrow b|bB\\ G_2[Z]:Z\rightarrow aBa,B\rightarrow b|Bb$

若 $L(G)=L(G')$ ，则 $G$ 和 $G'$ 为等价文法。

证明等价文法可转化为证明集合等价

递归文法

可用有穷条规则，定义无穷语言。

句型的短语、简单短语和句柄

相对于句型而言！！！

短语：前面句型中的某个非终结符所能推出的符号串，由每颗子树的叶子组成

任何句型本身一定是相对于识别符号 Z 的短语
简单子树：树的高度为两层的子树
简单短语：简单子树的叶子结点
句柄：最左简单短语，最左简单子树的叶子

语法树与二义性文法

推导与语法推导树

语法推导树：根结点——识别符号，中间结点——非终结符，叶结点——终结符

子树：某个结点连同向下生长的部分

规范归约：对句型中==最左简单短语（句柄）==进行的归约

二义性

若对于一个文法的某一个句子，存在两颗不同的语法树，即存在着两个不同的规范推导（不同的句柄），则是二义性文法

二义性：句柄不唯一

二义性不可通过有限步骤判定

扩充的 BNF 表示：

花括号{}使用： $\{t\}^m_n$ 表示符号串 t 可自重复连接 n 到 m 次，如果省略 n、m，表示可连接 0-任意多次

方括号[]使用： $[t]$ 表示符号串 t 可有可无

圆括号()使用：在规则中提取因子 $xy|xw|xz=x(y|w|z)$

有关文法的实用限制

$U::=U$ 这样的规则即为有害规则。

如果文法中无有害规则或多余规则，则称文法是压缩过的。

文法和语言分类

0 型：短语结构文法，左部右部均可以是符号串，一个短语可以产生另一个短语，可被图灵机接受

$P:u\rightarrow v,其中u\in V^+,V=V_n\cup V_t$
1 型：上下文有关，只有在 x，y 的情况下才可以改写，由线性界限自动机

$P:xUy\rightarrow xuy,其中U\in V_n,x,y,u\in V^*$
2 型：上下文无关文法，1 型文法 $x,y$ 为 $\varepsilon$ ，由下推自动机接受

$P:U\rightarrow u,其中U\in V_n,u\in V^*$
3 型：由有穷自动机接受

3 词法分析

识别单词，返回单词的类别和值

词法分析程序的功能：

词法分析：根据词法规则识别及组合单词，进行词法检查
对数字常数完成数字字符串到二进制数值的转化
删去空格和注释

实现方案：

保存单词：类别编码，单词值

正则文法和状态图

画状态图

自底向上，规约过程

每个非终结符设一个状态，并设置开始状态 S
若 $Q\rightarrow T,Q\in V_n,T\in V_t$ ，则
若 $Q\rightarrow RT,R\in V_n,T\in V_t$ ，则
增加终止状态标志（双圈）

构造词法分析程序

4 语法分析

根据文法规则，从源程序单词符号串中识别出语法成分，并进行语法检查

自顶向下分析

主要问题：

左递归问题：不能直接处理具有左递归性的文法

回溯问题：消耗时间

主要方法：

递归子程序法

LL 分析法

给定符号串 S 若预测是某一语法成分，则可根据该语法成分的文法，设法为 S 构造一颗语法树，若成功，则 S 最终被识别为某一语法成分，即 $S\in L(G[Z])$ ，其中 $G[Z]$ 为某语法成分的文法，若不成功，则 $S\notin L(G[Z])$

存在问题

左递归问题

不能处理具有左递归性的文法，必须要消除文法的左递归。

消除左递归：

（提因子） $U::=xy|xw|xz$ 可替换为 $U::=x(y|w|z)$

如果 $U\rightarrow x|xy$ ，应该写为 $U\rightarrow x(y|\varepsilon)$ 。
$U::=x|y|...|z|Uv$ 可替换为 $U::=(x|y|...|z)\{v\}$ ，将具有直接左递归的右部选择位于最后可取无限次
左递归改为右递归

回溯问题

避免回溯必须保证：对文法的任何非终结符号，特别是对那些规则右部有多个选择的非终结符号，当要用它去匹配输入串时，它能够根据所面临的输入符号准确的用齐规则右部的某一个选择去执行任务，并且工作的结果应是确信无疑的。

定义任一个选择 $a_i$ 所可能推出的终结符号串的首符号集 $FIRST(a_i)$ 需要满足：

$FIRST(A_i)\cap FIRST(a_j)=\emptyset(i\neq j)$

消除回溯：

改写文法：对具有多个右部的规则反复提取左因子
超前扫描：若各选择的首符号相交，向前侦查各输入符号串的第二个、第三个来确定要选择的目标

为了不采取超前扫描的前提下实现不带回溯的自顶向下分析，需要满足两个条件：

文法非左递归
对文法的任一非终结符，若其规则右部有多个选择时，各个选择所推出的终结符号的首符号集要两两不相交

不带回溯的充分必要条件：对于 G 的每个非终结符 A 的任意两条规则 $A::=\alpha|\beta$

$FIRST(\alpha)\cap FIRST(\beta)=\empty$
若 $\beta\rightarrow\epsilon$ ，则 $FIRST(\alpha)\cap FOLLOW(A)=\empty$

递归下降子程序法

对每一个非终结符都编一个分析程序，当根据文法和当时的输入符号预测到要用某个非终结符区匹配输入串时，就调用该非终结符的分析程序

自底向上分析

主要问题：

句柄的识别问题

主要方法：

算符优先分析法

LR 分析法

5 符号表管理技术

概述

符号表：编译程序用来记录源程序中各种名字的特性信息

名字：程序名、过程名、函数名、用户定义类型名、变量名…

特性信息：种类、类型、维数、参数个数

建表和查表的必要性：

变量声明时，将名字及其信息登录到符号表中，同时给变量分配存储单元，并将存储单元地址登录在符号表中

当编译到引用变量的位置时，需要查符号表取得相关信息

填表：说明|定义语句时，将名字和信息填入符号表中
查表：
- 检查同一作用域内名字是否重复定义
- 检查名字的种类与说明是否一致
- 对于强类型语言，检查表达式中各变量的类型是否一致
- 生成目标指令时，取得所需要的地址

符号表的组织与内容

名字	特性信息
	种类（简单变量、函数、过程、数组、标号、参数）类型（整形、浮点型、字符型、指针）性质（变量形参、值形参）值地址大小

组织形式：

统一符号表：按信息量最大的设计，浪费空间
不同种类的名字分别建立：节省空间，但查表不便
这种：大部分在一张表，特殊信息另设附表，用指针连接

非分程序结构语言的符号表组织

非分程序结构语言：每个可独立进行编译的程序单元是一个不包含有子模块的单一模块（所有标识符属于整个模块）

标识符

作用域：

全局：子程序名，函数名和公共区名
局部：程序单元中定义的变量

组织：

处理办法：

子程序、函数名和公共区名填入全局符号表
在子程序声明部分读到标识符，造局部符号表
- 检查是否同名
在语句部分读到标识符，查表
- 有局部表
- 无，查全局表——有即全局变量，无即没有定义
程序单元结束：释放局部符号表
程序编译完成：释放全部符号表

组织方式

无序符号表：按扫描顺序建表，逐项查找 $\frac{n+1}{2}$
有序符号表：按变量名字典式排序
- 线性查表： $\frac{n+1}{2}$
- 折半查表： $\log_2n -1$
- Hash 表：符号表地址=Hash(标识符)。解决冲突

分程序结构语言的符号表组织

分程序结构语言：模块内可嵌入子模块

处理办法：

建查符号表要遵循标识符的作用域规定进行
建表：不能重复，不能遗漏
查表：按标识符作用域
程序声明部分读到标识符：
- 查本层符号表有无同名，有——重复声明报错，无——填入符号表
在语句中读到标识符：
- 查本层符号表有无同名，有——已声明（局部量），无——是否是最外层，是——报错，否——转到外层（n-1）
标准标识符的处理（不必声明可全程使用）
- 单独建表|预先填入最外层

栈式符号表

当到达分程序结尾时，就弹出分程序的符号表。

分程序索引表指向每个分程序的开始（分程序名属于上一层符号表）：

6 运行时的存储组织及管理

目标程序运行时所需存储空间的组织与管理以及源程序中变量存储空间的分配

静态存储分配

在编译阶段就可以确定变量在运行时的空间大小且不改变（但并不是所有数据空间大小都能在编译过程中确定—>动态存储分配）

目标地址：绝对地址（单任务环境）|相对地址

开辟数据区（首地址加载时定）
按编译顺序给每个模块分配存储空间
在模块内部按顺序给变量分配存储，大小由类型决定
目标地址填入符号表

FORTRAN 子程序完整数据区：

变量
返回地址
形式参数
临时变量

动态存储分配

在目标程序运行时才分配，比如递归程序

栈式动态存储分配

进入一个过程时，在栈顶分配一个数据区
退出时撤销数据区

从 M1(X/Y)处调用 M1，然后进入 AR2 数据区，…，然后依次退出，撤销数据区

活动记录

局部数据区

存放模块中定义的各个局部变量

参数区

存放隐式参数和显式参数

显式参数：形参数据区

隐式参数：

prev abp：存放调用模块记录基地址，函数执行完时，释放其数据区，数据区指针指向调用前的位置（前一个作用域）
ret addr：返回地址，调用语句的下一条执行指令地址
ret value：函数返回值，无则空

display 区

存放各外层模块活动记录的基地址，为了访问外层变量。

变量二元地址： $(BL、ON)$ 。

$BL$ ：变量声明所在的层次，可得到该层数据区开始地址
$ON$ ：相对于显式参数区的开始位置的位移，即相对地址

当模块 4 执行完，就将 $abp=prev\ abp$ ，然后就恢复到进入模块 4 的情况。

建造 display 区的规则

从 $i$ 层模块调用 $j$ 层模块：

$j=i+1$ ：复制 $i$ 层的 display，在增加一个指向 $i$ 层的基地址指针
$j\leq i$ ：将 $i$ 层模块的 display 区前面的 $j-1$ 个复制到第 $j$ 层

运行时的地址计算

7 源程序的中间形式

波兰表示

设一个操作符栈，如果是操作数则立即输出，如果是操作符则与栈顶比较（空栈优先级最低），如果栈顶优先级更高则输出栈顶，反之则压入栈中。

语法树角度：后序遍历

if 语句

$if<expr>then<stmt_1>else<stmt_2>$

中间代码生成

expr 结束有跳到 else 的标签，stmt1 结束有跳到 if-else 结束的标签

N-元表示

三元式

操作符	左操作数	右操作数
+	x	y

直接三元式即使式子重复也要重新写出，间接三元式则省略重复直接复用

四元式

操作符	操作数 1	操作数 2	结果
			通常是由编译引入的临时变量，可由编译程序分配一个寄存器或主存单元，一般用 T1~T4

中间代码的图表示

抽象语法树

操作数出现在叶节点，操作符出现在中间节点

抽象语法树与三元式的关系：

DAG 图

有向无环图

抽象语法树—>DAG（删去多余支）：

SSA

每个变量只赋值一次

8 错误处理

概述

正确的源程序：通过编译生成中间代码

错误的源程序：通过编译发现并指出错误

错误处理能力：

诊察错误的能力
报错及时准确
一次编译找出错误的多少
错误的改正能力
遏止重复的错误信息的能力

错误分类

错误分为两类：

语法错误：源程序不合乎文法
语义错误：程序不符合语义规则或超越具体计算机系统的限制，将运行时错误也划分在语义错误范畴内

语义规则：

标识符引用要符合作用域规定

标识符先说明后引用

参与运算的操作数类型一致

过程调用时实参与形参要一致

下标变量下标不能越界

超越系统限制：

数据溢出

符号表、静态存储分配数据区溢出

动态存储分配数据区溢出

错误诊察和报告

错误诊察

违反语法和语义规则以及超过编译系统限制的错误（编译程序：语法和语义分析）
下标越界，计算结果溢出以及动态存储数据区溢出（目标程序：目标程序运行时）

错误报告

报告内容：

出错位置：行号|单词序号
出错性质：文字信息|错误编码

报告方式：

分析完再报告
边分析边报告

错误处理技术

进行错误改正或错误局部化处理

一般原则：诊察到错误，暂停对后面符号的分析，跳过错误

词法分析：显示错误，并跳过该标识符
语法语义分析：跳过所在语法成分，从新语句继续往下

错误局部化处理：将错误影响限制在局部范围内，避免错误扩散和影响程序其他部分的分析。一直跳到语句的右界符（eg：end）或语法程序的合法后继符号

9 语法制导翻译技术

翻译文法 TG 和语法制导翻译

目标：将中缀表达式转化为逆波兰表示。

则翻译的任务是将上述文法插入相应的动作符号。在什么时候插入打印终结符号

$E\rightarrow E+T@+$

以第一个为例，表示处理 E，读+，处理 T 并打印+。

同理：

$1.E\rightarrow E+T@+\\ 2.E\rightarrow T\\ 3.T\rightarrow T*F@*\\ 4.T\rightarrow F\\ 5.F\rightarrow(E)\\ 6.F\rightarrow i@i$

输入文法：未插入动作符号，可以推导产生输入序列
翻译文法：插入动作符号，可以推导产生活动序列（输入序列和动作序列）

从活动序列中，抽去动作符号即得输入序列 $(i+i)*i$ ；抽去输入序列可得动作序列 $ii+i*$ 。

翻译文法是上下文无关文法，其终结符号集由输入符号和动作符号组成。由翻译文法所产生的终结符号串称为活动序列

语法制导翻译：按照翻译文法进行的翻译

属性翻译文法 ATG

在翻译文法的基础上，可以进一步定义属性文法，翻译文法中的号，包括终结符、非终结符和动作符号均可带有属性，这样能更好的描述和实现编译过程。属性即符号所具有的值部分

综合属性

综合属性：自底向上，自右向左求值（左边等于右边）

表示属性的求值过程：

继承属性

继承属性：自顶向下，自左向右

翻译文法目标：填符号表@set_table

填表需要的信息：类型 Type，名字 id，填的位置

类型和名字在词法分析时得到，设为两个综合属性

L-属性翻译文法 L-ATG

输入文法要求是 LL(1) 文法，可用自顶向下分析构造分析器。在分析过程中可进行属性求值。

终结符、非终结符及动作符号都带有属性，且每个属性都有值域
非终结符号及动作符号的属性可分为继承属性和综合属性
开始符号的继承属性具有指定的初始值
终结符号的每个综合属性都有指定的初始值
属性的求值规则
- 继承属性：自顶向下，自左向右
  - 左部非终结符号的属性值，取右部该符号已有的值
  - 右部的属性值，用左部继承属性或出现在该符号左部的符号的属性值计算
- 综合属性：
  - 右部非终结符号的属性值取其下部左部同名值
  - 左部非终结符号的属性值，用产生式左部继承符号或右部属性

简单赋值形式的 L-属性翻译文法 SL-ATG

产生式右部继承符号是常量，等于左部符号的继承属性值或左边符号的综合属性值
左部综合属性是常量，等于左部继承属性值或等于右部综合属性值

显然不是 SL-ATG，如何转化？

解：

改写为：

自顶向下语法制导翻译

翻译看成对偶的集合：第一个元素为输入序列，第二个元素为动作序列。如果按文法得到这种对偶时，称为语法制导翻译

递归下降翻译器

只需在递归下降分析加上输出即可

递归下降属性翻译器

对于每个非终结符号都编写一个翻译子程序，根据该非终结符号具有的属性数目，设置相应的参数。

继承属性：赋值形参，继承属性值
综合属性：变量形参，属性变量名（传地址，返回时有值）

例子：

【ppt：P38】

10 语义分析和代码生成

语义分析的概念

上下文有关分析：标识符的作用域
类型的一致性检查
语义处理：
- 声明语句：填符号表
- 执行语句：按某种操作的目标结构生成代码

用上下文无关文法只能描述语法的语法结构，不能描述语义

因此，通常我们把与语义相关的上下文有关信息填入符号表中，并通过查符号表中的这些信息来分析程序的语义是否正确

栈式抽象机及其汇编指令

栈式抽象机：三个存储器、一个指令寄存器和多个地址寄存器

存储器：数据存储器（存放 AR 的运行栈），操作存储器（操作数栈），指令存储器

STN：栈底的值送到次栈底

声明的处理

主要任务：

分离出每个被声明的实体，并把他们的名字填入符号表
把被声明实体的有关特性信息尽可能多的填入符号表

属性翻译文法：

$@dec\_on_{\uparrow x}$ ：用于记录反填类型应该填到哪里

常量

$@insert_{\downarrow t,n,c,s}$ ：类别 t，名字 n，常量表达式值 c，常量表达式类别 s。

功能：

检查声明的类型 t 和常量表达式的类型 s 是否一致
将名字 n，类型 t 和常量表达式的值 c 填入符号表

简单变量

对于变长字符串：

动态申请存储空间，存储在堆中
通过指向存放该实体数据区的指针来引用该实体

数组变量

LOC 是数组首地址，数组定义有上下界 $B[L(1),U(1)]$

$ADDR=LOC+(x-L(1))*E$

表达式的处理

赋值语句的处理

控制语句的处理

过程调用和返回

11 词法自动化

正则文法和正则表达式

正则集合递归定义：

$\varepsilon$ 和 $\phi$ 都是 $\Sigma$ 上的正则表达式，分别为 $\{\varepsilon\}$ 和 $\phi$
任何 $a\in \Sigma$ ， $a$ 是 $\Sigma$ 上的正则表达式， $\{a\}$
如果 $e_1$ $e_{1}$ 和 $e_2$ $e_{2}$ 是 $\Sigma$ $Σ$ 是正则表达式，其正则集合分别为 $L_1$ $L_{1}$ , $L_2$ $L_{2}$ ，则
- $(e_1)|(e_2)$ -> $L_1 \cup L_2$
- $(e_1)(e_2)$ -> $L_1L_2$
- $e_1^*$ -> $L_1^*$

优先级：先*，后·，最后|

正则表达式相等=正则表达式表示的语言相等

$b\{ab\}=\{ba\}b\\ \{a|b\}=\{\{a\}\{b\}\}=(a^*b^*)^*$

性质：

正则（3 型）文法转换为正则表达式

代入： $A\rightarrow xB,B\rightarrow y$ ，转换为 $A\rightarrow xy$
消除递归： $A\rightarrow xA|y$ ，转换为 $A\rightarrow x^*y$
BNF： $A\rightarrow x,A\rightarrow y$ ，转换为 $A\rightarrow x|y$

有穷自动机

类别

确定的有穷自动机 DFA

不确定的有穷自动机 NFA

如果 $\delta$ 为多值函数，且输入允许为 $\varepsilon$ ，那么自动机就是不确定的，某一个状态，对于输入某个字符存在多个后继状态。

NFA 的确定化

$\varepsilon-Closure(I)$ ：

若 $s\in I$ ，则 $s\in \varepsilon-Closure(I)$
若 $s\in I$ ，则从 $s$ 出发经过任意条 $\varepsilon$ 弧能到达的状态都属于 $\varepsilon-Closure(I)$ 。

由 start： $I=\varepsilon-Closure(1)={1,4}$ 确定第一个状态

I	$I_a$	$I_b$	$I_c$
{1,4}	{2,3}	$\empty$	$\empty$
{2,3}	{2}	{4}	{3,4}
{2}	{2}	{4}	$\empty$
{4}	$\empty$	$\empty$	$\empty$
{3,4}	$\empty$	$\empty$	{4}

直至所有状态都分析完毕，给状态重新编号

包含原来终态的状态就是终态，DFA 可以有多个终态

对于任何一个 NFA M’，都可以构造出一个 DFA M，使得 L(M)=L(M’)

DFA 最小化

对于任意一个 DFA，存在一个唯一的状态最少的等价的 DFA

最简：没有多余状态且他的状态中没有两个是互相等价的，所以需要消除多余状态，合并等价状态

状态 s 和 t 等价条件是：

一致性条件：s 和 t 同时为可接受状态或不接受状态
蔓延性条件：对于所有输入符号，s 和 t 必须转换到等价的状态里

分割法：把一个 DFA（不包含多余状态）分割成一些不相关的子集，不同的两个子集状态都是可区别的，同一个子集中的任何状态都是等价的。

任何有后继的状态和任何无后继的状态一定不等价

区分终态和非终态
不同的两个子集状态都区别，同一子集的后继都要落到同一区。

正则表达式和有穷自动机的等价性

任何一个正则表达式，都可以构造出等价的 DFA，反之同理

有穷自动机 → 正则文法

对转换函数 $f(A,t)=B$ ，写成产生式 $A\rightarrow tB$
对可接受（终态）状态 Z，增加产生式 $Z\rightarrow \varepsilon$
有穷自动机的出态对应文法的开始符号，有穷自动机的字母表为文法的终结符号集

$G=({A,B,C,D},{a,b},P,A)\\ P:A\rightarrow aB|bD\\ B\rightarrow bC\\ C\rightarrow aA|bD|\varepsilon\\ D\rightarrow bD|aB|\varepsilon$

正则文法 → 有穷自动机

字母表与 G 的终结符号相同
为 G 中的每个非终结符生成 M 的一个状态，G 的开始符号 S 是开始状态 S
增加新状态 Z 作为 NFA 的终态
形如 $A\rightarrow tB$ ， $t\rightarrow 终结符|\varepsilon$ ，构造 $f(A,t)=B$

正则式 → 有穷自动机

【PPT P11】

有穷自动机 → 正则式

在自动机上增加两个结点 x，y，从 x 结点用 $\varepsilon$ 弧到 M 所有初态，从所有终态用 $\varepsilon$ 到 y 结点
逐步消去所有结点

正则文法 → 正则式

正则式 → 正则文法

词法分析程序的自动生成器

根据给定的正则表达式自动生成相应的词法分析程序

辅助定义式
识别规则
用户子程序

12 语法分析

自顶向下主要方法：递归子程序法，LL 分析法

自底向上主要方法：算符优先分析法，LR 分析法

LL 分析法

LL-自左向右扫描、自左向右地分析和匹配输入传，表现为最左推导的性质

组成部分

将语法成分的左右界符用#表示

分析表

是二维矩阵

$M[A,a]=A::=a_i$

表示 A 去匹配输入串时，且输入符号为 a 时，可以用 A 的第 i 个选择匹配

$M[A,a]=error$

表示不能匹配。

符号栈

开始状态：
工作状态：
出错状态：
结束状态：

执行程序

把#和文法识别符号 E 推进栈，读入下一个符号，重复下述过程直到正常结束或出错
测定栈顶符号 X 和当前输入符号 a
1. 若 $X=a=\#$ ，正常结束
2. 若 $X=a\neq \#$ ，把 X 推出栈，读入下一个符号
3. 若 $X\in V_n$ $X \in V_{n}$ ，查分析表
  1. $M[X,a]=X::=UVW$ ，将 X 弹出栈，UVW 入栈（U 在栈顶：最左推导）
  2. $M[X,a]=error$ ，出错处理
  3. $M[X,a]=X::=\varepsilon$ ，a 为 X 的后继符号，将 X 弹出栈（不读下一符号），继续分析

构造分析表

求 first 集和 follow 集，follow 即求非终结符右边所有终结符的集合（开始符号的 follow 集有#，follow 集不包含 ε）

follow 集合的定义：

若 A 是开始符号，则#就在 Follow (A) 中。
若存在产生式 B →aAg ，则 First (g) - {ε }在 Follow (A) 中。
若存在产生式 B →aA 或 B →aAg ，且 ε 在 First (g) 中，则 Follow (A)包括 Follow (B)。

将 first 集填入，如果可以推出 ε，就将 follow 所在的全部填入

不是所有的文法都能构造出上述的分析表，能使用的称为 LL(1)文法

LL(1)文法

其分析表 M 不含多重定义入口（即分析表中无两条以上规则）

是 LL(1)文法的充要条件，即证明是 LL(1)文法：

如果 G 是左递归的,或者是二义性的文法,则至少有一个多重入口

TODO：有些文法可以从非 LL(1)改写为 LL(1)

移进-归约分析

记录分析的历史和现状，确定下一步动作是移进还是归约

按扫描顺序一一移进符号栈
移进过程中检查栈中符号，若当前栈顶的若干符号形成当前句型的句柄时，就根据规则进行归约
- 将句柄从符号栈弹出，将非终结符号压入栈
- 检查栈内符号串是否构成新的句柄，若有就再次归约
分析一直读到右界符

但是 b 也可以直接归约为 A，为什么将 Ab 归约为 A 呢？

未真正解决句柄的识别

算符优先分析

预先规定相邻终结符之间的优先关系，从而确定句柄进行归约。

当栈顶项(或次栈顶项)终结符（除去非终结符）的优先级大于栈外的终结符的优先级，则进行归约，否则移进。（竖列是栈内，横列是栈外）

算符优先文法 OPG

OG 文法：无形如 $U=...VW...$ 的规则，这里 $V,W\in V_n$ 。

运算是以中缀形式出现的
如果是 OG 文法，就不会出现两个非终结符相邻的句型
算法语言中的表达式以及大部分语言成分的文法均是 OG 文法

构造优先关系矩阵

构造 FIRSTVT(U)：

构造 LASTVT(U)：

素短语：文法 G 的句型的素短语是一个短语，他至少包含一个终结符号，并且除他自身以外不再包含其他素短语

是找句型的最左子串（最左素短语）并进行归约。

LR 分析法

从左到右扫描(L)自底向上进行归约®，是规范归约

组成部分

状态栈：放置分析器状态和文法符号
分析表：两个矩阵，指示分析器的动作，是移进还是归约，根据不同的文法类采用不同的构造方法
控制程序：根据分析表所规定的动作，对栈操作

分析表种类

SLR 分析表（简单 LR 分析表）：构造简单，大多数上下文无关文法都能构造出
LR 分析表（规范 LR 分析表）：适用文法类最大，几乎所有上下文无关文法都能构造出，但分析表体积太大
LALR 分析表（超前 LR 分析表）：适用文法类和实现难易在两者之间，但很实用

状态转移表(GOTO)，分析动作表(ACTION)

构造 LR(0)

将文法拓广：使其只有一个接受状态，消除所有|，列出文法所有的项目
将有关项目组成项目集,所有项目集构成的集合即为 LR(0)

14 代码优化

概述

分类 1：

与机器无关：在中间代码的优化，包括数据流分析、常量传播、公共子表达式删除、死代码删除等等
与机器相关：充分利用系统资源，包括指令系统、寄存器资源。只在特定体系结构下有效

分类 2：

局部优化：基本块内，eg：局部公共子表达式删除
全局优化：函数/过程内，跨越基本块，eg：全局数据流分析
跨函数优化：整个程序，eg：跨函数别名分析，逃逸分析

基本块和流图

基本块

基本块，满足以下条件的最大序列：没有跳转，没有分支的最大序列

连续的语句序列
程序的执行只能从第一条进入
只能从最后一句离开

（1）-（6）：goto 可能直接跳到（3），所以不是

（3）-（8）：×，不是最大的

（7）-（13）：×

划分基本块

输入：四元式序列

输出：基本块列表，每个四元式仅出现在一个基本块中

方法：

确定入口语句（每个基本块的第一条语句）集合
- 整个序列的第一条语句
- 任何能由条件/无条件跳转转移到的第一条语句
- 紧跟在跳转语句之后的第一条语句
每个入口语句直到下一个入口语句或者程序结束，属于同一个基本块

流图

是有向图，节点为基本块，如果在某执行序列中，B2 紧跟在 B1 之后，则 B1 到 B2 有一条有向边。

循环的查找

循环体中的优化效果更好

如果从首节点出发，任何到达节点 B 的路径上都要经过 A，那么 A 就是 B 的必经节点，记为A dom B。

如果有边 $B\rightarrow A$ ，且 $A\ dom\ B$ ，该边即为循环的回边

循环体：能到达 B 且不经过 A

局部优化

也就是基本块内的优化

利用代数性质

编译时完成常量表达式的计算，整数类型与实型的转换
下标变量引用时，地址计算的一部分工作在编译时预先做好（运行时只计算可变部分）
运算强度削弱
常数合并和传播
删除冗余代码：判断语句永远为 true，那 else 部分则为死代码

消除公共子表达式

构建 DAG 图算法

输入：基本块内的中间代码序列

输出：完成局部公共子表达式删除后的 DAG 图

方法：

建立节点表，记录了变量名和常量值，以及他们当前多对应的 DAG 图中的节点的序号。该表初始状态为空
对于形如z=x op y的中间代码，首先在节点表寻找 x，如果找到则记录下对应节点号 i；反之新建叶节点，假设其节点号仍为 i，标记为 x（如 x 为变量名，该标记更改为 $x_0$ ）；在节点表中增加新的一项（x，i），表明二者关系。y 与 x 同理。
在 DAG 寻找中间节点，标记为 op，左操作数节点号为 i，右操作数节点号为 j。如果找到记录下其节点号 k；如果未找到，在 DAG 图中新建一个中间节点，假设其节点号仍为 k，并将节点 i 和 j 分别与 k 相连，作为其左子节点和右子节点
在节点表中寻找 z，如果找到，将 z 所对应的节点号更改为 k；如果未找到，在节点表中新建一项(z, k)，表明二者之间的对应关系

数组、指针及函数调用的 DAG 图

数组：将x=a[i]处理为[]为数组取值操作符；将a[j]=y处理为[]=为数组成员赋值操作符

指针：保守处理

函数调用：保守的认为函数调用改变了他所有可能改变的数据

从 DAG 图导出代码的算法

输入：DAG 图

输出：中间代码序列

方法：

初始化一个放置 DAG 图中间节点的队列
如果 DAG 图中还有中间节点未进入队列，则执行步骤 3，否则执行步骤 5
选取一个尚未进入队列，但其所有父节点均已进入队列的中间节点 n 将其加入队列；或选取没有父节点的中间节点，将其加入队列
如果 n 的最左子节点符合步骤 3 的条件，将其加入队列；并沿着当前节点的最左边，循环访问其最左子节点，最左子节点的最左子节点等，将符合步骤 3 条件的中间节点依次加入队列；如果出现不符合步骤 3 条件的最左子节点，执行步骤 2
将中间节点队列逆序输出，便得到中间节点的计算顺序，将其整理成中间代码序列

叶节点不属于节点，不占用最左的范围。eg： $t_3$ 的最左子节点为 $t_2$

窥孔优化：关注在一个目标指令的一个较短的序列上，删除冗余代码。不一定局限在同一基本块

全局优化

是跨基本块的优化，受到控制流的影响（分支、循环）。

消除死代码，变量的活性

数据流分析

用于获取数据在程序执行路径只如何流动

变量语句前后是否存活。 $V_{out}=f_{语句}(V_{in})$
变量何时定义
变量某一执行点上被定义的值，可能哪些执行点使用

考察在程序的某个执行点的数据流信息：

$out[S]=gen[S]\cup(in[S]-kill[S])$

S：某条语句|基本块|语句集合|基本块集合
out[S]：S 末尾得到的数据流信息
gen[S]：S 本身产生的数据流信息
in[S]：进入 S 时的数据流信息
kill[S]：S 注销的数据流信息，也就是覆盖了之前的赋值！

数据流方程求解过程的关键因素：

产生和注销的信息取决于具体问题，可以由 in 定义 out，也可以由 out 定义 in
数据是沿着程序的执行路径，所以分析结果收到控制程序==结构的影响

到达定义分析

Q：如果 p 处对该变量的引用，取得的值是否在 d 处定义？

A：如果从定义点 d 出发，存在一条路径达到 p，并且在该路径上，不存在对该变量的其他定义语句，则认为“变量的定义点 d 到达静态点 p”

可能存在循环

kill[d1]：程序中对 u 定义的其他定义点的集合，包括 d1 之前或之后的定义点

（cmp是比较）

对于基本块的 gen 和 out 计算：

内部还需要减去之前 kill 的

输入：程序流图，且基本块的 kill 集合【gen 修改了哪些变量】和 gen 集合已经计算完成

输出：每个基本块入口和出口处in[B]和out[B]

方法：

将包括代表流图出口基本块 $B_{exit}$ 的所有基本块的 out 集合初始化为空集
根据方程为基本块 B 以此计算 in 和 out

$in[B]=\cup_{B的前驱基本块P}out[P]\\ out[B]=gen[B]\cup(in[B]-kill[B])$
如果 out 与之前不一致，则重复计算直到不再变化

更快的运算：位运算

活跃变量分析

反向分析

变量 x 的值在 p 点或沿着从 p 出发的某条路经中会被使用，则称 x 在 p 点是活跃的。

对于寄存器分配有重要意义

不再活跃释放寄存器
活跃范围不重合，可共享寄存器

$in[B]=use[B]\cup(out[B]-def[B])\\ out[B]=\cup_{B的后继基本块P}in[P]$

def[B]：被定义先于对于他们的使用（定义了）
use[B]：被使用先于对他们的定义（用了）

例子：倒着往前算

死代码消除

哪些赋值后面没有用到

全局复制传播

寻找所有可以被替换成常量的变量

定义-使用链

冲突图

假设只有跨越基本块活跃的变量才能分配到全局寄存器，并且活跃范围重合的变量之间无法共享全局寄存器

边线连接：一个变量在另一个变量==定义（赋值）==时是活跃的

定义-使用链

定义-使用链：变量的某一定义点，以及所有可能使用该定义点所定义变量值的使用点所组成的一个链

链之中，第一个点是定义点，剩下都是使用点。 $<B1,1>$ B1 基本块的第一行被定义 or 使用

如果他们拥有某个同样的使用点，则合并为同一个网。

画出网络后，如果链之间有连接，说明变量之间有冲突

循环优化

循环不变式的代码外提

不随循环控制变量改变而改变的表达式

循环展开

以空间换时间

判断原则：

主存资源丰富，处理机时间昂贵
循环体语句越少越好

实现步骤：

识别循环结构，确定循环的初值，终值，步长
判断，以空间换时间是否合算来决定是否展开
展开，重复产生循环体所需的代码个数

归纳变量的优化和条件判断的替换

归纳变量：循环中固定增加或减少一个常量值

15 目标代码生成

代码生成器的输入：

源程序的中间表示
- 线性表示（波兰式）
- 三地址码（四元式）
- 栈式中间代码（p-code/java bytecode）
- 图形表示
符号表信息

目标程序种类：汇编语言，包含绝对地址的机器语言，可重定位的机器语言

目标体系结构：微处理器，虚拟机

现代微处理器体系结构简介

指令集架构

栈式指令集架构：在栈顶做运算

累加器式指令集架构：可以访问内存

寄存器-内存指令集架构 vs 寄存器-寄存器指令架构

区别：是否可以直接内存寻址

共性：内部有多个寄存器可以直接作为 ALU 指令的任一操作数

优点：减小内存访问，减小指令数

存储层次架构

地址空间

程序运行栈

子程序/函数运行时所需的基本空间：活动记录

地址空间从高地址到低地址向下生长

ESI：作为源地址指针使用
EDI：作为目的地址指针使用

寄存器的分配和指派

全局寄存器分配

全局是相对于基本块而言，分配对象主要是函数的局部变量，包括函数入口参数，有限分配给跨基本块仍然活跃的变量，尤其是循环体内最活跃的变量

专属于线程

引用计数

统计变量在函数内被引用的次数，根据被引用的特点赋予不同权重，计算唯一权值，根据权值大小分配

循环中的变量应该得到加权

【PPT P46】

图着色算法

思想：可供分配 k 个全局寄存器，用 k 种颜色给冲突图着色。

步骤：

通过活跃变量分析，构建变量的冲突图
尝试用 k 种颜色给该冲突图着色
不够用，考虑权重问题

启发式图着色

设寄存器数目为 k。

步骤：

找到第一个连接边数目小于 k 的节点从图中移走
重复步骤 1，直到无法从图中移走
在图中选取适当（权重等算法）的节点，将它记录为“不分配全局寄存器”的节点，从图中移走
重复，直到图中仅剩余一个节点
按照节点移走的顺序将点和边添加回去并分配颜色

临时寄存器分配

Q：为什么管理临时寄存器？

A：生成某些指令时，必须使用指令寄存器。临时寄存器保存有此前的计算中间结果。

临时寄存器池

进入基本块，清空临时寄存器池

申请处理：

有空闲：分配申请，做表示
没有：选取一个在即将生成代码中不会被使用的寄存器写回相应的内存空间

退出基本块：将寄存器池中的值写回内存，清空临时寄存器池

final

填空

规范归约：减掉当前句型的句柄

**句型（可以有非终结符）**的短语、简单短语、句柄、素短语：

乔姆斯基文法的定义和分类：

0 型：短语结构文法，左部右部均可以是符号串，一个短语可以产生另一个短语，可被图灵机接受

$P:u\rightarrow v,其中u\in V^+,V=V_n\cup V_t$
1 型：上下文有关，只有在 x，y 的情况下才可以改写，由线性界限自动机，1 型语言 L1

$P:xUy\rightarrow xuy,其中U\in V_n,x,y,u\in V^*$
2 型：上下文无关文法，1 型文法 $x,y$ 为 $\varepsilon$ ，由下推自动机接受

$P:U\rightarrow u,其中U\in V_n,u\in V^*$
3 型：由有穷自动机接受，正则文法

左线性：非终结符在最左，右线性：非终结符在最右

翻译文法：

是上下文无关文法，终结符号集由输入符号和动作符号组成，由翻译文法产生的终结符号串称为活动序列（终结符，动作符号）

活动序列=输入序列+动作序列（对偶集）

NFA：δ 是多值函数，输入允许为 ε，允许在某个状态下，输入字符存在多个后继状态

大题

正则表达式

NFA 确定化：

画出 NFA，可以先化简一些 $\varepsilon$ ，比如多个 $\varepsilon$ 连续，先去除若干状态
状态：从初始开始， $\varepsilon$ 能到达的地方的集合作为第一个状态，包含最终态的状态均为终态
画出 NFA，记得化终态

DFA 最小化：

将上面的状态-输入表整理
首先区分终态和非终态
下一状态均指向相同子集的作为同一状态，可以 3,5（割开的）作为相同子集
化 DFA，最终通过正则表达式验证一下是否合理

相互转化：

正则表达式：扩充 BNF

正则文法：

算符优先文法

不一定是严格的最左归约

算符优先文法定义：

若文法中无形如 $U::=·VW·$ 规则，这里 $V,W\in V_n$ ，则为算符文法。如果在其中任意两个终结符之间，至多只有上述关系的一种，则为算符优先文法

如果是算符优先文法，肯定在优先矩阵中最多只有一个关系

可以分析二义性文法，句柄不唯一

每次归约的是最左素短语：至少包含一个终结符，且不包含除自身之外的素短语

求 FIRSTVT 和 LASTVT：

构造 FIRSTVT(U)：

构造 LASTVT(U)：

简单而言就是：

$U\rightarrow b,U\rightarrow Va$

则，

$FIRSTVT(U)={b}+FIRSTVT(V)$

构造优先关系矩阵：

a 是栈内，b 是栈外：

a 是栈内，FIRSTVT(U)是栈外：

LASTVT(U)是栈内，b 是栈外：

关于#（开始符号和结束符号）：它是终结符，首先记住无论它在哪里，肯定是它最小

栈内#：代表开始符号，小于最开始的终结符和 FIRSTVT(E)（任意在最开始的非终结符）

栈外#：代表结束符号，小于最末尾的终结符和 LASTVT(E)（任意在最末尾的非终结符）

归约符号串：

小于移进，大于归约

到最后的时候是比较符号栈中最上面的终结符（可能最顶是非终结符）

符号表和运行栈

栈式符号表：

当不用的函数等出作用域时，就不用在写在符号表里了

层次：看题目从几开始，画出大括号，多个函数并列就是在同一层次
名字：Ident
种类：简单变量 var、函数 program、过程 procedure、数组 array、标号 real、参数 param
类型：int，char

注意函数属于上一次，如果两个函数并列，别忘了把上一个函数也写上

先画好层次大括号图

活动记录：

display：外层模块，存放各外层模块活动记录的基地址
压入栈：跟随运行过程，只要用到的都要压入栈
prev abp：是谁调用了本模块

数组需要占两行：f 和 f 模版

LL(1)文法

求 FIRST 和 FOLLOW：

如何求 First 集与 Follow 集（超详细）_first 集合和 follow 集合的求法-CSDN 博客

LL(1)文法分析表：

将所有 FIRST 集填入到表中，如果某非终结符可以推出 $\varepsilon$ ，将所有其 FOLLOW 中的终结符处都填上 $A\rightarrow \varepsilon$ 。

利用文法分析句子：

只有非终结符遇到非终结符才会出栈，否则一直根据分析表向下分析，不继续读入符号

判断是否是 LL(1)文法：

其分析表 M 不含多重定义入口（即分析表中无两条以上规则）

是 LL(1)文法的充要条件，即证明是 LL(1)文法：

证明有些一定不会 LL(1)文法：

如果 G 是左递归的，或者是二义性的文法，则至少有一个多重入口

左递归：

$U::=U...|a...$

则有 $FIRST(U...)\cap FIRST(a...)\neq \empty$

二义性：

对文法所定义的某些句子存在两个最左推导，即在推导的某些步存在多重定义，有两条规则可用，所以分析表是多重定义的

LR 分析法

LR(0)分析法：

将文法拓广，使其只有一个接受状态
列出文法的所有项目
将有关项目组成项目集，即为 LR(0)
计算项目集闭包 closure
计算状态转移函数 GOTO
有出边的填 Action(S)，没有出边的给拓展文法标号，填 Action®，给最初的 $E'\rightarrow E.$ 的ACTION[k,#]=acc

SLR(1)分析法：

只有归约过程改变，根据文法左边非终结符的 follow 集，填入到 Action 表中，编号是产生式的编号

$R\rightarrow .$ 也要填 $R\rightarrow \varepsilon$ 的序号

根据 Action 和 GOTO 表分析输入串：

表头：状态栈，已识别符号，待输入串，动作

S：移进，根据 Action
R：根据产生式归约，出栈（要根据产生式！！！），根据栈顶的状态查 GOTO 表

acc：如果没有扩展文法就是第一个式子在末尾点点的时候

如果是要归约 $R\rightarrow \varepsilon$ ，那就是压入栈中 R

求活前缀：

短语：前面句型中的某个非终结符所能推出的符号串，由每颗子树的叶子组成

任何句型本身一定是相对于识别符号 Z 的短语
简单子树：树的高度为两层的子树
简单短语：简单子树的叶子结点
句柄：最左简单短语，最左简单子树的叶子

活前缀：

求能识别活前缀的有效项目集：

将点点在最后一个字符的后面，然后求 closure

判断 SLR 分析法：

如果分析表有多重定义入口，分析动作不唯一，就不是 SLR(1)

代码优化

构建 DAG：

方法：

建立节点表，记录了变量名和常量值，以及他们当前多对应的 DAG 图中的节点的序号。该表初始状态为空
对于形如z=x op y的中间代码，首先在节点表寻找 x，如果找到则记录下对应节点号 i；反之新建叶节点，假设其节点号仍为 i，标记为 x（如 x 为变量名，该标记更改为 $x_0$ ）；在节点表中增加新的一项（x，i），表明二者关系。y 与 x 同理。
在 DAG 寻找中间节点，标记为 op，左操作数节点号为 i，右操作数节点号为 j。如果找到记录下其节点号 k；如果未找到，在 DAG 图中新建一个中间节点，假设其节点号仍为 k，并将节点 i 和 j 分别与 k 相连，作为其左子节点和右子节点
在节点表中寻找 z，如果找到，将 z 所对应的节点号更改为 k；如果未找到，在节点表中新建一项(z, k)，表明二者之间的对应关系

导出中间代码：

方法：

初始化一个放置 DAG 图中间节点的队列
如果 DAG 图中还有中间节点未进入队列，则执行步骤 3，否则执行步骤 5
选取一个尚未进入队列，但其所有父节点均已进入队列的中间节点 n 将其加入队列；或选取没有父节点的中间节点，将其加入队列
如果 n 的最左子节点符合步骤 3 的条件，将其加入队列；并沿着当前节点的最左边，循环访问其最左子节点，最左子节点的最左子节点等，将符合步骤 3 条件的中间节点依次加入队列；如果出现不符合步骤 3 条件的最左子节点，执行步骤 2
将中间节点队列逆序输出，便得到中间节点的计算顺序，将其整理成中间代码序列

叶节点不属于节点，不占用最左的范围。eg： $t_3$ 的最左子节点为 $t_2$

从活跃变量到冲突图：

in 集和一个 out 集，分别表示到该语句仍然活跃的活跃变量，在该语句之后的还保持活跃的活跃变量。

$in[B]=use[B]\cup(out[B]-def[B])\\ out[B]=所有后继的in[B]$

冲突图：

只有跨越基本块活跃的变量才能分配到全局寄存器：在多个 in 或 out 活跃的变量
并且活跃范围重合的变量之间无法共享全局寄存器