语法分析组合子

在计算机编程中 语法分析组合子 是一个 高阶函数 ，它接受几个的语法分析器作为输入，并返回一个新的语法分析函器作为其输出。 在这个上下文中， 语法分析器 是一个函数，它接受字符串作为输入，返回的一些结构作为输出，通常为 分析树 或一组索引表示在字符串中成功停止分析的位置。 分析器组合子使用 递归下降分析 战略，提倡模块式建造和测试。 这种分析技术是所谓的 组合分析。

使用组合子构建的分析器易于构造、可读、模块化、结构良好且易于维护它们被广泛地用于 领域特定语言（如数据库的自然语言接口）的编译器和处理器的原型设计中，在这些语言中，复杂多样的语义操作与语法处理紧密集成。1989年，Richard Frost和John Launchbury演示了使用语法分析组合子构造的自然语言解释器。Graham Hutton在1992年也使用了高阶函数进行基本解析。S.D. Swierstra在2001年还展示了解析器组合器的实用方面。在2008年，Frost、Hafiz和Callaghan用Haskell中描述了一组语法分析组合子，它们解决了长期存在的通用左递归的问题，它也是一个完整的，只需要多项式时间、空间的自顶向下解析工具。

基本想法

在任何一种编程语言，拥有 头等函数，分析器组合子可以用基本的分析器构造用于更复杂的规则的分析程序。 例如，上下文无关文法 (CFG)的产生式可能有一个或多个备选推导方案，每个备选方案可以由一系列的 非终结符 和/或 终结符，或者推导方案可以由一个单一的非终结符或终结符端或空串组成。如果一个简单的分析程序适用于这些推导方案，语法分析组合子可以用来组合这些分析器，返回一个新的分析器，这可以识别出的任何推导方案。

在支持 运算符重载 的语言中，一个语法分析组合子可以使用 中缀 操作符形式，用于将不同的分析器胶合成一个完整的规则。语法分析组合子使得分析程序能以一个嵌入式的风格编写，这使得程序结构上类似于正则文法的规则。 因此，实现方式可以被认作为可执行的规格并有所有的相关优点。 (值得注意的是：可读性)

组合子

为了保持讨论比较简单，我们只讨论语法分析组合子作为 识别器 的情况。 如果输入串的长 #input ，其成员通过一个索引 j，一个 识别器 是一个语法分析器，它返回一组索引，表示分析器在位置 j成功地识别出了一个序列的标记。一个空的结果表明在索引 j识别器没有识别到任何序列的开始。

• empty 识别器识别出空串。 这种分析器总是成功，在返回一个包含目前位置的单元素集合：

$empty(j)=\{j\}$

• 一个识别器 term x 识别出终结符 x。如果 j 位置上的token是 x，这种分析器返回元素为 j＋1的单元素集合 否则，返回空集。

$term(x,j)={\begin{cases}\left\{\right\},&j\geq \#input\\\left\{j+1\right\},&j^{th}{\mbox{ element of }}input=x\\\left\{\right\},&{\mbox{otherwise}}\end{cases}}$

注意可能有多个不同的方法来分析一个字符串，同时在相同的索引处结束：这表明一个 二义性文法 。简单的识别器不承认这些二义性；每个可能的结束索引在结果集中只出现一次。 对于更完整的结果集合，必须返回一个更复杂的对象，例如 分析树。

下面的定义的两个基本的识别器 p 和 q，我们可以界定两个主要的语法分析组合子，用于选择和顺序：

• '选择'的语法分析组合子, ⊕，在相同的输入位置 j 应用两个的识别器并返回两者结果的和。它是作为一个 p 和 q 之间的一个中缀操作符：

$(p\oplus q)(j)=p(j)\cup q(j)$

• 顺序识别器是使用⊛语法分析组合子完成的。像⊕一样它是作为 p 和 q 之间的中缀运算符。它在输入位置 j应用第一个识别器 p ，然后第二个识别器 q 应用于第一识别器返回的每个结果。⊛最终返回q的结果的并集。

$(p\circledast q)(j)=\bigcup \{q(k):k\in p(j)\}$

例

考虑一个有高度二义性的 上下文无关文法, s ::= 'x' s s|ε. 使用上面定义的组合子，我们可以模块化的定义可执行的符号，这种语法在一个现代化的函数式语言(例如 Haskell)作为 s = term 'x' <*> s <*> s <+> empty。当识别器 s 在一个输入序列 ..... 的位置 1上被应用，根据上述定义，它将返回的结果集合 {5,4,3,2}.