首页 > 代码库 > 南瓜不说话(M01)-正则表达式原理

南瓜不说话(M01)-正则表达式原理

      1.     文法
              1. 一个文法可以用一个四元来定义,G = {Vt,Vn,S,P}

              Vt:一个非空有限的符号集合,它的每个元素称为终结符号;

    1.        Vn:一个非空有限的符号集合,它的每个元素称为非终结符号,并且Vt∩Vn=Φ;
    2.       S∈Vn,称为文法G的开始符号;
    3.        P是一个非空有限集合,它的元素称为产生式;
    4.        产生式是指,其形式为α→β,α称为产生式的左部,β称为产生式的右部,符号“→”表示“定义为”,并且α、β∈(Vt∪Vn)*,α≠ε,即α、β是由终结符和非终结符组成的符号串;
    5.        开始符S必须至少在某一产生式的左部出现一次;

                文法可推导的语言标记为L(G);

                根据对产生式所施加的限制的不同,把文法分成0型、1型、2型和3型四种类型。

                    1.                 0型文法要求至少含有一个非终结符,基本没有什么限制,一个非常重要的理论结果是:0型文法的能力相当于图灵机
                1.                 1型文法也叫上下文有关文法,对应于线性有界自动机,要求每个产生式α→β,都有|β|>=|α|,|β|指长度;
                2.                 2型文法也叫上下文无关文法,对应于下推自动机,要求在1型文法的基础上,再满足:每一个α→β都有α是非终结符;
                3.                 3型文法也叫正则文法,它对应于有限状态自动机。它是在2型文法的基础上满足:A→α|αB(右线性)或A→α|Bα(左线性)。
                4.                1型文法是0型文法的一个子集,2型文法是1型文法的一个子集,,3型文法是2型文法的一个子集

                3型文法(正则文法)与正则表达式(Regular Expression)是等价的,任意一个正则文法总是可以转化成一个等价的正则表达式。同时正则表达式与有限自动机是等价的。

                一个能由有限自动机识别的语言,必然可以用正则表达式来表示,而一个用正则表达式表示的语言一定可以用一个有限自动机来识别。

                 

                有限状态自动机

                有限自动机分为多种最常见的是:确定型有限自动机(DFA)和非确定型有限自动机(NFA)两种;  

                DFA的文法描述是:G = {S,ε, f,S0,Z} NFA的文法描述是:M = {S,ε, f,S0,Z}
                S:一个非空有限的输入符号集合; S:一个非空有限的输入符号集合;
                ε:使状态改变的输入符号集合; ε:使状态改变的输入符号集合;
                f:映射; f:映射;
                S0:初始状态; S0:初始状态集合;
                Z:终止状态; Z:终止状态;

                f(S,a)=G的描述是:初始S状态再输入a的条件下转化到G状态:未标题-1

                每一个NFA都可以转化为一个DFA如图:

                IMG_20141213_143811[1]

                DFA和NFA的效率差异

                很容易理解,构造DFA的代价远大于NFA,假设NFA的状态数为K,那么等价DFA的状态数目理论上可达2的k次方,不过实际上几乎不会出现这么极端的情况,

                可以肯定的是构造DFA会消耗更多的时间和内存。

                但是DFA一旦构造好了之后,执行效率就非常理想了,如果一个串的长度是n,那么匹配算法的执行复杂度是O(n);而NFA在匹配过程中,存在大量的分支和回朔,

                假设NFA的状态数为s,因为每输入一个字符可能达到的状态数做多为s,那么匹配算法的复杂度及时输入串的长度乘以状态数O(ns)。

                正则表达式的NFA&DFA构造、转化、简化有一整套理论及方法,远比上面的例子复杂,本文仅通过一个简单的例子来说明原理。

                     NFA:表达式主导

                从表达式的第一个部分开始,每次检查一部分,同时检查当前文本是否匹配表达式的当前部分,如果是,则继续表达式的下一部分,如此继续,

                直到表达式的所有部分都能匹配,即整个表达式匹配成功。

                我们来看表达式 to(nite|knight|night) 匹配文本 ...tonight... 的过程: 表达式的第一个部分是t,它会不断重复扫描,直到在字符串中找到t,

                之后就检查随后的o,如果能匹配就继续检查下面的元素。这个例子中,下面的元素是(nite|knight|night) ,意思是nite或者knight或者night,引擎

                会依次尝试这三种可能。

                整个过程,控制权在表达式的元素之间转换,因此被称之为“表达式主导”。“表达式主导”的特点是每个子表达式都是独立的,不存在内在联系。

                子表达式与整个正则表达式的控制结构(多选、量词)的层级关系控制了整个匹配过程。

                      DFA:文本主导

                DFA在读入一个文本的时候,会记录当前有效的所有匹配的表达式位置(这些位置集合对应于DFA的一个状态)。以上面的匹配过程为例:

                1.        当引擎读入文本t时,记录匹配的位置是 t o(nite|knight|night);
                2.        接着读入o,匹配位置t o (nite|knight|night);
                3.        读入n,匹配位置to( n ite|knight| n ight),两个位置,knight被淘汰出局;
                4.        ...

                这种方式被称之“文本主导”是因为被扫描的字符串,控制了引擎的执行过程。

                     差异之一:NFA表达式影响引擎

                NFA表达式主导的特性,使得通过修改正则表达式来影响引擎,因此下面三个表达式尽管能够匹配同样的文本,但是引擎的执行过程各不相同:

                1.        to(nite|knight|night)
                2.        tonite|toknight|tonight
                3.        to(k?night|nite)

                但是对于DFA来说,没有任何区别。

                     差异之二:DFA能保证最长匹配

                对于包含或选项的表达式,NFA在成功匹配一个选项之后可能报告匹配成功,此时并不知道后面的选项是否也会成功,是否包含一个更长的匹配。

                假设使用 one(self)?(selfsufficient)? 来匹配 oneselfsufficient ,NFA首先匹配one,然后匹配self,此时发现 selfsufficient 无法匹

                配剩余子串,但是这个子表达式不是必须的,因此可以立即返回成功,此时匹配的串为 oneself

                实际上NFA引擎的匹配结果与具体实现有关,而DFA必然会成功匹配oneselfsufficient

                     差异之三:NFA支持更多功能

                NFA能够支持“捕获group”,“环视”,“占有优先量词”,“固话分组”等高级功能,这些功能都基于“子表达式独立进行匹配”这一特点。

                而DFA无法记录匹配历史与子表达式之间的关系,因而也无法实现这些功能。

                可见NFA引擎具备更大的实用价值,因而,我们在编程语言里面使用的正则表达式库都是基于NFA的。java的Pattern就是基于NFA的,Pattern.compile()

                方法显然就是在构造NFA状态图。

      1.      参考:    http://www.cnblogs.com/longhuihu/p/4128203.html

南瓜不说话(M01)-正则表达式原理