语法分析组合子

✍ dations ◷ 2025-11-10 11:16:44 #语法分析组合子

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

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

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

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

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

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

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

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


相关

  • 麦秆.mw-parser-output ruby.zy{text-align:justify;text-justify:none}.mw-parser-output ruby.zy>rp{user-select:none}.mw-parser-output ruby.zy>rt{font-feature-settings:
  • 尤斯塔斯二世 (布洛涅)布洛涅伯爵尤斯塔斯二世(法语:Eustache II, comte de Boulogne,约1015 – 约1087),别称小胡子尤斯塔斯(Eustace aux Gernons),自1049年起至1087年逝世时止为布涅洛伯爵。尤斯塔斯在
  • 草凪瑞穗草凪瑞穗(1979年2月3日-)(日语:草凪みずほ),东立译名为MIZUHO KUSANAGI,日本漫画家。熊本县出身。2002年,以作品《御神兄弟がゆく!?》获得第27回白泉社雅典娜新人大赏优秀新人赏。代
  • 纳尼亚传奇:凯斯宾王子《纳尼亚传奇:凯斯宾王子》(英语:The Chronicles of Narnia: Prince Caspian),是《纳尼亚传奇》电影系列的第二部,由安德鲁·亚当森执导,剧情改编自英国作家C·S·路易斯在1951年出
  • 读者服务读者服务或读者顾问服务约在1920年代开始发展,并受到美国公共图书馆的重视。费城公共图书馆对读者服务所作的定义为“阅读指导、选择资料来满足特定的兴趣或需要,为既定目的,协
  • VAST娱乐VAST娱乐(韩语:VAST엔터테인먼트)是韩国的经纪公司。VAST娱乐成立于2016年。2019年10月,Kakao M宣布已完成收购VAST娱乐,将纳入为Kakao M子公司。
  • globeglobe(日文名称:グローブ,中文名称:地球乐团)为日本乐团,由日本音乐制作人小室哲哉、新人女歌手试演会中选拔出来的主唱KEIKO、日法混血饶舌歌手MARC PANTHER所组成的乐团。乐队X
  • 费莉达·古斯塔夫臣费莉达·古斯塔夫臣(Frida Gustavsson;1993年6月6日-),瑞典超级名模。她是高级时装品牌:Prada、Etro、Mulberry的代言人。费莉达上过Vogue China及Numero等杂
  • 前81年
  • 弗朗西斯科·西尔维拉弗朗西斯科·西尔维拉·德勒维列乌泽(西班牙语:Francisco Silvela y de Le Vielleuze,1845年12月15日-1905年5月29日) ,西班牙保守党政治人物。他曾在马丁内斯·坎波斯内阁中出任内政大臣,在卡诺瓦斯内阁担任恩典与司法大臣和内政大臣。在卡诺瓦斯遇刺后成为保守党党首,两次担任首相。在第一届内阁中兼任外交大臣,第二次内阁中兼任海军大臣。1845年12月15日出生于马德里,是家里的第四个孩子。父亲弗朗西斯科·奥古斯丁·西尔维拉是一名律师和政治家,曾在1838年担任内政大