编译原理-词法分析

发表于 更新于 分类于 阅读次数： Changyan： 本文字数： 6.3k 阅读时长 ≈ 10 分钟

编译原理-词法分析

编译器模型：

graph LR
源代码-->|词法分析器|词法单元
词法单元-->|语法分析器|语法分析树
语法分析树-->|中间代码生成器|中间代码
中间代码-->|代码优化,机器无关|中间代码
中间代码-->|代码生成器|目标代码
目标代码-->|机器相关代码优化|机器码
机器码-->output((机器码执行))

词法分析是编译的第一阶段，将构成源程序的字符流处理成词法单元组成的词符流。此外，它还会完成一些工作:

  • 过滤掉源程序中的注释和空白。
  • 将编译器生成的错误信息与源程序位置关联起来。

关于词法分析，有3个术语:

  • 词法单元: 词法单元由一个词法单元名和一个可选属性组成。词法单元名是一个表示某种词法单元的抽象符号，例如一个特定的关键字，或者一个代表标识符的输入字符序列。
  • 词素: 词素是源程序的一个字符序列，和某个词法单元的模式匹配。
  • 模式: 模式描述了一个词法单元的词素可能具有的形式。当词法单元是是一个关键字时，它的模式就是组成这个关键字的字符序列，对于标识符和其它词法单元，模式是一个更复杂的结构。

词法分析做的事就是：通过模式识别匹配词素，从而生成词法单元

下面是一些常见例子:

词法单元 非正式描述 词素示例
if 字符i,f if
comparison <或>或<=或>=或==或!= <=,!=
id 字母开头的字母或数字串 pi,score,a1
number 任何数字常量 0,2.435
literal 在两个"之间，除"以外的任何字符 “String”

如果有多个词素可以和一个模式匹配，那么词法分析器必须提供额外信息用于后续阶段的区分。例如，0和1都可以匹配数字常量。因此，对于某些词法单元，词法分析器还会返回其属性。例如:

1
2
3
4
5
6
# 对于表达式 a=b*2 ,下面的 id 和 number 均带有其属性值
<id,a>
<assign_op>
<id,b>
<mult_op>
<number,2>

词法分析仅是用于处理字符到词法单元的转换，本身很难发现源代码中的错误。例如:

1
fi(a==f(x))...

在上面的代码片段中，在遇到 fi 时，无法指出 fi 究竟是关键字 if 的误写还是一个标识符 id，具体的错误会在稍后的语法分析中发现和处理。

假设出现所有词法单元的模式都无法和剩余输入的某个前缀相匹配，此时，词法分析器无法继续处理，在这种情况下，可以进行错误恢复。常见的恢复策略有:

  • 从剩余输入中删除一个字符;
  • 向剩余输入中插入一个遗漏字符;
  • 用一个字符来替换另一个字符;
  • 交换两个相邻字符;

显然词法分析的重点在于模式和词素的匹配，从而生成不同 Class 的词法单元。正则表达式是一种用来描述词素模式的重要表示方法。

关于这方面介绍几个术语的定义:

  • 字母表是一个有限的符号集合。符号的典型例子包括字母，数位和标点符号。${0,1}$是二进制字母表;ASCII是字母表的一个重要例子;同样 Unicode 也是字母表的一个重要例子。
  • 字母表上的串是该字母表中符号的一个有穷序列。串 s 的长度通常记作$\vert{s}\vert$，指串中符号的个数。空串使用$\epsilon$表示。
  • 语言是某个给定字母表上的任意可数个的串的集合。$\varnothing$表示空集。
运算 定义
语言L和语言M的连接 $LM={st\vert{s属于 L 且 t 属于 M}}$
语言L和语言M的并 $L\cup{M}={s\vert{s属于L或者s属于M}}$
语言L的幂 $L^{i}$,一个原因 L连接 i 次后得到的集合,$L^{0}={\epsilon}$
语言L的闭包 $L^{*}=\cup^{\infty}_{i=0}L^{i}$
语言L正闭包 $L^{+}=\cup^{\infty}_{i=1}L^{i}$

下面使用上面的定义来描述某个字母表$\Sigma$上的正则表达式。下面是两个基础的规则:

  • 首先，$\epsilon$是一个正则表达式，$L(\epsilon)={\epsilon}$,即该语言只包含空串。
  • 如果 a 是$\Sigma$上的一个符号，那么a是一个正则表达式，并且$L(a)={a}$。也就是说这个语言仅包含长度为1的符号串a。

下面是由小的正则表达式构造较大的正则表达式的步骤。假设 r 和 s 都是正则表达式，分别是 L(r)和 L(s),那么:

  • $(r)|(s)$ 是一个正则表达式，表示语言 $L(r) \cup L(s)$。
  • $(r)(s)$ 是一个正则表达式, 表示语言 $L(r)L(s)$
  • $(r)^{*}$ 是一个正则表达式，表示语言 $(L(r))^{*}$
  • $(r)$ 是一个正则表达式，表示语言 $L(r)$。这是说明表达式两边加上括号不会影响表达式代表的语言。

按照上面的的规定，正则表达式常会包含一些不必要的括号，如果，我们设置好运算符优先级，那么就可以丢掉一些无用的括号。通常约定的优先级如下：

  1. 一元算符$*$拥有最高优先级,并且是左结合的。
  2. 连接有次高的优先级，也是左结合的。
  3. 并$|$的优先级最低，也是左结合的。

显然，$(a)|((b)*(c))$可以被简化为 $a|b*c$。

根据上述描述，如果我们将表达同样语言的两个表达式称为等价，那么我们可以推导出下面的代数规则:

定律 描述
$r{\vert}s = s{\vert}sr$ $\vert$满足交换律
$r{\vert}(s{\vert}t) = (r{\vert}s){\vert}t$ $\vert$满足结合律
$r(st) = (rs)t$ 连接满足结合律
$r(s{\vert}t)=rs{\vert}rt$ 连接对$\vert$是可分配
${\epsilon}r=r{\epsilon}=r$ $\epsilon$是连接的单位元
$r^{*}=(r\vert{\epsilon})^{*}$ 闭包中一定包含$\epsilon$
$r^{*^{*}}=r^{*}$ $r^{*}$具有幂等性

如果$\Sigma$是基本符号的集合，那么一个正则定义是具有如下形式的定义序列:

  • 每个$d_i$都是一个新符号，它们都不在$\Sigma$中，并且各不相同
  • 每个 都是字母表 和 上的正则表达式。如果把换成对应的全由组成的,这样可以被构造出只含有$\Sigma$中符号的正则表达式。

例如:

下面我们来看看如何使用正则表达式表示的模式，来实现对词法单元的识别。

状态转换图

词法分析的开始，我们需要把模式转换成状态转换图。状态转换图有一组被称为状态的结点。每个状态代表一个可能和模式匹配的词素。状态图中的边从图的一个状态指向另一个状态。每条边的标号包含了一个或多个符号。

如果我们处于某个状态 s，并且下一个输入符号是 a，那么我们就会寻找一条从 s 离开且标号为 a 的边(该边的标号中可能还包括其它符号)。如果找到这样的边，那么就进入该边所指的状态s1。如果找不到对应的边就回退，或终止。

graph LR
state((状态S))-->|转换条件:字符a|state1((转态S1))

基于状态转换图，我们可以根据状态机模式来手写出词法分析的解析代码。

有穷自动机

上面已经介绍过状态转换图的方式来解析词法单元，下面介绍下，有穷自动机，可以更通用的处理词法分析。有穷自动机本质上是和状态转换图类似的图，但是有下面几点不同:

  1. 有穷自动机是识别器,它们只会对每个输入串，简单回答”是”或”否”。
  2. 有穷自动机分为两类:
    • 确定的有穷自动机(DFA),对于每个状态及自动机输入字母表的每个符号，有且只有一条离开该状态、以该符号为标号的边。
    • 不确定的有穷自动机(NFA),对其边上的标号没有限制。一个符号可以标记离开同一状态的多个边，这些边的离开条件相同。并且${\epsilon}$串也可以作为标号。

NFA

一个不确定的有穷自动机(NFA)由下面几个部分组成:

  • 一个有穷的状态集 $s$。
  • 一个输入符号集合$\Sigma$,即输入字母表,我们假设代表空串的${\epsilon}$不是$\Sigma$中的函数。
  • 一个转换函数，它为每个状态和中的每个符号都给出了转移的后继状态的集合。
  • $s$ 中的一个状态$s_{0}$被指定为开始状态,或者说是初始状态。
  • $s$ 的一个子集F 被指定为接受状态的集合。

我们可以把NFA表示成一张转换图,图中的节点是状态，带标号的边表示自动机的转换函数。这个图和状态转换图很相似,但是:

  1. 同一个符号可以标记从同一状态出发，到达多个目标状态的多条边。
  2. 一条边的标号不仅可以是输入字母表的符号，也可以是空串${\epsilon}$。

下面是 $(a|b)^{*}ab$ 的NFA(3是结束状态):

graph LR
id(begin) -->|start|id0((0))
id0 -->|a|id0
id0 -->|b|id0
id0 -->|a|id1((1))
id1 -->|b|id2((2))
id2 -->id3(3)

上图NFA的转换表:

状态 输入a 输入b
0 {0,1} {0}
1 $\varnothing$ {2}
2 $\varnothing$ $\varnothing$

$\varnothing$ : 空集

观察从状态0到状态1的变化，在输入符号a时，可以看到a对应的跳转状态集合是 {0,1}，这是一个多状态的结果，所以称为不确定状态机。

DFA

确定有穷自动机(DFA)是不确定有穷自动机的一个特例。在 DFA中:

  • 没有输入${\epsilon}$的转换函数
  • 对每个状态s和每个输入符号a,有且只有一条标号为 a 的边离开。

下面是识别 $(a|b)^{*}ab$ 的DFA:

graph LR
id(begin) -->id0((0))
id0 -->|b|id0
id0 -->|a|id1((1))
id1 -->|a|id1
id1 -->|b|id2((2))
id2 -->|a|id1
id2 -->|b|id0
id2 -->id3((3))

正则表达式构建 NFA

Thompson构造法是一个能将正则表达式转化为一个与之等价的非确定有限状态自动机（NFA）的算法。算法通过递归地将一个正则表达式划分成构成它的子表达式，在得到每个子表达式对应的NFA之后，根据子表达式之间的运算关系和一系列规则构造表达式自身对应的NFA。

对于表达式$\epsilon$,直接转换成下面的图:

表达式ϵ

字母表中的子表达式a直接转化为：

表达式a

下面针对正则表达式的三种运算——并、连接和闭包给出NFA的构造规则。设子表达式为s和t，则它们对应的NFA分别记作$N(s)$和$N(t)$。

两个正则表达式的并$s|t$可以转化为:

or运算

通过ε转移， 状态q 可以直接到达$N(s)$或$N(t)$的初态。而$N(s)$或$N(t)$原来的终态也可以通过$\epsilon$转移直接到达整个NFA的新终态。

连接表达式st可以转化为：

连接

$N(s)$的初态成为新的NFA的初态。 原来$N(s)$的终态成为$N(t)$的初态。而原来$N(t)$的终态成为新的NFA的终态。

闭包$s^{*}$可以转化为：

幂运算

将新表达式的初态和终态以及夹在中间的子表达式的NFA $N(s)$连接起来的$\epsilon$转移使得可以选择经过或者不经过子表达式。而从$N(s)$的终态到初态的ε转移使得s可以重复任意多次。

加括号的表达式 (s) 直接转化为 $N(s)$自身即可。

NFA到DFA的变换-子集构造法

DFA 的书写比 NFA 要复杂很多，我们通常可以基于 NFA 来生成 DFA。

子集构造法的基本思想是让构造的DFA的一个状态对应NFA的一个状态集合。DFA 在输入a1,a2,…an后能到达的状态对应于NFA从开始状态出发沿着a1,a2,…an为标号的路径能到达的状态的集合。

预先定义几个概念:

  • $\epsilon - cloure (s)$ : 从 NFA 状态 s 出发，只通过 $\epsilon$ 能到达的状态集合。
  • $\epsilon -cloure(T)$ : 从状态集合T中的一个状态出发，只通过$\epsilon$ 能到达的状态集合。
  • $move (T,a)$ : 从状态集合T中的一个状态出发，只通过标号 a 的转换能到达的状态集合。

一开始DFA States 里只有一个状态:$\epsilon-cloure(0)$,且未标记;

当DFA States 中有未标记状态T时:

  1. 给T 加上标记
  2. 对于每个输入符号$a_{i}$:
    1. U = $\epsilon-cloure(move(T,a))$。
    2. 若 U 不在 DFA states 中，将其加入，且不加标记
    3. 构建转换函数 DFA $transform(T,a_{i}) = U$

我们以上面的$(a|b)^{*}ab$为例，来描述下这一过程;

graph LR
id(begin) -->|start|id0((0))
id0 -->|ϵ|id1((1))
id1 -->|ϵ|id2((2))
id1 -->|ϵ|id4((4))
id2 -->|a|id3((3))
id4 -->|b|id5((5))
id3 -->|ϵ|id6((6))
id5 -->|ϵ|id6((6))
id6 -->|ϵ|id1
id6 -->|ϵ|id7((7))
id0 -->|ϵ|id7
id7 -->|a|id8((8))
id8 -->|b|id9(9)

NFA的输入字母表是 {a,b}。等效DFA 的开始状态是$\epsilon-cloure(0)$,即{0,1,2,4,7}。

  1. 我们先标记A, 并 根据字母表计算转换函数 $tranform(A,a)$和 $tranform(A,b)$
  2. 在 A 集合中只有状态2和状态7 有 a 上的转换，对应 $move (A,a) = {3,8}$,在计算$\epsilon$的可达，最终有 $transform (A,a) = {1,2,3,4,6,7,8}$,我们称为 B 集合。
  3. 同样可以计算得到$transform (B,a )= {1,2,4,5,6,7}$,称此状态为 C 集合。
  4. 继续对 B，C 进行 … …
  5. 直到不会出现新的未标记状态
NFA 状态 DFA 状态 a b
{0,1,2,4,7} A B C
{1,2,3,4,6,7,8} B B D
{1,2,4,5,6,7} C B C
{1,2,4,5,6,7,9} D B C

包含开始状态0的 A 是 DFA 的开始状态，包含结束状态9的 D 是 DFA 的结束状态

graph LR
sa((SA)) -->|a|sb((SB))
sa((SA)) -->|b|sc((SC))
sb((SB)) -->|a|sb((SB))
sb((SB)) -->|b|sd((SD))
sc((SC)) -->|a|sb((SB))
sc((SC)) -->|b|sc((SC))
sd((SD)) -->|a|sb((SB))
sd((SD)) -->|b|sc((SC))

DFA 化简

参考