跳转至

中科大《编译原理》

第二章 语言及其文法

2-1 词法语法分析基本概念

字母表 Σ 是一个 有穷符号集合

  • 符号:字母、数字、标点符号、...

  • 例如:二进制字母表 {0,1}、ASCII 字符表、Unicode 字符表等都是字母表

既然字母表是集合,那么就可以对其进行集合运算。

  • 乘积:{0,1}{a,b}={0a,0b,1a,1b}
  • n 次幂:即 n 个 Σ 相乘,当 n=0 时,为空集合,即{ε},ε(epsilon)为空串的意思。
  • 正闭包:Σ 的各个正数次幂的并集,Σ+1∪Σ2∪Σ3∪...Σn
  • 克林(kleen)闭包:Σ*+∪Σ0,因此字母表的克林闭包表示任意字符串(长度可以为零)构成的集合。

对于不同的语言,字母表 Σ 是不同的,如果编译 C 语言,则字母表是 ASCII 字符表,如果编译 Java 语言,则字母表是 Unicode 字符表

串:设 Σ 是一个字符串,∀x∈Σ*,此时称 x 为 Σ 的一个串。因此串就是字母表中符号的一个有穷序列。

串的长度:串 s 的长度,通常记作|s|,指 s 中符号的个数,例如|ab|=2,|ε|=0

串的连接:如果 x 和 y 是串,那么 x 和 y 的连接是把 y 附到 x 的后面而形成的串,记作 xy。例如 x=house,y=dog,则 xy=housedog。空串是连接运算的单位元(identity),对于任何串 s 都有 εs=sε=s。

串的前缀和后缀:设 x,y,z 是三个串,如果 z=xy,则 x 是 z 的前缀,y 是 z 的后缀。

串的幂运算:把串的连接运算看做乘法运算,那么就可以定义幂运算。例如,s0=ε,s1=ab,s2=abab,

2-2 文法的定义

文法用 G 表示,其定义为四元组:G=(VT, VN, P, S)

  • VT:终结符(terminal symbol)集合,是文法定义的语言的基本符号,有时也称为 token
  • VN:非终结符(nonterminal)集合,是用来表示 语法成分 的符号,有时也称为语法变量,通常用<>包裹。

注意:VT∩VN=∅,:VT∪VN表示 文法符号 集,是一个字母表。

  • P:产生式集合,描述了将终结符和非终结符组合成串的方法
  • 一般形式:α→β,即 α 定义为 β
  • α∈(VT∪VN)+,且 α 中至少包含 VN中的一个元素,称为产生式的头部(head)或左部(leftside)
  • β∈(VT∪VN)*,称为产生式的体(body)或右部(rightside)
  • 产生式的简写:α→β1 , α→β2 可以简写为 α→β12,其中 βn称为候选式,|读作或。
  • S:开始符号,S∈VN,表示该文法中最大的 语法成分

注意:在不引起歧义的情况下啊,可以仅用产生式集合 P 表示文法。

此外还有一些符号约定:

终结符:字母表中排在前面的小写字母(a, b, c, ...)、运算符、标点符号、数组、粗体字符串(id、if 等)

非终结符

  • 字母表中排在前面的大写字母(A, B, C)
  • 字母 S 表示开始符号
  • 小写、斜体的名字,如*expr*、*stmt*等
  • 代表程序构造的大写字母,如 E(表达式)、T(项)和 F(因子)

字母表中排在后面的大写字母(X, Y, Z)表示 文法符号,即终结符或非终结符,VT∪VN

字母表中排在后面的小写字母(主要是 u, v, w, ...)表示 终结符号串(包括空串)

小写希腊字母,如 α、β 表示 文法符号串(包括空串)

2-3 语言的定义

推导(Derivations)和规约(Reductions)

image-20220526110916420

  • ⇒,直接推导
  • n,例如 α0⇒α1, α1⇒α2, α2⇒α3,则记为, α03α3
  • +表示“经过正数步推导”
  • *表示“经过若干(可以是 0)步推导”

有了文法(语言规则),如何判定某一词串是否是该语言的句子?

  • 句子的推导(派生)- 从生成语言的角度
  • 句子的规约 - 从识别语言的角度

句型和句子

  • 如果 S⇒*α,α∈(VT∪VN)*,则称 α 是 G 的一个句型。一个句型中既可以包含终结符,又可以包含非终结符,也可能是空串。
  • 如果 S⇒*w,w∈VT*,则称 w 是 G 的句子。句子是不包括非终结符的句型。

语言

由文法 G 的开始符号 S 推导出的所有 句子构成的集合 称为文法 G 生成的语言,记为 L(G)。

即:L(G)={w|S⇒*w, w∈VT*}

2-4 文法的分类

产生式集合:α→β

  • 0 型文法:仅要求 α 中至少包含一个非终结符
  • 1 型文法,上下文有关文法(CSG):|α|≤|β|
  • 2 型文法,上下文无关文法(CFG):α∈VN,即 α 只能是一个非终结符,一般形式为 A→β。可以描述大部分程序设计语言的语法构造。
  • 3 型文法,正则文法(RG),分为两类:
  • 右线性文法:A→wB 或 A→w,表达式的右部只能是终结符 w,要么是 wB
  • 左线型文法:A→Bw 或 A→w

四种语法之间是逐级限制和逐级包含的关系。即,如果一个文法是 3 型文法,那他一定是 2 型文法,也一定是 1 型文法,也一定是 0 型文法。

2-5 上下文无关文法(CFG)分析树

分析树

image-20220522104324356

  • 根节点的标号为文法开始符号

  • 内部结点表示对一个产生式 A→β 的应用,该结点的标号是此产生式左部 A 。该结点的子结点的标号从左到右构成了产生式的右部 β

  • 叶结点的标号既可以是非终结符,也可以是终结符。从左到右排列叶节点 得到的符号串称为是这棵树的 产出( yield )或边缘(frontier)

分析树本质上是推导的图形化显示,给定一个推导 α0⇒α1⇒α2⇒α3 ,对于推导过程中得到的每一个句型 αi,都可以构造出一个边缘为 αi的分析树。

推导过程:E ⇒ -E ⇒ -(E) ⇒ -(E+E) ,其语法分析树如图所示。

句型的短语:给定一个句型,其分析树中的每一棵子树的边缘称为该句型的一个短语。如果子树只有父子两代结点,即分析树的高度为 2,那么这棵子树的边缘称为该句型的一个 直接短语

二义性文法

如果一个文法可以为某个句子生成多颗分析树,则称这个文法是二义性的。

第三章 词法分析

本章共阐述了三个等价的概念:

  • 正则表达式
  • 正则文法
  • 有穷自动机(FA)

正则表达式

正则表达式(Regular Expression, RE)是一种用来描述 正则语言 的更紧凑的表示方法,其定义如下:

  • 对于给定的字符集 Σ={r1, r2, ..., rn}
  • 归纳定义:
  • 空串 ε 是正则表达式
  • 对于任意 r∈Σ,r 是正则表达式
  • 如果 M 和 N 是正则表达式,则以下也是正则表达式:
    • 选择:M|N = {M, N}
    • 连接:MN = {mn | m∈M, n∈N}
    • 克林闭包:M* = {ε, M, MM, MMM, ...}

正则语言:每个正则表达式 r 表示一个语言,叫做正则语言或正则集合,记为 L®

令 Σ = {a, b},则:L((a|b)(a|b)) = L(a|b) L(a|b)={a, b}{a, b}= { aa, ab, ba, bb }

正则定义:具有如下形式的定义序列 di→ri

  • 每个 di都是一个新符号,它们都不在字母表 Σ 中,而且各不相同。
  • 每个 ri是字母表 Σ∪{d1, ... , di-1}上的正则表达式。

语法糖: 语法糖的概念主要用于简化构造。

  • [r1-rn] == r1|r2|...|rn
  • r+ == 一个或多个 r
  • r? == 零个或一个 r。等价于 ε|r
  • "a*" == 表示 a*自身,而不是 a 的克林闭包
  • a{i,j} ==i 到 j 个 e 的连接
  • . == 出'\n'外的任意字符

语法糖都不是必须的,可以使用最基本的定义也能实现相同的功能,但应用语法糖实现起来会更简单。

事实上,根据汇编语言的知识,可以知道,只需要使用两个操作就可以实现图灵机乃至现代计算机的所用功能:

  • 赋值
  • 跳转

那为什么需要使用 java、c 等高级语言来实现功能?就是为了实现起来更简单!最终都将翻译为赋值和跳转两个功能。

因此 java 和 c 也可以理解为语法糖,本质就是一种封装。

例子

如何用正则表达式表示 C 语言中的关键字?以 if 为例:

已知 C 语言中的字母表 Σ 是 ASCII 字符集,因此 i,f∈Σ,因此 i 和 f 都是正则表达式。

对 i 和 f 进行连接运算,构成了 if,因此 if 也是正则表达式。

如何用正则表达式表示 C 语言中标识符?使用正则定义的方式:

  • digit → 0|1|2|…|9
  • letter* → A|B|…|Z|a|b|…|z|*
  • id → letter*(letter*|digit)*

定义了以英文字母或下划线开头的,由数字、字母和下划线组成标识符名。

正则文法

正则文法与正则表达式等价:

  • 对任何正则文法 G,存在定义同一语言的正则表达式 r
  • 对任何正则表达式 r,存在生成同一语言的正则文法 G

有穷自动机

FA 使用转换图表示:

  • 结点:FA 的状态
  • 初始状态:只有一个,由 start 箭头指向
  • 终止状态:又称接受状态,可以有多个,用双圈表示
  • 带标记的有向边:如果对于输入 a,存在一个从状态 p 到状态 q 的转换,就在 p、q 之间画一条有向边,并标记上 a

image-20220522170834364

给定输入输入串 x,如果存在一个对应于串 x 的从初始状态到某个终止状态的转换序列,则称串 x 被该 FA 接受。

由一个有穷自动机 M 接受的所有串构成的集合称为是该有穷自动机定义的语言,记为 L(M)。

如图 FA 定义的语 X 言是所有以 abb 结尾的字母表{a,b}上的串的集合。

  • L(M)中的 M 为 FA 实例,其如图所示
  • L®中的 r 为正则表达式:(a|b)*abb

FA 存在 最长字串匹配原则,即在到达某个终态之后,只要输入带上还有符号,FA 就继续前进,以便寻找尽可能长的匹配。

FA 分为两类:

  • DFA:确定的有穷自动机
  • NFA:不确定的有穷自动机

DFA

DFA 用五元组定义:M = ( S,Σ ,δ,s0,F )

  • S:有穷状态集
  • Σ:输入字母表,即输入符号集合。假设 ε 不是 Σ 中的元素
  • δ:将 S×Σ 映射到 S 的转换函数。∀s∈S, a∈Σ, δ(s,a)表示从状态 s 出发,沿着标记为 a 的边所能到达的 状态
  • s0:开始状态,s0∈ S
  • F:接收状态(或终止状态)集合,F⊆ S

image-20220522172905452

如图所示,是一个 DFA,可以看到,每一个输入到达的目的地结点都是确定的。

  • S:有穷状态集,{0, 1, 2, 3}
  • Σ:输入字母表,{a, b}
  • δ:{ (s0, b)→s0,(s0, a)→s1, ... }
  • s0:开始状态,0
  • F:接收状态集合,{3}

此外,可以用 转换表 表示 FA。

NFA

同样使用五元组 M = ( S,Σ ,δ,s0,F )定义,仅 δ 不同:

  • δ:将 S×(Σ∪ε)映射到 S 的幂集的转换函数。∀s∈S, a∈Σ, δ(s,a)表示从状态 s 出发,沿着标记为 a 的边所能到达的 状态集合

image-20220522172853573

如图所示,是一个 NFA,可以看到,输入的目的地结点不是确定的,而是有多种可能的结点集合。

此时 δ={ (s0, a)→{s0, s1}, ...}

转换

DFA 和 NFA 具有等价性,对任何非确定的有穷自动机 NFA ,存在定义同一语言的确定的有穷自动机 DFA,反之亦然。

前文提及,正则表达式、正则文法、有穷自动机三者是等价的,往往需要将正则表达式,表示为有穷自动机。

此外,构造识别给定语言的 NFA 往往比构造这个语言的 DFA 要容易很多,因此首先会基于正则表达式构建 NFA,因为 NFA 需要回溯,因此 NFA 效率更低,往往还需要基于 NFA 构建 DFA。

image-20220522183118660

第四章 语法分析

语法分析主要有两种方式:

  • 自顶向下的分析(Top-Down Parsing)
  • 自底向上的分析(Bottom-up Parsing)

前文提及推导和规约,每一步推导中,都需要做两个选择:

  • 替换当前句型中的哪个 非终结符
  • 用该非终结符的哪个候选式进行替换

首先解决第一个问题,分为两种不同的推导方式:

  • 最左推导(Left-most Derivation):始终选择每个句型的 最左非终结符 进行替换。

image-20220522185837759

自顶向下的语法分析采用最左推导方式 。

  • 最右推导(Right-most Derivation)

image-20220522185848268

在自底向上的分析中,总是采用最左归约的方式,因此把最左归约称为规范归约,而最右推导相应地称为规范推导。

同一个串可能有多种推导方式,但最左推导和最右推导都是 唯一 的。

最后解决第二个问题,用该非终结符的哪个候选式进行替换?

可以通过提取左公因子来推迟决定:

文法G1
S → aAd | aBe
A → c
B →

文法G2 提取左公因子
S → a S'
S' → Ad | Be
A → c
B → b

自顶向下的分析

自顶向下分析过程中,可能需要回溯而导致效率较低,因此引入 预测分析,通过在输入中向前看 k 个数的符号来选择正确的产生式,称为 LL(k)文法。

首先讲解自顶向下分析、最左推导时会遇到的两个问题及其解决办法,后续介绍使用预测分析的 LL(1)文法。

问题一

文法G
S → cA | cB
A → a
B → b
输入
c b

同一非终结符的多个候选式存在共同前缀,将导致回溯现象。

如上述文法,输入 cb,自顶向下最左推导,首先进入 c,然后选择 A,A 产生式仅有 a,因此回溯,选择 B,

正确。

问题二

文法G1 直接左递归
A → Aa|b

文法G2 间接左递归

S → Aa|b
A → Sc

如果一个文法中有一个非终结符 A 使得对某个串 α 存在一个推导 A ⇒+Aα ,那么这个文法就是左递归的。

上述两个文法分别是直接左递归和间接左递归,会导致最左推导时出现无限循环。

消除左递归的方式就是将左递归替换成右递归。

文法G3 左递归
A → Aα|β(α≠空串ε,β不以A开头)

上述文法的正则表达式 r 为 βα*,构建其对应的等价右递归文法为:

文法G4 右递归
A → βA′
A′ → αA′|ε

转换的代价是引入了新的非终结符和空串 ε。

LL(1)文法

在介绍 LL(1)文法之前,首先需要介绍三种符号集合:

  • 非终结符的后继符号集,某个句型中紧跟在非终结符 A 后边的终结符 a 的集合,记为 FOLLOW(A)。若 A 为某个句型的最右符号,则将结束符”$“添加到 FOLLOW(A)中。

例如:能推导出 Aa 和 Ab,此时 FOLLOW(A) = {a,b}

  • 串首终结符集:给定一个文法符号串 α,α 的串首终结符被定义为可以从 α 推导出的所有串首终结符构成的集合,记为 FIRST(α)。如果 α ⇒ *ε,那么 ε 也需要添加到 FIRST(α)中。

通俗解释:FIRST(A) = 从非终结符 A 推导得到的句子开头的所有可能终结符的集合。

例如:A 可以推导出两个句子。ab 和 bc。此时称 FIRST(A) = {a,b}

  • 产生式的可选集,是指可以选用该产生式进行推导时,对应的输入符号的集合,记为 SELECT(A→β)。基于上述两个符号集,可选集可以被定义为:
  • 如果 ε∉FIRST(α), 那么 SELECT(A→α)= FIRST(α)
  • 如果 ε∈FIRST(α), 那么 SELECT(A→α)=( FIRST(α)-{ε} )∪ FOLLOW(A)

下面介绍 LL(1)文法:

  • 第一个 L:表示从左到右扫描输入
  • 第二个 L:表示最左推导
  • 1:表示每一步中只需要向前看一个输入符号来决定语法分析动作

当文法 G 是 LL(1)的,当前仅当 G 的任意两个具有相同 左部(即两个产生式都是 A→xxx) 的产生式 A→α|β 满足下面的条件:

  • 如果 α 和 β 均不能推导出 ε,则 FIRST(α)∩FIRST(β)=Φ

  • 如果 α 和 β 中至多有一个能推导出 ε

  • β ⇒* ε,则 FIRST (α)∩FOLLOW(A) =Φ;

  • α ⇒* ε,则 FIRST (β)∩FOLLOW(A) =Φ;

实例

串首终结符集

产生式 串首终结符集
E → TE' FIRST ( E ) =
E' → +TE' |ε FIRST ( E' ) =
T → FT ' FIRST ( T ) =
T' → *FT ' |ε FIRST ( T' ) =
F → (E)|id FIRST ( F ) =

非终结符的后继符号集

产生式 串首终结符集 非终结符的后继符号集
E → TE' FIRST ( E ) = FOLLOW( E ) =
E' → +TE' |ε FIRST ( E' ) = FOLLOW( E' )=
T → FT' FIRST ( T ) = FOLLOW( T ) =
T' → FT' |ε FIRST ( T' ) = FOLLOW( T' ) =
F → (E) |id FIRST ( F ) = FOLLOW( F ) =

①FOLLOW(E):

  • 由于 E 是句型 E 的最右符号,因此$加入其中。
  • 由于存在产生式F → (E) \|id,E 的后面是),因此把`)加入其中。

②FOLLOW(F)

  • 根据产生式T → FT',FOLLOW(F) ∪= FIRST ( T' ) = { _ } 注意:ε∈FIRST ( T' ) = { _ ε }
  • 由于 ε∈FIRST ( T' ) ,因此 FOLLOW(F) ∪= FOLLOW( T' ) = { + $ ) }
  • 因此最终 FOLLOW( F ) = { * + $ ) }

基于上述两个符号集,可以计算出产生式的可选集,并构建出预测分析表。

image-20220522205406346

LL(1)文法的分析方法

  • 递归的预测分析法
  • 非递归的预测分析法

详细见 PDF。

自底向上的分析

待续

第五章 语法制导翻译

编译的阶段共有六个部分:词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成。

其中语义分析的结果通常直接表示为中间代码的形式,因此语义分析和中间代码生成两个步骤通常合为一个步骤,称为语义翻译。

甚至可以在语法分析的同时进行语义翻译,称为 语法制导翻译

语法制导翻译使用上下文无关语法(CFG)来引导对语言的翻译。

将语义规则同语法规则(产生式)联系起来要设计两个概念:

  • 语法制导定义(Syntax-Directed Definitions,SDD)
  • 语法制导翻译方案(Syntax-Directed Translation Scheme,SDT)

SDD 是对 CFG 的推广

  • 将每个文法符号和一个语义属性集合相关联
  • 将每个产生式和一组语义规则相关联,这些规则用于计算该产生式中各文法符号的属性值。

如果 X 是一个文法符号,a 是 X 的一个属性,则用 X.a 表示属性 a 在某个标号为 X 的分析树结点上的值


上述内容来源于哈工大的编译原理教程,我的评价是,概念 PPT 点读机,不知道要做啥,放弃。

下面看看中科大的编译原理教程


编译器

概述

高级语言有成千上万种,机器是如何运行这些不同的语言的呢?

编译器是一个程序,核心功能是把源代码静态翻译成目标代码,常见的如

  • 源代码:C、Java...
  • 目标代码:X86、bytecode(java 字节码)、ARM、IA64、MIPS...

编译器翻译后的目标代码的语义和源代码相同,该目标代码可以在目标机器上运行,例如对于 Java,该机器即为 Java 虚拟机。

因此,编译器的输出是一个可执行程序,需要加载到内存中执行后,才能得到程序的执行结果,而相对来说,翻译器的输出直接就是执行结果。

结构

编译器被划分为两个部分,前端和后端。前端接受源程序,产生一个中间表示代码;后端接受中间表示代码,将其处理为目标机器的相关代码。

前端和后端被抽象为多个阶段(phase),因此编译器可以看作是多个阶段构成的流水线结构。

编译器接受字符序列,经过如下阶段:

  • 前端

  • 词法分析:记号序列

  • 语法分析:抽象语法树

  • 语义分析:中间代码

  • 后端

  • 代码生成:目标代码

词法分析

任务

如上述所示,词法分析接受源程序(字符序列),输出记号序列。

为了方便理解,以一个简单的代码为例:

if (x > 5)
    y = "hello";
else
    z = 1;

值得注意:

  • 每一行的末尾存在未显示的换行符
  • 字符序列的末尾存在未显示的文件结束符 EOF
  • 往往会无视空白符

输出的此法分析结果如下:

IF LPAREN IDENT(X) GT INT(5) RPAREN
    IDENT(y) ASSIGN STRING("hello") SEMICOLON
ELSE
    IDENT(z) ASSIGN INT(1) SEMICOLON EOF

为了实现这个转换的程序,首先需要定义记号的数据结构:

enum kind {IF, LPAREN, ID RPAREN}
struct token{
    enum kind k;
    char *lexeme;  //值,若无则为空
};

实现

词法分析器 至少有两种实现方法

  • 手工编码实现:相对复杂,但目前的主流的开源编译器大多采用手工编码。例如 gcc、llvm
  • 词法分析器自动生成器:程序员提供词法规则声明,即可快速自动生成,但较难控制细节。自动生成工具有 lex、flex、jlex 等

手工实现

理解手工实现的核心前提是理解转换图。

自动生成

自动生成涉及的数学理论:

  • 正则表达式
  • 有穷自动机(有限状态自动机,FA)

上述数学原理见前文。

自动生成工具(e.g. lex, flex, jlex),接受声明式规范,自动生成 词法分析器

一般来说,词法分析器的代码量在几千行,而声明式规范的代码量往往只有几百行。

在自动生成中,只需要提供声明式规范即可,下面讲解的内容是,自动生成工具是如何实现的!

词法分析自动生成

已知在自动生成词法分析器的过程中,需要提供词法规则声明,该声明使用正则表达式 RE 来提供。

如图所示是自动生成的各个步骤,首先需要通过 Thompson 算法将 RE 转换为 NFA,由于 NFA 不适用直接用于词法分析器的识别,因为它的状态转移是不确定的,因此我们的算法往往需要回溯,对于分析的效率会较低。

因此需要使用子集构造算法将 NFA 转换成 DFA。

RE→NFA:Thompson 算法

正则表达式(Regular Expression, RE)是一种用来描述 正则语言 的更紧凑的表示方法,其定义如下:

  • 对于给定的字符集 Σ={r1, r2, ..., rn}
  • 归纳定义:
  • 空串 ε 是正则表达式
  • 对于任意 r∈Σ,r 是正则表达式
  • 如果 M 和 N 是正则表达式,则以下也是正则表达式:
    • 选择:M|N = {M, N}
    • 连接:MN = {mn | m∈M, n∈N}
    • 克林闭包:M* = {ε, M, MM, MMM, ...}

Thompson 算法基于对 RE 的结构做归纳:

  • 对基本的 RE 直接构造:归纳定义前两条是基本 RE。
  • 对复合的 RE 递归构造:归纳定义的第三条下共有三条,是复合 RE。

算法详细内容见:RE 转换 NFA

示例:a(b|c)*,其基于 Thompson 生成的 NFA 如图所示:

image-20220524194433535

NFA→DFA:子集构造算法

由于 NFA 的状态转移不确定,因此往往需要回溯,而导致词法分析效率低,因此需要将 NFA 转化为等价的 DFA,同样以 a(b|c)*为例,其根据子集构造算法生成的 DFA 如图所示:

image-20220524194525386

DFA→ 词法分析器:Hopcroft 最小化算法

通过子集构造算法构建的 DFA 不是最简单的 DFA,有进一步优化的空间,同样以 a(b|c)*为例,将上述生成的 DFA 优化后的结果如图所示:

image-20220524194858613

代码实现词法分析器

生成了最终的 DFA 之后,根据其构建一个转移表,如图所示:

image-20220524200500203

然后使用代码实现词法分析器,共有几种方法:

  • 转移表
  • 哈希表
  • 跳转表
转移表

首先要用代码实现图中的转移表,代码如下:

char table[M][N];

table[0]['a'] = 1;
table[1]['b'] = 1;
table[1]['c'] = 1;
//other table entries are ERROR,可以理解ERROR = -1

然后实现词法分析驱动代码,用于识别一个 token,即记号。

nextToken()
    state = 0
    stack = []
    while(state != ERROR) // 在上面的表格中表示为空,则循环结束
        c = getChar()
        if(state is ACCEPT)  // 接受状态,q1; 表格中表示为状态1,有(1,b), (1,c)
            clear(stack)
        push(state)  // 把state压入stack栈底
        state = table[state][c]
    // 此时已经成功识别了第一个token,但多读入了一个,因此需要pop出来,并且回滚
    while(state is not ACCEPT)
        state = pop()
        rollback()

例如输入"abcabc",当依次读入 a, b, c 之后,栈中都是空的,然后读入 a,此时 state 为 ERROR,因此需要出栈,并且字符指针回滚。然后 nextToken()方法的执行到此结束,识别了第一个 token——"abc"。

此处的 stack 栈数据结构是为了实现 最长匹配

跳转表

使用跳转表的方式,代码上更为直观,且由于指定了转换的字符,因此可以提高转换的效率。且无需在内存中维护一个转换表,往往实际中转换表还是比较大的。

因此很多实际的开发工具,例如 flex 都是采用跳转表这种方式。

nextToken()
    state = 0
    stack = []
    goto q0
q0:
    c = getChar()
    if(state is ACCEPT)
        clear(stack)
    push(state)
    if(c == 'a')
        goto q1
q1:
    c = getChar()
    if(state is ACCEPT)
        clear(stack)
    push(state)
    if(c == 'b' || c == 'c')
        goto q1

语法分析

任务

语法分析器接收词法分析器输出的记号流,生成语法树。

image-20220526120525740

此外,对于语法分析阶段还基于语言的语法规则,检测语法错误,只有正确的语法才能生成对应的语法树。

image-20220526120639353

当程序员将错误修改之后,生成对应的语法树。

image-20220526120801901

学习路径

  • 数学理论:上下文无关文法(context-free grammar,CFG),是用于描述语言语法规则的数学工具。
  • 自顶向下分析
  • 递归下降分析算法(预测分析算法)
  • LL 分析算法
  • 自底向上分析
  • LR 分析算法

文法

文法共有四类:

image-20220526142107881

产生式集合:α→β

  • 0 型文法:仅要求 α 中至少包含一个非终结符
  • 1 型文法,上下文有关文法(CSG):|α|≤|β|
  • 2 型文法,上下文无关文法(CFG):α∈VN,即 α 只能是一个非终结符,一般形式为 A→β。可以描述大部分程序设计语言的语法构造。
  • 3 型文法,正则文法(RG),分为两类:
  • 右线性文法:A→wB 或 A→w,表达式的右部只能是终结符 w,要么是 wB
  • 左线型文法:A→Bw 或 A→w

四种语法之间是逐级限制和逐级包含的关系。即,如果一个文法是 3 型文法,那他一定是 2 型文法,也一定是 1 型文法,也一定是 0 型文法。

其中 3 型文法,也就是正则文法,被应用于词法分析中,2 型文法,即上下文无关文法被应用于语法分析中。而 0 型和 1 型文法目前没有广泛的应用场景。

Add 20231108,参考 https://www.bilibili.com/video/BV1gL411j7vS/ 0:22:57

上下文有关文法其右侧可以是非终结符,例如:

  • aE → aEb

此时必须出现 aE 才能替换,即必须同时出现终结符 a 和非终结符 E 才能替换,因此是上下文有关(敏感)的。

而对于上下文无关文法,例如:E → aEb,只要出现了非终结符 E 就可以替换,因此是上下文无关的。

2 型文法—上下文无关文法

上下文无关文法 CFG,其定义为四元组:G=(VT, VN, P, S)

  • VT:终结符(terminal symbol)集合,是文法定义的语言的基本符号,有时也称为 token
  • VN:非终结符(nonterminal)集合,是用来表示 语法成分 的符号,有时也称为语法变量,通常用<>包裹。

注意:VT∩VN=∅,:VT∪VN表示 文法符号 集,是一个字母表。

  • P:产生式集合,描述了将终结符和非终结符组合成串的方法
  • α∈VN,即 α 只能是 VN中的一个元素,因此上下文无关文法的产生式的一般形式为 A→β
  • β∈(VT∪VN)*,称为产生式的体(body)或右部(rightside)
  • 产生式的简写:α→β1 , α→β2 可以简写为 α→β12,其中 βn称为候选式,|读作或。
  • S:开始符号,S∈VN,表示该文法中最大的 语法成分

注意:在不引起歧义的情况下啊,可以仅用 产生式集合 P 表示文法,而省略 VT, VN, S。

推导和分析树

推导和规约

给定文法 G,从 G 的开始符号 S 开始,用产生式子的右部替换左部的非终结符。

此过程不断重复,直到不出现非终结符为止。

最终推导得到的串称为句子。

推导有两种特殊的方式:

  • 最左推导:每次总是选择最左侧的符号进行替换
  • 最右推导:每次总是选择最右侧的符号进行替换

与之相反的过程称为规约。

分析树和二义性

推导可以表达成树状结构,树的特点如下:

  • 树中的每个内部节点代表非终结符
  • 每个叶子节点代表终结符
  • 每一步推导代表如何从双亲结点生成它的直接孩子节点

通过最左推导、最有推导和其他推导,都可以推导出相同的串,但却有不同的分析树。

分析树的含义取决于树的后序遍历,此时,不同的分析树的含义不同,甚至错误。

给定文法 G,如果存在句子 s,它有两颗不同的分析树,那么称 G 是 二义性文法

从编译器的角度来看,二义性文法存在下述问题:

  • 同一个程序会有不同的含义
  • 因此程序运行的结果不是唯一的。

可以通过 文法重写 来解决二义性问题。

自顶向下分析

语法分析的目的是,给定文法 G 和句子 s(记号流),回答 s 是否能从 G 推导 出来。

自顶向下分析,就是为了实现语法分析的目的。其算法的基本思想是:

  • 从 G 的开始符号出发,随意推导出某个句子 t,比较 t 和目标句子 s:
  • 若 t==s,则语法分析回答:yes
  • 若 t!=s,则重新随意推导,若所有推导结果都是 t!=s,则语法分析回答:no
// 文法G
S -> N V N
N -> s|t|g|w
V -> e|d

// 句子s
g d w

// 回答
yes

其算法的伪代码如下:

tokens[];   // 句子s,即所有的记号。在上述例子中,tokens = [g,d,w]
i=0;
stack=[S];  // 非终结符S是开始符号
while(stack!=[])
{
  if(stack[top] is a terminal t)
  {
    if(t==tokens[i++])
      pop();   // 如果推导的终结符和句子s相同,则弹出该终结符,并且i++。表示已匹配,例如N->g,此时和tokens[0],也就是g相同。
    else
      backtrack();         // 回溯。在上述例子中,句子s是g d w,第一次推导N->s和N->t都不匹配,回溯。直到选择N->g的推导。
  }
  else if(stack[top] is a nonterminal T)
  {
    // 如果是终结符,则将产生式的右部压入栈中。
    // 例1  遇到非终结符S,选择产生式S -> N V N。此时stack=[S],因此先pop(S),然后将N V N压入栈中。
    //      注意,S -> N1 V N2,压入栈后,N1应该在栈顶。
    // 例2 遇到非终结符N,其产生式有四个,首先选择第一个产生式 N->s,此时弹出N,压入s。
    //     显然不匹配,因此回溯,选择下一个产生式N->t。如此依次尝试。
    pop();
    push(the next right hand side of T)
  }
}

上述代码存在一个严重的性能问题,也就是backtrack()回溯,比如选中正确的 N->g 的产生式时,需要两次回溯。

为了保证编译器的高效,需要线性时间的算法,可以避免回溯,引出自顶向下分析常用的两个算法:

  • 递归下降分析算法(预测分析算法)
  • LL(1)分析算法

递归下降分析算法

又称为预测分析算法,该算法高效、易 手工实现编码、错误定位和诊断信息准确,因此被如 GCC 4.0、LLVM 等开源和商业的编译器所采用。

算法的基本思想如下:

  • 每个终结符构造一个分析函数
  • 用前看符号指导产生式规则的选择

仍旧以上述的文法的句子为例,其伪代码如下:

parse_S()
{
  parse_N();
  parse_V();
  parse_N();
}

parse_N()
{
  token = tokens[i++];
  if(token==s||token==t||token==g||token==w)
    return
  error("解析失败");
}

此处使用前看符号,取出寻找的目标匹配元素 token,然后寻找产生式中是否存在该 token。

LL(1)分析算法

递归向下分析算法,主要用于手工实现编译器的语法分析器,而 LL(1)分析算法,主要用于 自动生成 语法分析器。

和自动生成词法分析器类似,自动生成语法分析器也需要输入一些声明式规范,这个规范一般是上下文无关语法(CFG)。

LL(1)分析算法是语法生成工具可以选用的算法之一,采用 LL(1)分析算法的语法分析器生成工具如 ANTLA,它通过接受语法定义,生成语法分析器。

当使用 LL(1)分析算法时,通过扫描 CFG 得到一个预测分析表,然后在配合驱动这个表的程序代码,即可生成语法分析器。

LL(1)分析算法的基本思想是:表驱动的分析算法

  • 第一个 L:表示从左到右扫描输入
  • 第二个 L:表示最左推导
  • 1:表示每一步中只需要向前看一个输入符号来决定语法分析动作

image-20220528152758844

其伪代码如下:

tokens[];
i=0;
stack=[S];
while(stack!=[])
{
  if(stack[top] is a terminal t)
  {
    if(t==tokens[i++])
      pop();
    else
      // 自顶向下分析:backtrack();
      error("...")  // LL(1)分析
  }
  else if(stack[top] is a nonterminal T)
  {

    pop();
    // 自顶向下分析:push(the next right hand side of T)
    push(the correct right hand side of T by table[N,T]) // LL(1)分析
  }
}

根据改代码,LL(1)算法相较于自顶向下分析的算法,改动的地方主要如下:

  • 当遇到非终结符时,不是依次选择产生式,不停的尝试-回溯。而是直接通过 预测分析表,找到正确的表达式,将其右部压入栈中。
  • 由于每次要么找到正确的产生式,要么找不到。因此无需回溯!当找不到时,直接报错即可。

为了构建预测分析表,首先需要构建两个集合:

  • FIRST 集
  • FOLLOW 集

基于这两个集合构建出 SELECT 集合,基于 SELECT 集合构建出预测分析表。详细内容参见LL(1)文法

上述示例的预测分析表如下:

image-20220528163532510

  • 前看符号 是 s 的时候,如果栈顶的非终结符是 S,则将产生式 0 的右部压入栈中
  • 前看符号 是 t 的时候,如果栈顶的非终结符是 N,则将产生式 2 的右部压入栈中
  • ...
LL(1)分析冲突处理

下面两个问题会导致 LL(1)构建的预测分析表有冲突,而导致回溯。

问题一

文法G
S → cA | cB
A → a
B → b
输入
c b

同一非终结符的多个候选式存在共同前缀,将导致回溯现象。

如上述文法,输入 cb,自顶向下最左推导,首先进入 c,然后选择 A,A 产生式仅有 a,因此回溯,选择 B,

正确。

问题二

文法G1 直接左递归
A → Aa|b

文法G2 间接左递归

S → Aa|b
A → Sc

如果一个文法中有一个非终结符 A 使得对某个串 α 存在一个推导 A ⇒+Aα ,那么这个文法就是左递归的。

上述两个文法分别是直接左递归和间接左递归,会导致最左推导时出现无限循环。

消除左递归的方式就是将左递归替换成右递归。

文法G3 左递归
A → Aα|β(α≠空串ε,β不以A开头)

上述文法的正则表达式 r 为 βα*,构建其对应的等价右递归文法为:

文法G4 右递归
A → βA′
A′ → αA′|ε

转换的代价是引入了新的非终结符和空串 ε。

image-20220526155207272

image-20220526164834353

自底向上分析

LL(1)具有运行高效、有现成工具可用的优点,但也有两个较为严重的缺陷:

  • 能分析的文法类型受限,很多文法都分析不了
  • 即便是能分析的文法,由于分析表中不能出现冲突,往往需要 改写文法。且改写后的文法往往变得复杂且不直观。

自底向上分析算法可以解决上述问题,在此仅研究其中最重要且应用最广泛的算法:LR 分析算法,又称移入-规约算法。

LR 分析算法在兼具运行高效、有现成工具可用的优点同时,相对于 LL(1)还拥有如下优势:

  • 更大的文法分析范围
  • 不需要对文法进行改写

LR 分析算法也是目前应用广泛的一类语法分析器的自动生成器中采用的算法,例如 YACC、bison、CUP、C#yacc 等都采用了该算法。

LR(0)分析算法

  • 第一个 L:表示从左到右扫描输入
  • 第二个 R:表示最右推导,实际上是最右推导的逆过程,即最左规约。

为了方便标记语法分析器已经读入了多少输入,引入点记号。

// 已经读入了E+3,*4还未读入。
E+3·*4

该算法主要是以下两个步骤:

  • 移进:读入一个记号,压入栈顶
  • 规约:栈顶上的 n 个符号(某产生式的右部),规约为左部的非终结符。
  • 例如对产生式 A->β1 ... βn
    • 如果 β1 ... βn 在栈顶上,则 β1 ... βn 全部弹出
    • 压入 A

该算法的核心问题是:如何确定移进和规约的时机?

image-20220528213355983

SLR 分析算法

LR 算法存在两个问题:

LR(1)分析算法

LR(1)分析工具(以 yacc 为例)

语法制导翻译

传统的语法分析的工作主要是接受:

  • 词法分析的记号流
  • 编译语言的语法规则

回答语法是否正确,并生成语法树。

但是,编译器在做语法分析的过程中,除了回答程序语法是否合法外,还必须完成后续工作,包括但不限于:

  • 类型检查
  • 目标代码生成
  • 中间代码生成

这些后续工作一般可以通过语法制导的翻译完成。

通过给每条产生式规则附加一个语义动作(通常是代码片段),该语义动作在产生式归约时执行。

line: exp '\n'      {printf("value=%d\n", $1);}

exp:n               {$$=$1;}
    | exp '+' exp   {$$=$1+$3;}
;

上述 yacc 的代码的左侧是产生式规则,右侧{}中的内容就是语义动作,将在产生式归约时执行。

实现原理

## 产生式 ai是语义动作,最左侧的n是分析状态
1: X -> β1   a1
2:     |β2   a2
...
n:     |βn   a3

## 代码实现
if(action[s,t]=="ri")
  ai   ## 归约时执行语义动作
  pop(βi)
  state s' = stack[top]
  push(x)
  push(goto[s'],x)

在分析栈上维护三元组:

其中 symbol 是终结符或非终结符,state 是当前的分析状态,这两个是本身就需要维护的内容,value 是新加入的值,表示 symbol 所拥有的值。

抽象语法树

在上述的语法分析过程中,已经生成了语法树,例如15*(3+4)的抽象语法树如图左所示:

image-20220722203628568

根据冯诺依曼计算机架构,编译器工作的过程中,从磁盘中读取源代码,然后生成对应的语法树存入 内存 中。

语法分析树编码了句子的具体推导过程,其中包含了许多不必要的信息,这些信息需要占用额外的宝贵内存空间。

由此引入两种具体语法和抽象语法的概念:

  • 具体语法:语法分析器使用的语法,必须适合于语法分析,如各种分隔符、消除左递归、提取左公因子等
  • 抽象语法:表达语法结构的内部表示,现代编译器一般都采用抽象语法 作为前端(词法、语法分析)和后端(代码生成)的中间接口。

在编译器中,为了定义抽象语法树,需要使用编译器的实现语言来定义一组数据结构。以 C 语言为例:

// 抽象语法
E -> n
    | E + E
    | E * E
// 数据结构
enum kind {E_INT, E_ADD, E_TIMES};
struct Exp {
  enum kind kind;
};
struct Exp_Int {
  enum kind kind;
  int n;
};
struct Exp_Add {
  enum kind kind;
  struct Exp *left;
  struct Exp *right;
};
struct Exp_Times{
  enum kind kind;
  struct Exp *left;
  struct Exp *right;
}
// 构造函数
struct Exp_int *Exp_Int_new(int n)
{
  struct Exp_Int *p = malloc(sizeof(*p));
  p->kind = E_INT;
  p->n = n;
  return p;
}
struct Exp_Add *Exp_Add_new(struct Exp *left, struct Exp *right)
{
  struct Exp_Add *p = malloc(sizeof(*p));
  p->kind = E_Add;
  p-left = left;
  p-right = right;
  return p;
}
// 用数据结构来编码程序 2+3*4
e1 = Exp_Int_new(2)
e2 = Exp_Int_new(3)
e3 = Exp_Int_new(4)
e4 = Exp_Times_new(e2,e3)
e5 = Exp_Add_new(e1,e4)

早期的编译器有的不采用抽象语法树数据结构,直接在语法制导翻译中生成代码。但为了更好的系统输出和简化编译器的设计,现代的编译器一般都采用抽象语法树作为语法分析器的输出。

抽象语法树是编译器前端和后端的接口,程序一旦被转化成抽象语法树,则源代码就会被编译器丢弃,后续的阶段只处理抽象语法树。

因此抽象语法树必须编码足够多的源代码信息,例如:必须编码每个语法结构在源代码中的位置(文件,行号,列号等),这样后续的阶段才能精准报错。

位置信息的代码实现如下:

struct position_t{
  char *file;
  int line;
  int column;
};
struct Exp_Add{
  enum kind kind;
  Exp *left;
  Exp *right;
  struct position_t form;  // 新增位置记录
  struct position_t to;
}

语义分析

语义分析是编译器前端最后一步工作,在现代编译器中其输入为抽象语法树,输出是中间表示。

semantic-analysis

语义分析又称为类型检查、上下文 相关 分析。

语义分析主要负责检查程序(抽象语法树)的上下文相关的属性,这是具体语言相关的,典型的情况包括:

  • 变量在使用前先进行声明
  • 每个表达式都有合适的类型
  • 函数调用和函数的定义一致
  • ...
int main()
{
  f(5);                 // 调用未定义的函数
  x+=4;                 // 变量x在使用前未声明
  break;                // break用于跳出循环,此时上文无循环
  return;               // main函数定义中返回int,此处未返回任何值
}

上述的代码都符合语法分析,都符合上下文无关文法的规范,但是对上下文相关的语义分析来说,是完全错误的。

大部分的程序设计语言都采用自然语言来表达程序语言的语义,例如,对于+运算,要求左右操作数都必须整型数。因此编译器的实现者必须对语言中的语义规定有全面的理解。

符号表

为了实现语义分析的代码,必须借助符号表。

符号表用来存储程序中的 变量相关信息

  • 类型
  • 作用域
  • 访问控制信息
  • ...

符号表必须在空间和时间之间进行权衡,以保证语义分析的速度和程序的规模。

符号表的接口如下,以 C 语言为例:

typedef ... Table_t
Table_t Table_new();                           // 创建符号表
void Table_enter(Table_t, Key_t, Value_t);     // 数据写入符号表
Value_t Table_lookup(Table_t, Key_t);          // 搜索符号表的数据

其中Value_t是即将要写入符号表的数据,其形式如:

typedef struct Value_t{
  Type_t type;
  Scope_t scope;
  ...// 其他必要字段
}value_t;

为了高效,可以使用哈希表等数据结构来实现符号表,O(1);为了节约空间,也可以使用红黑树等平衡树,O(lg N)。

作用域

int x;
int f()
{
  if(...){
    int x;
    x = 1;
  }
  else{
    int x;
    x = 2;
  }
  x = 3
}

在上述代码中x的作用域发生了多次改变,因此在符号表中的记录也应该做处理,一般有下述方法:

  • 单个符号表的方法:进入作用域时,插入元素;退出作用域时,删除元素。
  • 采用符号表构成的栈:进入作用域时,压入新的符号表,退出作用域时,删除栈顶符号表。

使用单个符号表的方法时,由于表中可能同时存在两个相同元素,如上述代码的x,因此需要对不在当前作用域的x做屏蔽操作。

采用符号表构成的栈时,为每个作用域新增一个符号表,优先在当前的符号表中查询,若查询不到,再去外部的符号表查询。

命名空间

命名空间,又称为名字空间,Name Space。

注意区分作用域和命名空间的区别:

  • 作用域:作用域是针对命名空间而言,指命名空间在程序里的可应用范围。在某些地方,这个命名空间中的名字可以直接使用。
  • 命名空间:从名字到对象的一个映射关系。不同命名空间是相互独立的,没有任何关系的,所以同一个命名空间中不能有重名,但不同的命名空间是可以重名而没有任何影响。
struct list
{
  int x;
  struct list *list;
}*list;
void walk(struct list *list)
{
  list:
  printf("%d\n", list->x);
  if(list = list->list)
    goto list;
}

在上述代码中,出现了很多的list,这些list可以在同一个作用域中重复出现,原因是它们分布在四个互不干扰的命名空间中:

  • 结构体名:struct list
  • 变量名
  • 结构体内的域:list->list
  • 标号:goto list

可以采用符号表来处理命名空间的问题,为每一个命名空间单独使用一个符号表,这样不同的命名空间之间就不会互相干扰。

代码实现示例

在介绍了符号表等背景知识之后,可以开始简单的实现语义分析,以 check_exp 为例:

// 抽象语法
E -> n
    | true
    | false
    | E + E
    | E * E
// 实现代码
enum type {INT, BOOL};
enum type check_exp(Exp_t e)
{
  switch(e->kind):
  case EXP_INT: return INT;
  case EXP_TRUE: return BOOL;
  case EXP_FALSE: return BOOL;
  case EXP_ADD:
                t1 = check_exp(e->left);
                t2 = check_exp(e->right);
                if(t1!=INT || t2!=INT)
          {
            error("trype mismatch");
          }
                else return INT;
  case EXP_... // 类似
}

其他问题

语义分析中还需要考虑的一些其他问题:

  • 类型相容性:由于引用类型的存在,相容性的考虑变得尤为重要,往往需要递归比较。(还包括对象继承等)
  • 错误诊断:要尽可能多、准确的错误信息及错误位置。
  • 代码翻译:现代的编译器中的语义分析模块,除了做语义分析外,还要负责生成中间代码或目标代码。

综上所述,语义分析模块往往是编译器中最庞大也最复杂的模块。

代码生成

在得到抽象语法树之后,正式进入编译器的中间端。

image-20220724181403503

其中经过多次翻译->中间表示之后,最后生成目标机器上的汇编语言,我们将其称为代码生成。

目标机器可以是真实的物理机器,也可以是虚拟机。

代码生成有两个重要的任务:

  • 给源程序的数据分配计算资源

  • 源程序的数据:全局变量、局部变量、动态分配的空间等

  • 机器计算资源:寄存器、数据区、代码区、栈区、堆区

需要根据程序的特点和编译器的设计目标,合理的为数据分配计算资源,例如变量放在内存里还是寄存器里等问题。

  • 给源程序的代码选择指令

  • 源程序的代码:表达式运算、语句、函数等

  • 机器指令:算术运算、比较、跳转、函数调用返回等

使用机器指令实现源程序的代码需要对机器指令集体系结构(ISA)十分熟悉,才能保证二者的等价性及执行效率。

下面将分别基于栈式计算机和寄存器计算机进行讲解。

栈式计算机

栈式计算机在上世纪 70 年代曾非常流行,由于效率等原因已经基本退出了历史舞台。今天仍旧讨论栈式计算机的原因是:

  • 给栈式计算机生成代码是最容易的,方便本课程的讨论。
  • 如今仍旧有许多栈式虚拟机:Pascal P Code、Java virtual machine、Postscript 等

stack-pc-structure

栈式计算机的抽象结构如图,我们自己定义:

  • 内存 Memory:存放所有变量
  • 栈 Stack:进行运算的空间
  • 执行引擎 ALU:指令的执行

机器指令

该计算机的指令定义如下(来源于 JVM):

s -> push NUM
     | load x
     | store x
     | add
     | sub
     | times
     | div

简单介绍几个指令具体的内存和栈操作:

// push NUM
top++;            // 栈指针上移,注意此处栈指针始终指向栈顶元素
stack[top] = NUM; // 压入新的栈元素

// load x
top++;
stack[top] = x;   // 内存中的值压入栈中

// store x
x = stack[top];
top--;

// add
temp = stack[top-1] + stack[top];  // 栈顶的前两个元素相加
top -= 2;                          // 指针下移
push temp;                         // 计算结果压入栈顶

变量的内存分配伪指令

默认该栈计算器只允许处理整形数 int,将给变量 x 分配内存的伪指令是.int x。该机器在装载一个程序时,就会读取伪指令,并且给相关变量分配内存空间。

int x;       .int x
x = 10;      push 10      // 把10压入栈顶
                     store x      // 把栈顶元素赋值给x

递归下降代码生成算法

...
S -> id = E                    Gen_S(S)
     | printi(E)
     | printb(E)
E -> n                                               Gen_E(E)
     | id
     | true
     | false
     | E + E
...

若要完成上述 C--语言的部分抽象语法,需要完成两个递归函数,以Gen_E为例:

Gen_=E(E e)
{
  switch(e)
    case n: emit("push n"); break;
    case id: emit("load id"); break;
      case true: emit("push 1"); break;
      case false: emit("push 0"); break;
      case e1+e2:
                Gen_E(e1);
                Gen_E(e2);
                emit("add");
                break;
    case ...: //similar
}

如此,就可以完成栈式计算机的代码生成。

寄存器计算机

寄存器计算机是目前最流行的机器体系结构之一,其机器体系结构规整且效率很高,基于寄存器的架构有如下特征:

  • 典型的有 16、32 或更多的寄存器,所有的操作都在寄存器中进行
  • 访问内存都通过 load、store 进行,内存不能直接运算

寄存器计算机结构示意图

寄存器计算机抽象体系结构如上图所示,定义如下:

  • 内存 Memory:存放溢出的变量
  • 寄存器 Reg:进行运算的空间,注意,本次假设寄存器数量无限,因此,不会有溢出的变量,内存永远不会被使用!
  • 执行引擎 ALU:指令的执行

机器指令

s -> movn   n, r
     | mov r1, r2
     | load [x], r
     | store r, [x]
     | add r1, r2, r3
     | sub r1, r2, r3
     | times r1, r2, r3
     | div r1, r2, r3

变量的寄存器分配伪指令

同样默认仅允许处理整型数 int,并且给变量 x 分配寄存器的伪指令是.int x

在代码生成的阶段,假设 Reg 机器上游无限多个寄存器:

  • 因此每个声明变量和临时变量都会占用一个(虚拟)寄存器
  • 把虚拟寄存器分配到物理寄存器的过程称为 寄存器分配

递归下降代码生成算法

同样使用递归下降代码生成算来来实现代码生成。

抽象语法同上:

...
S -> id = E                   void  Gen_S(S)
     | printi(E)
     | printb(E)
E -> n                                            R_t Gen_E(E)
     | id
     | true
     | false
     | E + E
...

Gen_E为例:

R Gen_E(E e)
{
  switch(e)
    case n: r = fresh();
                    emit("movn n, r");
                    return r;
    case id: r = fresh();
                     emit("mov id, r");
                     return r;
    case true: r = fresh();
                         emit("movn 1, r");
    case e1+e2: r1 = Gen_E(e1);
                            r2 = Gen_e(e2);
                            r = fresh();
                            emit("add r1, r2, r");
                            return r;
    case ...: // 类似,不赘述
}

中间代码

在上一节,我们已经知道,生成机器语言的过程称为代码生成,但是在现代编译器中,不会直接从抽象语法树生成机器代码,而是会经过多次的翻译-中间表示的过程,划分为多个中间表示的考虑如下:

  • 编译器工程考虑:阶段划分、任务分解、代码工程(实现、维护)。
  • 程序分析和代码优化的需要:二者都与程序的中间表示密切相关,许多优化在特定的中间表示上才可以或才容易进行。

常用的中间代码如下:

  • 树和有向无环图(DAG):高层表示,适用于程序源代码
  • 三地址码(3-address code):低层表示,靠近目标机器
  • 控制流图(CFG):更精细的三地址码,程序的图状表示,适合做 程序分析、程序优化等
  • 静态单赋值形式(SSA):更精细的控制流图,同时编码控制流信息和数据流信息
  • 连续传递风格(CPS):更一般的 SSA

通用编译器语言:Java、Python 等语言都编译为同一种中间表示语言,该中间表示语言又可以编译为多种目标机器语言,如 X86、ARM、Sparc 等。

后续介绍:

  • 常用的中间表示:三地址码、控制流图、静态单赋值形式
  • 介绍在中间表示上做程序分析的理论和技术:控制流分析、数据流分析

代码优化打下基础。

三地址码

基本思想

  • 给每个中间变量和计算结果命名,没有复合表达式
  • 只有最基本的控制流,没有循环等复杂控制结构,只有 goto,call 等基本控制流

因此,三地址码可以看成是抽象的指令集,三地址码指令定义为:

s -> x = n                    // 常数赋值
     | x = y  z                // 二元运算
     | x = θ y                                  // 一元运算
   | x = y                    // 数据移动
     | x[y] = z                                 // 内存写
     | x = y[z]                                 // 内存读
     | x = f(x1, ..., xn)               // 函数调用
     | Cjmp(x1, L1, L2)                 // 条件跳转
     | Jmp L                                        // 无条件跳转
     | Label L                                  // 标号
     | Return X                                 // 函数返回

使用示例:

a = 3 + 4 * 5

// 对应三地址码
x_1 = 4;
x_2 = 5;
x_3 = x_1 * x_2;
x_4 = 3;
x_5 = x_4 + x_3;

if(x < y)
  z = 6;
else
  z = 7;
...

// 对应三地址码
Cjmp(x<y, L_1, L_2);
L_1:
    z = 6;
    jmp L_3
L_2:
    z = 7;
    jmp L_3;
L_3:
    ...

如何使用抽象语法树生成对应的三地址码?

类似于上述的递归下降代码生成算法。

控制流图及控制流分析

三地址码的不足之处在于,难以看到程序的跳转关系,因此引入控制流图,能带来很多好处:

  • 控制流分析:对很多程序分析来说,程序的内部结构很重要,典型的问题如程序中是否存在循环?
  • 进一步进行其他分析,如数据流分析。典型问题如:程序第 5 行的变量 x 可能的值是什么?

现代编译器的早期阶段就会倾向做控制流分析,方便后续阶段的分析。

基本概念

  • 基本块:是语句的一个序列,基本块中第一条语句执行到最后一条语句时,不能从中间进入和退出,即跳转语句只能出现在基本块的末尾。
  • 控制流图:控制流图是一个有向图G=(V, E)
  • 节点 V:基本块
  • 边 E:基本块之间的跳转关系

控制流图示意图

如何生成控制流图?

  • 直接从抽象语法树生成:高层语言具有特别规整的控制流结构,如 Java
  • 先生成三地址码,然后继续生成控制流图:高层语言包含 goto 等非机构化的控制流语句,如 C;此外,阶段划分也是更加通用的方式。

控制流图的基本操作:

  • 标准的图论算法都可以用在控制流图的操作上:各种遍历算法、生成树、必经节点结构等
  • 图节点的顺序有重要的应用:拓扑序、逆拓扑序、近似拓扑序等

死基本块删除优化为例,讲解图算法的应用:

int f()
{
  int i = 3;
  while(i<10){
    i = i+1;
    printi(i);
    continue;
    printi(i); // 这句话无效
  }
}

其对应的控制流图如下:

死基本快

如图所示L3是死基本块,可以删除,删除算法:

// 输入:控制流图g
// 输出:经过死基本块删除后的控制流图
dead_blocks_elim(g)
{
  dfs(g);
  for(each node n in g){
    if(!visited(n))
      delete(n);
  }
}

数据流分析

抽象语法树也可以被认为是一种中间表示,代码优化的过程可以在每一种中间表示上进行。

翻译-优化

优化的一般模式分两步进行:

  • 程序分析:

  • 控制流分析、数据流分析、依赖分析、...

  • 分析后得到待优化程序的静态保守信息,这是对动态运行行为的近似。

静态保守:例如 x 是程序输入,只有运行时才能知道值,编译器只能采用 静态 能够获取的信息对程序做 保守 估计。

  • 程序重写

  • 根据程序分析得到的信息对程序进行重写

介绍两种数据流分析:到达定义分析和活性分析。

到达定义分析

定义(def):对变量的赋值

使用(use):对变量值的读取

数据流方程及其算法实现(todo)

活性分析

在代码生成的讨论中,我们假设目标及其有无限多个(虚拟)寄存器可用,由此简化了代码生成算法,但是实际的物理机器只有有限多个寄存器,因此必须要把无限多个虚拟寄存器分配到有限个寄存器中。

为了优化寄存器分配的任务,需要将进行活性分析。

干扰图等(todo)

代码优化

代码优化是对被优化的程序进行的一种 语义保持变换。变换的目的是让程序比变换前更小、更快、更节能、Cache 行为更好等。

语义保持:程序的可观察行为不能改变,如 IO、file、network 等

不存在完全优化,这也戏称为”编译器从业者永不失业定律“。

代码优化十分困难:

  • 不能保证优化总能产生好的结果
  • 优化的顺序和组合很关键
  • 很多优化问题是非确定的
  • 优化的正确性论证很微妙

路线图:

  • 前端优化
  • 局部的、流不敏感的
  • 常量折叠、代数优化、死代码删除等
  • 中期优化
  • 全局的、流敏感的
  • 常量传播、拷贝传播、死代码删除、公共字表达式删除等
  • 后端优化
  • 在后端(汇编代码级)进行
  • 寄存器分配、指令调度、窥孔优化等

前端优化

即在抽象语法树上进行优化。

常量折叠

基本思想:在编译期间计算表达式的值

  • a = 3 + 5 ==> a = 8
  • if(true && false)··· ==> if(false)

可以在整形、布尔型、浮点型等数据类型上进行。

常量折叠容易实现、可以在语法树或者中间表示上进行,通常被是线程公共子函数被其他优化调用。

值得注意的是,必须很小心遵守语言的定义,例如考虑溢出或异常,0xffffffff + 1 ==> 0,该有化是否正确?

答:如果是符号数,则正常计算为 0,若为非符号数,则溢出,虽然溢出后也为零,但有些语言该情况下需要抛出异常。

代数化简

基本思想:利用代数系统的性质对程序进行化简。

示例:

  • a = 0 + b ==> a = b
  • a = 1*b ==> a = b
  • 2*a ==> a + a (强度消弱)
  • 2*a ==> a << 1 (强度消弱)

强度消弱指的是,在计算时,2*a的复杂程度高于a+aa<<1,因此优化后可以提高效率。

同时也必须非常仔细的处理语义,例如(i-j) + (i-j) ==> i+i-j-j的优化存在问题,需要考虑溢出等。

死代码(不可到达代码)删除

基本思想:静态移除程序中不可到达的代码

示例:

if(false)
  s1;
else s2;

// 优化为
s2

在控制流图上也可以进行这些优化,但在早期做这些优化可以简化中后段。

中期优化

对中间表示上的代码进行优化,因此依赖于具体所使用的中间表示:控制流图(CFG)、控制依赖图(CDG)、静态单赋值形式(SSA)、后续传递风格(CPS)等。

在进行中期优化时,往往都需要程序分析。其优点是在全局进行的,而不是局部。通用的模式是:程序分析 -> 程序重写。

  • 常量传播

  • 拷贝传播

  • 死代码删除