正则表达式基础

发表于   |  

主要参考陈梓瀚

历史

  • 神经元

    问题概述

  • 如何分析正则表达式
  • 如何扩展NFA以便表达正则表达式的高级功能（预查、捕获等）

    正则表达式的语法

  • 字符集合
  • 并联串联
  • 重复
  • 表达式引用
  • 正向预查
  • 反向预查
  • 匿名捕获
  • 命名捕获
  • 命名检查
  • 边界
  • 非贪婪匹配
    通过整理，得到以下几种元素及各自所需要的数据：
    •字符集合 ：一个范围的列表
    •串联 ：子树列表
    •并联 ：子树列表
    •重复 ：最小次数，最大次数，是否无限
    •左边界
    •右边界
    •功能 ：子树
    功能（正常、匿名捕获、正向预查、反向预查）
描述（表达式命名、表达式引用、命名捕获、命名检查）
名字

扩展正则表达式构造NFA

重复

正向预查/反向预查

匿名捕获/命名捕获

边界/命名检查

NFA压缩算法

贪婪匹配算法

捕获堆栈

每一个捕获堆栈的元素具有以下属性：
•名称（包括匿名）
•产生这个捕获元素的时候状态堆栈的深度
•捕获的起始位置
•捕获的长度

命令堆栈

每一个命令堆栈的元素具有以下属性：
•功能边
•参数
•前一个未终结指令在堆栈中的位置
•产生这个命令的字符串起始位置

状态堆栈

每一个状态堆栈的元素具有以下属性：
•NFA状态
•当前边序号
•状态产生的时候命令堆栈的深度
•字符串的起始位置

其他

回溯
  • 回溯处理分支
    • /h(ello|appy) world/.test(“hello bigbone, happy world”);
    • 上面一行正则表达式用于匹配”hello world”或者”happy world”
    • 测试一开始查找一个h,接下来走到分支，按从左到右执行原则，先查找ello
    • 走到bigbone时,”b”无法匹配”w”，开始回溯到之前的最后一个检查点，即匹配首字母”h”
    • 继续走分支”appy”，由于从首字母”h”开始没有匹配到”ha”,所以从首字母开始的匹配尝试都失败
    • 继续从第二字母”e”开始匹配正则，但是”e”无法匹配”h”，也失败
    • 重复上一步骤，直到第15个字母”h”，这是”happy”的首字母，匹配了正则首字符”h”
    • 接下来成功匹配”happy world”
  • 回溯处理重复量词
    • 贪婪重复
      • var str = “

        I’m page 1.

        I’m page 2.

        End.
        “;
      • /

        .*

        /i.test(str);
      • 上面的正则表达式用于匹配标签

        开始和标签

        结束的html
      • 由于*是贪婪匹配，所以再匹配了首字母

        后，直接匹配了除换行符以外的字符

      • 又由于指定了

        字符匹配，所以从末尾开始回溯<
      • 回溯到的<,’<’匹配’<’,继续匹配’/‘,但是’p’不能匹配’d’
      • 所以继续向前回溯到’2.

        ‘
      • 这时正则’

        ‘完全匹配字符串中的’

        ‘
      • 成功匹配结果 “

        I’m page 1.

        I’m page 2.

        “
    • 懒惰重复
      • var str = “

        I’m page 1.

        I’m page 2.

        End.
        “;
      • /

        .*?

        /i.test(str);
      • 因为懒惰匹配是最少匹配原则，零重复
      • 因此在匹配首字符

        后，优先跳过’.*?’，直接查找

      • 再继续匹配’.*?’
      • 结果就是”

        I’m page 1.

        “