【编译原理】词法分析：正则表达式与有限⾃动机基础
引⾔：
  编译语⾔设计的精髓在于⾃动化过程，即如果要设计⼀门编程语⾔，那么⼀定要设计⼀个⾃动化系统，能够⾃⾏读⼊分析程序员写⼊的程序，将其翻译为机器能够识别的指令等信息。当然⾼级语⾔的编译不是⼀蹴⽽就的，⽽是通过若⼲步的分解、规约、转换、优化，最后得到⽬标程序。
  具体的编译步骤如下：
  源程序就是我们写⼊的⾼级语⾔，编译的第⼀步叫做“词法分析”。词法分析的本质，就是要拆解出语句的每⼀个单词，然后对这个单词的类型进⾏辨识。
  ⾸先拿中⽂来举例。⽐如有⼀句话是“我喜欢你”，那么⾸先我们要把这句话拆成“我”、“喜欢”、“你”，然后再逐个分析他们的类型，得到“我”->主语；“喜欢”->谓语；“你”->宾语。这样我们就把这句话每个单词都分析出来了，也就完成了中⽂的“词法分析”。
  那么回到编程语⾔，它的词法分析就是将字符序列转换为单词（Token）序列的过程。翻译成俗话，就是把我们写的⼤⽚语⾔⽂本分解为⼀个⼀个单词，再输出每个单词的类型。举⼀个例⼦：
int p = 3 + a;
  这个语句⾮常简单，即定义⼀个变量p，它的初值为变量a与3的加和。那么接下来我们要对这个语句进⾏词法分析，⾸先我们要把这段⽂本拆解成单词，拆出来就是'int'、'p'、'='、'3'、'+'、'a'、';'。对这些单词再进⾏类型的辨识，那么就得到以下结果：
语素语⾔类型
int关键字
p标识符
=运算符
3数字
+运算符
a标识符
  这样我们就把这段⽂本中的每个单词的类型都分析出来了。乍⼀看⾮常简单对不对，对于⼈类⽽⾔你只需要⽤⾁眼就可以轻松观察出来每个单词的类型，但对于计算机⽽⾔，它可没有⼈类那样的智能。如果想要计算机能够识别并分析语素的类型，那就需要我们⼈类来为它构造⼀个⾃动化输⼊和分析的系统。
  构造⾃动系统的步骤主要分为如下⼏步：
  ①编写正则表达式（RE）
  ②将正则表达式转换为⾮确定有限⾃动机（NFA）
  ③将⾮确定有限⾃动机转换为确定有限⾃动机（DFA）
  ④将确定有限⾃动机最⼩化、规范化
  ⑤利⽤确定有限⾃动机编程
  那么接下来就介绍⼀下上述提到的这⼏个系统。
正则表达式：
  正则表达式的英⽂名称是Regular Expression，简称RE。我们先来看⼀下定义：正则表达式是对字符串操作的⼀种逻辑公式，就是⽤事先定义好的⼀些特定字符、及这些特定字符的组合，组成⼀个“规则字符串”，这个“规则字符串”⽤来表达对字符串的⼀种过滤逻辑。
  ⽤俗话来解释，就是正则表达式可以指定⼀种字符串的规则，只有满⾜相应规则的字符串才能与表达式相匹配。那么接下来介绍⼏种最简单的RE：
  ① a|b  ->  只有⼀个字符且⾮a即b
  ② ab  ->  字符串必须是ab连接
  上述两个⾮常基础，也很好理解。举个例⼦，单个数字的正则表达式就是0|1|2|3|4|5|6|7|8|9，即要想匹
配“单个数字”这个规则的内容，必须是⼀个数字且是0~9中的⼀个；两位数字的正则表达式就是10|11|12|...|99，不多赘述。接下来会有稍微复杂的表达式：
  ③(a|b)*  ->  有任意个(a|b)连接，例如正则化英文
  ④(a|b)+ ->  有⾮零个(a|b)连接
  ⑤(a|b)? ->  有零到⼀个(a|b)，相当于只有单个a 或单个b 或ε（空串）可以匹配
  ⑥[^ab]  ->  匹配⾮a⾮b的字符
  ⑦^ab    ->  匹配以ab开头的字符串
  ...
  其实还有很多种正则表达类型，但是⽂法分析⽤不到那么复杂的，因此就没再列了。对上述规则熟悉后，我们便可以⽤正则表达式来表达⼀些我们想要匹配的字符串类型。例如我们想匹配规范的偶数，那么我们就可以这样设计正则表达式：
(1|2|3|4|5|6|7|8|9)?(0|1|2|3|4|5|6|7|8|9)*(0|2|4|6|8)
  即⾸位不能是零，中间位可以是任意个数的任意数字，末位必须是偶数的数字。
  再举⼀个：以a开头和结尾的⼩写字母串，那么正则表达式就是：
a((a-z)*a)?
  即确定a为开头，后⾯内容可有可⽆，如果后⾯有内容，那么必须强⾏a结尾。这⾥要提⽰的是，像上述的正则表达式我们都是根据题意下意识直接构造的，它并不规范，具有很强的不确定性。规范确定的正则表达式也叫正规表达式，之后会介绍这部分内容，这⾥只是做个提⽰。
⾮确定有限⾃动机：
  上⽂我们使⽤正则表达式把要匹配的⽂本模式表⽰了出来，但是RE也并⾮计算机能够直接识别的内容，因为计算机对于*、+这些符号的反应机制很难构造。这⾥我们要引⼊⼀个新东西：⾃动机（Automata）。⾃动机这个东西其实很好理解，如下图：
  ⾃动机共由5部分组成，分别是状态集合S、输⼊字符Σ、状态转移函数f、初态S0、终⽌态Z，即状态⾃动机M=
(S,Σ,f,S0,Z)。对于上图⽽⾔：
  S={休息，Coding，加班Coding，卒}
  Σ={上班，下班，需求完成，产品经理脑洞⼤开，过劳}
  S0=休息
  Z={卒}          ps：终态可以不唯⼀
  f是⼀系列映射的集合，映射就是某状态获得某输⼊后转移到某新状态的意思。
  在这个⾃动机中，最开始是休息状态，获得上班的输⼊以后就会转移到Coding的状态，以此类推，当状态变为卒时，便可以终⽌该⾃动机的运⾏。
  如果⼀个⾃动机的状态是有限的，那么我们称其为有限状态机（Finite Automata，简称FA）。但是存在这么⼀种状态机，它存在下述两种情况：
  ①同⼀个状态获得同⼀个输⼊，却转移到多个不同的输出状态；
  ②状态的输⼊存在ε-边，即⽆条件状态转移。
  下⾯我们可以看⼀下这两个例⼦：
  特点还是⽐较明显的。图1的状态0获得输⼊a后，分别指向了状态0和状态1；图2中的状态A可以⽆条件转移到状态B，状态B⼜⽆条件转移到状态C。当⼀个有限⾃动机存在这些特点时，这个⾃动机是不稳定的、不确定的，ε-边的存在导致了状态不稳定性，多重输出的存在导致了状态转移的不确定性。含有这些特点的状态机我们叫做⾮确定有限⾃动机
（Nondeterministic Finite Automata，简称NFA）。
  那么，为什么要先介绍NFA这种存在瑕疵的⾃动机呢？这是因为当我们拿到正则表达式RE后，能直接构造出来的状态机就是⾮确定的。接下来我们来了解⼀下如何将RE转化为NFA。
  ⾸先我们来看⼀些NFA的转化规则：
  简⽽⾔之就是：遇到连接字符串，则分离字符；遇到或符号，则分多条路；遇到*号，则创建ε-边进⼊
到⼀个“⾃循环”状态。运⽤这个规则，我们就可以对(a|b)*(aa|bb)(a|b)*这种正则表达式进⾏NFA转换了，如图3下半张图就是(a|b)*(aa|bb)(a|b)*这个正则表达式对应的NFA结果。仔细观察可以看到，ε-边和多重输⼊的状态是很难避免的，因此我们说从RE转成的FA绝⼤部分情况会是NFA。
确定有限⾃动机：
  与NFA对⽴，确定有限⾃动机（Deterministic Finite Automata，简称DFA）就要具备两个条件：不能存在ε-边，不能存在相同输⼊的多状态转移，例如：
  图中的DFA对于每个状态⽽⾔，⼀种输⼊只能有⼀个固定的去向，消去了NFA多重状态转移的问题。那么，如何证明这个DFA和原来的NFA是等价的呢？我们可以测试所有输⼊，然后检查两个⾃动机是否有相同的匹配结果。例如在NFA中输⼊bbabb可以进⼊到终态，在DFA中输⼊bbabb同样可以到终态。对于所有的输⼊都有相同的匹配结果，那么这个DFA和NFA 就是等价的。
  判断不难判断，但NFA转换为等价DFA这个⼯作可不是随便画两笔就能完成的。这⾥我们要引⼊⼀个新的概念：ε-闭包
（ε-closure）。什么是ε-闭包呢，就是某个状态通过若⼲步ε-边转移以后，所能到达的所有状态集合。ε-closure(A)的意思就是从A状态出发，经过⽆限次ε-边转移以后所能经过的所有状态。举个实例：
  这个图⾥⾯，如果要求ε-closure({5})，那么我们就从状态5出发，不断⾛ε-边，易得经过的状态有5、6、2（必须包括5⾃⼰）。这样{5,6,2}就是ε-closure({5})所求的闭包集合。
  ⼤家⼀定猜到闭包的实质是在⼲嘛了：因为DFA要求没有ε-边，因此我们就把有ε-边连接的⼏个状态给划分为⼀团（即闭包），这样ε-边只会出现在这个闭包内。如果我们把闭包定义为新的状态，那么这个闭包内部的ε-边⾃然就没了。拿刚才的ε-closure({5})举例，5、6、2之间有很多ε-边，现在我们把5、6、2塞到⼀团⾥成为⼀个闭包，然后再把这个闭包定义为⼀个新状态，那么ε-边就成功消除了。
  好，现在ε-闭包可以帮助我们消去ε-边，但现在还有⼀个问题没解决，那就是单输⼊出现多状态转移的问题。针对这个问题，我们的解决⽅式依然是闭包，只不过这回不是ε-闭包，⽽是a-闭包、b-闭包、c-闭包...（其中abc都是输⼊）
  a-闭包的定义可以仿照ε-闭包，即对于某状态集，经过⼀步a转换后所能经过的状态的集合（注意是⼀步，不再像ε-闭包那样是任意步），然后对这些状态分别再求ε-闭包。这个可能有点绕，拿刚才的图举例⼦，如果要求a-closure({1,2})，那么⾸先我们对状态1和2分别输⼊a，得到的是{3,4,5}，然后再对{3,4,5}求ε-闭包，得到的就是{3,4,5,6,2,8,7}，这样{3,4,5,6,2,8,7}就成为了⼀个新的闭包和状态。
  a-闭包解决多状态转移的思路与ε-闭包解决ε-边的思路⾮常相似。由于有的状态输⼊a以后有多个状态转移，那我直接把这多个去向划分为⼀团（即闭包），这样多重a-边转移就只会出现在闭包内，再把闭
包转换为⼀个新状态，那么多重转移就消除了。
  上图是⼀个NFA转DFA的例⼦。⾸先我们第⼀个闭包选择初态p的ε-闭包，发现结果就是p，那么我们把这个ε-闭包结果作为新的状态0放到I列中。接下来我们要对这个新状态0分别求0-闭包和1-闭包：p输⼊0以后能到达的状态是q和s，再对q和s 求ε-闭包发现还是q和s，那么{q,s}就是状态0的0-闭包。这时发现{q,s}是⼀种新的状态（未在I列出现），我们要把这些新的状态添加到I列中，然后不断重复上述⼯作，直到状态不再增加为⽌。
  此时新的状态已经出来了，那么每个状态经过输⼊以后转移到什么状态也就出来了，例如上表状态0输⼊0以后转移到状态1，输⼊1以后转移到状态2，以此类推，然后我们就可以轻松构建出⼀个DFA⾃动机了。
DFA最⼩化：
  DFA的成功建⽴意味着可以进⾏编程⼯作了，只要编码完成计算机便拥有了分析输⼊串的能⼒。但是有时候我们得到的
DFA⾮常庞⼤，其中不乏⼀些⽆⽤状态。因此我们需要精简DFA，去掉⼀些⽆⽤状态，将⼀些等价状态进⾏合并。
  在最开始，我们将所有状态划分为两个闭包，⼀个是终结态闭包，包含了所有终结状态；⼀个是⾮终结态闭包，包含了所有⾮终结状态。对于闭包内部，我们可以进⼀步进⾏划分：当同⼀闭包内的两个状态不是等价状态时，它们就可以划分为不同的闭包。
  什么叫等价状态呢？这词是我编的，定义如下：如果两个状态对于所有输⼊，最后转移到的闭包相同，那么两个状态就是等价的，可以进⾏合并。举个例⼦：
  按照上述规则，⾸先我们把这⼏个状态分为终结态闭包{0,1}和⾮终结态闭包{2}，对于{0,1}这个闭包进⾏测试：当输⼊a 时，0和1指向的都是⾃⾝闭包；当输⼊b时，0和1指向的都是2那个闭包，即满⾜“对于所有输⼊，最后转移到的闭包相同”，因此我们说0和1是等价状态，可以合并：
　可以看到原来的0和1就合并为了新的0，整个⾃动机少了⼀个冗余的状态，这样我们就得到了⼀个精简化的DFA。接下来我们可以对DFA进⾏编程，这应该相对⽐较容易（但是码量很庞⼤），因此就不再多赘述了。
⼩结：
  词法分析的关键在于正则表达式的准确构造、NFA的建⽴、NFA与DFA的转化以及DFA的最⼩化，这样便将⼀个符号表达式转化为⼀个计算机可⾃动读⼊、分析输⼊串的⾃动机程序。词法分析的结果是分离的tokens和属性，那么如何判断这些属性的搭配是否合理呢？那就涉及到编译原理的下⼀层——语法分析了。语法分析的难度将会更上⼀层，只有认真体会设计思想、多思考多练习，才能将编译原理学习得更加深⼊。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。