第2章：程序语法与语义（Program Syntax and Semantics）

一、导读

1.1 学习目标

本章深入探讨编程语言的语法和语义两个基本方面。通过本章学习，读者应当能够：准确区分语法与语义的概念及其关系；掌握BNF范式描述语法规则的方法；理解操作语义、指称语义和公理语义三种语义模型的基本思想；认识语法与语义的分离对语言设计和编译器实现的重要意义；了解形式化方法在语言定义中的应用。

1.2 语法与语义的重要性

当我们编写一段程序代码时，实际上同时涉及了两个层面：代码的书写形式（语法）和代码所表达的含义（语义）。一个程序可以在语法上完全正确，但在语义上毫无意义——就像一句语法正确但内容荒谬的句子。编译器首先检查程序的语法合法性，然后才关注其语义正确性。理解语法与语义的区别和联系，是深入认识编程语言本质的基础。

1.3 形式化方法的必要性

自然语言可以通过词典和语法书来描述，但这种描述往往不够精确，存在大量例外和歧义。编程语言不允许这种模糊性——编译器必须能够无歧义地判断任何字符序列是否属于合法程序，以及合法程序的确切含义。因此，我们需要使用数学上严格的形式化方法来定义编程语言的语法和语义。

二、核心概念详解

2.1 语法的形式化描述

语法（Syntax）定义了编程语言的合法形式，即哪些字符序列构成合法的程序。语法关注的是程序的结构而非含义。语法的描述通常分为两个层次：

词法（Lexical Structure） 定义了合法的单词（Token）形式，包括关键字、标识符、运算符、字面量和分隔符等。词法规则通常使用正则表达式来描述，例如标识符的词法规则可以表示为 [a-zA-Z_][a-zA-Z0-9_]*，表示以字母或下划线开头，后跟零个或多个字母、数字或下划线。

语法结构（Syntactic Structure） 定义了如何将单词组合成合法的语句和程序。语法规则描述了程序的层次结构，例如表达式可以由操作数和运算符组成，语句可以由表达式和关键字组成。语法结构通常使用上下文无关文法（Context-Free Grammar）来描述。

巴科斯-瑙尔范式（Backus-Naur Form, BNF） 是描述上下文无关文法的标准表示方法。BNF使用产生式规则来定义语法结构，每条规则由一个非终结符、一个等号和一个由终结符与非终结符组成的序列构成。例如，算术表达式的BNF描述可以写为：

<expr>   ::= <term> | <expr> "+" <term> | <expr> "-" <term>
<term>   ::= <factor> | <term> "*" <factor> | <term> "/" <factor>
<factor> ::= <number> | "(" <expr> ")"

这个文法精确定义了算术表达式的结构层次，隐含地表达了运算符的优先级关系。

扩展BNF（EBNF） 在标准BNF的基础上增加了可选、重复和分组等语法糖，使得文法描述更加简洁。例如，使用方括号表示可选元素，使用花括号表示重复，使用竖线表示选择。EBNF与BNF在表达能力上是等价的，但EBNF更加实用。

2.2 语法分析树与歧义性

语法分析树（Parse Tree）是源程序语法结构的树形表示。树的根节点代表整个程序或语句，叶节点代表终结符（单词），内部节点代表非终结符，反映了语法规则的应用过程。

一个文法是歧义的（Ambiguous），如果存在某个句子可以生成两棵不同的语法分析树。歧义性在编程语言中是不可接受的，因为同一段代码不应有两种不同的解释。例如，经典的"悬空else"问题就是由歧义文法引起的：

if (x > 0)
    if (y > 0)
        z = 1;
    else
        z = 2;

这里的 else 究竟与哪个 if 配对？大多数语言通过约定"else与最近的未匹配if配对"来解决这一歧义，这实际上是对文法施加了额外的约束。

消除歧义的常用方法包括：重写文法使其无歧义、引入优先级和结合性规则、以及使用消歧义约定。在编译器实现中，通常通过限制文法的形式（如要求LL或LR文法）来从根本上避免歧义。

2.3 语义的形式化描述

语义（Semantics）定义了合法程序的含义，即程序执行时的行为。与语法相比，语义的形式化要复杂得多。目前主流的语义描述方法有三种：

操作语义（Operational Semantics） 通过定义抽象机器上的状态转换来描述程序行为。程序的含义被定义为一系列状态转换的序列：给定初始状态，程序执行后到达的最终状态就是程序的含义。操作语义最接近程序的实际执行过程，因此最直观易懂。小步操作语义（Small-step Semantics）描述每一步的计算细节，大步操作语义（Big-step Semantics）直接描述从初始状态到最终状态的映射。

指称语义（Denotational Semantics） 将程序映射到数学对象（通常是数学函数）上。程序的含义被定义为一个数学函数，该函数描述了输入状态到输出状态的映射关系。指称语义的优势在于它提供了精确的数学基础，可以用于证明程序的等价性和正确性。然而，指称语义的数学抽象程度较高，对于复杂语言特性的定义可能非常困难。

公理语义（Axiomatic Semantics） 基于逻辑断言来刻画程序的性质。程序的含义不是通过其执行行为来定义，而是通过满足该程序的一组逻辑断言来刻画。Hoare逻辑是公理语义的典型代表，它使用三元组 {P} S {Q} 来表示程序S在满足前置条件P的情况下执行后，将满足后置条件Q。公理语义特别适合用于程序验证，即证明程序满足其规格说明。

2.4 语法与语义的关系

语法与语义是编程语言的两个正交维度。语法定义了程序的合法形式，语义定义了合法程序的含义。两者之间存在以下重要关系：

语法正确是语义正确的前提。编译器在处理源代码时，首先进行语法分析，只有语法正确的程序才会进入语义分析阶段。一个语法错误的程序根本无法被编译器理解，更谈不上语义正确性。

语法相同并不意味着语义相同。不同的编程语言可能具有相似的语法，但语义可能截然不同。例如，Java和JavaScript在语法上有许多相似之处，但它们的类型系统、作用域规则和对象模型存在根本差异。

语法与语义的分离使得语言设计更加灵活。设计者可以在保持语义不变的情况下改进语法（如Python 3对print语句的语法改进），也可以在保持语法兼容的情况下扩展语义（如C++各版本标准对语言特性的语义增强）。

三、深入分析

3.1 静态语义与类型系统

除了语法和运行时语义之外，还有一类介于两者之间的约束称为静态语义（Static Semantics）。静态语义是在编译时可以检查的程序约束，最典型的例子就是类型检查。

例如，表达式 x + y 在语法上是合法的（两个标识符通过加号连接），但如果 x 是整数类型而 y 是字符串类型，这个表达式就违反了静态语义约束。类型检查器在编译期检测这类违反，防止程序在运行时出现类型错误。

静态语义可以看作是对语法分析树施加的额外约束。语法分析确定了程序的结构，而静态语义分析则为这棵树添加了类型标注，确保每个节点的操作对其操作数的类型是合法的。这种分层检查策略将复杂的程序验证问题分解为多个可管理的子问题。

3.2 语义等价与程序变换

两个程序是语义等价的（Semantically Equivalent），如果它们在所有可能的输入上产生相同的行为。语义等价的概念在编译器优化和程序重构中具有重要应用。

编译器优化本质上是在保持语义等价的前提下，将程序变换为更高效的版本。例如，将循环不变量提取到循环外部、消除公共子表达式、内联函数调用等优化技术，都要求变换前后的程序在语义上完全等价。

程序重构同样遵循语义等价的原则。当程序员重命名变量、提取方法、或重新组织代码结构时，程序的外部行为不应发生改变。理解语义等价的条件有助于我们判断哪些重构是安全的，哪些可能引入微妙的行为变化。

四、实践案例

4.1 案例一：用BNF描述JSON语法

JSON（JavaScript Object Notation）是一种广泛使用的数据交换格式。其语法可以用BNF精确描述如下：

<json>     ::= <object> | <array>
<object>   ::= "{" <members> "}" | "{" "}"
<members>  ::= <member> | <member> "," <members>
<member>   ::= <string> ":" <json>
<array>    ::= "[" <elements> "]" | "[" "]"
<elements> ::= <json> | <json> "," <elements>
<string>   ::= """ <characters> """
<number>   ::= <integer> <fraction> <exponent>

这个文法清晰地展示了JSON的层次结构：JSON值可以是对象或数组，对象由键值对组成，数组由元素序列组成。通过这种形式化描述，我们可以精确地判断任何字符串是否是合法的JSON文档，并为JSON解析器的实现提供明确的规范。

4.2 案例二：操作语义的应用

考虑一个简单的赋值语句 x = x + 1，我们用操作语义来描述其含义。程序的状态可以表示为变量到值的映射，例如 {x: 5, y: 3}。赋值语句的操作语义规则可以表述为：

首先对右侧表达式 x + 1 在当前状态下求值，得到值 6

然后将变量 x 在状态中的绑定更新为新值 6

最终状态变为 {x: 6, y: 3}

这种状态转换的描述方式虽然简单，但它为形式化定义更复杂的程序结构（如条件语句、循环语句）的语义提供了基础框架。对于循环语句，操作语义需要定义不动点来描述可能执行任意次的循环行为。

五、常见误区

5.1 误区一：语法正确就意味着程序正确

语法正确只是程序正确的最基本要求。一个程序即使通过了语法检查，仍可能存在类型错误（违反静态语义）、逻辑错误（违反预期语义）或运行时错误（违反运行时语义约束）。编译器能检查的只是语法和部分静态语义，程序的逻辑正确性最终需要程序员通过测试和形式化验证来保证。

5.2 误区二：BNF可以描述所有语法规则

BNF能够精确描述上下文无关语言的语法，但编程语言的某些语法规则是上下文相关的，无法用BNF单独表达。例如，变量必须先声明后使用、函数参数的个数必须与声明一致、break语句只能出现在循环内部等。这些约束属于静态语义的范畴，需要在语法分析之后的语义分析阶段进行检查。

5.3 误区三：语义只有运行时才重要

虽然语义确实描述了程序的运行时行为，但语义分析在编译时就已经开始。类型检查、常量折叠、可达性分析等编译时活动都属于语义分析的范畴。忽视编译时的语义分析会导致许多可以在早期发现的错误被推迟到运行时，增加调试成本。

5.4 误区四：不同语言的语法差异比语义差异更大

实际上，语法相似的语言可能在语义上存在巨大差异。JavaScript的 var 声明具有函数作用域提升特性，而Java的变量声明具有块作用域且不会提升。两者在语法上几乎相同，但语义完全不同。理解语言之间的真正差异，需要深入到语义层面而非停留在语法表面。

六、本章小结

本章系统讲解了编程语言语法和语义的基本概念与形式化描述方法。语法规定了程序的书写形式，通过BNF等工具可以精确表达程序的层次结构；语义定义了程序的实际行为，需要借助操作语义、指称语义或公理语义等形式化模型来描述。语法与语义的分离是语言设计的重要原则，它使得形式与含义可以独立演化。静态语义作为语法和运行时语义之间的桥梁，承担了类型检查等重要的编译时验证任务。理解语法与语义的关系有助于我们深入认识编译器的处理过程，为后续学习词法分析、语法分析以及类型系统奠定理论基础。

七、思考题

请用BNF范式描述一种你熟悉的编程语言中if-else语句的语法规则，并讨论可能存在的歧义性及其解决方案。

操作语义、指称语义和公理语义各有什么优缺点？在什么场景下你会选择使用其中某一种？

为什么说类型检查属于静态语义的范畴而非语法分析的范畴？请举例说明仅靠语法无法捕获的类型错误。

请解释"语法等价但语义不同"和"语义等价但语法不同"这两个概念，并各举一个具体例子。

在实际编程中，你遇到过哪些因为语法相似但语义不同而导致的错误？这些经验如何影响了你对语言选择的理解？