持续更新…

一、概述

一个编译器的结构

  • 词法分析:词法分析(lexical analysis)是编译器的第一个步骤,它负责读入组成源程序的字符流,并将它们组织成为更有意义的词素(lexeme)序列,对于每个词素,词法分析器产生一个二元组形式的词法单元(token)作为输出
  • 语法分析:语法分析(syntax analysis)使用由词法分析生成的词法单元来构建树形的中间表示,通常为一个语法树(syntax tree)
  • 语义分析:语义分析器(semantic analyzer)使用语法树和符号表中的信息来检查源程序是否和语言定义的语义一致。 它可时也收集类型信息,并提这些信息存放在语法树或符号表中,以便在随后的中间代码生成过程中使用
  • 中间代码生成器
  • 代码优化器
  • 代码生成器

二、词法分析

1 词法分析介绍

1.1 词法分析的主要任务

词法分析是编译的第一个阶段。它的主要任务是读取源程序的输入字符,识别出各个单词,将它们组成词素,生成并输出一个词法单元(token)。词法分析器通常要和符号表进行交互,当词法分析器发现了一个标识符的词素时,它将这个词素添加到符号表中。在某些情况下,词法分析器也会从符号表中读取有关标识符种类的信息,以确定向语法分析器传送哪个词法单元。

另外,在读取源程序字符的过程中,词法分析器还会做一些额外工作,比如:

  • 过滤掉源程序中的注释和空白(如换行符、空格、制表符等用于分割词法单元的字符)
  • 将编译器生成的错误消息与源程序的位置关联(如记录下遇到的换行符个数,以便给予每个错误消息一个行号)

因此,词法分析器可以分为两个原子模块:

  1. 扫描阶段
  2. 词法分析阶段

1.2 词法单元、模式、词素

词法分析中首先要了解三个相关但有区别的术语:

  • 词法单元:是一个由词法单元名(种别码)和一个可选的属性值组成:

    1
    token<词法单元名,属性值>

    其中:

    • 词法单元名是一个表示某种词法单位的抽象符号,类比于英文的名词、动词、形容词一样,常见的词法单元名如:关键字ifelse,常量intfloat等。
    • 属性值是可选的,比如,关键字if是程序设计中的唯一标识,事先已经确定,则不需要属性值;而常量01都能和词法单元名number匹配,但是对于代码生成器而言,需要具体知道number是什么,因此,还需要附加一个描述该词法单元的属性值。
  • 模式:描述了一个词法单元的词素可能具有的形式。

  • 词素:是源程序中的一个字符序列,它和某个词法单元的模式相匹配,并被词法分析器识别为词法单元的一个实例。

在很多程序设计语言中,词法单元可以总结为如下形式:

词法单元类型 词法单元名 举例
关键字 keyword ifelsewhilefor、…
运算符 operator +-*/=、…
标识符 identifier 变量名、数组名、…
常量 constant 1088.88、…
标点符号(分隔符) separator {}()、…

2 串和语言

首先介绍几个基本概念:

2.1 字母表(alphabet)

字母表是一个有限的符号集合,以下例子都是字母表:

  • 一个字母表包括英文字母、数字和标点符号
  • 一个二进制字母表包括0、1两种数字
  • ASCII字符集
  • Unicode字符集

2.2 串(string)

串是某个字母表中符号的一个有穷序列。串s的长度通常记作|s|,是指s中符号出现的次数,例如apple是一个长度为5的串;空串的长度为0,用ε(Epsilon)表示。

image-20220805233441677

如果xy是串,那么xy的连接xy是指把y附加到x后面形成的串,例如x=dogy=banana,那么xy=dogbanana;空串ε是连接运算的单元,也就是说,对于任何串s都有sε=εs=s

如果把两个串的连接看作是“乘积”,则串的指数运算如下:定义s0=ϵs^0=\epsilon,并且对于整数i>0i>0,有si=si1ss^i=s^{i-1}s,由于εs=s,则有s1=s,s2=ss,s3=sss...s^1=s,s^2=ss,s^3=sss...

2.3 语言(language)

语言是某个给定字母表上一个任意的可数的串的集合。根据这个定义:

  • 空集是语言
  • 空串ε是语言
  • 所有语法正确的C程序是语言
  • 所有语法正确的英语句子是语言

2.4 语言上的运算

语言上的运算实际上等价于字母表上的运算,在词法分析中,最重要的运算是并、连接和闭包的运算。其中:

  • 并运算是集合中的并 \cup 运算
  • 连接运算是指:以各种可能的方式,从第一个语言中任取一个串,再从第二个语言中任取一个串,然后将它们连接起来得到的所有串的集合
  • 对于一个语言LL的克林闭包(Kleene closure)记作LL^*,是指将LL连接0次或多次后得到的串的集合。对于L0L^0,即将LL连接0次得到的串的集合,被定义为|ε|,对于LL被归纳地定义为Li1LL^{i-1}L
  • 语言LL的正闭包是指LL^*但不包含L0L^0

闭包closure是什么?==todo==

举个具体的例子:

L={A,B,...,Z,a,b,...,z}L=\{A,B,...,Z,a,b,...,z\}D={0,1,...,9}D=\{0,1,...,9\},前面说过,我们可以用两种方式来考虑LLDD,这两种方式是等价的。一种方法是将LL看成大小写组成的字母表,将DD看成是10个数位组成的字母表;另一种方式是将LLDD看作语言,它们中所有串的长度都为一。我们可以通过运算来得到新的语言:

  • LDL \bigcup D是字母和数位的集合,令S=LD={A,B,...,Z,a,b,...,z,0,1,...,9}S=L \bigcup D=\{A,B,...,Z,a,b,...,z,0,1,...,9\},则SS是一个包含62个长度为1的串,每个串是一个字母或者一个数位。(或者说SS是一个大小写和数位组成的字母表)
  • LDLD是包含520个长度为2的串的集合,令S=LD={A0,A1,...,A9,B0,B1...,B9,...,a0,a1,...,z9}S=LD=\{A0,A1,...,A9,B0,B1...,B9,...,a0,a1,...,z9\},则SS的数量为一个全排列,即L元素的个数D元素的个数=5210=520L元素的个数*D元素的个数=52*10=520
  • L4L^4是所有由四个字母构成的串的集合,令S=L4={AAAA,AAAB,...,zzzz}S=L^{4}=\{AAAA,AAAB,...,zzzz\}SS的数量为L元素的个4=524=7,311,616L元素的个数^4=52^4=7,311,616
  • LL^{*}是所有由字母构成的串的集合(即克林闭包),包括空串ε,一个语言的克林闭包也可以表示为S=L=L0L1L2...Ln={ϵ,L1,L2,L3...,Ln},其中n为正整数S=L^{*}=L^0 \bigcup L^1 \bigcup L^2 \bigcup ... \bigcup L^n=\{\epsilon,L^1,L^2,L^3...,L^n\},其中n为正整数
  • L(LD)L(L \bigcup D)^{*}是所有以字母开头的,由字母和数位组成的串的集合
  • D+D^{+}是由一个或多个数位构成的串的集合(即正闭包),不包括空串ε,即K=L+=L1L2...Ln={L1,L2,L3...,Ln},其中n为正整数K=L^{+}=L^1 \bigcup L^2 \bigcup ... \bigcup L^n=\{L^1,L^2,L^3...,L^n\},其中n为正整数

3 文法

这部分在后续的语法分析中会更加具体地介绍。

3.1 文法定义

这里的定义是指上下文无关文法。

文法描述了一个程序设计语言的层次化语法结构。文法由一个四元组构成:

G=(VT,VN,P,S)G=(V_T,V_N,P,S)

其中:

  • GGgrammar的缩写

  • VTV_Tterminal symbol的缩写,即终结符号集合,也被称作上文所述的词法单元(token)。终结符号是指该文法所定义语言的基本符号的集合。

  • VNV_Nnonterminal symbol的缩写,即非终结符号集合,也被称作语法变量。它是用来表示一个终结符号串的集合。

  • PPproduction的缩写,即产生式集合。它描述了某个构造的某种书写形式,换句话说就是描述了如何将终结符和非终结符组合的方法。

    产生式的形式如下:

    AβA \rightarrow \beta

    其中,AA是产生式头(或左部)的非终结符号,β\beta是产生式体(或右部)的由终结符和非终结符组成的序列。\rightarrow读作“可以具有如下形式”或“定义为”。因此,上述形式整体读作:“AA定义为β\beta”。

    其中,AA中至少包含非终结符中的一个元素。

  • SSstart symbol的缩写,即开始符号。它用来描述文法中“最大的”语法成分。

根据上述定义,我们可以来描述一个if-else语句:

1
if (expression) statement else statement

即一个条件语句由关键字if、左括号(、表达式expression、语句statement、关键字else、右括号)、语句statement构成。它的产生式如下:

statement    if  (expression)  statement  else  statementstatement\;\rightarrow\;if\;(expression)\;statement\;else\; statement

其中,关键字if和括号这样的元素就是终结符号,而statementexpression这样的变量为非终结符。

下面用一个简单的例子来看看一个文法的完整书写格式。

我们在小学一年级学过加减法,一个加减法表达式由数位、加号、减号构成。比如3+67-1或者6,如果是两个数位,则它们之间必须用+-相连。该文法的完整定义如下:

G=(VT,VN,P,S)=({+,,0,1,2,3,4,5,6,7,8,9},{expr,digit},P,expr)P={expr  expr  +  digitexpr  expr    digitexpr  digitdigit  0123456789}G=(V_T,V_N,P,S)=(\{+,-,0,1,2,3,4,5,6,7,8,9\},\{expr,digit\},P,expr)\\ P=\{expr\rightarrow\;expr\;+\;digit\\ expr\rightarrow\;expr\;-\;digit\\ expr\rightarrow\;digit\\ digit\rightarrow\;0|1|2|3|4|5|6|7|8|9 \}

其中,终结符号为

1
+ - 0 1 2 3 4 5 6 7 8 9

非终结符号为

1
2
expr      digit
表达式 数位

由于expr是整个文法中最大的语法成分,因此开始符号S=exprS=expr

产生式PP的定义用白话描述:

1
2
3
4
表达式定义为表达式+数位
表达式定义为表达式-数位
表达式定义为数位
数位定义为符号0或1或2或3或4或5或6或7或8或9

这里的0,1,2...,9也被称为digit的候选式。

另外,在实际使用上,如果不会引起歧义,我们可以省略文法的其它部分,只保留产生式作为文法的定义。

3.2 文法推导

我们可以通过一个文法从开始符号出发,不断地将某个非终结符号替换为该非终结符号的某个产生式的体。比如,在上文中的文法:

expr  expr  +  digitexpr  expr    digitexpr  digitdigit  0123456789expr\rightarrow\;expr\;+\;digit\\ expr\rightarrow\;expr\;-\;digit\\ expr\rightarrow\;digit\\ digit\rightarrow\;0|1|2|3|4|5|6|7|8|9

由于digit可以表示从0到9中的任意数位,再根据第三条产生式,单个数位本身就是表达式,而第一条和第二条说明:任何表达式后面跟一个+-再跟一个数位可以构成一个新的表达式。因此,我们可以推导出9-5+2是一个表达式:

  1. 因为9是数位,根据第三条可知,9是表达式
  2. 因为5是数位,9是表达式,根据第二条可知,9-5也是表达式
  3. 因为2是数位,9-5是表达式,根据第一条可知,9-5+2也是表达式

3.3 文法分类

todo

4 正则表达式

4.1 基本概念

如果要描述C语言所有合法标识符的合集,它差不多就是在2.4中的例子:

  • L(LD)L(L \cup D)^{*}是所有以字母开头的,由字母和数位组成的串的集合

唯一不同的是C语言中标识符可以有下划线。

在这个例子中,我们可以首先给出字母LL和数字DD集合,然后通过并、连接、闭包运算来描述标识符。正则表达式是一种更紧凑的表示方法,它可以描述所有通过某个字母表上的符号通过运算而得到的语言。

正则表达式可以由较小的正则表达式递归构建,下面两个规则构成了归纳基础:

  1. ϵ\epsilon是一个正则表达式,L(ϵ)=ϵL(\epsilon)=|\epsilon|,即该语言只包含空串
  2. 如果α\alpha是字母表Σ\Sigma上的一个符号,那么α\alpha是一个正则表达式,并且L(α)=αL(\alpha)=|\alpha|。也就是说这个语言仅包含一个长度为1的符号串α\alpha

假设rrss都是正则表达式,分别表示语言L(r)L(r)L(s)L(s),将小的正则表达式构造为大的正则表达式的归纳步骤有如下四步:

  1. (r)(s)(r)|(s)是一个正则表达式,表示语言L(r)L(s)L(r)\cup L(s)
  2. (r)(s)(r)(s)是一个正则表达式,表示语言L(r)L(s)L(r)L(s)
  3. (r)(r)^*是一个正则表达式,表示语言(L(r))(L(r))^*
  4. (r)(r)是一个正则表达式,表示语言L(r)L(r),这一条的意思是在表达式两边加括号并不影响表达式所表示的语言。

另外,为了简化,我们可以将不必要的括号去掉,在去掉括号之前,需要先进行如下约定:

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

左结合和右结合的概念是指在相同运算优先级下,操作符对操作数的执行顺序:

如果一个操作符对其操作数是自左向右执行的,则称该操作符是左结合的;

如果一个操作符对其操作数是自右向左执行的,则称该操作符是右结合的;

比如,赋值运算符=是右结合的,a=b=c的运算顺序就是先将c赋值b再将b赋值a

加法+是左结合的,a+b+c的运算顺序就是先计算a+b再计算(a+b)+c

4.2 使用正则表达式描述语言

现在使用正则表达式来描述语言,令字母表Σ={a,b}\Sigma=\{a,b\},则:

  • 正则表达式aba|b表示语言{a,b}\{a,b\}
  • 正则表达式(ab)(ab)(a|b)(a|b)表示语言{aa,ab,ba,bb}\{aa,ab,ba,bb\},即字母表Σ\Sigma上长度为2的所有串的集合,也可以用另一个等价正则表达式来描述:aaabbabbaa|ab|ba|bb
  • 正则表达式aa^*表示语言{ϵ,a,aa,aaa,...}\{\epsilon,a,aa,aaa,...\},即所有由零个或多个α\alpha组成的串的集合
  • 正则表达式(ab)(a|b)^*表示语言{ϵ,a,b,aa,ab,ba,bb,aaa,...}\{\epsilon,a,b,aa,ab,ba,bb,aaa,...\},即所有由零个或多个α\alphabb组成的串的集合
  • 正则表达式aaba|a^*b表示语言{a,b,ab,aab,aaab,...}\{a,b,ab,aab,aaab,...\},即α\alpha和以bb结尾的零个或多个α\alpha组成的串的集合

可以用正则表达式定义的语言叫做正则集合(regular set)。如果两个正则表达式可以表示同样的语言,则称它们等价,例如(ab)=(ba)(a|b)=(b|a),正则表达式遵循一些代数定律,每个定律中两个不同形式的表达式等价。如下图:

image-20220810110658376

4.3 正则定义

为了方便,我们可以给正则表达式命名,之后将这些名字像使用符号一样使用这些名字。如果Σ\Sigma是基本符号的集合,那么一个正则定义是具有如下形式的定义序列:

d1r1d2r2...dnrnd_1 \to r_1\\ d_2 \to r_2\\ ...\\ d_n \to r_n

其中:

  • 每个did_i都是一个新符号,它们都不在Σ\Sigma中,并且各不相同
  • 每个rir_i是字母表Σ{d1,d2,...,di1}\Sigma\cup\{d_1,d_2,...,d_{i-1}\}上的正则表达式

并且,为了防止递归定义,我们限制每个rir_i中只含有Σ\Sigma中的符号和它之前定义的各个djd_j,并且,我们可以为每个rir_i构造出只包含Σ\Sigma中符号的正则表达式。比如我们可以首先将r2r_2(它只能使用d1d_1)中的d1d_1替换为r1r_1,然后再将r3r_3中的d1d_1d2d_2替换为r1r_1和替换之后的r2r_2,以此类推,最终,每个rir_i中都只包含Σ\Sigma中的符号。

前面提到C语言中标识符应该是数字、字母、下划线组成的串,我们用letter_letter\_表示字母或下划线,用digitdigit表示数位,它的正则定义如下:

letter_AB...Zab...z_digit01...9idletter_(letter_digit)letter\_ \to A|B|...|Z|a|b|...|z|\_\\ digit \to 0|1|...|9\\ id \to letter\_(letter\_|digit)^*

4.4 正则表达式的扩展

下面介绍一种当今仍在使用的扩展正则表达式表示法:

  • 单目后缀运算符++表示一个或多个,即一个正则表达式及其语言的正闭包。++*具有同样的优先级和结合性。
  • 单目后缀运算符??表示零个或一个,??*具有同样的优先级和结合性。
  • 字符类。一个正则表达式a1a2...ana_1|a_2|...|a_naia_i是字母表中的各个符号)可以缩写为[a1a2...an][a_1a_2...a_n],如果它们构成一个逻辑上连续的序列,比如连续的字母,可以表示为[a1an][a_1-a_n],因此[abc][abc]abca|b|c的缩写,[az][a-z]ab...za|b|...|z的缩写。

根据这个扩展表示法,我们可以将上面C语言中标识符的正则定义改为:

letter_[AZaz_]digit[09]idletter_(letter_digit)letter\_ \to [A-Za-z\_]\\ digit \to [0-9]\\ id \to letter\_(letter\_|digit)^*

5 词法单元的识别

词法单元识别即根据输入的字符串中找出某个模式匹配的词素。

5.1 状态转换图

作为构造词法分析器的中间步骤,首先将模式转换成具有特定风格的流图,即状态转换图(transition diagram),它有一组被称为状态(state)的结点或圆圈,词法分析器在扫描输入串的过程中寻找和某个模式匹配的词素,而转换图中的每个状态代表一个可能在这个过程中出现的情况。状态图中的边(edge)从图的一个状态指向另一个状态,每条边的标号包含了一个或多个符号。如下图所示:

image-20220810152909318

图中,每个结点都表示一个状态,并且:

  • 有一个开始状态,它由一条没有出发结点的、标号为start的边指明,在读入任何符号之前,状态转换图总是位于开始状态
  • 用双圈表示的叫做接受状态(最终状态),如图中标号为3的圆圈,它表示已经找到了一个词素,最终状态可以有多个
  • 如果需要回退一个位置,那么我们会在接受状态的附近标上*,如果需要回退多个位置,则对应地会附加多个*

上图中的状态转换图能够识别正则表达式(ab)abb(a|b)^*abb,即由aabb组成的,以字符串abbabb结尾的语言。我们将结合下一节进行具体介绍。

5.2 有穷自动机

  • 有穷自动机(finite automata,FA)由两位神经物理学家MeCuloch和Pitts于1948年首先提出,是对一类处理系统建立的数学模型
  • 这类系统具有一系列离散的输入输出信息和有穷数目的内部状态(状态:概括了对过去输入信息处理的状况)
  • 系统只需要根据当前所处的状态和当前面临的输入信息就可以决定系统的后继行为。每当系统处理了当前的输入后,系统的内部状态也将发生改变

有穷自动机在本质上与状态转换图类似,但前者只能对每个可能的输入回答“是”或者“否”。

对于一个输入串x,如果存在一个对应于串x的从初始状态到某个终止状态的转换序列,则称串x被该自动机FA接收(识别、定义)。比如对于上图中的自动机,我们的输入串如果为aabbabb,则前四个字母aabb都可以被状态0接收,之后,对于后三个字母abb,则依次由状态1,2,3接收,由于这个状态转换是从初始状态0到终止状态3,因此输入串aabbabb能够被上图中的自动机接收。另外,在自动机的匹配过程中,当输入串的多个前缀与一个或多个模式匹配时,总是会选择最长的前缀进行匹配,即遵循最长子串匹配原则。

5.3 有穷自动机的分类

有穷自动机FA分为两类

  • 不确定有穷自动机(nondeterministic finite automata,NFA)对其边上的标号没有任何限制。一个符号标记离开同一状态的多条边,并且空串也可以作为标号
  • 确定有穷自动机(deterministic finite automata,DFA)对于每个状态及自动机输入字母表中的每个符号,有且只有一条离开该状态、以该符号为标号的边

确定和不确定的有穷自动机能识别(接收)的语言的集合是相同的。事实上,这些语言的集合正好就是能够用正则表达式描述的语言的集合,这个集合中的语言称为正则语言(regular language)。

在实践中,我们不会想用正则表达去描述空的语言,但是有穷自动机可以定义空语言,因此,在理论研究中,\emptyset被视为一个额外的正则表达式,这个表达式被用于定义空语言。

DFA的完整定义为一个五元组:

M=(S,Σ,δ,S0,F)M=(S,\Sigma,\delta,S_0,F)

  • SS为一个有穷的状态集合
  • Σ\Sigma为一个输入符号集合,即输入字母表(input alphabet)。我们假设空串ϵ\epsilon不是该集合中的元素
  • δ\delta为一个转换函数(transition function),它为每个状态和输入符号中的每个符号都给出了相应的后继状态的集合。即对于SS中任意的状态ss,给定任意一个字母表Σ\Sigma中的符号aaδ(s,a)\delta(s,a)表示从状态ss出发,沿着标记为aa的边所能到达的状态
  • S0S_0为开始状态,或者称为初始状态,它是SS中的一个状态
  • FF为所有接收状态(接收状态可能不止一个)的集合

对于NFA的定义,与DFA的区别在于:

  • δ\delta转换函数中,对于SS中任意的状态ss,给定任意一个字母表Σ\Sigma中的符号aaδ(s,a)\delta(s,a)表示从状态ss出发,沿着标记为aa的边所能到达的状态集合(与DFA相比,NFA所能到达的状态集合不唯一),且字符集中可以包括空串ε

在5.1图中的转换图就描述了这样的一个NFA。因为当读入字符a时,自动机所能进入的状态并不是唯一确定的(可以是状态0,也可以是状态1)。我们可以用一张转换表来描述,如下:

状态\输入 a b ϵ\epsilon
0 {0,1} {0} \emptyset
1 \emptyset {2} \emptyset
2 \emptyset {3} \emptyset
3 \emptyset \emptyset \emptyset

表的各行对应于状态,各列对应于输入符号和空串。对于一个给定状态和给定输入的条目就是将NFA的转换函数应用到这些参数得到的值。如果转换函数没有给出结果,就把\emptyset放入对应的表项中。比如,上表中,在状态0输入字符a,自动机所能进入的状态为{0,1}集合,可以是状态0,也可以是状态1,因此也确定了它是一个NFA。

转换表的优点在于我们可以很清楚直观地看到一个给定状态和输入符号所对应的转换,但是缺点在于,如果字母表很大,且大多数状态\输入字符没有对应的转换时,需要填充很多\emptyset,这占用了大量无用空间。

对于DFA的转换图,和NFA有一点点区别。DFA没有了ε上的转换动作,且表中的表项没有花括号集合,而是一个确定的状态。如下图的DFA:

image-20220811103733183

它接收的语言与5.1图中的NFA所能表示的语言相同,都是(ab)abb(a|b)^*abb,它的转换表如下:

状态\输入 a b
0 1 0
1 1 2
2 1 3
3* 1 0

如上所述,在DFA的转换表中,没有对于空串的转换动作,且所有的表项都对应确定的状态。

对于一个给定输入串ababb,这个DFA的状态进入序列为0、1、2、1、2、3,对于最后的输入,自动机处于最终状态,因此它回答yes

我们可以用如下的伪代码来模拟这个DFA:

1
2
3
4
5
6
7
8
9
10
11
12
// s:当前状态
s=s0;
// c:当前字符
c = nextChar();
while(c!=eof){
// 不断地遍历串,直到结束
// 根据当前状态和字符,决定自动机的状态
s=move(s,c);
c = nextChar();
}
if (s在接收状态集F中) return "yes";
else return "no";

5.4 从正则表达式到有穷自动机

实际上,给定一个正则表达式,则一定能够构造一个DFA,但是,直接构造比较困难。由于一个NFA也能够转化为等价的DFA。且在语法分析实现的层面,我们更倾向于DFA。

我们将首先介绍如何构造一个NFA,然后再将NFA转化为DFA。一般的构造步骤如下:

1
正则表达式--->NFA--->DFA
5.4.1 从正则表达式构造NFA

现在我们介绍一个从正则表达式构造NFA的Mcmaughton-Yamada-Thompson算法,它可以将任何正则表达式转变为接收相同语言的NFA。

  • 算法输入:字母表Σ\Sigma上的一个正则表达式rr

  • 算法输出:一个接收L(r)L(r)的NFA NN

  • 方法:首先对rr进行语法分析,分解除组成它的子表达式。构造一个NFA的规则,分为基本规则和归纳规则两组。基本规则处理不包含运算符的子表达式,而归纳规则根据一个给定表达式的直接子表达式的NFA构造出这个表达式的NFA。

  • 基本规则:对于表达式ϵ\epsilon,构造出对应的NFA:

    image-20220811165129249

    这里i是一个新状态,也是这个NFA的开始状态;f是另一个新状态,是这个NFA的终止状态。由if之间的有向边ε表示从状态i只需要接收空串就可以到达状态f

    对于字母表Σ\Sigma中的符号aa对应的NFA:

    image-20220811165459320

    同样,这里i是一个新状态,也是这个NFA的开始状态;f是另一个新状态,是这个NFA的终止状态。从if需要接收一个符号a

    在这两个基本构造规则中,对于ε和某个a作为r的子表达式的每次出现,我们都是用新状态分别构造出一个独立的NFA。

  • 归纳规则:假设正则表达式sstt的NFA分别为N(s)N(s)N(t)N(t)

    1. 对于r=str=s|t的NFA,即N(r)N(r),可以按照下图方式构造得到。

    image-20220811171758824

    这里的if是新状态,分别是N(r)N(r)的开始和接收状态。从iN(s)N(s)N(t)N(t)的开始状态各有一个ϵ\epsilon转换,从N(s)N(s)N(t)N(t)到接收状态f也各有一个ϵ\epsilon转换。

    1. 对于r=str=st的NFA,可以按照下图方式构造:

      image-20220811182011240

      N(s)N(s)的开始状态变成了N(r)N(r)的开始状态,N(t)N(t)的接收状态变成N(r)N(r)的唯一接收状态。N(s)N(s)的接收状态和N(t)N(t)的开始状态合并为一个状态,合并后的状态拥有原来进入和离合并前的两个状态的全部转换。一个路径不可能在离开N(s)N(s)后再次进入N(s)N(s),因此,N(r)N(r)恰好接收L(s)L(t)L(s)L(t),它是r=str=st的一个正确的NFA。

    2. 对于r=sr=s^*的NFA,可以按照下图方式构造:

      image-20220811182605082

      这里,if是两个新状态,分别是N(r)N(r)的开始和唯一接收状态,要从i到达f,我们可以沿着标号为ε的路径前进,这个路径对应于L(s)0L(s)^0中的一个串。我们也可以到达N(s)N(s)的开始状态,然后经过该NFA,再零次或多次从它的接收状态回到它的开始状态并重复上述过程。因此,它可以接收L(s)1L(s)^1L(s)2L(s)^2等集合中的所有串,因此N(r)N(r)识别的所有串的集合就是L(s)L(s)^*

    3. 最后,对于r=(s)r=(s),那么L(r)=L(s)L(r)=L(s),我们可以直接把N(s)N(s)当做N(r)N(r)

经过该算法构造的NFA具有如下性质:

  • N(r)N(r)的状态数最多为rr中出现的运算符和运算分量的总数的2倍,这是因为算法的每一个构造步骤最多只引入两个新状态。
  • N(r)N(r)有且仅有一个开始状态和一个接收状态,接收状态没有出边,开始状态没有入边。
  • N(r)N(r)中除接收状态之外的每个状态要么有一条标号为符号表Σ\Sigma中符号的出边,要么有两条标号为ϵ\epsilon的出边。

下面尝试使用该算法为正则表达式r=(ab)abbr=(a|b)^*abb构造一个NFA。下图展示了rr的一颗语法分析树:

image-20220811235013854

对于子表达式r1r_1,即第一个aa,构造如下的NFA:

image-20220812000743942

同理,对于r2r_2

image-20220812000835942

现在我们可以使用Mcmaughton-Yamada-Thompson算法,将N(r1)N(r_1)N(r2)N(r_2)合并,得到r3=r1r2r_3=r_1|r_2的NFA:

image-20220812001018677

r4r_4的NFA和r3r_3相同。r5=(r3)r_5=(r_3)^*的NFA构造如下图:

image-20220812001142983

现在考虑r6r_6,它是表达式中的另一个aa,因此,我们的状态必须使用新的而不能重复使用为r1r_1构造的那个NFA:

image-20220812001303624

要得到r7=r5r6r_7=r_5r_6的NFA,我们应用上述算法,得到如下图所示的NFA:

image-20220812001407971

最终我们得到下图所示的(ab)abb(a|b)^*abbNFA

image-20220812001539032

5.4.2 从NFA到DFA的转换

我们利用子集构造法的技术,可以将NFA转化为DFA,其基本思想是:让构造的得到的DFA的每个状态对应于NFA的一个状态集合。

  • 算法输入:一个NFA NN

  • 算法输出:一个接收同样语言的DFA DD

  • 方法:我们的算法为DD构造一个转换表Dtran。DD的每个状态是一个NFA状态集合,我们构造Dtran,使得D"并行地"模拟NN在遇到一个给定输入串时可能执行的所有动作。我们面对的第一个问题是正确处理NN的空串ϵ\epsilon转换。在下表中我们可以看到一些函数的定义,这些函数描述了一些需要在这个算法中执行的NN的状态集上的基本操作。ss标识NN的单个状态,TT标识NN的一个状态集合。

    操作 描述
    ϵclosure(s)\epsilon-closure(s) 能够从NFA的状态ss开始只通过ϵ\epsilon转换到达的NFA状态集合
    ϵclosure(T)\epsilon-closure(T) 能够从TT中某个NFA状态ss开始只通过ϵ\epsilon转换到达的NFA状态集合
    move(T,a)move(T,a) 能够从TT中某个状态ss出发通过标号为aa的转换到达的NFA状态集合

    我们必须找出当NN读入了某个输入串之后可能位于的所有状态集合。首先,在读入第一个输入符号之前,NN可以位于集合ϵclosure(s0)\epsilon-closure(s_0)中的任何状态上,其中s0s_0是开始状态。下面进行归纳。

    • 假设NN在读入输入串xx之后可以位于集合TT中的状态上,如果下一个输入符号是aa,那么NN可以立即移动到集合move(T,a)move(T,a)中的任何状态。
    • NN可以在读入aa后再执行几个ϵ\epsilon转换,因此NN在读入xaxa后可以位于ϵclosure(move(T,a))\epsilon-closure(move(T,a))中的任何状态上。

    根据这些思想,我们可以得到DD的状态集合Dstates和DD的转换函数Dtran,算法如下:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    一开始,ε-closure(s0)是Dstates中的唯一状态,且它未加标记;
    while(在Dstates中有一个未标记状态T){
    给T加上标记;
    for(每个输入符号a){
    U=ε-closure(move(T,a));
    if(U不在Dstates中) 将U加入到Dstates中,且不加标记;
    Dtran[T,a]=U;
    }
    }

    DD的开始状态是ϵclosure(s0)\epsilon-closure(s_0),接收状态是所有至少包含了NN的一个接收状态的状态集合。我们只需要说明对NFA的任何状态集合TT计算ϵclosure(T)\epsilon-closure(T),就可以完整地描述子集构造法。这个计算过程是从一个状态集合开始的一次简单的图搜索过程,不过此时假设这个图中只存在标号为ϵ\epsilon的边,算法如下:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    将T的所有状态压入stack中;
    将ε-closure(T)初始化为T;
    while(stack非空){
    将栈顶元素t弹出栈;
    for(每个满足如下条件的u:从t出发有一个标号为ε的转换到达状态u)
    if(u不在ε-closure(T)中){
    将u加入到ε-closure(T)中;
    将u压入栈stack中;
    }
    }

我们拿5.4.1中的NFA(ab)abb(a|b)^*abb来应用上述算法:

image-20220812001539032

1
一开始,ε-closure(s0)是Dstates中的唯一状态,且它未加标记;

等价NFA的开始状态AAϵclosure(0)\epsilon-closure(0),即能够从状态0出发,只经过标号为ϵ\epsilon的路径到达的所有状态:A={0,1,2,4,7}A=\{0,1,2,4,7\}。由于路径可以不包含边,因此0状态也属于集合A。此时,A是Dstates状态中的唯一状态,且它未加标记,

1
2
3
4
while(在Dstates中有一个未标记状态T){
给T加上标记;
...
}

进入循环,为AA加上标记。

1
2
3
4
5
6
for(每个输入符号a){
U=ε-closure(move(T,a));
U=ε-closure(move(T,a));
if(U不在Dstates中) 将U加入到Dstates中,且不加标记;
Dtran[T,a]=U;
}

NFA中的字母表是{a,b}\{a,b\},因此我们需要分别计算Dtran[A,a]=ϵclosure(move(A,a))Dtran[A,a]=\epsilon-closure(move(A,a))Dtran[A,b]=ϵclosure(move(A,b))Dtran[A,b]=\epsilon-closure(move(A,b))

在状态A={0,1,2,4,7}A=\{0,1,2,4,7\}中,只有状态2和状态7具有aa的转换,分别到达状态3和状态8,因此move(A,a)={3,8}move(A,a)=\{3,8\},则ϵclosure({3,8})={1,2,3,4,6,7,8}\epsilon-closure(\{3,8\})=\{1,2,3,4,6,7,8\},因此我们有:

Dtran[A,a]=ϵclosure(move(A,a))=ϵclosure({3,8})={1,2,3,4,6,7,8}Dtran[A,a]=\epsilon-closure(move(A,a))=\epsilon-closure(\{3,8\})=\{1,2,3,4,6,7,8\}

我们称这个集合为BB,得到Dtran[A,a]=BDtran[A,a]=B

在状态A={0,1,2,4,7}A=\{0,1,2,4,7\}中,只有状态4具有bb的转换,到达状态5,因此move(A,b)={5}move(A,b)=\{5\},则ϵclosure({5})={1,2,4,5,6,7}\epsilon-closure(\{5\})=\{1,2,4,5,6,7\},因此我们有:

Dtran[A,b]=ϵclosure(move(A,b))=ϵclosure({5})={1,2,4,5,6,7}Dtran[A,b]=\epsilon-closure(move(A,b))=\epsilon-closure(\{5\})=\{1,2,4,5,6,7\}

我们称这个集合为CC,得到Dtran[A,b]=CDtran[A,b]=C

经过本轮循环,我们的栈中得到了两个未加标记的集合B和C,继续进行这个算法,最终会使得这个DFA的所有状态都被加上标记。在这个例子中我们实际会构造出5个不同的DFA状态,这些状态、它们对应的NFA状态集以及DD的转换表如下:

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 E
{1,2,4,5,6,7,10} E B C

DD的转换图如下:

image-20220812110631549