从正则表达式到有限自动机

【编译原理】词法分析：正则表达式与有限⾃动机基础引⾔： 编译语⾔设计的精髓在于⾃动化过程，即如果要设计⼀门编程语⾔，那么⼀定要设计⼀个⾃动化系统，能够⾃⾏读⼊分析程序员写⼊的程序，将其翻译为机器能够识别的指令等信息。

当然⾼级语⾔的编译不是⼀蹴⽽就的，⽽是通过若⼲步的分解、规约、转换、优化，最后得到⽬标程序。

具体的编译步骤如下： 源程序就是我们写⼊的⾼级语⾔，编译的第⼀步叫做“词法分析”。

词法分析的本质，就是要拆解出语句的每⼀个单词，然后对这个单词的类型进⾏辨识。

⾸先拿中⽂来举例。

⽐如有⼀句话是“我喜欢你”，那么⾸先我们要把这句话拆成“我”、“喜欢”、“你”，然后再逐个分析他们的类型，得到“我”->主语；“喜欢”->谓语；“你”->宾语。

这样我们就把这句话每个单词都分析出来了，也就完成了中⽂的“词法分析”。

那么回到编程语⾔，它的词法分析就是将字符序列转换为单词（Token）序列的过程。

翻译成俗话，就是把我们写的⼤⽚语⾔⽂本分解为⼀个⼀个单词，再输出每个单词的类型。

举⼀个例⼦：int p = 3 + a; 这个语句⾮常简单，即定义⼀个变量p，它的初值为变量a与3的加和。

那么接下来我们要对这个语句进⾏词法分析，⾸先我们要把这段⽂本拆解成单词，拆出来就是'int'、'p'、'='、'3'、'+'、'a'、';'。

对这些单词再进⾏类型的辨识，那么就得到以下结果：语素语⾔类型int关键字p标识符=运算符3数字+运算符a标识符 这样我们就把这段⽂本中的每个单词的类型都分析出来了。

乍⼀看⾮常简单对不对，对于⼈类⽽⾔你只需要⽤⾁眼就可以轻松观察出来每个单词的类型，但对于计算机⽽⾔，它可没有⼈类那样的智能。

如果想要计算机能够识别并分析语素的类型，那就需要我们⼈类来为它构造⼀个⾃动化输⼊和分析的系统。

乔姆斯基和句法分析乔姆斯基之于语言学和认知科学，就像图灵之于计算机科学。

没有这些“先知”，我们不知还要在黑暗中摸索多久。

这个说法不只是比喻性的：乔姆斯基的句法频谱后来被证明和几种自动机有着深刻的关联：乔姆斯基3型文法（正则表达式）等价于有限自动机，2型文法（上下文无关文法）等价于下压自动机，1型文法（上下文相关文法）等价于线性有界非确定图灵机，0型文法等价于图灵机。

乔姆斯基的句法研究导致了乔姆斯基在哲学上的理性主义立场，这与英美的经验主义主流不合拍。

其实乔姆斯基的理性主义与欧陆传统的理性主义并不完全一致，倒是和丘奇-图灵论题可互为佐证。

这话展开了讲太长，语言学和哲学系找不到课题的博士生可以试试这个。

乔姆斯基决定干语言学其实缘于他的政治兴趣。

他是结构主义语言学开山哈里斯（Zellig Harris）的学生，他们都是犹太人，有同样的政治主张。

大二时，乔姆斯基对学业困惑，准备退学，哈里斯劝他说：你干嘛不试试语言学呢，可先从数学和哲学入手。

哈里斯给了他一本自己尚未出版的《结构语言学方法》一书的草稿，乔姆斯基从此开了窍，走上了语言学之路。

传统的人文范儿的语言学家必是那些懂多种语言的人才。

但哈里斯把语言学从人文转变成科学，他在宾夕法尼亚大学（UPenn）建立了美国第一个语言学系。

乔姆斯基在宾大得了本科和硕士学位后，在那时还在宾大哲学系教书的古德曼（Nelson Goodman）的影响下，前往哈佛投奔当时美国哲学界的领袖蒯因（Quine），他在哈佛还被选为初级研究员（Fellow）。

哈佛的这个Fellow是给那些明日学术之星准备的，在乔姆斯基之前，王浩、库恩等都得过。

在哈佛期间，乔姆斯基发表了他的第一篇学术论文“句法分析系统”（Systems of Syntactic Analysis）。

值得一提的是，这篇文章并未发表在语言学杂志上，而是在数理逻辑最权威的《符号逻辑杂志》（JSL ）上。

这本杂志由丘奇创办，从杂志创刊开始，丘奇就为JSL 写评论，一直写到他80岁高龄。

正则表达式（Regular Expression）是一种用于匹配字符串的强大工具，而NFA（Non-deterministic Finite Automaton，非确定性有限自动机）是一种可以用于匹配正则表达式的模型。

下面是将正则表达式转换为NFA的一般步骤：1. 将正则表达式转换为Brzozowski标准形式。

Brzozowski标准形式是一种将正则表达式转换为后缀形式的方法。

在Brzozowski标准形式中，每个操作符都被放在括号中，例如(ab)*c表示匹配零个或多个ab，后面跟着一个c。

2. 将Brzozowski标准形式转换为Thompson构造法。

Thompson构造法是一种通过构建一组字符串来模拟正则表达式的匹配过程的方法。

在Thompson构造法中，每个操作符都被表示为一个特定的字符串，例如星号(*)表示重复零个或多个次数的字符串，括号()表示匹配括号内字符串的重复次数。

3. 将Thompson构造法转换为NFA。

在Thompson构造法中，每个字符串都表示一个状态转换。

因此，可以将每个字符串转换为一个状态，并根据字符串之间的顺序将这些状态连接起来。

在NFA中，每个状态都表示一个可能的输入序列，而状态之间的转换则表示输入序列的下一个可能的输入。

4. 确定NFA的起始状态和终止状态。

在NFA中，起始状态是开始匹配正则表达式的状态，而终止状态是匹配结束的状态。

可以根据Thompson构造法中每个字符串的顺序来确定起始状态和终止状态。

例如，如果最后一个字符串是正则表达式的结尾，那么它对应的状态就是终止状态。

5. 确定NFA的转换函数和接受集。

转换函数是将一个状态和一个输入字符映射到下一个状态的函数。

接受集是一个状态集合，当自动机达到这个状态集合时，它就匹配成功。

可以根据NFA中的状态转换来确定转换函数和接受集。

通过以上步骤，可以将正则表达式转换为NFA，以便进行字符串匹配。

1.写出表示下列语言的正则表达式。

⑴ {0, 1}*。

解：所求正则表达式为：(0+1)*。

⑵ {0, 1}+。

解：所求正则表达式为：(0+1)+。

⑶ { x│x∈{0,1}+ 且x中不含形如00的子串 }。

解：根据第三章构造的FA，可得所求正则表达式为：1*(01+)*(01+0+1)。

⑷ { x│x∈{0,1}*且x中不含形如00的子串 }。

解：根据上题的结果，可得所求正则表达式为：ε+1*(01+)*(01+0+1)。

⑸ { x│x∈{0,1}+ 且x中含形如10110的子串 }。

解：所求正则表达式为：(0+1)*10110(0+1)*。

⑹ { x│x∈{0,1}+ 且x中不含形如10110的子串 }。

解：根据第三章的习题，接受x的FA为：要求该FA对应的正则表达式，分别以q0、q1、q2、q3、q4为终结状态考虑：q为终态时的正则表达式：(0*(11*0(10)*(ε+111*11*0(10)*)0)*)*q1为终态时的正则表达式：0*1(1*(0(10)*111*1)*(0(10)*00*1)*)*q2为终态时的正则表达式：0*11*0((10)*(111*11*0)*(00*11*0)*)*q3为终态时的正则表达式：0*11*0(10)*1(11*11*0((10)*(00*11*0)*)*1)*q4为终态时的正则表达式：0*11*0(10)*11(1*(11*0((00*11*0)*(10)*)*11)*)*将以上5个正则表达式用“+”号相连，就得到所要求的正则表达式。

⑺ { x│x∈{0,1}+ 且当把x看成二进制数时，x模5与3同余和x为0时，│x│=1且x≠0时，x的首字符为1}。

解：先画出状态转移图，设置5个状态q0、q1、q2、q3、q4，分别表示除5的余数是0、1、2、3、4的情形。

另外，设置一个开始状态q.由于要求x模5和3同余，而3模5余3,故只有q3可以作为终态。

由题设，x=0时，│x│=1，模5是1，不符合条件，所以不必增加关于它的状态。

正规式与有限自动机正规式与有限自动机之间的转换1）有限自动机转换为正规式对于S上的NFAA/,可以构造一个S上的正规式/?,使得切⑷。

拓广状态转换图的概念，令每条弧可用一个正规式作标记。

为S上的NFA Af构造相应的正规式及，分为如下两步。

（1）在M的状态转换图中加两个节点，一个x节点，一个y节点。

从x节点到NFAM 的初始状态节点引一条弧并用e标记，从NFAM的所有终态节点到y节点引一条弧并用e 标记。

形成一个与A/等价的MS AT只有一个初态jc和一个终态少。

（2）按下面的方法逐步消去中除x和；；的所有节点。

在消除节点的过程中，用正规式来标记弧，最后节点jc和；；之间弧上的标记就是所求的正规式。

消除节点的规则如图2-12所示。

2）正规式转换为有限自动机同样地，对于S上的每个正规式/?,可以构造一个S上的NFAAf,使得L（A0=Z（及）。

（1）对于正规式i,可用图>13所示的拓广状态图表示。

R o（1）通过对正规式/?进行分裂并加入新的节点，逐步把图转变成每条弧上的标记是E上的一个字符或e,转换规则如图2-14所示。

最后所得的图即为一个NFAM,JC为初态节点，少为终态节点。

显然，L（A0=I（及）。

【试题2-24】2011年11月真题48下图所示为一个有限自动机（其中，A是初态、C是终态），该自动机识别的语言可用正规式（48）表示。

A. (0|1)*01B. 1*0*10*1C. 1*(0)*01D. 1*(0|10)*1*分析：在正规式中，符号*表示重复若干次（包括0次），符号|表示“或”。

在状态A，可以输入1或0，如果输入1还可以回到状态A，如果输入0直接到达状态B；在状态B，可以输入0或1，如果输入0则还回到状态B，而输入1，则进入到状态C；在状态C可以输入0或1，输入0到达状态B，输入1到达状态A，但由于C是终态，自动机可识别的语言是由0、1构成的字符串的集合，但该集合必须以01结果，因此选项A正确。

北京大学信息科学技术学院2015年春季学期《编译技术》第3章词法分析（2）Lexical Analysis【对应教材 3.3- 3.5】取下一个Token符号表语法分析器词法分析器上节内容回顾☐词法分析器的作用Token(词法单元)源程序☐词法单元的描述方法⏹ 字母表、符号串和语言⏹正则集合、正则表达式和正则定义Review Questions☐写一个正则表达式，表示所有能被5整除的十进制数。

☐写一个正则表达式，表示所有能被5整除的不包含前导0的十进制数。

☐写一个正则表达式，表示所有能被5整除的二进制数。

☐词法分析器的作用☐词法单元的规约⏹串和语言；正则表达式、正则定义☐词法单元的识别☐词法分析器生成工具—LEX☐有限自动机(Finite Automata)☐正则表达式到有限自动机☐词法分析器生成工具的设计☐一般有两种方式：⏹借助状态转换图（有限自动机的图形表示）手工构造词法分析器。

⏹通过LEX自动生成词法分析器。

正则表达式⇒ NFA⇒ DFA⇒ minDFA⇒词法分析器☐状态转换图(transition diagram)⏹状态(state)：表示在识别词素时可能出现的情况状态看作是已处理部分的总结某些状态为接受状态或最终状态，表明已找到词素加上*的接受状态表示最后读入的符号不在词素中 ☐开始状态（初始状态）：用“开始”边表示⏹边(edge)：从一个状态指向另一个状态；边的标号是一个或多个符号当前符号为s，下一个输入符号为a，就沿着从s离开,标号为a的边到达下一个状态= 2r 1> 3<other *开始40 =>5 return(relop, EQ)= other 768 *eturn(relop, LE) return(relop, NE) return(relop, LT)return(relop, GE) return(relop, GT)letter或digit开始letter other *11 return(getToken(), installId( ))9 10number → digit+ (.digit+)? (E (+ | -)? digit+)?digit Edigitdigitdigit开始12 digit13.14digit15E+/-16digit17 18other other other*19开始20delim21other*22delimdelim → blank | tab | newline ws → delim +北京大学信息科学技术学院手动编写词法分析程序：以relop 为例TOKEN getRelop ( ){ TOKEN retToken = new ( RELOP ) ;while ( 1 ) { /* 反复读入字符，直到return 或 遇到错误 */switch (state) {case 0 : c = nextChar ( ) ;if ( c == ' < ' ) state = 1 ; else if ( c == ' = ' ) state = 5 ; else if ( c == ' > ' ) state = 6 ; else fail ( ) ; /* 非关系算符 */ break ;case 1 : …… …… 2 =return(relop, LE) case 8 : retract ( ); retToken.attribute = GT; return (retToken); 开始1> < other3 return(relop, NE)4 * return(relop, LT)} 0= } >5 return(relop, EQ)} 2015年春季学期 《编译技术》课程= 6 other 7 return(relop, GE)8* return(relop 1, G 1T)首先通过正则表达式来描述词法单元的模式 基本目标：判断一个串s是否属于一个正则表达式R表示的语言s∈L(R)在现实中，还要能够连续识别多个不同类别的词法单元if (a == b) …(1)分别为每一类词法单元写出正则表达式R i(2)构造一个正则表达式R来匹配所有的词法单元R = R1 | R2 | … | R k(3)设输入为x1x2…x n, 对1≤i≤n，检查是否x1…x i∈L(R)(4)如果匹配成功，则存在j，使得x1…x i∈L(R j)(5)把x1…x i从输入中移走，继续执行（3）如何确定匹配的长度？有可能多个前缀都可以产生匹配解决办法：匹配最长可能的串选择哪个正则表达式来匹配？有可能多个正则表达式都可以匹配解决办法：排在前面的正则表达式优先匹配如果所有正则表达式都不能匹配怎么办？怎么报错？解决办法：可以构造一个ERROR正则表达式，放到所有表达式在后面，用来报告错误信息14Quiz：选择题使用如下的词法描述，在识别字符串“dictatorial” 的过程中会如何进行分割？dict (1)dictator (2)[a-z]* (3)dictatorial (4)a)4b)3c) 1, 3d) 2, 3内容提要词法分析器的作用词法单元的规约串和语言；正则表达式、正则定义 词法单元的识别☐词法分析器生成工具—LEX 有限自动机(Finite Automata)正则表达式到有限自动机词法分析器生成工具的设计Lex 简介Lex 是一种词法分析程序的自动构造工具。

正则表达式转dfa例题
正则表达式（Regular Expression）是描述字符串模式的一种方式，而确定有限状态自动机（DFA，Deterministic Finite Automaton）是一种用于识别正则表达式描述的字符串模式的计算机科学概念。

下面我将简要介绍一个例题，说明如何将正则表达式转换为DFA。

假设我们有一个简单的正则表达式，(a|b)abb.
首先，我们需要将正则表达式转换为NFA（Nondeterministic Finite Automaton），然后再将NFA转换为DFA。

1. 将正则表达式转换为NFA：
首先，我们需要将正则表达式转换为后缀表达式，然后根据后缀表达式构建NFA。

这里省略了具体的转换步骤，但需要注意的是，NFA中的状态表示了正则表达式中的每个字符或操作符。

2. 将NFA转换为DFA：
接下来，我们使用子集构造法（Subset Construction）将NFA转换为DFA。

这个过程涉及到状态的转移和状态的合并，最终得到一个等价的DFA。

在这个例题中，我们可以得到一个DFA，它包含了多个状态和状态之间的转移，最终可以用来识别符合正则表达式描述的字符串模式。

需要注意的是，正则表达式的复杂程度和特性会影响到转换的复杂程度，有些正则表达式可能会转换成更简单的DFA，而有些可能会比较复杂。

同时，转换过程中需要考虑一些特殊情况，比如空字符、闭包操作等。

希望这个简要的例题能够帮助你理解如何将正则表达式转换为DFA。

如果你对具体的转换步骤或其他相关内容有更多疑问，欢迎继续提问。

状态机分类
状态机是一种计算模型，它将计算过程看作状态的转换。

根据状态机的特性和实现方式的不同，我们可以将状态机分为以下几类：
1. 有限状态自动机（FSM）
有限状态自动机是最简单的状态机，它包含一组状态和一组转移条件。

在任何时候，状态机只能处于其中一个状态，而转移条件定义了从一个状态到另一个状态的转换。

有限状态自动机通常用于解决识别问题，例如正则表达式匹配。

2. 基于事件的状态机（EFSM）
基于事件的状态机扩展了有限状态自动机的转移条件，使其能够对事件做出响应。

事件可以是内部事件，例如超时或计数器溢出，也可以是外部事件，例如输入或输出。

基于事件的状态机通常用于实现协议或通信模型。

3. 层次状态机（HSM）
层次状态机是一种分层的状态机，它将状态和转移条件分组成层。

每一层都有自己的状态和转移条件，而底层状态机可以控制上层状态机的转换。

层次状态机通常用于处理复杂的控制流程，例如嵌入式系统或游戏引擎。

4. 反应式状态机（RSM）
反应式状态机是一种特殊的状态机，它可以对外部事件做出反应并改变其内部状态。

反应式状态机还可以将其状态和行为分成可
重用的模块，从而使状态机模型更加模块化和可扩展。

反应式状态机通常用于实现基于事件的系统和应用程序。

总之，状态机是一种强大的计算模型，可用于建模和实现各种计算问题。

通过了解不同类型的状态机，我们可以选择最适合特定问题的状态机实现方式。

hyperscan 原理
Hyperscan是一种高性能的正则表达式引擎，具有快速匹配大量模式
的能力。

它使用了多种优化技术，包括哈希表、DFA（确定有限状态
自动机）和SIMD（单指令多数据）指令集等。

在Hyperscan中，正则表达式被编译成一个DFA图（确定有限状态
自动机）。

该图由一组状态和转换组成，其中每个状态代表一个正则
表达式的子集。

当输入文本流经DFA时，它会在图中移动，并根据当前状态和输入字符来决定下一个状态。

如果当前状态是某个正则表达
式的最终状态，则匹配成功。

为了提高匹配速度，Hyperscan使用了哈希表来加速查找当前状态的
转换。

哈希表将每个状态映射到一个桶中，并且可以通过桶中的链表
来快速访问相邻的状态。

此外，Hyperscan还利用了SIMD指令集来并行处理多个字符。

这意
味着它可以同时比较多个字符，并在同一时钟周期内执行多个匹配操作。

这使得Hyperscan非常适合处理具有大量模式和长输入流的情况。

总之，Hyperscan是一种基于DFA图、哈希表和SIMD指令集的高
性能正则表达式引擎，具有快速匹配大量模式的能力。

它的优化技术使得它可以在处理大规模数据时保持高效率和高吞吐量。