美文网首页
第八章 匹配原理

第八章 匹配原理

作者: 马小跳_ | 来源:发表于2018-12-20 21:11 被阅读9次

    8.1 有穷自动机

    正则表达式能迅速进行复杂处理的秘密就在于,它采用了一种特殊的理论模型:有穷自动机(finite automata),也叫做有穷状态自动机(finite-state machine)。这种机器具备有限个状态,可以根据不同条件在状态之间转移。
    严格的说起来,有穷自动机必须满足4个条件:

    1. 具有有限多个状态
    2. 有一套状态转移函数(规则)
    3. 有一个开始状态
    4. 有一个或多个最终状态

    8.2 正则表达式的匹配过程

    正则表达式所使用的理论模型就是有穷自动机,其具体实现称为正则引擎(regex engine)。用正则表达式处理字符串,首先需要生成自动机(“编译”正则对象);之后无论输入什么字符串,正则引擎都只需要老老实实地在状态之间游走。

    8.3 回溯

    比起DFA,NFA看起来足够“麻烦”:它的状态是不确定的,这有点像走迷宫,越走岔路口越多,最后不会迷路吗?

    不过,NFA的正则引擎自有办法:如果有多个可能的状态,它们会在选择时记录下这些状态备用,然后才选择其中某个状态尝试;如果之后遇到死路,则退回去,选择最近一次记录的且未尝试过的状态;如果又遇到死路,再选择最近一次记录的且未尝试过的状态...

    这有点像在分岔路口留下标记——如果我们在遇到的每个分岔路口都留下标记,即使前头是死路,也可以根据标记返回,而不会迷路。

    8.4 NFA和DFA

    根据状态的确定与否,一般我们会把有穷自动机(正则引擎)分为两类:一类是确定型有穷自动机(definite finite automata,简称DFA),在任何时刻,它所处的状态是确定无疑的;另一台是非确定型有穷自动机(non-definite finite automata,简称NFA),在某个时刻,它所处的状态可能是不确定的。

    相关文章

      网友评论

          本文标题:第八章 匹配原理

          本文链接:https://www.haomeiwen.com/subject/pbiukqtx.html