(四十四)深度解析领域特定语言(DSL)第八章——语法分析器组合子思想概述
本文对比了组合子模式与递归下降法两种语法分析器实现方式。组合子模式采用自底向上的组件化设计,通过组合小型分析器构建复杂分析器,具有较好的复用性但理解难度较高;而递归下降法则采用自顶向下的过程式设计,更符合人类思维但复用性较差。文章指出无论采用何种方式,语法分析树结构应保持一致,并建议DSL设计遵循"约定大于配置"原则,避免过度追求灵活性。通过具体文法示例,文章展示了两种方法的结
完成基本准备工作后,接下来让我们对组合子思想做一些相对深入的分析。相较于面向过程的递归下降语法分析,基于组合子模式的语法分析器在理解上存在一定复杂度。这本质上是面向对象编程中常见的类型碎片化问题,此类情形为代码阅读者带来诸多困扰。相对而言,面向过程的方法更贴合人类思考问题的逻辑模式,其代码组织通常围绕功能实现展开,虽不同功能模块间代码独立性较强,但在跨场景复用方面存在局限性。笔者无意探讨两种编程方法的优劣——二者各具特色、各有短长,需读者在日常工作中悉心体会。值得注意的是,无论采用何种模式实现分析器,语法分析树的结构应保持一致。以代码8-1为例,其对应的语法分析树如图 8.3所示,只要文法定义不变,该语法分析树的结构便恒定不变。
从图 8.3还可得知:DSL脚本的编写顺序对语法分析器的运行结果具有直接影响。以RULE_BLOCK和SERVICE_TYPE_BLOCK为例,若置换两个代码块的位置,语法分析过程必然抛出错误。从语义层面分析,二者的先后顺序本无实质影响,这一点在Java语言中体现得较为典型——例如允许先声明setter/getter方法,后声明对应的字段,通过回溯机制解决因代码顺序引发的语法分析问题,同时提升代码灵活性。然而在DSL领域,笔者认为此类处理并非必要:其核心原因在于投入产出比失衡。遵循“约定大于配置”原则,预先约定DSL脚本的结构与顺序即可,无需强求通过技术手段实现完全无约束的代码顺序,避免因过度追求灵活性而增加不必要的设计复杂度。
为简化实现,本章案例暂未引入回溯机制。事实上,回溯处理逻辑并不复杂,只需操作词法分析器或其输出缓冲区的读取索引即可,相关设计模式可参考前文。
需要特别注意的是,本次案例的实现方式与前几章存在显著差异,因此需要结合代码学习逐步理解具体实现细节。在此之前,有必要先明确语法分析器组合子的核心概念,这有助于理解该模式背后的设计思想。
组合子模式遵循“小即是美”的软件设计哲学,在结构设计上采用自底向上的构建方式(需注意,此处的“自底向上”指分析器的组件构成模式,而非语法分析算法)。回顾传统递归下降语法分析器的实现——其为每个非终结符设计独立的处理过程,属于典型的面向过程编程方法,本质上是一种自顶向下的模式:将复杂结构逐层拆解直至不可再分。而组合子模式要求设计者转变思路:从语法分析树的最底层符号出发,先设计处理基础语法单元的小型分析器,再通过组合这些小型分析器逐步构建处理复杂语言结构的分析器,直至形成完整的语言分析能力。在此过程中,每个小型分析器都是独立的组件,因此该模式同时体现了面向组件编程的思想。
为更直观地理解,让我们以文法8-2为例,考察如何运用组合子模式进行语法分析器设计。
文法8-2
p1) S -> DECL ';'
p2) DECL -> A B
p3) A -> 'type' ':'
p4) B -> 'integer' ',' 'integer'
对于文法8-2所示的语法规则,代码“int : 3,5;”是可以通过语法分析的。友情提示一下,读者不必纠结该代码是否合理,我们的目标是学习组合子模式。按照约定,应首先从非终结符A和B开始设计子语法分析器,之后再进行DECL的设计,最后是S。假设产生式p4、p3对应的分析器类为C1、C2,那么我们可以将C1和C2组合成C3来处理p2产生式。也就是说我们在设计非终结符DECL所对应的分析器C3时,只需将C1和C2类型的对象作为其内部的字段即可。p1产生式所对应的分析器C4也可如法炮制,它由C3和分号(;)构成。如果为终结符分号、冒号、逗号等也设计一个分析器T的话,那么C4的构成元素就是C3和T。
可以看到,对于上述案例,真正实现语法分析逻辑的其实只有T这一个子分析器,而其他的分析器都只是子分析器的组合。当输入为“int : 3,5;”时,图 8.4展示了文法8-2所对应的语法分析器结构,其中T的下标用于表示T的不同实例。当然,如果读者不怕麻烦的话,也可将T拆分为更小的子分析器,即每个终结符都对应一个。对于当前案例而言,我们需要为分号、逗号、冒号、type、integer这5个终结符分别设定对应的分析器。
图 8.4 基于组合子设计模式,文法8-2所对应的语法分析器结构
作为对比,让我们看一下传统递归下降语法分析方式所对应的语法分析器结构,如图 8.5所示。需要注意的是,图 8.4所体现的是子分析器的组合关系;而图 8.5所体现的则是方法间的调用关系。
图 8.5 基于面向过程设计模式,文法8-2所对应的语法分析器的结构
从表面上看,图 8.4和图 8.5所示的语法分析器有着非常类似的结构,但二者间的区别并不在实现方式上,而是设计理念。基于组合子的分析器采用了自底向上的设计模式,每一个子分析器先天具备了可复用性。而面向过程的实现,则是按文法说明一点点推导出来的,代码虽然更好理解,但对于大型语法分析器而言,方法的可复用性可能会变得比较低。这两种实现方式的区别,实际上也是面向过程与面向对象的区别。对于小规模的DSL而言,选择哪种方式都可以,视团队技术水平而定。
上一章 下一章
更多推荐
所有评论(0)