语法分析组合子

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

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

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

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

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

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

${\displaystyle 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 之间的一个中缀操作符：

${\displaystyle (p\oplus q)(j)=p(j)\cup q(j)}$ 

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

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

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