（二十八）深度解析领域特定语言（DSL）第六章——语法分析：巴科斯-诺尔范式

        在之前的章节中，笔者曾多次运用BNF（巴科斯 - 诺尔范式）对语言的语法规则进行描述，却未对其展开深入阐释。本篇将聚焦这一主题，探讨其发展历程及使用技巧。

        巴科斯-诺尔范式简称BNF，最初由约翰·巴科斯（John Backus）于20世纪50年代提出，首先被用于描述ALGOL 60编程语言的语法。在BNF出现之前，形式语言理论已经开始萌芽。Noam Chomsky提出了著名的乔姆斯基层级，对形式语言进行了分类，为BNF的发展奠定了理论基础。作为ALGOL 60的前身，ALGOL 58的语法描述方式比较混乱并且缺乏足够的严谨性，这促使人们寻求更规范的语法描述方法。1959年，Backus为ALGOL 58开发了一种描述语法的符号系统，使用类似于数学公式的符号来表示语法规则，这被认为是BNF的前身。之后的若干年，彼得·诺尔、唐纳德·克努特等人先后对这套符号系统进行了改进与扩展。当今，BNF及其变体被广泛地用于描述编程语言、数据格式、指令集和其他形式系统的语法。

        在前期内容中，笔者已多次提及“文法”这一概念，其核心功能是定义语言的语法结构，包括确定哪些字符串属于该语言，以及如何将这些字符串分解为更小的语法单元等。显然，采用自然语言描述语言结构存在显著局限性，极易引发二义性问题。而BNF（巴科斯-诺尔范式）则有效弥补了这一缺陷，其通过形式化方法表达文法规则，使文法描述更具清晰性、可理解性和实用性。关于文法的主要作用，笔者已在前文阐述：其既可为语法分析器生成工具提供生成依据，亦可作为语法分析器的设计参考。  

        需要说明的是，尽管文法文件至关重要，但目前尚未形成统一的标准格式，其具体书写方式通常取决于所使用的工具及实际应用场景。若需将文法作为手写语法分析器的设计指导，建议参考文法6-1（基于文法5-8）的书写形式。

文法6-1#语法规则
S -> 'set' RATE 'where' CONDITIONS ';'
RATE -> 'rate' '=' 'number'
CONDITIONS -> SPEC | SPEC 'and' CONDITIONS
SPEC -> 'field' OPERATOR VALUE
...#词法规则
field -> [a-zA-Z][a-zA-Z0-9_]*
any_string -> "[\s\S]*?"
rate -> rate
...

        上述文法文件包含语法规则和词法规则两部分内容。其中词法规则仅用于描述终结符，且仅被词法分析器调用。需要注意的是，语法规则中出现的'set'、'where'等终结符虽与词法规则中的标识符形式一致，但本质上表示Token类型，与词法规则的字符匹配逻辑无直接关联。这一特性表明，词法规则的设计应以Token类型为导向，避免出现字符匹配与语法类型的映射遗漏。语法规则作为语法分析器的核心基础，其作用不言而喻。在编写文法文件时，建议将语法规则置于词法规则之前。

        作为设计文档，将语法规则与词法规则集中于同一文法文件进行管理是值得推荐的实践。尽管部分技术人员倾向于将词法规则嵌入代码或与语法规则分离，这种做法在语言结构复杂时可避免文法文件体积过大、可读性下降等问题，但对于复杂度有限的DSL而言，集中式管理更便于规则的查找、修改和维护。关于文法文件的管理策略，笔者提出以下建议：  

1. 保持与代码逻辑的一致性。在对DSL编译器进行任何修改或扩展时，应优先调整文法规则，确保文法描述与实际实现的同步性，避免出现规则与代码的语义偏差。  
2. 采用代码管理工具（如git）对文法文件进行版本控制，通过追踪文件变更记录，可清晰呈现语法规则的演化过程，提升团队协作效率并降低维护成本。

        让我们重新回到BNF的讨论。关于BNF的基本用法，笔者已在前文进行了简要介绍。本节将探讨其高级用法。除原始形式外，BNF还存在扩展形式——EBNF（Extended BNF），二者可相互转换。根据笔者的实践经验，在日常使用中可灵活混用这两种形式，无需严格区分。实际上，多数场景下使用EBNF更为合适。毕竟文法的主要受众是人，而人在阅读时，简洁性显然更为重要。至于使用语法分析器生成器的场景，具体支持何种形式的文法，则取决于工具本身的限制。

        需要注意的是，EBNF存在多种变体。尽管国际标准化组织（International Organization for Standardization，ISO）于1996年发布了EBNF标准，但并未实现EBNF的完全统一，因此业界在使用(E)BNF时存在多种不同的实现方式。

        相对于BNF，EBNF在表达形式方面更显简洁。以上一章给出的二进制字符串文法为例，使用基本形式进行描述时，将呈文法6-2所示的形式：

文法6-2S -> S BIT | BIT
BIT -> '0' | '1'

        为描述二进制字符串中允许包含多个0或1的结构，笔者采用了递归方式（即第一条产生式）。由于示例相对简单，该表达方式未造成理解障碍。但需注意，初次接触此类递归产生式时，可能存在一定理解门槛，尤其在递归层级较多的场景下，复杂度会显著提升。这种情况下，EBNF的作用就开始突显出来了，其在BNF的基础上增加了一些非常有用的符号来增强文法的描述，具体如下：

1. ？：其左侧的符号可出现0次或1次。
2. *：其左侧的符号可出现0次或多次。
3. +：其左侧的符号可出现1次或多次。

        其实并不需要死记硬背，这些符号的作用和它们在正则表达式中的作用是完全一样的。如果用EBNF来描述文法6-2的话，只需要一条产生式即可，如文法6-3所示：

文法6-3S -> ('0' | '1')+

        文法6-1中，CONDITIONS所对应的产生式也包含了递归，我们可以使用EBNF对其进行简化，如文法6-4所示：

文法6-4CONDITIONS -> SPEC ('and' SPEC)*

        这样改造后是不是感觉清晰很多了？实际上，EBNF的应用场景有很多，不仅仅可以用来描述语言的语法，还可以使用它来定义某些协议的格式或数据的格式。比如我们常见的XML，其实就是使用EBNF进行定义的。

          除上述三个符号之外，EBNF中还引入一些其他的符号来增加表达能力。在此主要介绍如下三个：

1. []：可选项，其内部的语法结构是可选的，可最多出现1次。
2. {}：重复项，其内部的语法结构可重复出现0次或多次。
3. ()：分组，将多个语法结构组合在一起并形成一个整体。

        符号“[]”和问号“?”都可以被用来表示被修饰的符号只能出现0或1次，二者最大的差异在于“[]”主要用于修饰一组语法元素；而“?”则主要被用于修饰某一个元素。以此类推，重复项“{}”和“*”的区别也在于是否可以被用来修饰一组元素。实践中我们应尽量遵守各自的使用约束，这样的话您编写的文法才更容易被人理解。

        现实当中，许多语言都使用了EBNF或其变体进行语法规则的描述，比如C（ISO/IEC 9899标准）、C++、JavaScript（ECMAScript标准）、Java等。文法6-5展示了MySQL的DELETE语法，也是基于EBNF进行描述的。除了MySQL之外，您还可以在微软官网找到使用EBNF描述的SQL Server产品的SQL语法规则。值得注意的是，虽然不同语言或规范所使用的EBNF变体存在着不同，但它们的核心思想都是基于EBNF，并使用类似的符号来描述语法。

文法6-5DELETE [LOW_PRIORITY] [QUICK] [IGNORE] FROM tbl_name [[AS] tbl_alias]
[PARTITION (partition_name [, partition_name] ...)]
[WHERE where_condition]
[ORDER BY ...]
[LIMIT row_count]

        EBNF之所以得到广泛应用，主要得益于其具备的以下两项核心优势：

1. 消除认知歧义。理想情况下，语言的语法规则一旦确定，其描述应确保不同读者的理解完全一致。尽管自然语言理论上可用于语法定义（如法律条文般追求严谨性），但其表述往往冗长复杂，增加理解成本。EBNF通过形式化符号系统简化语法描述，在保持数学严谨性的同时显著提升可读性。其符号约定（如[]表示可选、{}表示重复）直观易懂，即使未经过系统学习的软件技术人员也能快速理解规则含义，有效避免了自然语言固有的歧义性。
2. 机器友好性。由于EBNF的无歧义特性，多数语法分析器生成工具（如ANTLR、Yacc）要求用户使用EBNF格式描述语法规则。以ANTLR为例，它所要求的文法文件格式如代码6-1所示。很明显，其遵循了EBNF规范。只要不出现人为的失误，ANTLR便可以根据文法自动生成唯一且正确的语法分析器。

代码6-1grammar Hello;
r  : 'hello' ID ;         // match keyword hello followed by an identifier
ID : [a-z]+ ;             // match lower-case identifiers
WS : [ \t\r\n]+ -> skip ; // skip spaces, tabs, newline

上一章  下一章