软件开发

编译器设计（教程翻译）

2018-09-01  本文已影响84人  dannyvi

链接地址：https://www.tutorialspoint.com/compiler_design/compiler_design_quick_guide.htm (如有版权问题，请联系删除）

编译器设计 - 概览

计算机是软硬件的综合体。硬件被驱动程序控制功能设备。硬件理解和执行电荷产生的指令，相当于软件程序中的二进制语言。二进制语言只有两个字符，0和1。 要发出指令，硬件码必须编写成二进制的形式，就是一列0100101000001....。这对于程序员编写而言太过复杂，所以我们需要编译器来编写这样的代码。

语言处理系统

我们已经了解到，任何电脑系统都是软硬件构成。硬件能够理解的机器语言是人类难以读懂的。所以我们使用容易理解和记忆的高阶语言。高阶程序被送入系列工具和操作系统组件，以获取机器运行所需要的代码，就是语言处理系统。

语言处理系统

高阶语言通过多个周期（phase）转换成二进制语言。一个编译器就是一个将高阶语言转换成汇编语言的程序。同样的，一个汇编器就是将汇编语言转换成机器码的程序。

首先了解下一个c程序是如何机器中执行的。

在深入到编译器的其他概念之前，我们需要先了解一些其他的与编译器关系密切的工具。

预处理器 (Preprocessor)

预处理器大致理解为编译器的一部分，为编译器产生输入。它负责宏处理，增强，文件包含，语言扩展等功能。

解释器 (Interpreter)

解释器与编译器类似，将高阶语言翻译成低阶语言。不同之处在于他们读入代码或输入的方式。一个编译器一次性读入整段代码，创建标记(token)，检查语义(semantic)，生成中间代码， 执行整个程序。它可能有多个遍历(pass)。一个解释器从输入中读取一个语句(statement)，转换成中间代码，执行它，然后再取下一个语句。如果错误发生，一个解释器就停止执行，并且报告，而编译器会读取整个程序，即使碰见好几个错误。

汇编器 (Assembler)

汇编器将汇编语言翻译成机器码。汇编器输出的内容叫对象文件(object file)，包含了一组机器指令，和放置这些代码到内存所需的数据。

连接器 (Linker)

连接器连接合并多个对象文件(object file)，产生一个可执行文件。这些文件有可能是不同的汇编器生成的。连接器的主要目标是搜索和定位引用程序中的模块和循环，确定这些代码在内存中的加载位置，让程序指令定位到绝对地址（调用的时候需要地址定位）。

加载器 (Loader)

加载器是操作系统的一部分，负责加载可执行文件到内存并且执行它。它计算程序的大小(指令和数据)并且创建内存空间。它还要初始化多个寄存器的值来启动程序执行。

交叉编译器 (Cross-compiler)

在A平台运行，为B平台生成可执行代码，就叫做交叉编译器。

源代码编译器 (Source-to-source compiler)

将一种程序语言转换成另一种程序语言，就叫源代码编译器。

编译器结构

编译器大致分为两个周期(phase)，基于它编译的方式。

分析周期

又名编译器前端，分析周期读取源程序，将其分解为核心部件，然后检查词法(lexical)，文法(grammar)和语法(syntax)错误。分析周期生成程序的一种中间表达和符号表，可以作为推导周期的输入。

编译器分析推导

推导周期

又名编译器后端，推导周期读入中间代码和符号表，生成目标程序。

一个编译器可以有很多个周期(phase)和遍历(pass)。

编译器周期

编译过程就是以个多周期序列。每个周期从上个阶段取输入，对源代码进行自己的表达，然后将内容输出到下个周期。让我们理解下编译器周期。

编译周期

词法分析

第一个周期就是个文字扫描器。这个周期将源代码视为一个字符流进行扫描，并转换为词素单位。词法分析器将这些词素表示为标记(token):

<标记名,  属性值>

语法分析

下个周期叫语法分析(syntax analysis 或 parsing)。它取词法分析器的产出，token标记，作为输入， 生成语法树。这个周期安照源代码语法检查标记的排列，分析器检查标记产生的表达式是否符合语法。

语义分析

语义分析检查语法树是否按照语言规则构建。比如，所赋的值和类型是否匹配，或者字符串和数字相加。并且，语义分析器保持追踪标识符(identifier)，及其类型和表达式；标识符使用在声明之前等等。语义分析器产生一个注释语法树作为输出。

中间代码生成

语义分析后，编译器为目标机器生成源码的一个中间代码。它是一种抽象机器的表示程序，介于高阶语言和机器语言之间。这种中间语言应该便于翻译成目标机器语言。

代码优化

下个周期做中间代码的优化工作。优化可以看作是某种比如说移去不必要的代码，安排语句顺序，加速程序执行，不浪费资源(CPU，内存)。

代码生成

这个周期，代码生成器取优化中间码，并将其映射为目标机器语言。代码生成器将中间码翻译成一序列可重定位的机器语言。机器指令序列的执行等价于中间代码。

符号表

在全部编译周期维护的同一个数据结构。所有的标识符名称，以及类型都存储于此。符号表使编译器迅速查询标识符记录。符号表也用于作用域管理。

编译器设计 - 词法分析

词法分析是编译器的第一个周期。它以预处理器修改过的语句形式的源代码作为输入。词法分析器将这些语句分解成一系列标记，去除掉了空白和注释。

如果词法分析器发现无效标记，就生成一个错误。词法分析器和语法分析器密切合作。它从源码读取字符流，检查合法标记，传递数据到语法分析器。

标记传递

标记

词素(lexeme)就是标记(token)中的字符序列。一集预定义好的规则产生的词素，被标识为有效标记。这些规则被定义为语法规则，或者样式(pattern)。一个样式解释了什么是标记。这些样式是用正则表达式定义的。

在程序语言中，关键词，常量，标识符，字符串，数字，操作符和标点符号都被看作是标记。

例如，在C语言中，变量声明行

int value = 100;

包含了以下标记：

标记的说明

让我们理解下语言理论是如何处理以下组合的：

字母表

符号{0,1}的任何有限集合都是一个二进制字母表的集，{0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}是一个十六进制字母表的集合，{a-z, A-Z}是英语字母表的一个集合。

字符串

任何字母表的有限集都叫字符串。字符串长度就是字母出现的次数。比如，字符串 tutorialspoint 长度是 14，标记为 |tutorialspoint| = 14。一个没有字母表的字符串，一个零长度的字符串被认做空字符串，标记为 ε。

特殊符号

一个典型的高阶语言包含以下符号：

类型 符号
数学符号 加(+), 减(-), 模(%), 乘(*), 除(/)
标点符号 逗号(,), 分号(;), 句号(.), 箭头(->)
赋值 =
特殊赋值 +=, /=, *=, -=
比较 ==, !=, <, <=, >=
预处理 #
定位符 &
逻辑 &, &&, , , !
位移操作 >>, >>>, <<, <<<

语言

语言指的是有限字母表构成的有限集合。计算机语言指的是有限集合和可以作用在其上的数学集合操作。有限语言可以被正则表达式描述。

正则表达式

词法分析器需要扫描和标识一个属于该语言的有效的 字符串/标记/词素 的有限集合。它搜索由语言规则定义的样式。

正则表达式可以通过定义由符号组成的有限字符串样式来表达有限语言。正则表达式定义的语法被称为正则语法。正则语法定义的语言叫正则语言。

正则表达式是指定某种样式的重要标记法。每个样式匹配一集字符串，所以正则表达式可以表达字符串名字。程序语言标记可以被正则语言所描述。正则表达式可以用一个递归定义来说明。正则语言容易理解，也可以有效实现。

正则表达式遵从一系列代数规则，可以用在等式中控制正则表达式。

操作

语言中的操作是：

标记法

如果 r 和 s 是代表 语言 L(r) 和 L(s) 的正则表达式，那么

优先级和结合性

在正则表达式中表示一个语言里的有效标记

如果 x 是一个正则表达式，那么:

用正则表达式表示符号

letter = [a-z] or [A-Z]
digit = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 或者 [0-9]
sign = [ + | - ]

用正则表达式表示语言标记

Decimal = (sign)?(digit}+
Identifier = (letter)(letter | digit)*

现在，词法分析器剩下的唯一问题就是如何确认正则表达式制定的语言关键词样式是有效的。一个广为接受的方案是使用有限自动机来检验。

有限自动机

有限自动机是一个状态机，它取一串符号为输入，并且为之改变状态。有限自动机是一个正则表达式的识别器。当正则表达式字符串装入有限自动机时，它为每个文字改变状态。如果输入字符串成功处理，并且自动机到达终点状态，字符串被接受，也就是说，字符串被认可为该语言的有效标记。

有限自动机的数学模型：

转换函数 (δ) 将 有限状态集(Q)映射到输入符号表(Σ), Q × Σ ➔ Q

有限自动机的构建

假设 L(r) 是一个能被有限自动机(FA)识别的正则语言。

例子: 我们假设 FA 接受任意三个以1为结尾的二进制值。FA = {Q(q0, qf), Σ(0,1), q0, qf, δ}

有限自动机

最长匹配规则

当词法分析器读取源代码时，它逐个扫描代码字符，当遇到空白，操作符或者特殊符号时，它就确定这个词完成了。

例子:

int intvalue;

当扫描两个词素到 'int'，词法分析器不能确定是否它是关键词int还是标识符intvalue的开头。

最长匹配规则指定词素扫描应该基于标记可能获取的最长匹配。

词法分析器也遵循规则优先级，当一个保留字，在语言中被赋予优先级高于用户输入。也就是说，如果词法分析器找到一个词素匹配到存在的保留字时，它就生成一个错误。

编译器设计 - 语法分析器

语法分析是编译器的第二周期。这一章里我们将学习语法分析器的基本概念。

我们已经看到一个词法分析器可以用正则表达式和样式规则来识别标记。但是一个词法分析器无法检查语句的语法，因为正则表达式的限制。正则表达式无法检查配平标记，比如括号。因此，这个阶段使用上下文无关文法（CFG)，可被下推自动机所识别。

CFG，在另一方面，是正则文法的超集，如下图：

上下文无关文法

它显示出每个正则文法都是上下文无关的，但是存在一些问题超出了正则文法的作用。CFG是一个有用的工具，来描述程序语言的语法。

上下文无关文法

在这一节，我们首先看上下文无关文法的定义，并且介绍语法分析技术的术语。

一个上下文无关文法包含四个组件：

字符串就是从开始符得到的，通过不断替换非终端为产生式右侧。

例子

我们取不能被正则表达式描述的回文语言做例子。 L = { w | w = wR } 不是一个正则语言。但它可以被CFG描述绘制：

G = ( V, Σ, P, S )

在此：

V = { Q, Z, N }
Σ = { 0, 1 }
P = { Q → Z | Q → N | Q → ℇ | Z → 0Q0 | N → 1Q1 }
S = { Q }

这个文法描绘了回文语言，诸如： 1001， 11100111, 00100, 1010101, 11111等等。

语法分析器

一个语法分析器用前面词法分析器产生的标记流作为输入。语法分析器按照产生式规则分析源代码(标记流)，来探测代码中的错误。这个周期的输出就是一个语法树。

语法分析

语法分析器完成两个目标，分析代码，寻找错误和生成语法树作为这个周期的输出。

语法分析器即便遇到错误，也应该完成整个代码的分析。分析器采用错误回复机制，我们将在这一章学习。

推导

一个推导过程就是一列能够得到输入字符串的产生式规则。在分析过程中，我们对输入的语句形式做两种决策：

要决定哪个非终端被替换，我们有两种选择。

左推导

如果输入的句型从左向右扫描和替换，它就叫左推导。左推导的巨型叫左句型。

右推导

反之就是右推导和右句型。

例子

产生式规则：

E → E + E
E → E * E
E → id

输入字符： id + id * id

左推导：

E → E * E
E → E + E * E
E → id + E * E
E → id + id * E
E → id + id * id

注意最左边的非终端总是先替换。

右推导：

E → E + E
E → E + E * E
E → E + E * id
E → E + id * id
E → id + id * id

语法树

一个语法书就是一个推导过程的图示。它可以很方便的看到字符串是如何从开始符号推导的。推导的开始符号就是语法树的根节点。让我们看下例子。

我们可以从左推导得出 a + b * c

左推导过程：

E → E * E
E → E + E * E
E → id + E * E
E → id + id * E
E → id + id * id

步骤1:

   
E → E * E image

步骤2:

   
E → E + E * E image

步骤3:

   
E → id + E * E image

步骤4:

   
E → id + id * E image

步骤5:

   
E → id + id * id image

在一个语法树中：

一个语法树描绘出操作符的结合性和优先级。最深的子树首先通过，因此它的操作符优先级要高于它的父节点。

分析的种类

语法分析器遵守产生式规则，这个规则是由上下文无关文法定义的。产生式规则的实现方式分为两种： 自顶至下分析(顺序分析)和自底至上分析(逆序分析)。

顺序分析

当一个分析器从开始符构建语法树，然后试图变换开始符到输入，就叫顺序分析。

逆序分析

如名字所示，逆序分析从输入符号开始尝试构建语法树到开始符号。

例子:

输入字符串： a + b * c

产生式规则:

S → E
E → E + T
E → E * T
E → T
T → id

让我们开始逆序分析

a + b * c

读取输入和检查是否有产生式匹配输入：

a + b * c
T + b * c
E + b * c
E + T * c
E * c
E * T
E
S

多义性

一个文法G如果能够产生两种语法树，就说这个文法有多义性。

例子

E → E + E
E → E – E
E → id

对于字符串 id + id - id，以上文法生成两个语法树。

image

多义性文法产生的语言名为固有二义。文法多义性对于编译器构建而言并不是好事。没有方法可以自动检测和移除多义性，但是他可以通过重写文法来消除多义性，或者设置和遵循结合性和优先级限制也可以消除多义性。

结合性

如果一个预算数在它的两边都有操作符，那么这个操作数应该取哪边的符号，就取决于它的结合性。如果操作是左结合的，就取左边，反之则取右边。

例子

操作，比如加法，乘法，减法和除法都是左结合。如果表达式包含：

id op id op id

它将会作为下面的式子来求值：

(id op id) op id

比如，(id + id) + id

像幂运算这样的操作符，就是右结合，也就是说，求值顺序应该是：

id op (id op id)

比如， id ^ (id ^ id)

优先级

如果两个不同的操作符共用一个操作数，操作符的优先级决定去哪个符号取到操作数。比如，2+34 可以有两个语法树，一个是(2+3)4 另一个是 2+(3*4)。通过设置优先级，这个问题可以轻易解决。像前面的例子那样，数学运算中的 (乘法) 有比 +(加法) 更高的优先级，所以表达式 2+34只有一种形式：

2 + (3 * 4)

这些方法减少了文法语言中的多义性。

左递归

一个文法，如果有任何非终端'A'，并且它的推导式包含'A'在最左侧，那么它就是左递归的。左递归文法在顺序分析中被认为是有问题的状况。顺序分析器从开始符号开始分析，当分析器遇到同样的非终端是，就很难确定在哪儿停止，它就会进入到无限循环。

例子:

(1) A => Aα | β

(2) S => Aα | β 
      A => Sd

(1)是直接左递归，(2)是间接左递归。


image

一个顺序分析器首先分析A，将会存入一系列A，分析器无限循环。

去除左递归

去除左递归的一种技术：

产生式

A => Aα | β

被转换成以下产生式

A => βA’
A => αA’ | ε

这不会影响到文法产生的字符串，但他消除了左递归。

第二个方法是用以下算法，它可以消除所有的直接或间接的左递归。

Algorithm
START
Arrange non-terminals in some order like A1, A2, A3,…, An
for each i from 1 to n
{
for each j from 1 to i-1
    {
    replace each production of form Ai⟹Aj𝜸
    with Ai ⟹ δ1𝜸  | δ2𝜸 | δ3𝜸 |…| 𝜸 
    where Aj ⟹ δ1 | δ2|…| δn  are current Aj productions
}
    }
    eliminate immediate left-recursion
END

例子

产生式

S => Aα | β 
A => Sd

应用以上算法后

S => Aα | β 
A => Aαd | βd

然后，用第一项技术去除直接左递归

A => βdA’
A => αdA’ | ε

现在产生式已经消除掉直接或间接左递归了。

提取左因子

如果多个产生式都有一个共同的前缀字符串，那么顺序分析器就不能决定哪个产生式应该被使用。

例子

如果顺序分析器遇到这样的产生式

A  ⟹ αβ | α𝜸 | …

那么它不能决定遵守哪个产生式，因为两个产生式都从同样的终端（或者非终端）开始。要去除掉这种混淆，我们使用一种技术叫提取左因子。

提取左因子将文法转换为适用于与顺序分析器。在这个技术，我们为所有共同的左因子生成一个新产生式，并附加到推导的其他过程里。

例子

上面的产生式可以写成

A => αA’
A’=> β | 𝜸 | …

现在分析器只有一个产生式来应对同样的前缀了。

先集和后集(First Sets, Follow Sets)

语法表构建的一个重要部分就是创建先集和后集。这些集合可以在推导过程中提供终端的实际位置。这个工作在按照产生式规则替换表达式 T[A, t] = a时完成，它可以用来创建分析表。

先集(First Sets)

这个集合决定了非终端替换为终端时先选取哪个符号。 比如，

α → t β

就是 a 推导出 t （终端）在第一个位置。所以，t ∈ FIRST(α)。

计算先集的算法

观察先集 FIRST(a) 的定义：

先集可以被认为是： FIRST(α) = { t | α →* t β } ∪ { ℇ | α →* ε}

后集

类似的，我们计算非终端a产生的终端符号的取值。我们不考虑非终端可以生成什么，但是我们观察非终端的产生式生成的下一个终端是什么。

计算后集的算法

后集可以认为是： FOLLOW(α) = { t | S αt}

错误恢复策略

一个分析器应该可以探测和报告程序中的任何错误。预期当遇到一个错误时，分析器应该可以处理它并且在分析后面的输入时一直保留它。绝大部分时候，分析器应该检查错误，但错误可能在编译的各个阶段出现。一个程序的不同阶段应该有以下几类错误：

有四类错误恢复策略可以在分析器中实现，用以处理代码错误。

崩溃模式

当一个分析器遇到语句中的错误时，忽略掉语句的其他部分（从错误到分隔符比如逗号）。这是错误恢复的最简单模式，并且它阻止了分析器进入无限循环。

语句模式

当分析器遇到错误，它尝试找到合适的度量，这样的话，语句的其他部分可以被分析器分析。比如，插入一个错误的分号，错误输入冒号为分号，等等。分析器设计者应该小心，因为一个错误的更正有可能导致无限循环。

错误产生式

有些常见的错误已被编译器设计者所了解。设计者创建增强的文法产生式来识别错误，可以生成错误文法。

全局更正

分析器将程序看作一个整体，判断程序的意图并且尝试找到一个最接近的没有错误的匹配，当一个错误输入语句X被装入，它创建一个最类似的正确语句Y的语法树。这个可能会允许分析器对源代码做一些修改，但是因为策略的复杂性问题（空间和时间），目前还没有在使用中实现。

抽象语法树

语法树表达，不太容易被编译器分析，因为他们包含了许多不需要的细节。下图为例：

如果仔细观察，我们发现绝大部分叶节点是它的父节点的唯一子节点。这个信息可以在装入下个周期之前消除掉。通过隐藏额外信息，我们可以获得语法树如下图：

image

抽象语法树可以表示为：

image

AST 在编译器是重要的数据结构，它包含最少不必要的信息。AST比语法树更紧凑，它很容易被编译器使用。

分析器的限制

语法分析器以标记的形式从词法分析器获取输入。词法分析器有义务确保标记的有效性。语法分析器有以下缺点：

这些目标在语义分析器中完成，我们将进行学习。

编译器设计 - 语义分析器

我们已经学习了一个语法分析器如何在语法分析周期中构建语法树。这个阶段生成的纯语法树对编译器并无用处，因为它并没有携带求值信息。上下文无关文法（CFG）产生式构建的语言规则，并不管如何解释它。

比如

E → E + T

上面的CFG产生式没有语义规则关联到它，也不能产生任何含义。

语义

语言的语义为构建（诸如标记和语法结构）提供了含义。语义帮助解释符号，类型，和它们的相互关系。语义分析判断代码中的语法结构是否能产生含义。

CFG  + 语义规则 = 语法制导翻译（Syntax Directed Definitions）

例如：

int a = “value”;

不会在词法和语法分析周期指示错误，但是会产生一个语义错误，因为赋值的类型与声明不符。这些规则在语言文法中设置，在语义分析周期检测。语义分析周期完成以下任务：

语义错误

我们已经提到语义分析器期望检测以下错误：

属性文法

属性文法是上下文无关文法的一种特殊形式，一些附加信息（属性）附加到非终端，以便于提供上下文相关的信息。每个属性都有经过良好定义的域和值，比如整数，小数，字符，字符串和表达式。

属性文法是一个中间形式，为上下文无关文法提供语义，并且它帮助指定程序语言的语法和语义。属性文法（当做语法树观察时）可以在节点之间传递值和信息。

例子:

E → E + T { E.value = E.value + T.value }

CFG的右侧包含了语义规则，指定语法如何被解释。在此，非终端E和T的值被加到一起，结果拷贝为E的值。

语义属性可能在赋值或条件，传递或求值时被赋值。基于属性获取值的方式，大概分为两类：综合属性 和 继承属性。

综合属性(Synthesized attributes)

这些属性从它们的子节点获取值。要证明它，假设一下产生式：

S → ABC

如果S从它的子节点（A，B，C）取值，那么它被认为是一个综合属性，因为ABC的值被综合到了S。

如同前例( E → E + T)，父节点E 从它的子节点获取值。综合属性绝不会从它的父节点或者旁节点获取值。

继承属性(Inherited attributes)

与综合属性不同，继承属性可以从父节点或旁节点取值。如下产生式：

S → ABC

A可以从S，B和C取值，B可以从S，A，C取值。C可以从S，A，B取值。

展开： 当一个非终端逐个展开为终端时：

image

规约：当一个终端按照文法规约到它相应的非终端时。语法树被顺序分析，从左到右。不管规约是否产生，我们对其应用相应的语义规则（actions)。

语义分析使用语法制导翻译 （Syntax Directed Translations ）来完成以上目标。

语义分析器从前一个阶段(语法分析)收到AST(抽象语法树).

语义分析器将属性信息附加到语法树，名为属性语法树。

属性，是两个元组值，<属性名，属性值>

比如：

int value = 5;
<type, “integer”>
<presentvalue, “5”>

对每个产生式，我们附加一个语义规则。

S-属性SDT（语法制导翻译）

如果一个SDT只有综合属性，它就叫S-属性SDT。这些属性用S-属性SDT求值，语义动作写在产生式右侧。

如上图描绘，S-属性SDT在逆序分析中求值，因为父节点的值取决于子节点的值。

L-属性SDT

这个形式的SDT使用两种属性（综合和继承），但是限制不能从右侧节点取值。

在L-属性SDT中，一个非终端可以从父节点，子节点和旁节点取值，如以下产生式：

S → ABC

S可以从A，B，C取值（综合），A可以从S取值。B可以从S和A取值。C可以从S，A，B取值。非终端不能从右侧取值。

L-属性SDT属性值进行深度求值和左右求值。

我们可以结论，如果一个定义是S-属性，那它也是L-属性，因为L-属性定义包含了S-属性定义。

编译器设计 - 分析器

在前面的章节，我们理解了分析器的基本概念。这一章我们将学习构建分析器的各种不同的方法。

分析器可以定义为顺序分析或者逆序分析。

顺序分析

我们上一章学习了顺序分析技术分析输入，并且从根节点开始向叶节点移动构建一个语法树。顺序分析描绘如下：

递归下降分析

递归下降是顺序分析的一种技术，它从顶部开始构建语法树，输入从左到右读取。它对每个终端或者非终端实体使用过程。这种分析技术递归分析输入来产生语法树，回溯是其中的可能性。但是文法关联（如果没有提取左因子）不能回避回溯。不需要任何回溯的递归下降分析名为预测分析。

这种分析技术视为递归，因为它使用的上下文无关文法就是自然递归的。

回溯

顺序分析器从根节点（开始符号）开始，按照产生式规则匹配输入字符串并且逐一替换（如果匹配的话）。要理解它的话，参考下面的例子：

S → rXd | rZd
X → oa | ea
Z → ai

对一个输入字符串：read， 顺序分析器进行如下行为：

它从产生式中的开始符S开始，匹配最左侧的字母r，正好S产生式(S → rXd)匹配它。所以顺序分析器前进到下个输入字母e。分析器尝试展开非终端X，并且检查它的产生式，从左边开始(X → oa)。它不会匹配下个符号。所以顺序分析器回溯并且获取X的下个产生式规则，(X → ea)。

现在分析器在有序的行为里匹配到了所有的输入字符。字符串被接受。

预测型分析器

预测分析器是一个递归下降分析器，有能力预测使用哪个产生式来替换输入字符串。预测分析器不用进行回溯。

要完成这项任务，预测分析器使用一个前视指针，指向下一个输入符号。要让分析器免于回溯，预测分析器对文法会进行一些限制，并且只接受一类叫做LL的文法。

预测分析器使用一个栈结构和分析表来分析输入，并且生成一个语法树。栈和输入都包含一个$符号来表示栈是空的，或者输入已经消费。分析器引用分析表来决定输入和栈元素的合并。

在递归下降分析中，分析器对于一个输入单例会有多于一个的产生式进行选择，而在预测分析器，每一步最多只有一个产生式。也存在没有产生式匹配的可能性，这会导致分析过程失败。

LL分析器

一个LL分析器接受LL文法。LL文法是一个上下文无关文法的子集，它带有一些限制来获取简化，达到一个相对容易的实现。LL文法可以被递归下降或者表驱动算法等价地实现。

LL分析器标示为LL(k)。第一个L表示从左到右，第二个L表示左推导。k表示前视数。通常 k = 1， 所以LL(k) 通常写成LL(1)。

LL分析算法

我们进入确定性LL(1)来解释分析器，因为表的大小随着k的值指数递增。第二，如果一个给定的文法不是LL(1)，那通常他也不是任何LL(k)。

以下是LL(1)分析的算法：

Input: 
string ω 
parsing table M for grammar G
Output:
   If ω is in L(G) then left-most derivation of ω,
   error otherwise.

Initial State : $S on stack (with S being start symbol)
   ω$ in the input buffer

SET ip to point the first symbol of ω$.
repeat
let X be the top stack symbol and a the symbol pointed by ip.
if X∈ Vt or $
if X = a
   POP X and advance ip.
    else
   error()
    endif
else    /* X is non-terminal */
   if M[X,a] = X → Y1, Y2,... Yk    
POP X
PUSH Yk, Yk-1,... Y1 /* Y1 on top */
   Output the production X → Y1, Y2,... Yk 
   else
   error()
   endif
    endif
until X = $ /* empty stack */

一个文法G是LL(1)，如果A-> alpha | b 是G的两个不同的产生式。

逆序分析

逆序分析从叶节点开始分析，一直上升到达根节点为止。在这里，我们从一个语句开始，然后以相反的方式应用产生式规则，以到达开始符号。下图描绘了可用的逆序分析器。

image

规约分析

规约分析使用两个独特的步骤。这些步骤名为移去步骤和规约步骤。

LR分析器

LR分析器是一个非递归的，移去规约的，逆序分析器。它使用一集上下文无关文法，使其成为最有效的语法分析技术。LR分析器也命名为LR(k)分析器，L意思是从左到右扫描，R意思是从右到左构建，k表示前视的数量。

有三个广泛使用的算法，用于构建LR分析器：

LR分析算法

我们描述一个LR扫描器的算法骨架：

token = next_token()
repeat forever
   s = top of stack
   if action[s, token] = “shift si” then
       PUSH token
       PUSH si 
       token = next_token()
   else if action[s, token] = “reduce A::= β“ then 
       POP 2 * |β| symbols
       s = top of stack
       PUSH A
   PUSH goto[s,A]
   else if action[s, token] = “accept” then
    return
   else
        error()

LL vs. LR

LL LR
最左推导 最右推导
从栈里的根节点非终端开始 以栈的根节点非终端为结束
结束后栈是空的 以一个空栈开始
用栈来指定还需要的元素 栈存放已经看到的元素
顺序构建语法树 逆序构建语法树
栈连续弹出非终端，压入相应的右侧 尝试识别右侧，弹出，并压入非终端
展开非终端 规约非终端
读取栈中弹出的终端 读取压入栈中的终端
前序通过语法树 逆序通过语法树

编译器设计 - 运行时环境

一个程序源代码仅仅是一集文字（代码，语句等），要让他运行起来，就需要目标机器上可以执行的动作。一个程序需要内存资源来执行指令。一个程序包含过程名，标识符等，需要在运行时映射到实际内存位置。

在运行时，指的是执行中的程序。运行时环境是一集目标机器的状态，包括软件库，环境变量，等等，为系统中运行的进程提供服务。

运行时支持系统是一个包，大部分是执行程序自己生成，并促进进程间通讯，介于进程和运行时环境。它在程序运行时负责内存申请和释放。

活动树

一个程序是一序列的指令，绑定了一些过程。过程的指令按顺序执行。一个过程有一个开始和结束分隔符，之内的所有东西就叫这个过程的体。过程标识符和在其内的有限指令序列构成了过程的体。

过程的执行就叫它的活动(activation)。一个活动记录包括所有调用它所需要的信息。一个活动记录可能包含以下单元(取决于使用的语言)。

暂存 存储表达式暂时值和中间值
本地数据 存储过程体的内部数据
机器状态 存储机器状态，如寄存器，程序计数器等等
控制连接 存储调用程序的活动记录地址
存取连接 存储本地作用域之外的数据
实参 存储实际参数，也就是说，实际送入调用过程的参数
返回值 存储返回值

不管一个过程是否执行，它的活动记录都存在栈中，又名控制栈。当一个过程体调用另一个时，调用者的执行被挂起，直到被调用者完成执行。这个时候，被调用者的活动记录存储在栈中。

我们假设程序控制以一个序列的方式流动，当一个过程被调用，它的控制转换到被调用过程。当一个被调用过程执行完成时，它返回控制给调用者。这种控制流使得表达一系列活动树形式变得容易，名为活动树。

要理解这个概念，我们用一些代码作为例子：

. . .
printf(“Enter Your Name: “);
scanf(“%s”, username);
show_data(username);
printf(“Press any key to continue…”);
. . .
int show_data(char *user)
   {
   printf(“Your name is %s”, username);
   return 0;
   }
. . .

以下是代码的活动树。

现在我们理解了过程体是以深度优先的方式执行，因此栈申请是过程活动最好的存储方式。

存储申请

运行时环境管理运行时内存，需要以下实体：

静态申请

在这个申请计划里，编译数据绑定到内存中的一个固定位置并且它在程序执行时不会改变。内存需求和存储位置是确定的，因此不需要内存申请和释放的运行时支持。

栈申请

过程调用和活动由栈空间申请来管理。它是后进先出（LIFO）的，它的申请策略非常适合递归过程调用。

堆申请

过程的本地变量仅仅在运行时申请和释放。堆申请用于动态申请内存到变量，在变量不再被需要时，也负责回收它。

除了静态申请内存区域，栈和堆内存可以动态和不可预期地增长和收缩。因此，它们不能在系统内固定的提供一个空间来满足。

如上图所示，代码的文字部分申请了一个固定空间。栈和堆排列在程序内存空间的两端。收缩和增长都相向而行。

参数传递

过程体的通讯媒介就名为参数传递。调用过程的变量值以某种机制传递到被调用程序。在继续之前，先了解下程序中存在的传值技术。

r-值 （右值）

表达式的值叫它的r-值。一个单变量包含的值同样是r-值，如果它在赋值操作符的右侧。r-值总是可以赋值给其他变量。

l-值 （左值）

表达式被存储在的内存位置就叫它的左值。它总是出现在赋值操作符的左边。

比如：

day = 1;
week = day * 7;
month = 1;
year = month * 12;

从这个例子，我们理解了常量值比如1，7，12，和变量值如 day, week, month 和 year, 都有r-值。只有变量有左值，因为它们也表达为他们申请到的内存空间。

比如：

7 = x + y;

是一个左值错误，因为常量7不能表达任何内存空间。

形式参数

变量，保存调用者过程传递信息的，就叫形式参数。这些变量在被调用者程序中声明。

实际参数

变量的值或地址，被传递到被调用过程的，就叫实际参数。这些变量由调用者在参数中指定。

例子：

fun_one()
{
   int actual_parameter = 10;
   call fun_two(int actual_parameter);
}
   fun_two(int formal_parameter)
{
   print formal_parameter;
}

形参保存实参的方式取决于使用的参数传递技术。可以是值或地址。

传值

在传值机制，调用过程传递右值（实参），编译器将它放入被调用过程的活动记录。形式参数获取到调用过程传递的值。如果形参获取的值发生变化，将不会影响到实际参数。

传引用

在引用机制，实际参数的左值被拷贝到被调用程序的活动记录。这种方式下，被调用过程拥有实参的内存位置，形参引用到同样的内存位置。因此，如果形参的值改变，实参也会因此改变。

传复制重写

这个参数传递机制有点像传引用机制，除了它的实参是在被调用过程结束时改变。在函数调用中，实参的值在被调用过程的活动记录中被拷贝。形式参数如果改变了，并不会在实参中产生实时影响（如同左值传递），但是当被调用过程结束，形参的左值就被拷贝到实参的左值中。

例子：

int y; 
calling_procedure() 
{
   y = 10;     
   copy_restore(y); //l-value of y is passed
   printf y; //prints 99 
}
copy_restore(int x) 
{     
   x = 99; // y still has value 10 (unaffected)
   y = 0; // y is now 0 
}

当函数结束，形参x的左值被拷贝到实际参数y。即使y的值在过程结束前改变了，x的左值也被拷贝到y的左值，以使他行为跟y一样。

传名

像Algol那样的语言提供了一种新的参数传递机制，就像c语言的预处理器一样。在传名机制中，被调用的过程名被更换为它的体。传名机制将过程调用的参数表达式按照它在过程体中的参数进行文法替换，因此它可以像实参一样工作，很像传引用机制。

编译器设计 - 符号表

符号表是一个重要数据结构，由编译器创建和维护，目的是为了存储各个实体的信息，比如变量名，函数名，对象，类，接口等。符号表用于分析和推理过程。

一个符号表可能提供以下目的：

符号表就是一张简单的表，可以是线性的，或者哈希表。它以如下形式维护每个名字的入口。

<符号 名字,  类型,  属性>

例如，如果一个字符表必须存储下面变量声明的信息：

static int interest;

然后它将存储条目为：

<interest, int, static>

属性语句包含了名字关联的入口。

实现

如果一个编译器要处理少量的数据，然后符号表可以被实现为一个未排序的列表，容易编码，但是只适合小表格。一个符号表可以被实现为以下形式：

在这些之中，符号表最常被实现为哈希表，源代码符号本身被看作是哈希函数的一个key，返回值就是符号的信息。

操作

一个符号表， 线性或者哈希，应该提供以下操作。

insert() 插入

这个操作最常被分析周期使用，也就是说，编译器的前半部分，标记被识别，名字被存储进到表里。这个操作用于添加信息到符号表，关于代码中出现的唯一命名。命名存储的格式或者结构取决于编译器。

源代码中一个符号的属性是符号关联的信息。这个信息包含了值，状态，作用域和类型。insert()函数取符号和属性为参数，存储信息到符号表。

例如：

int a;

应该被编译器处理为：

insert(a, int);

lookup()

lookup() 操作用于搜索一个符号表中的名字，以确定：

lookup()的格式根据语言而不同。基本格式应该匹配以下：

lookup(symbol)

这个方法返回0，如果符号不存在于符号表中。如果符号存在于符号表，它返回它在表中的属性值。

作用域管理

一个编译器维护两种符号表：一个全局符号表，可以被所有过程存取，和作用域符号表，为每个作用域创建。

要确定作用域名，符号表被安排成分层结构如下例：

. . . 
int value=10;

void pro_one()
   {
   int one_1;
   int one_2;

      {              \
      int one_3;      |_  inner scope 1 
      int one_4;      | 
      }              /
  
   int one_5; 

      {              \   
      int one_6;      |_  inner scope 2
      int one_7;      |
      }              /
   }

void pro_two()
   {
   int two_1;
   int two_2;

      {              \
      int two_3;      |_  inner scope 3
      int two_4;      |
      }              /
  
   int two_5;
   }
. . .

以上程序可以表示为分层结构符号表：

image

全局符号表包含一个全局变量(int value) 和两个过程名，可以被所有子节点所见。在pro_one符号表（以及所有子节点）内提到的名字不会被pro_two 符号和它的子表所见到。

这个符号表数据结构层级存储在语义分析器中，并且任何时候一个符号表名字需要被搜索时，它使用下面的算法进行搜索。

编译器设计 - 中间代码生成

一个源码可以直接被翻译成它的目标机器代码，为什么还需要翻译到中间代码，然后在转换成目标代码？让我们看看原因。

image

中间表达

中间码可以表达为多种形式，各有优点。

中间代码可以是语言特定的（比如java字节码），也可以是语言无关的（三地址码）

三地址码

中间代码生成器从前一个处理周期，语义分析器中接收输入，以注释语法树的形式。这个语法树可以转换为线性表达，比如后缀记号。中间码尝试成为机器无关码。因此，代码生成器假设有无限个存储单元来生成代码。

比如：

a = b + c * d;

中间码生成器会尝试将表达式分割成子表达式，然后生成相应的代码。

r1 = c * d;
r2 = b + r1;
a = r2;

r在目标机器中用作寄存器。

一个三地址码有最多三个位置来计算表达式。一个三地址码可以表达成两种形式： 四元组和三元组。

四元组

每个四元组指令都分割成四个域：操作符，参数1，参数2，结果。以上例子在下表表达为四元组：

Op arg1 arg2 result
* c d r1
+ b r1 r2
+ r2 r1 r3
= r3 a

三元组

每个三元组指令都有三个域：op, arg1, arg2。子表达式的结果标注在表达式的位置。三元组表达DAG和语法树的类似性。在表达式中，它们等价于DAG。（有向无环图）

Op arg1 arg2
* c d
+ b (0)
+ (1) (0)
= (2)

间接三元组

这种表达式三元组的增强表达。它使用指针来替代位置。这个允许优化器自由重定位子表达式来产生优化代码。

声明

一个变量或者过程需要在使用前进行声明。声明包含了符号的内存申请空间和入口类型和符号表名字。一个程序可以在脑中编码和设计为目标机器结构，但是不能总是可能精确转换源码到目标语言。

将整个程序作为一集过程和子过程，就容易在过程中进行声明。内存申请连续完成，并且名字申请到内存，按照它们在程序中声明的方式。我们使用偏移变量，并将其设置为0{offset=0}，标示了基地址，下一个声明的名字，会申请相邻的内存地址。

例子：

我们取c语言程序作为例子，整数变量值赋值为两个字节的内存空间，浮点数为四个字节。

int a;
float b;
Allocation process:
{offset = 0}
int a;
id.type = int
id.width = 2
offset = offset + id.width 
{offset = 2}
float b;
   id.type = float
   id.width = 4
   offset = offset + id.width 
{offset = 6}

要进入到符号表的细节，一个过程入口可以被使用。这个方法应该是以下结构：

enter(name, type, offset)

这个过程会创建一个符号表入口，对于变量名，有它的类型和相对地址偏移。

编译器设计 - 代码生成

代码生成可以看作是编译的最后一个周期。通过代码生成后，优化进程可以应用到代码上，但它们可以看作是代码生成周期的一部分。编译器生成的代码是一个对象object,由低阶程序语言组成，例如汇编语言。我们可以看到高阶语言写成的源代码已经转换成低阶对象中的低阶语言，应当有以下属性：

我们将会看到中间代码是如何转换成目标对象代码（此处指汇编码）。

有向非循环图

有向无环图（DAG）是一种描绘基本块的工具，可以看到值在基本块之间的流动，并且提供了优化。DAG提供了块的简单转换。DAG可以理解如下：

例子：

t0 = a + b
t1 = t0 + c
d = t0 + t1
[t0 = a + b] [t1 = t 0 + c] [d = t0 + t1]
image image image

窥视优化

优化技术在源代码本地运作，将其转换成优化版本。本地指的是一部分代码块。这些方法可以运用到中间码或者目标码。语句被分析检查，看是否可以应用以下优化。

冗余指令消除

在源代码级别，以下工作可以被用户完成。

1

int add_ten(int x)
   {
   int y, z;
   y = 10;
   z = x + y;
   return z;
   }

2

int add_ten(int x)
   {
   int y;
   y = 10;
   y = x + y;
   return y;
   }

3

int add_ten(int x)
   {
   int y = 10;
   return x + y;
   }

4

int add_ten(int x)
   {
   return x + 10;
   }

在编译级别，编译器搜索指令冗余。多种加载和存储指令会携带同样的信息，即使它们被去除掉了。比如：

MOV x, R0
MOV R0, R1

我们可以删除掉第一个指令并且重写句子为：

MOV x, R1

不执行的代码

不执行代码是程序代码中永远不会到达的那些代码，由程序结构导致的。程序员不小心写的。

例子：

void add_ten(int x)
{
   return x + 10;
   printf(“value of x is %d”, x);
}

在这个代码片段， printf 永远不会执行，因为程序控制已经返回了，这样 printf 可以被移除。

控制流优化

代码中有一种实例，就是程序跳转往返，并不执行任何任务。这种空跳转可以移除。考虑下面的代码：

...     
MOV R1, R2
GOTO L1
...
L1 :   GOTO L2
L2 :   INC R1

代数表达式简化

有一些数学表达式可以化简。比如 a = a + 0 可以替换为 a ，a = a + 1 可以替换为 INC a。

强度规约

有那种消耗多空间和时间的操作。 它们的“强度” 可以规约，通过替换为其他消耗量小的等价操作。

比如， x * 2 可以更换为 x << 1，这样就只有一个左移操作。另外 a * a 和a2虽然概念上等价，但a2效率在实现上要高很多。

存取机器码

目标机器可能部署更精巧的指令，可以更有效实现特定的操作。如果目标语言可以直接模拟这些指令，那就不仅提高了代码质量，而且也能暂存更多的值。

代码生成器

代码生成器需要理解目标机器运行时环境和指令集。代码生成应该将以下问题纳入考虑：

描述符

代码生成器生成代码时应该追踪寄存器和地址。以下两个描述符应该被使用：

代码生成器实时保存两种描述符。当加载一个语句LD R1，x，代码生成器：

代码生成

基本块包含一序列三地址码。代码生成器将这些指令序列作为输入。

注意： 如果名字的值在多于一个地方出现（寄存器，缓存，或者内存），寄存器的值将会优先选择缓存或者内存。缓存优先于内存。内存基本是最低优先级。

getReg: 代码生成器使用getReg函数来决定可用寄存器和名字值的位置。 getReg工作如下：

对于指令 x = y OP z, 代码生成器可能执行以下动作。让我们假设L是选中寄存器的位置，y OP z的输出将存于此：

MOV y', L

y'表示y的拷贝值。

OP z', L

z'表示z的拷贝值。

其他代码构建诸如循环和条件语句，被转换到汇编语言，通过通常的汇编方式。

编译器设计 - 代码优化

代码优化是一种程序转换技术，尝试提高代码效率，消耗更少资源，带来更高速度。

在优化中，高阶通用语言被替换为高效的低阶程序码。一个代码优化过程必须遵循以下三个规则：

优化代码的工作可以从编译中不同的级别开展。

优化大致列为以下两类： 机器相关和机器无关的。

机器无关优化

在这个优化过程，编译器输入中间码，转换不包含任何CPU寄存器和绝对内存地址那部分代码。比如：

do 
{
    item = 10;
    value = value + item;
} while(value<100);

这个代码包含重复声明，可以这样修改。

Item = 10;
do
{
   value = value + item; 
} while(value<100);

不仅可以节省CPU流程，也可以用在任何其他处理器。

机器相关优化

机器相关的优化是在目标码生成和代码转换到机器码以后。它包含了CPU寄存器，和绝对内存地址引用。机器相关的优化器努力将内存继承发挥到最大效果。

基本块

源代码通常有一些指令，总是按顺序执行，这样可以将它们看作代码块。基本块没有任何跳转语句，也就是说，第一条指令执行时，所有同一块都按照顺序执行，不会失控。

一个程序可以用基本块进行多种构建，比如IF-THEN-ELSE，SWITCH-CASE条件语句和循环比如DO-WHILE，FOR，和REPEAT-UNTIL，等。

基本块定义

我们可以用以下算法来找到程序里的基本块：

基本块是代码生成和优化的重要概念。

基本块在标示那种多个块使用的变量时，扮演重要角色。如果一个变量使用超过一次，变量申请到的寄存器不能为空，直到块完成执行为止。

控制流图

程序中的基本块可以表示为控制流图。一个控制流图描绘了程序控制是如何在块间传递的。它是一个有用的工具，帮助优化定位不需要的循环。

image

循环优化

很多程序都以循环的形式在系统运行。所以有必要优化循环来节省CPU和内存。循环可以被以下技术优化：

死代码消除

死代码是以下代码语句：

因此，死代码不扮演任何角色，所以可以被消除。

部分死代码

有一些代码语句的计算值只用到了一定的情况，也就是说值只在一部分时候被使用，这种代码叫部分死代码。

image

以上控制流图描绘了一个程序 变量a被使用和赋值给表达式 'x * y'。让我们假设赋给a的值从未在循环中使用。然后控制流离开循环，a便赋值给了z的值。我们在此结论，a的赋值从不在任何其他任何地方使用，因此它可以被消除。

image

类似的，上图描绘的控制流语句结果总是false，隐含这样的含义，true分支永远不会执行，所以可以被消除。

部分冗余（偏冗余）

冗余表达式指的是在平行路径被重复计算的表达式，没有任何改变。偏冗余表达式指的是在同一路径重复计算的表达式。比如

冗余表达式 偏冗余表达式
image image

循环不变代码是偏冗余的，可以用移动代码技术消除。

另一个偏冗余代码例子是：

If (condition)
{
   a = y OP z;
}
else
{
   ...
}
c = y OP z;

我们假设操作数的值(y和z)在赋值给a和c时不变。这里，如果条件语句结果为真，那么 y OP z 会被计算两次，否则就是一次。代码移动可以用于消除这种冗余，如下：

If (condition)
{
   ...
   tmp = y OP z;
   a = tmp;
   ...
}
else
{
   ...
   tmp = y OP z;
}
c = tmp;

这里，不管条件是否为真，y OP z 都只计算一次。

上一篇下一篇

猜你喜欢

热点阅读