Parser combinator (original) (raw)

在计算机编程中 语法分析组合子 是一个 高阶函数 ，它接受几个的语法分析器作为输入，并返回一个新的语法分析函器作为其输出。 在这个上下文中， 语法分析器 是一个函数，它接受字符串作为输入，返回的一些结构作为输出，通常为 分析树 或一组索引表示在字符串中成功停止分析的位置。 分析器组合子使用 递归下降分析 战略，提倡模块式建造和测试。 这种分析技术是所谓的 组合分析。 使用组合子构建的分析器易于构造、可读、模块化、结构良好且易于维护它们被广泛地用于 领域特定语言（如数据库的自然语言接口）的编译器和处理器的原型设计中，在这些语言中，复杂多样的语义操作与语法处理紧密集成。1989年，Richard Frost和John Launchbury演示了使用语法分析组合子构造的自然语言解释器。Graham Hutton在1992年也使用了高阶函数进行基本解析。S.D. Swierstra在2001年还展示了解析器组合器的实用方面。在2008年，Frost、Hafiz和Callaghan用Haskell中描述了一组语法分析组合子，它们解决了长期存在的通用左递归的问题，它也是一个完整的，只需要多项式时间、空间的自顶向下解析工具。