Saber2pr's Blog

不确定下推自动机

解释:不确定下推自动机的状态是一个深度可自由伸缩的栈,无法枚举所有情况即不确定的状态

例如jsx语法解析,可以列出jsx的语法规则:

JSX
  = Text
  = OpenTag JSX CloseTag

很明显是一个长度不确定的栈,如果使用正则表达式去匹配JSX模式,如果是贪婪匹配将无法终止,如果是非贪婪匹配结果将不完整,例如:

<div>
  <span>
    text1
  </span>
</div>
<div>
  text2
</div>

使用正则:

/<[\w\W]*>/ // 贪婪,将匹配所有文本
/<[\w\W]*?>/ // 非贪婪,匹配不完整

正则的这两种匹配模式决定了只能处理有限状态,即不支持嵌套的语法

嵌套的语法需要手动记录出栈入栈,推荐使用parsec。