一、前言
在语言处理的例程中，有穷自动机可以设计用来识别有效的字符串的处理器，而正则语言和有穷自动机是等价的，每一个正则语言都可以用一个有穷自动机接受，因此词法分析的要旨在于构造正则文法，生成有穷自动机和自动机的推演。
二、基本概念
形式文法：形式文法是一个有序的四元组G = <V,T,S,P>，其中V是一个非空的有穷集合，它的元素称作变元或非终结符；T是一个非空的有穷集合且V∩T=ø，T的元素称作终结符；S∈V称作起始符号；P是一个非空的有穷集合，它的元素称作产生式或改写规则，形如：α→β，这里α,β∈（V∪T）*。
正则文法：在以上的形式文法的定义中，如果G中P的形式如下：A→αB，A→α（右线性）或者A→Bα，A→α（左线性），其中A,B∈V,α∈T*，那么该形式文法成为正则文法。
非确定有穷自动机：是一个有序的五元组M=<Q,∑,δ,q,F>，其中Q是非空的有穷的状态集合；∑是非空有穷的输入字母表；δ:Q×∑→P(Q)是状态转移函数；q∈Q是初始状态；F∈Q是终结状态集合。
三、正则表达式
正则表达式描述了一个字符子串的匹配的模式，用于从一个字符串中提取匹配的子串。正则表达式由普通字符、转义字符、限定字符和操作字符组成，表述如下：
|
普通字符 |
含义 |
|
a,z,A,Z… |
普通字母字符 |
|
0,9 |
普通数字字符 |
|
@,#,.. |
其他可打见字符 |
|
\b,\r,\n,\v,\t,\0 |
空格符、换行符、制表符、终结符等 |
|
转义字符 |
含义 |
|
\ |
将保留字符转义为普通字符，如\| ,\(,\[,\],\*,\+,等 |
|
限定字符 |
含义 |
|
* |
限定匹配零次或多次，如a*，(ab)* |
|
+ |
限定匹配一次或多次，如a+，[ab]+ |
|
? |
限定匹配零次或一次，如a? |
|
{n} |
限定匹配N次，如a{3} |
|
操作字符 |
含义 |
|
| |
或操作，a|b匹配a或b的串 |
|
^ |
非操作，^a匹配不含a的串 |
|
[] |
含操作，[abc]匹配含有abc任一字符的串 |
|
- |
范围操作,a-z之居于a,z之间包括a,z的任意字符 |
|
() |
优先操作,ab*为abb…，(ab)*为abab… |
四、正则表达式的解析
正则表达式的解析的目的是将正则表达式推导成为非确定的有穷状态机，即生成输入字母表、状态转移函数、状态集合（初始状态、中间状态和终结状态）。
在推导之前，先定义一些必要的存储结构来保存相关的推导数据：
词串判定树（TREE）：输入字母表的判定表达式。
有向图（GRAPH）：节点为状态集合，有向边代表状态转移，边的权值对应词串列表中的判定表达式。
这里用一个简单的数值的正则式(\-|+)?[0-9]*.?[0-9]*来说明它的推导过程：
第一步、正则式例子中可以提取出如下词串，(\-|+)?表示零个或一个正负号，[0-9]*表示可重复N次的数字，.?表示零个或一个小数点，[0-9]*表示可重复N次数字，姑且把以上词串称为一个解析单元，可以看出一个解析单元由N个普通字符、0或N个操作符和一个限定符组成。没有限定符的，为它附加一个限定符，比如ab解析为(ab){1}。
第二步、解析单元提取后，将他普通字符和操作符的组合词串转换为规则的判定式，比如：(\-|+) 转换为 (OR)[-][+]，[0-9]转换为 (BET)[0][9]，[abc]转换为(IN)[a][b][c]，(ab)转换为：(IS)[ab]，嵌套类型的词串([0-9]|[A-z])可以转换为：(OR)[sub1][sub2] sub1转换为：(BET)[0][9] sub2转换为：(BET)[A][z]。判定式的格式为：(操作符号)[字串1][字串2]…，其中IS为一元操作，BET为二元操作，OR、IN为多元操作。判定式存储在判定树中。
第三步、为每个解析单元生成一个中间状态，加上初始状态和终结状态，生成有向图的节点。有向边的推导按如下规则：首先从初始状态到终结状态依次建立一条有向边，贯通节点序列，然后根据限定符的含义，推导其他有向边，限定符*和?表示零次或多次匹配，因此除了为该节点生成环路外，还需要回溯到所有含有零次匹配前继节点，为这些前继节点和它的后继节点生成有向边，限定符+和{n}表示一次或多次匹配，除了生成环路，不需要回溯处理，匹配的限定次数可以存储在有向边的权值结构中。
根据以上步骤，上述数值正则式可以解析成如下结果：
输入字母的判定树：TN_1: (OR)[-][+] TN_2: (BET)[0][9] TN_3: (IS)[.] TN_4: (BET)[0][9]，这里还需要引入一个终结符NIL来代表词串结束。
状态转移的有向图：GN_0(开始状态) GN_1 GN_2 GN_3 GN_4 GN_5(结束状态)
初始序列生成的有向边：(GN_0,GN_1,TN_1) (GN_1,GN_2,TN_2) (GN_2,GN_3,TN_3) (GN_3,GN_4,TN_4) (GN_4,GN_5,NIL)
由GN_1推导的有向边：(GN_0,GN_2,TN_2)
由GN_2推导的有向边：(GN_2,GN_2,TN_2) (GN_1,GN_3,TN_3) (GN_0,GN_3,TN_3)
由GN_3推导的有向边：(GN_2,GN_4,TN_4) (GN_1,GN_4,TN_4) (GN_0,GN_4,TN_4)
由GN_4推导的有向边：(GN_4,GN_4,TN_4) (GN_3,GN_5,NIL) (GN_2,GN_5,NIL) (GN_1,GN_5,NIL) (GN_0,GN_5,NIL)
这样，我们基本完成了正则式的解析，建立了可用于计算机推演的输入字母表、状态转移函数和状态集合的数据结构。
五、正则表达式的应用
正则表达式的最常见的应用是匹配词串，根据以上的推导，某一词串如果被正则式接受，那么它在有向图中至少存在一条从开始状态到结束状态的路径，因此匹配的过程实质上是搜索路径的过程，搜索策略是深度优先。
这里，还是用以上的数值正则式来举例，说明它的匹配过程：
词串 –12.4 ，扫描头在匹配过程中依次读入 – 1 2 . 4 NIL
读入 - ：当前状态为GN_0，由GN_0出发的边有(GN_0,GN_1,TN_1) (GN_0,GN_2,TN_2) (GN_0,GN_3,TN_3) (GN_0,GN_4,TN_4) (GN_0,GN_5,NIL) 符合判定的有TN_1，因此择取(GN_0,GN_1,TN_1) 状态转为GN_1
读入 1：当前状态为GN_1，由GN_1出发的边有(GN_1,GN_2,TN_2) (GN_1,GN_3,TN_3) (GN_1,GN_4,TN_4) (GN_1,GN_5,NIL) 符合判定的有TN_2、TN_4，先择取(GN_1,GN_2,TN_2) 状态转为GN_2
读入 2：当前状态为GN_2，由GN_2出发的边有(GN_2,GN_2,TN_2) (GN_2,GN_3,TN_3) (GN_2,GN_4,TN_4) (GN_2,GN_5,NIL) 符合判定的有TN_2、TN_4，先择取(GN_2,GN_2,TN_2) 状态仍为GN_2
读入 .：当前状态为GN_2，由GN_2出发的边有(GN_2,GN_2,TN_2) (GN_2,GN_3,TN_3) (GN_2,GN_4,TN_4) (GN_2,GN_5,NIL) 符合判定的有TN_3，择取(GN_2,GN_3,TN_3) 状态转为GN_3
读入 4：当前状态为GN_3，由GN_3出发的边有(GN_3,GN_4,TN_4) (GN_3,GN_5,NIL) 符合判定的有TN_4，择取(GN_3,GN_4,TN_4) 状态仍为GN_4
读入 NIL：当前状态为GN_4，由GN_4出发的边有(GN_4,GN_4,TN_4) (GN_4,GN_5,NIL) 符合判定的有NIL，择取(GN_4,GN_5,NIL) 状态转为GN_5
扫描停止于NIL，当前状态为GN_5为终结状态，因此词串 –12.4可以接受，即存在一条(GN_0,GN_1,TN_1) (GN_1,GN_2,TN_2) (GN_2,GN_2,TN_2) (GN_2,GN_3,TN_3) (GN_3,GN_4,TN_4) (GN_4,GN_5,NIL)由初始状态到终结状态的可达路径。
再举一个例子，词串 23A ，扫描头在匹配过程中依次读入 2 3 A NIL
读入 2 ：当前状态为GN_0，由GN_0出发的边有(GN_0,GN_1,TN_1) (GN_0,GN_2,TN_2) (GN_0,GN_3,TN_3) (GN_0,GN_4,TN_4) (GN_0,GN_5,NIL) 符合判定的有TN_2、TN_4，先择取(GN_0,GN_2,TN_2) 状态转为GN_2
读入 3：当前状态为GN_2，由GN_2出发的边有(GN_2,GN_2,TN_2) (GN_2,GN_3,TN_3) (GN_2,GN_4,TN_4) (GN_2,GN_5,NIL) 符合判定的有TN_2、TN_4，先择取(GN_2,GN_2,TN_2) 状态仍为GN_2
读入 A：当前状态为GN_2，由GN_2出发的边有(GN_2,GN_2,TN_2) (GN_2,GN_3,TN_3) (GN_2,GN_4,TN_4) (GN_2,GN_5,NIL) 没有符合判定的节点，扫描头回溯，当前状态重置为GN_2
读入 3：当前状态为GN_2，由GN_2出发的边有(GN_2,GN_2,TN_2) (GN_2,GN_3,TN_3) (GN_2,GN_4,TN_4) (GN_2,GN_5,NIL) 符合判定的有TN_2、TN_4，TN_2已被淘汰，因此择取(GN_2,GN_4,TN_4) 状态转为GN_4
读入 A：当前状态为GN_4，GN_4出发的边有(GN_4,GN_4,TN_4) (GN_4,GN_5,NIL) 没有符合判定的节点，扫描头回溯，当前状态重置为GN_2
读入 3：当前状态为GN_2，由GN_2出发的边有(GN_2,GN_2,TN_2) (GN_2,GN_3,TN_3) (GN_2,GN_4,TN_4) (GN_2,GN_5,NIL) 符合判定的有TN_2、TN_4，TN_2、TN_4均被淘汰，扫描头回溯，当前状态重置为GN_0
读入 2 ：当前状态为GN_0，由GN_0出发的边有(GN_0,GN_1,TN_1) (GN_0,GN_2,TN_2) (GN_0,GN_3,TN_3) (GN_0,GN_4,TN_4) (GN_0,GN_5,NIL) 符合判定的有TN_2、TN_4，TN_2已被淘汰，因此择取(GN_0,GN_4,TN_4) 状态转为GN_4
读入 3：当前状态为GN_4，GN_4出发的边有(GN_4,GN_4,TN_4) (GN_4,GN_5,NIL) 符合判定的有TN_4，择取(GN_4,GN_4,TN_4) 状态仍为GN_4
读入 A：当前状态为GN_4，GN_4出发的边有(GN_4,GN_4,TN_4) (GN_4,GN_5,NIL) 没有符合判定的节点，扫描头回溯，当前状态重置为GN_4
读入 3：没有边可择取，扫描头回溯，状态重置为GN_0
读入 2：没有边可择取，扫描头回溯，停机，当前状态为GN_0，因此23A未能接受。
以上例子还有一个没有提及的要点是由限定符{n}推导环路次数限定，我们可以作如下处理：在边的权值结构中引入环路限定数，0为没有限定，n>0为n次限定，当择取该条边后n减1，当n为0时淘汰该边。
六、后记：
以上的推导可以很容易地转化为程序结构，在此不再赘述。
发表评论 
打印本文
推荐本文
加入收藏
返回顶部
关闭窗口
