(0) 阅读 (1080)

解析器组合器 编辑

词条创建者 匿名用户

解析器组合器

编辑

计算机编程中,解析器组合器是一个高阶函数,它接受几个解析器作为输入并返回一个新的解析器作为其输出。在这种情况下,解析器是一个接受字符串作为输入并返回一些结构作为输出的函数,通常是一个解析树或代表解析成功停止的字符串中的位置的一组索引。解析器组合器实现了一种递归下降的解析策略,有利于模块化的分片构建和测试。这种解析技术被称为组合式解析。使用组合器的解析器已被广泛用于特定领域语言的编译器和处理器的原型设计,如数据库的自然语言界面,其中复杂多样的语义动作与句法处理紧密结合。1989年,RichardFrost和JohnLaunchbury展示了使用分析器组合器来构建自然语言解释器。GrahamHutton也在1992年将高阶函数用于基本解析,在1996年将单体解析用于基本解析。S.D.Swierstra也在2001年展示了解析器组合器的实用性。2008年,Frost、Hafiz和Callaghan在Haskell中描述了一套解析器组合器,它解决了长期存在的容纳左递归的问题,并在多项式时间和空间内作为一个完整的自上而下的解析工具工作

基本思想

编辑

在任何具有一流函数的编程语言中,解析器组合器都可以用来组合基本的解析器,以构建更复杂的规则的解析器。例如,上下文自由语法(CFG)的生产规则可能有一个或多个选择,每个选择可能由一串非终端和/或终端组成,或者选择可能由一个非终端或终端或空字符串组成。如果这些替代物中的每一个都有一个简单的解析器,那么可以使用解析器组合器来组合这些解析器,返回一个可以识别任何或所有替代物的新解析器。在支持运算符重载的语言中,解析器组合器可以采取infix运算符的形式,用来粘合不同的解析器以形成一个完整的规则。因此,解析器组合器使解析器能够以嵌入式风格定义,其代码结构与形式语法的规则相似。因此,实现可以被认为是具有所有相关优点的可执行规范。(特别是:可读性)

组合器

编辑

为了使讨论相对直接,我们只讨论识别器方面的分析器组合器。如果输入字符串的长度为#input,并且其成员是通过索引j来访问的,那么识别器就是一个解析器,它作为输出返回一组索引,代表解析器成功完成了对从位置j开始的标记序列的识别。一个空的结果集表示识别器未能识别任何从索引j开始的序列。空识别器识别的是空字符串。这个解析器总是成功的,返回一个包含当前位置的单子集:empty(j)={j}{displaystyleempty(j)={j}}。如果输入字符串中j位置的标记是x,这个解析器返回一个包含j+1的单子集;否则,它返回空集。Term(x,j)={{},j≥#input{j+1},jth的元素input=x{},否则{displaystyleterm(x,j)={begin{cases}left{right},&jgeq#input\left{j+1right},&j{th}{mbox{elementof}}input=x\left{right},&{mbox{otherwise}}end{cases}}}请注意,一个字符串可能有多种不同的解析方式,同时在同一索引处完成:这表示一个模糊的语法。简单的识别器不承认这些模糊性;每个可能的结束索引在结果集中只列出一次。对于一个更完整的结果集,必须返回一个更复杂的对象,如解析树。

解析器组合器

在两个基本识别器p和q的定义之后,我们可以定义两个主要的解析器组合,用于替代和排序。替代"解析器组合器,⊕,在同一输入位置j上应用两个识别器,并将两个识别器返回的结果相加,最终作为最终结果返回。它被用作p和q之间的infix运算符,如下所示:(p⊕q)(j)=p(j)∪q(j){displaystyle(poplusq)(j)=p(j)cupq(j)}识别器的排序是通过⊛分析器组合器完成的。但它将xxx个识别器p应用于输入位置j,如果这个应用有任何成功的结果,那么第二个识别器q将应用于xxx个识别器返回的结果集的每个元素。⊛最终ret


内容由匿名用户提供,本内容不代表vibaike.com立场,内容投诉举报请联系vibaike.com客服。如若转载,请注明出处:https://vibaike.com/164021/

发表评论

登录后才能评论

词条目录
  1. 解析器组合器
  2. 基本思想
  3. 组合器

轻触这里

关闭目录

目录