那么传统的自顶向下的解析器就能很好地工作

  一定要先看看第7部分!如果您第一次遇到这个系列,您可以在本文顶部找到其余的帖子。

  Packrat(PEG)

  Packrat经常与正式语法PEG相关,因为它们是由同一个人Bryan Ford发明的。Packrat在他的论文中首先被描述了:Packrat Parsing:具有回溯的实用线性时间算法。标题说几乎所有我们关心的事情:它有一个线性的执行时间,不使用回溯。

  其效率的另一个原因是记忆:在解析过程中存储部分结果。缺点是,直到最近才使用该技术的原因是存储所有中间结果所需的内存数量。如果所需的内存超过了可用的内存,算法将失去执行的线性时间。

  Packrat也不支持左递归规则,因为PEG需要总是选择第一个选项。实际上,一些变体可以支持直接的左递归规则,但是以牺牲线性复杂性为代价。

  如果需要的话,Packrat解析器可以执行无限量的lookahead。这会影响执行时间,在最坏的情况下可能是指数级的。

  递归下降解析器(Recursive Descent Parser)

  递归下降解析器是一个解析器,它与一组(相互)递归过程一起工作,对于语法的每个规则通常是一个过程。因此,解析器的结构反映了语法的结构。

  termpredictive解析器以几种不同的方式使用:有些人把它作为自顶向下解析器的同义词,有些人认为它是从不回溯的递归下降解析器。

  第二个含义的反义词是一个递归下降解析器,它会回溯。也就是说,通过依次尝试每一个规则,然后每次失败就返回,找到与输入相匹配的规则。

  通常,递归下降解析器在解析左递归规则时会遇到问题,因为算法会一次又一次地调用同一个函数。这个问题的一个可能的解决方案是使用尾递归。使用此方法的解析器称为尾递归解析器。

  尾递归本身只是在函数结束时发生的递归。然而,尾部递归与语法规则的转换一起使用。转换语法规则和在过程结束时进行递归的组合允许处理左递归规则。

  Pratt解析器

  Pratt解析器是一个广泛未使用的,但非常值得赞赏的(由少数人知道的),由Vaughan Pratt在一篇名为“Top Down Operator Precedence”的论文中定义的解析算法。本文首先从BNF语法的论战开始,笔者认为错误的是解析研究的唯一问题。这是缺乏成功的原因之一。实际上,该算法不依赖于语法,而是直接对tokens进行操作,这使解析专家变得不同寻常。

  第二个原因是,如果你有一个有意义的前缀来帮助区分不同的规则,那么传统的自顶向下的本科证书解析器就能很好地工作。例如,如果您得到token FOR,您正在查看for语句。由于这基本上适用于所有的编程语言及其语句,所以很容易理解为什么Pratt解析器没有改变解析世界。

  Pratt算法的亮点在于表达式。事实上,优先的概念使得不可能仅仅通过查看tokens的顺序来理解输入的结构。

  基本上,该算法要求您为每个运算符token分配一个优先值,并根据token的左侧和右侧确定要执行的操作。然后,它使用这些值和函数在遍历输入的同时将操作绑定在一起。

  虽然Pratt算法没有公开地成功,但它用于解析表达式。JSLint也为Douglas Crockford(JSON成名)所采用。

  解析器组合器

  解析器组合器是一个高阶函数,接受解析器函数作为输入,并返回一个新的解析器函数作为输出。解析器函数通常意味着接受一个字符串并输出解析树的函数。

  解析器组合器是模块化的并且易于构建,但是它们也比较慢(在最坏的情况下它们具有O(n4)复杂性)并且不太高端。它们通常被用于更简单的解析任务或原型设计。从某种意义上说,解析器组合器的用户部分手动构建解析器,但依赖于创建解析器组合器的人所做的艰苦工作。

  通常,它们不支持左递归规则,但是有更高级的实现可以做到这一点。例如,参见用于模糊左递归语法的解析器组合器,其也设法描述具有执行多项式时间的算法。

  许多当代实现被称为monadic解析器组合器,因为它们依赖于称为monad的函数式编程的结构。Monad是一个相当复杂的概念,我们不能在这里解释。但是,monad基本上可以将依赖于数据类型的功能和操作组合起来。关键的特点是数据类型指定如何组合不同的值。

  最基本的例子是Maybe monad。这是一个正常类型的包装器,比如整数,在值有效的时候(567)返回值本身,当它不是时(即未定义或被零除),则返回一个特殊的值Nothing。因此,你可以避免使用空值,并毫不客气地崩溃程序。相反,Nothing值是正常管理的,就像管理任何其他值一样。

  请继续关注第9部分!

上一篇:容器服务中的节点失效时Docker容器重新调度介绍


下一篇:SAP Fiori Elements里的Smart Table工作原理解析