我要成为编译高手

文法

$$符号串乘积\{a,b\} * \{c,d\} = \{ac，ad，bc，bd\}\\ 幂运算\\ A^0={ε},A^1 = A ,A^2 = AA\\ 正闭包: A^+=A^1∪A^2...∪A^n\\ 闭包: A^*=A^0∪A^1∪A^2...∪A^n$$

Vn：非终结符号集

Vt：终结符号集

P：产生式或规则的集合

Z：开始符号（识别符号） Z∈Vn

基本概念

推导

一步或多步

零步一步或多步

最右推导：规范

句子句型

句型：Z零步一步或多步推导到x

句子：Z一步或多步推导到x，且x内符号都是终结符

语言：所有句子的集合 L(G[Z])

若两个文法语言相同，则文法等价。

短语、句柄

短语是相对于一个句型的

简单短语要求只有一步推导

句柄是最左简单短语

规约

按照最左简单短语进行规约为规范规约。

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

递归文法

U::= Uy，左递归

U::= xU，右递归

左递归不能用自顶向下

二义性

1. 一个文法的某一句子存在两棵不同的语法树，则该文法是二义性的
2. 若一个文法的某句子存在两个不同的规范推导，则该文法是二义性的
3. 若一个文法的某规范句型的句柄不唯一，则该文法是二义性的

压缩文法

U::=U的文法是有害的

规则的左部非终结符不出现在任何句型中的文法是无用的

无有害规则或多余规则的文法是压缩过的

文法类型

0型：左部和右部都可以是符号串；一个短语可以产生另一个短语；可以被图灵机接受

1型：上下文有关文法，xUy::= xuy ; 可以被线性界限自动机接受

2型：上下文无关文法，U::= u，U∈Vn , n∈V* ； 可以被下推自动机接受

3型：正则文法，U::=t，U::=Wt（左线性）或U::=tW（右线性） 其中U、W∈Vn，t∈Vt，可以被有穷自动机接受

词法分析

状态图

左线性文法状态图：

设置开始状态S，若Q::=t,

若Q::=Rt，

正则表达式

运算符

|：或

*或{ }：重复

DFA

NFA（非确定）

一个状态经过一个终结符可以到多个状态，可以输入空值

生成NFA（和状态图不一样）

用右线性文法，因为左线性会死循环

A→tB：

A→t：则A经过t到终结状态

或

NFA的确定化

1.确定集合I的ε-闭包：I以及从I经过ε弧能到的所有状态集合

2.确定闭包的Ia、Ib、…

3.得到新的状态图

最小化

消除多余状态：肉眼看，删除不会到达的状态

划分等价状态：

1. 将状态先分为终结状态和非终结状态
2. 在每个区域中看哪些状态经过符号后到达的状态等价

语法分析

自顶向下分析

不能有左递归！

要消除左递归：

• 使用BNF改写：
  1. U::= xy|xw → U::=x(y|w)
  2. T∷= T * F | T / F | F → T∷= F { * F | / F }
• 左递归改成右递归：
  1. P::= Pa|b → P ::= bP’ P’ ::=aP’ | ε

消除一般左递归：

消除回溯问题，将xV|xU改成 x(V|U)，并尽力保证FIRST(V)和FIRST(U)不相交。

无法消除回溯的话，可以超前扫描几个符号

递归下降子程序

简单

LL(1)分析法

自左向右扫描符号串

First、Follow集

First

若Xi∈Vt，则First(Xi)={Xi}

若Xi∈Vn，Xi::= a…| ε, First(Xi) = {a, ε}

若Xi∈Vn ，

• Xi::= y1y2…yk，将FIRST(y1 ) – {ε} 加入First（Xi）
• 若ε ∈ FIRST( y1 ) ，则将FIRST(y2 ) – {ε} 加入
• …
• 若全都有ε，First集加入ε

Follow

若S为识别符号，则 # 加入Follow（S）

若 A ::= αBβ 则把 FIRST(β)-{ε} 加入到 Follow（B）

若 A ::= αBβ β能推出ε 或 A::= αB ，则把**Follow(A)**加入到Follow(B)

构造分析表

• S ::= A是某规则，a为终结符或#, 把所有 a∈ FIRST( A ) ，M[S, a] 放入该条规则
• 若A=ε或 A能推出ε，则把所有 a∈ FOLLOW( S )的 M[S,a]放 S::=ε
• 剩下的全是error

如果没有多重定义入口，则是LL(1)文法

LL(1)判断方法

如果是LL（1），那么当 S::= A1|A2

• First(A1) ∩ First(A2) = Ф

• 若A2 是 ε或可推出 ε，那么 First(A1) ∩ First(S) = Ф

执行过程

假设E是识别符号

符号栈开始状态 #E，读入输入串第一个符号

根据栈顶符号X和输入符号a

• 若 X ∈ Vt，X=a=#，停止
• 若 X ∈ Vt，X=a不等于#，将X退出栈
• 若 X ∈ Vt，X不等于a，出错
• 若 X ∈ Vn，查表
  1. 若M[X,a] 为 X∷= U V W，则X弹出，先后将W、V、U入栈（注意顺序，U在栈顶）
  2. 若M[X,a] 为 X::=ε 则把X弹出栈

自底向上分析

算符优先分析

算符文法不允许两个非终结符相邻！

FirstVT、LastVT

… 可以代表任意或为空

FirstVT( U ) = {b | U→b… 或 U→Vb… , b ∈ Vt, V ∈ Vn}

LastVT( U ) = {a | U→…a 或 U→…aV , a ∈ Vt, V ∈ Vn}

构造FirstVT：

• 如果有U::= b… 或 U::= Vb… 则 b∈FIRSTVT( U )
• 如果有U::= V…，则所有 b∈FIRSTVT( V )，都有b∈FIRSTVT( U )

构造LastVT：

• 如果有U::= …a 或 U::= …aV 则 a∈LASTVT( U )
• 如果有U::= …V，则所有 a∈LASTVT( V )，都有a∈LASTVT( U )

构造优先关系矩阵

打不出来，所以下面

= 代表

< 代表

> 代表

对于每条规则进行处理，

假设规则为U::=X1 X2 … Xn

for（i = 1；i<=n-1 ; i++）

• 如果Xi 和 Xi+1都是Vt，则 Xi = Xi+1
• 如果i<=n-2 且 Xi 和 Xi+2都是Vt，但Xi+1是Vn，则Xi = Xi+2
• 如果 Xi 是Vt Xi+1是Vn ，则 Xi< FIRSTVT(Xi+1)中每个符号
• 如果 Xi 是Vn Xi+1是Vt ，则 LASTVT(Xi)中每个符号 > Xi+1

素短语

素短语是一个 至少包含一个终结符号，且除了它自身不含更小的素短语的 短语

句柄是最左短语

最左素短语不一定是句柄！

执行过程

算符优先文法对最左素短语规约

• <：移进
• =：移进
• >：规约

LR分析法

哦我的老天

LR分析法规约的是句柄，算符优先归约的是最左素短语

活前缀

规范句型是通过规范规约（最左）得到的句型

对于 αβt ，β表示句柄 ，若αβ = u1u2…ur，那么符号串u1…ui（1<=i<=r）是活前缀

构造LR(0)

1.让文法开始符号的规则只有一条

2.构造闭包项目集

3.构造goto

action构造：

A→a. 规约

E’→a. 接受

A→a.b （b∈ Vt）移进

A→a.b （b∈ Vn）待约（无动作）

会有 移进-规约 冲突

SLR（0）

改为看Follow集

当A→α. B→α. X→α.b

读入符号当 a = b，移进

a∈Follow（A），A→α

a∈Follow（B），B→α

符号表管理

符号表结构：

名字、特性（类型、值、种类等）

组织方式：

统一符号表（不管什么都填入到一个格式的符号表），结构简单

不同种类建立不同的，节省空间但是不方便

折中办法：共有信息总结成统一格式，特殊信息用指针连接到附表

非分程序结构和符号表

可独立进行编译的程序单元是不包含有子模块的单一模块

作用域：

子程序名、函数名、公共区域名 —— 全局

程序单元内变量 —— 局部

组织方式：

全局符号表
局部符号表

分程序结构语言和符号表

模块内可嵌入子模块

作用域：标识符定义时所处于的模块

过程或函数说明中定义的标识符（包括形参）其作用域为本过程体。

循环语句中定义的标识符，其作用域为该循环语句

分程序符号表结构

Outern	Ecount	Pointer

Outern：直接外层编号

Ecount：符号表项个数

Pointer：该符号表起始位置

出块后删除块符号表

红框内删了

运行时存储管理

栈地址寄存器，该空间位于高地址

静态存储分配

每个变量所需空间的大小在编译时已知

在编译阶段由编译程序实现对存储空间的管理，为源程序中的变量分配存储

条件：在编译时能够确定源程序中变量在运行时的数据空间大小

• 不允许指针或动态分配
• 不允许递归调用过程

开辟一数据区，目标地址填入变量的符号表中

没鸟用，我觉得不考🤓👆

动态存储分配

这个必考🤓👆

局部数据区
参数区
display区

局部数据区：存放局部变量

参数区：

形参数据区：显式参数区
prev adb：存放调用模块记录基地址
ret addr：返回地址
ret value：函数返回值

display区：存放各外层模块活动记录的基地址

1{ 2{ } 3{ 4{ } } } 中，4应当存放AR1和AR3的基地址

例题

重点：看call 了谁再加入活动记录

易错点：局部变量在参数上面，因为其实是从下往上构建的

数组需要加一个“数组的模块”

运行时地址计算：考鸡毛，PPT就一页

错误处理？

就几页PPT，肯定只考小题

语法错误：不符合语法、词法的错误

语义错误：不符合语义规则或超越具体计算机系统限制（数据溢出、常数太大；符号表、静态存储溢出；动态存储溢出）

分析以后再报告：保存错误，全分析完了再打印

边分析边报告：顾名思义

• 一般原则：诊断到错误并记录后，跳过当前语法成分继续分析

运行时错误：下标变量、下标值越界；计算结果溢出；动态存储分配数据区溢出

错误局部化处理: 发现错误后，尽可能将把错误的影响限制在一个局部的范围避免错误扩散和影响程序其它部分的分析

翻译文法

翻译文法概念 、 活动序列

输入文法：

• 没插入动作符号的文法。
• 推导产生输入序列

翻译文法：

• 插入了动作符号的文法
• 推导产生活动序列

**活动序列：**包含 输入序列、动作序列

• 输入序列：由终结符组成
• 动作序列：由动作符号组成

翻译文法是上下文无关文法

**符号串翻译文法：**输出@后的字符串的文法

中缀表达式文法→逆波兰表示

加入动作

属性翻译文法

L-属性翻译：

• 继承属性
  1. 产生式左部非终结符号的继承属性，取前面表达式的右部该符号 的继承属性值
  2. 产生式右侧符号的继承属性，使用当前式左侧符号的继承属性或在该符号左边的符号属性计算
• 综合属性
  1. 产生式右部非终结符号的综合属性值，取其推导产生式左部同名非终结符号的综合属性值
  2. 产生式左侧非终结符号的综合属性值，使用当前产生式左侧继承属性或右侧符号的属性计算
  3. 动作符号的综合属性，使用该符号的继承属性或右侧符号的属性计算

简单赋值L-属性翻译要求：

产生式右侧符号继承属性等于左部符号的继承属性值，或等于出现在所给符号左部某个符号的综合属性值

产生式左部非终结符号的综合属性，等于自身的继承属性，或右部某个符号的综合属性

变换：

不符合规则，因为需要对f求值，修改为

数组变量的声明处理

n维数组元素地址的计算

$$i维的下界L(i)，i维的上界U(i)\\ i维元素当前数组的 下标V(i) \\ E：数组元素大小\\ ADR=LOC+\Sigma_{i=1}^{n}[V(i)-L(i)]\times P(i) \times E \\ 当i=n时，P(i) = 1\\ 当1<=i<n时，P(i) = \Pi_{j=i+1}^n [U(j)-L(j)+1] \\$$

其他内容

常量：识别类型，识别名字，赋值

简单变量：要alloc

记录变量：是用来引用几个不同名字所组成的实体

过程声明：调用前需要确定参数、返回值

马勒戈壁看不懂

中间代码

波兰表示

算术表达式： F * 3.1416 * R * ( H + R )

波兰表示： * F 3.1416 * R * + H R

**逆波兰表达式：**F 3.1416 * R * H R + *

赋值语句 := 符号优先级最低

if语句：if < expr > then < stmt1 > else < stmt2 >

< expr > < label1 > BZ < stmt1 > < label2 > BR < stmt2 >

BZ:如果< expr >结果为0，则跳转到label1，

BR：跳转到label2

label1再BR头，label2在BR尾

N元表示

三元式：

直接三元式

间接三元式：

四元式：

(op, 操作数1, 操作数2, 结果)

Pcode？

DAG图

代码优化

优化分类

• 局部优化：指在基本块内进行的优化
• 全局优化：跨越基本块，在函数/过程内进行的优化，进行全局控制流和数据流分析
• 循环优化：对循环语句所生成的中间代码序列上所进行的优化
• 跨函数优化：整个程序，跨函数别名分析，逃逸分析

划分基本快

1. 整个语句第一条语句属于入口语句
2. 任何 条件/无条件 跳转语句转移到的提一条是入口
3. 紧跟在跳转语句后 第一条是入口

DAG图

中间代码构造DAG

**特殊注意：**如果出现 op A或 A op B；其中A、B为常数，需要合并常数

**省流：**找左右操作数，找不到就新建，找到了就记录→找op，找不到就新建，找到了就记录节点号→找结果对应的变量，找不到就添加到op节点，找到了就把变量改到op节点

DAG转中间代码

**省流：**从左向右，把没有父节点且不是叶节点的节点扔进队列，最后逆序输出。

数据流分析

到达定义分析

分析的是数据流信息 d1、d2、…

gen[S]：S本身产生的数据流信息

kill[S]：S注销的数据流信息

in[S]：进入S时的数据流信息

in[B] = out[P1] ∪ out[P2] ∪ … （所有B的前驱块）

out[S]：S末尾得到的数据流信息

out = gen ∪ ( in - kill )

步骤

1. 先写出gen和kill，能瞪眼看出来
2. 从上往下，迭代执行计算每个基本块的in和out

例题

活跃变量分析

分析的是变量x、y、i、…

在use里出现的不可能在def出现，反之亦然

def[B] : 在B中被定义先于任何使用的变量

use[B] : 在B中被使用先于任何定义的变量

in[B] : use ∪ (out - def)

out[B] : in[P1] ∪ in[P2] ∪ … （所有B的后继块）

**注意：**形如 x = x + 1的语句中，x先被使用 再被定义

步骤：

1. 瞪眼法瞪出来每个块的use和def
2. 把所有块的in初始化为空
3. 从下往上，**迭代**执行：计算每个块的out和in

例题

冲突图 和 定义-使用链

两个变量中一个变量在另一个变量定义处是活跃的，那么他们之间有边连接。

定义-使用链

全局寄存器分配

• 寄存器分为全局寄存器和临时寄存器

引用计数法

访问次数越多越可能获得全局寄存器，循环内变量获得加权

图着色法

假设寄存器数目为K，假设K=3

1. 不断移去所有连接边小于K的点，直到不能移去
2. 选一个适当的点，记录为“不分配全局寄存器”，然后移走
3. 重复1、2，直到只剩一个点
4. 给最后一个点着色，按照节点移除顺序，把边和节点放回，并着色。“不分配全局寄存器”的节点不着色

循环优化？

归纳变量

比如for（i=1；i<=10;i++）a[i] = b[i] + c[i]

生成代码里

t1=4*i （为了获取地址）

t2 = b[t1]

…

i=i+1

可把4*优化掉，直接i = i+4

**代码外提：**不需要在循环中的放出去

**循环展开：**原本for循环把a[10]全变成0，现在不用for，一条一条置0

基本块内优化类型

常数合并：2+3直接用5

运算强度削弱：乘法改成左移、x/5改成x*0.5等

复写传播优化：如x:=y语句，某些时候可以删去。

删除死代码

消除局部公共子表达式

窥孔优化：化关注在目标指令的一个较短的序列，删除其中的冗余代码

指令集架构

C = A + B

栈式：

Push A
Push B
Add
Pop C

累加器式：

LOAD A
ADD B
STORE C

寄存器-内存式：

LOAD R1, A
ADD R2, R1, B
STORE R2,C

寄存器-寄存器式：

LOAD R1, A
LOAD R2, B
ADD R3, R1, R2
STORE R3, C