（四十四）深度解析领域特定语言（DSL）第八章——语法分析器组合子思想概述

本文对比了组合子模式与递归下降法两种语法分析器实现方式。组合子模式采用自底向上的组件化设计，通过组合小型分析器构建复杂分析器，具有较好的复用性但理解难度较高；而递归下降法则采用自顶向下的过程式设计，更符合人类思维但复用性较差。文章指出无论采用何种方式，语法分析树结构应保持一致，并建议DSL设计遵循"约定大于配置"原则，避免过度追求灵活性。通过具体文法示例，文章展示了两种方法的结

weixin_46217641

25757人浏览 · 2025-08-06 09:05:51

weixin_46217641 · 2025-08-06 09:05:51 发布

完成基本准备工作后，接下来让我们对组合子思想做一些相对深入的分析。相较于面向过程的递归下降语法分析，基于组合子模式的语法分析器在理解上存在一定复杂度。这本质上是面向对象编程中常见的类型碎片化问题，此类情形为代码阅读者带来诸多困扰。相对而言，面向过程的方法更贴合人类思考问题的逻辑模式，其代码组织通常围绕功能实现展开，虽不同功能模块间代码独立性较强，但在跨场景复用方面存在局限性。笔者无意探讨两种编程方法的优劣——二者各具特色、各有短长，需读者在日常工作中悉心体会。值得注意的是，无论采用何种模式实现分析器，语法分析树的结构应保持一致。以代码8-1为例，其对应的语法分析树如图 8.3所示，只要文法定义不变，该语法分析树的结构便恒定不变。

图 8.3 代码8-1所对应的语法分析树

从图 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而言，选择哪种方式都可以，视团队技术水平而定。