编译器设计-有限自动机

Compiler Design - Finite Automata

有限自动机是一种状态机，它以一串符号作为输入，并相应地改变其状态。有限自动机是正则表达式的识别器。当正则表达式字符串被输入到有限自动机中时，它会为每个文本更改其状态。如果输入字符串成功处理并且自动机达到其最终状态，则接受它，即刚刚输入的字符串被认为是当前语言的有效标记。

有限自动机的数学模型包括：

Finite
set of states (Q)
Finite
set of input symbols (Σ)
One
Start state (q0)
Set
of final states (qf)
Transition
function (δ)

设L（r）是有限自动机（FA）识别的正则语言。

状态States：FA的状态用圆圈表示。状态名写在圆圈里。

开始状态Start state：自动机开始的状态，称为开始状态。开始状态有一个箭头指向它。

中间状态Intermediate states ：所有中间状态至少有两个箭头；一个指向外，另一个指向内（自己）。

最终状态Final state：如果成功解析输入字符串，则自动机应处于此状态。最终状态用双圆表示。它可能有任意奇数个指向它的箭头和偶数个指向它的箭头。奇数箭头的数目比偶数大一个，即奇数=偶数+1。

转换Transition：当在输入中找到所需的符号时，从一个状态转换到另一个状态。在转换时，自动机可以移动到下一个状态，也可以保持在相同的状态。从一个状态到另一个状态的移动显示为定向箭头，箭头指向目标状态。如果自动机保持在相同的状态，则会绘制一个从状态指向自身的箭头。

Example : We assume FA accepts any three digit binary value
ending in digit 1. FA = {Q(q0, qf), Σ(0,1), q0, qf, δ}

语法分析或分析是编译器的第二个阶段。在本章中，我们将学习构造解析器时使用的基本概念。

我们已经看到，词法分析器可以借助正则表达式和模式规则来识别标记。但是由于正则表达式的限制，词法分析器无法检查给定句子的语法。正则表达式无法检查平衡标记，如括号。因此，这个阶段使用上下文无关语法（CFG），这是由下推自动机识别的。

另一方面，CFG是正则语法的超集，如下所示：

这意味着每一种规则语法都是上下文无关的，但也存在一些超出规则语法范围的问题。CFG是描述编程语言语法的有用工具。

上下文无关语法Context-Free Grammar

在本节中，我们将首先看到上下文无关语法的定义，并介绍用于解析技术的术语。
上下文无关语法有四个组成部分：

一组非终端（V）。非终结符是表示字符串集的语法变量。非终端定义字符串集，帮助定义由语法生成的语言。

一组标记，称为终端符号（∑）。终端是构成字符串的基本符号。

一组产品（P）。语法的产生指定了终端和非终端可以组合成字符串的方式。每个产品都由一个称为产品左侧的非终端、一个箭头和一系列令牌和/或终端（称为产品右侧）组成。
其中一个非终端被指定为开始符号；从那里开始生产。

字符串是从开始符号派生的，方法是重复地将非终端（最初是开始符号）替换为生产的右侧（对于该非终端）。

例子

我们讨论回文语言的问题，它不能用正则表达式来描述。也就是说，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等。

语法分析器syntax analyzer

语法分析器或解析器以令牌流的形式接受词法分析器的输入。解析器根据生产规则分析源代码（令牌流），以检测代码中的任何错误。这个阶段的输出是一个解析树。

这样，解析器完成两个任务，即解析代码、查找错误和生成解析树作为阶段的输出。
即使程序中存在错误，解析器也需要解析整个代码。解析器使用错误恢复策略，我们将在本章后面学习。

派生Derivation

派生基本上是一系列产生式规则，以便获取输入字符串。在解析过程中，我们对某些句子形式的输入做出两个决定：

决定要更换的非终端。

决定生产规则，用它来代替非终端。

要决定用生产规则替换哪个非终端，我们可以有两个选择。

最左端派生 Left-most Derivation

如果从左到右扫描并替换输入的句子形式，则称之为最左派生。由最左边派生出来的句子式叫做左边的句子形式。

最右派生

如果我们Right-most Derivation

从右到左扫描并用产生式规则替换输入，则称为最右派生。从最右边派生出来的句子形式叫做右边的句子形式。

例子

生产规则

E → E + EE → E * EE → id

Input string: id + id * id

The left-most derivation is:

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

请注意，最左边的非终端总是先处理。

最正确的推导是：

E → E + EE → E + E * EE → E + E * idE → E + id * idE → id + id * id

Parse Tree

请注意，最左边的非终端总是先处理。

解析树

解析树是派生的图形描述。可以方便地看到字符串是如何从开始符号派生的。派生的开始符号将成为解析树的根。让我们从上一个主题的一个例子来看这个问题。

我们取a+b*c的最左边的导出

最左边的推导是：

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




在解析树中

All
leaf nodes are terminals.
All
interior nodes are non-terminals.
In-order
traversal gives original input string.

所有叶节点都是终端。

所有内部节点都不是终端。

按顺序遍历给出原始输入字符串。

按顺序遍历给出原始输入字符串。解析树描述运算符的关联性和优先级。最深的子树首先遍历，因此该子树中的运算符优先于父节点中的运算符。

模棱两可

如果语法G对于至少一个字符串有多个解析树（左派生或右派生），则称它是不明确的。

Example

E → E + EE → E – EE → id

对于字符串id+id–id，上面的语法生成两个解析树：

由歧义语法生成的语言被称为天生的歧义。语法中的歧义不利于编译器构造。没有一种方法能够自动检测和消除歧义，但是可以通过重新编写整个语法而不产生歧义，或者通过设置和遵循关联性和优先约束来消除歧义。

关联性Associativity

如果一个操作数的两边都有运算符，则运算符接受此操作数的那一边由这些运算符的关联性决定。如果操作是左关联的，则操作数将由左运算符执行；如果操作是右关联的，则右运算符将执行操作数。

例子

加法、乘法、减法和除法等运算是左关联的。如果表达式包含：

id op id op id

it will be evaluated as:

(id op id) op id

例如，（id+id）+id

指数运算之类的运算是右关联的，即同一表达式中的求值顺序为：

id op (id op id)

For example, id ^ (id ^ id)

优先Presedence

如果两个不同的运算符共享同一个操作数，则由运算符的优先级决定哪个将成为该操作数。也就是说，2+34可以有两个不同的解析树，一个对应于（2+3）4，另一个对应于2+（34）。通过设置运算符之间的优先级，可以很容易地解决此问题。如上例所示，数学上（乘法）优先于+（加法），因此表达式2+3*4将始终解释为：

2 + (3 * 4)

这些方法减少了语言或语法中的歧义。

左递归 Left Recursion

如果语法有任何非终端“A”，其派生包含“A”本身作为最左边的符号，则语法将变为左递归。对于自顶向下的解析器来说，左递归语法被认为是一个有问题的情况。自上而下的解析器从开始符号开始解析，开始符号本身是非终端的。因此，当解析器在派生过程中遇到同一个非终端时，就很难判断何时停止解析左边的非终端，从而进入无限循环。

Example:

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

（1） 是立即左递归的一个例子，其中A是任何非终端符号，α表示一个非终端字符串。
（2） 是间接左递归的一个例子。

自上而下的解析器将首先解析A，然后A将产生一个由A本身组成的字符串，解析器可能永远进入一个循环。

删除左递归

删除左递归的一种方法是使用以下技术：

生产

A => Aα | β

is converted into following productions

A => βA’A’=> αA’ | ε这不会影响从语法派生的字符串，但会删除立即左递归。
第二种方法是使用下面的算法，它应该消除所有直接和间接的左递归。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
}
} e
liminate immediate left-recursion
END

Example

The production set

S => Aα | β A => Sd

after applying the above algorithm, should become

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

and then, remove immediate left recursion using the first technique.

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

Now none of the production has either direct or indirect left recursion.

左因子分解 Left Factoring
如果多个语法生成规则具有公共前缀字符串，则自上而下的解析器无法选择应使用哪个生成来解析手头的字符串。
例子
如果自顶向下的解析器遇到A ⟹ αβ | α𝜸 | …然后，由于两个产品都从同一个终端（或非终端）开始，它无法确定要遵循哪个产品来分析字符串。为了消除这种混乱，我们使用了一种称为左因子分解的技术。
左阶乘转换语法，使其对自顶向下的解析器有用。在这种技术中，我们为每个公共前缀生成一个结果，其余的派生结果由新的结果添加。
例子
以上作品可以写成A => αA’A’=> β | 𝜸 | … 现在解析器每个前缀只有一个产品，这使得决策更容易。
第一组和第二组
解析器表构造的一个重要部分是创建第一个集合和后续集合。这些集合可以提供派生中任何终端的实际位置。这样做是为了创建解析表，其中用一些产生式规则替换T[A，T]=α的决定。
第一组
创建此集合是为了知道非终端在第一个位置派生的终端符号。例如，α → t β即α在第一个位置导出t（终端）。所以，t∈第一（α）。
计算第一组的算法
看第一（α）组的定义：
如果α是终端，那么首先（α）={α}。
如果α是非终端且α→ℇ是产物，则首先（α）={ℇ}。
如果α是非终端且α→𝜸1𝜸2𝜸3…𝜸n且任何第一个（𝜸）包含t，则t在第一个（α）中。
第一组可以看作：

跟随集合Follow Set
同样地，我们计算在产生式规则中，哪个终端符号紧跟非终端α。我们不考虑非终端可以生成什么，而是看到在非终端生成之后的下一个终端符号是什么。
计算跟随集的算法：
如果α是开始符号，则FOLLOW（）=$
如果α是非终端且具有产物α→a B，则除ℇ外，先（B）在后（a）中。
如果α是非终端的，并且具有产生α→a B，其中Bℇ，则FOLLOW（a）在FOLLOW（α）中。
Follow集可以看作：Follow（α）={t | Sαt}语法分析器的局限性Limitations of Syntax Analyzers
语法分析器以标记的形式从词汇分析器接收它们的输入。词法分析器负责语法分析器提供的令牌的有效性。语法分析器有以下缺点-
它无法确定令牌是否有效，
它无法确定令牌在使用前是否已声明，
它无法确定令牌在使用前是否已初始化，
它无法确定对令牌类型执行的操作是否有效。
这些任务是由语义分析器完成的，我们将在语义分析中对其进行研究。