语法分析组合子

基本想法

在任何一种编程语言，拥有 头等函数，分析器组合子可以用基本的分析器构造用于更复杂的规则的分析程序。 例如，上下文无关文法 (CFG)的产生式可能有一个或多个备选推导方案，每个备选方案可以由一系列的 非终结符 和/或 终结符，或者推导方案可以由一个单一的非终结符或终结符端或空串组成。如果一个简单的分析程序适用于这些推导方案，语法分析组合子可以用来组合这些分析器，返回一个新的分析器，这可以识别出的任何推导方案。
在支持运算符重载 的语言中，一个语法分析组合子可以使用中缀 操作符形式，用于将不同的分析器胶合成一个完整的规则。语法分析组合子使得分析程序能以一个嵌入式的风格编写，这使得程序结构上类似于正则文法的规则。 因此，实现方式可以被认作为可执行的规格并有所有的相关优点。 (值得注意的是：可读性)

例

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