bittern.cn
2编程语言实现模式（第2版）

语法

程序的结构

BNFEBNF上下文无关文法解析

🎯 AI 时代的学习建议：不要只读理论。理解这一章的设计动机（为什么需要这个概念？）和边界条件（什么情况下会失效？）。当 AI 生成的代码涉及这些概念时，你能判断它是否用对了场景。AI 能帮你总结内容，但无法替代你亲手阅读、思考、建立直觉的过程。

第2章：语法（程序的结构） Syntax: The Structure of Programs

一、导读

语法是编程语言的骨架，它定义了哪些字符序列构成合法的程序。就像自然语言有语法规则一样，编程语言也有严格的形式化规则来约束程序的书写形式。一个字符序列即使语义完全合理，如果不符合语法规则，也无法被编译器接受。

本章将深入探讨语法的形式化定义方法和解析技术。理解语法不仅有助于我们使用编程语言，更有助于我们理解编译器如何处理源代码、设计新的语言特性以及调试语法错误。

学习目标：

掌握 BNF 和 EBNF 的语法表示方法

理解上下文无关文法的基本概念

了解词法分析和语法分析的基本过程

理解歧义性文法的问题及解决方法

能够用文法描述简单的编程语言片段

核心问题： 编译器如何判断一段代码是否"合法"？语法规则是如何被形式化定义和自动化处理的？

二、核心概念详解

2.1 巴科斯-瑙尔范式（BNF, Backus-Naur Form）

BNF 是一种用于描述上下文无关文法的形式化表示方法，由 John Backus 和 Peter Naur 在 1950 年代为描述 Fortran 语言的语法而发明。BNF 的核心要素包括：

  • 终结符（Terminal）：语言中不可再分的基本符号，如关键字 if、运算符 +、标识符等
  • 非终结符（Non-terminal）：可以进一步展开的语法范畴，如 <表达式>、<语句>、<条件>
  • 产生式（Production）：定义非终结符如何由终结符和其他非终结符组成，形式为 <非终结符> ::= <符号序列>

例如，算术表达式的 BNF 定义：

<表达式> ::= <项> | <表达式> "+" <项> | <表达式> "-" <项>
<项>     ::= <因子> | <项> "*" <因子> | <项> "/" <因子>
<因子>   ::= <数字> | "(" <表达式> ")"
<数字>   ::= "0" | "1" | "2" | ... | "9"

BNF 能够精确描述语言的层次化结构，但存在一个重要的局限：它无法描述上下文相关的语法规则。例如，"变量在使用前必须先声明"这一规则无法用 BNF 表达，需要用其他机制（如语义动作或属性文法）来处理。

2.2 扩展巴科斯-瑙尔范式（EBNF, Extended BNF）

EBNF 在 BNF 基础上引入了三种扩展符号，使语法描述更加简洁：

  • 可选（Optional）：用方括号 [...] 表示，如 <语句> ::= "if" <条件> <语句> ["else" <语句>]
  • 重复（Repetition）：用花括号 {...} 或 * 表示零次或多次重复，如 <参数列表> ::= <参数> {"," <参数>}
  • 分组（Grouping）：用圆括号 (...) 表示，用于组合多个可选项

EBNF 不增加 BNF 的表达能力（两者等价），但显著提升了语法规范的可读性。现代语言规范（如 Java Language Specification、C++ Standard）普遍采用 EBNF 或其变体来描述语法。

2.3 上下文无关文法（Context-Free Grammar, CFG）

上下文无关文法是定义编程语言语法的数学基础。其核心特征是：每个产生式的左部只包含单个非终结符，这意味着非终结符的替换不依赖于其上下文环境。

CFG 的形式化定义包含四个要素：

  • 终结符集合 T
  • 非终结符集合 N
  • 产生式集合 P
  • 开始符号 S

CFG 的派生（Derivation）过程是从开始符号出发，反复应用产生式规则，最终得到一个全部由终结符组成的串。这个串就是语言中的一个合法句子。

2.4 解析方法（Parsing Techniques）

解析是将源程序的字符流转换为语法树的过程。主要分为两大类：

自顶向下解析（Top-Down Parsing）：

从开始符号出发，尝试推导出与输入匹配的串。代表方法包括：

  • 递归下降解析（Recursive Descent）：为每个非终结符编写一个递归函数
  • LL(1) 解析：从左到右扫描输入，使用最左推导，向前查看 1 个符号

自底向上解析（Bottom-Up Parsing）：

从输入的终结符出发，尝试归约到开始符号。代表方法包括：

  • LR(1) 解析：从左到右扫描输入，使用最右推导的逆过程，向前查看 1 个符号
  • LALR(1)：LR(1) 的简化版本，Yacc/Bison 等工具使用的就是这种算法

2.5 词法分析（Lexical Analysis）

词法分析是语法分析的前置步骤，负责将字符流分割为有意义的词法单元（Token）。词法分析器通常使用正则表达式来定义 Token 的模式：

  • 标识符：[a-zA-Z_][a-zA-Z0-9_]*
  • 整数常量：[0-9]+
  • 运算符：+、-、*、/、==、!= 等
  • 关键字：if、else、while、return 等

词法分析工具如 Lex/Flex 能够根据正则表达式规则自动生成词法分析器代码。

三、深入分析

3.1 文法的歧义性（Ambiguity）

一个文法如果存在某个句子，它有两棵不同的语法树（或两种不同的最左推导），则该文法是歧义的（Ambiguous）。歧义性是语法设计中的严重问题，因为它意味着程序的含义不唯一。

经典的歧义案例是"悬空 else"（Dangling Else）问题：

<语句> ::= "if" <条件> "then" <语句> | "if" <条件> "then" <语句> "else" <语句>

对于代码 if a then if b then s1 else s2，else 既可以与内层的 if 配对，也可以与外层的 if 配对。大多数语言通过"最近匹配"规则解决这一歧义：else 总是与最近的未匹配的 if 配对。

解决歧义性的方法包括：

  • 重写文法，消除歧义结构
  • 添加优先级和结合性规则
  • 在解析器中引入特殊处理逻辑

3.2 运算符优先级与结合性

运算符优先级（Precedence）和结合性（Associativity）是解决表达式文法歧义的重要手段。

优先级决定了不同运算符之间的绑定紧密程度。例如，在 2 + 3 * 4 中，乘法优先级高于加法，因此结果为 14 而非 20。

结合性决定了相同优先级的运算符如何分组。大多数二元运算符是左结合的（从左到右分组），而赋值运算符通常是右结合的（从右到左分组）。例如 a = b = c 等价于 a = (b = c)。

在文法层面，可以通过分层定义来编码优先级：

<表达式>   ::= <表达式> "+" <项> | <表达式> "-" <项> | <项>
<项>       ::= <项> "*" <因子> | <项> "/" <因子> | <因子>
<因子>     ::= <数字> | "(" <表达式> ")"

越外层的非终结符优先级越低，这种分层结构自然地编码了运算符的优先级关系。

3.3 解析器生成工具

现代编译器开发很少手写解析器，而是使用解析器生成工具。主要工具包括：

  • Lex/Flex：词法分析器生成器，根据正则表达式规则生成 C 代码
  • Yacc/Bison：语法分析器生成器，根据 LALR(1) 文法生成 C 代码
  • ANTLR：支持 LL(*) 解析的通用解析器生成器，可生成 Java、C++、Python 等多种语言
  • PEG（Parsing Expression Grammar）：一种新兴的语法描述形式，天然无歧义，Packrat 解析器可以在线性时间内完成解析

这些工具极大地降低了编译器前端开发的复杂度，使语言设计者能够专注于语法设计本身。

四、实践案例

案例1：用 BNF 描述 JSON 语法

JSON 是一种广泛使用的数据交换格式，其语法可以用 BNF 简洁地描述：

<value>     ::= <object> | <array> | <string> | <number> | "true" | "false" | "null"
<object>    ::= "{" {<member>} "}"
<member>    ::= <string> ":" <value> {"," <member>}
<array>     ::= "[" [<value> {"," <value>}] "]"
<string>    ::= """ {<字符>} """
<number>    ::= ["-"] <数字> [<小数部分>] [<指数部分>]

这个文法清晰地展示了 JSON 的递归嵌套结构：对象可以包含数组，数组可以包含对象，形成任意深度的嵌套。

案例2：递归下降解析器的实现

递归下降解析器是最直观的自顶向下解析方法。为文法中的每个非终结符编写一个函数，函数之间通过互相调用来实现推导过程。例如，对于上述 JSON 文法：

function parseObject():
    expect("{")
    while (lookahead != "}")
        parseMember()
        if (lookahead == ",") consume(",")
    expect("}")

function parseMember():
    key = parseString()
    expect(":")
    value = parseValue()

递归下降解析器的优点是代码结构清晰、易于理解和调试，缺点是对于左递归文法会陷入无限递归，需要通过文法变换消除左递归。

五、常见误区

误区1：语法正确的程序一定是正确的程序

语法只是程序正确性的必要条件，而非充分条件。x = "hello" + 5 在 Python 中语法完全合法，但语义上可能是错误的（类型不匹配）。return 语句出现在函数外部也是语法合法但语义错误的情况。编译器通常分阶段检查：先检查语法，再检查语义。

误区2：BNF 能描述所有编程语言的语法规则

BNF 只能描述上下文无关的语言，无法表达上下文相关的约束。例如，"变量必须先声明后使用"、"break 只能出现在循环或 switch 内部"、"函数返回值的类型必须与声明一致"等规则都无法用纯 BNF 表达。这些约束需要在语义分析阶段通过符号表和其他机制来检查。

误区3：LL 解析和 LR 解析能力相同

LR 解析的能力严格强于 LL 解析。存在可以用 LR 文法描述但不能用 LL(1) 文法描述的语言。例如，左递归文法 A ::= A "+" B 可以被 LR 解析器处理，但 LL(1) 解析器无法处理左递归。这也是为什么递归下降解析器（LL 类）需要对文法进行左递归消除的原因。

误区4：正则表达式可以描述所有语法结构

正则表达式只能描述正则语言，其表达能力严格弱于上下文无关文法。嵌套结构（如括号匹配、HTML 标签配对）无法用正则表达式描述。这就是为什么用正则表达式解析 HTML 或嵌套代码结构是不可靠的，必须使用真正的解析器。

六、本章小结

本章系统讲解了编程语言语法的定义方法和解析技术。BNF 和 EBNF 提供了描述语法规则的形式化工具，上下文无关文法为语法分析奠定了理论基础。解析技术分为自顶向下和自底向上两大类，各有其适用场景和局限性。歧义性是语法设计中需要特别注意的问题，可以通过文法重写、优先级规则等方式解决。词法分析作为语法分析的前置步骤，使用正则表达式将字符流分割为有意义的 Token。理解这些概念有助于我们深入认识编译器的工作原理，也为设计和实现新的编程语言提供了必要的知识储备。

七、思考题

请用 BNF 描述一门简单计算器语言的语法，支持加减乘除和括号运算。

解释"悬空 else"歧义问题，并说明至少两种解决方法。

比较 LL(1) 递归下降解析器和 LR 解析器的优缺点，各举一个适合使用它们的场景。

为什么正则表达式不能用来解析嵌套的括号结构？请用形式语言理论解释。

选择你熟悉的一门编程语言，用 EBNF 描述其 if-while-for 控制流语句的语法。

2/9语法
0%