1.1. 语法分析树¶

本节内容包括：

1. 文法术语

2. 推导与语法分析树

文法为表达程序设计语言的语法提供了一种形式化方法。随后便用这种语法对语言中的“程序”进行语法分析，也就是确定它在语法上是否正确。一个 文法 由以下三个要素组成。

• 一组 终结符 （terminal）。这些终结符表示逻辑上属于同一类的词法单元或字符组，例如运算符符号、分隔符、关键字，以及最终构成被分析程序或表达式的变量名。对于代数表达式而言，终结符就是变量、数值常量、括号，以及允许使用的各种运算符。

• 一组 非终结符 （non-terminal）。这些非终结符表示我们正在分析的语言中的各种语法结构。特别地，其中一个非终结符被指定为该文法的开始符号。

• 一组 产生式 （production）。产生式是形式化规则，用来定义上一要点中非终结符的语法构成。产生式的形式为：

我们说，这样一条产生式左端（LHS）的非终结符 推导 出右端（RHS）的字符串。

本课程中使用的这类文法（即每条产生式左端只有一个非终结符的文法）更准确的说法是 上下文无关文法 （context-free grammar）或 BNF 文法 （Backus-Naur Form 的缩写，即巴科斯范式）。由于本课程不讨论其他类型的形式文法，我们可以放心地直接称它们为文法。

一个文法的例子有助于阐明上面的三部分定义。按照惯例，第一条产生式左端的非终结符就是开始符号，它最终必须能够被分析，才能构成语言中的一个完整表达式。因此，在下面的例子中，\(<exp>\) 就是开始符号。

1.1.1. 第一个示例文法¶

\[\begin{split}\begin{eqnarray*} <exp> &::=& <term>\\ &|& <exp> + <term> \\ &|& <exp> - <term> \\ &|& <exp> * <term> \\ &|& <exp> / <term> \\ <term> &::=& <var> \\ &|& ( <exp> ) \\ <var> &::=& A\ |\ B\ |\ C\ |\ \ldots\ |\ X\ |\ Y\ |\ Z \end{eqnarray*}\end{split}\]

这本质上是一个代数表达式文法，其中变量（即 \(<var>\) 非终结符）允许是单个大写字母。阅读文法时，竖线 \(|\) 表示“或”。因此 \(<var>\) 可以是 A 或 B 或 C……。\(<term>\) 非终结符要么是一个 \(<var>\) ，要么是一个带括号的 \(<exp>\) 。按照该文法，表达式 \(A + B * C\) 的推导过程如下面的幻灯片所示，最终结果是一棵 语法分析树 。你应当逐步浏览所有幻灯片，确保在每一步都理解正在应用哪条产生式来“生长”这棵语法分析树。

Settings

Saving...
Server Error
Resubmit

注意，在一棵完整的语法分析树中，叶结点总是终结符，而一次遍历该树、输出这些叶结点的过程将重现被分析的表达式。上面的幻灯片用红色高亮显示了这一点。

在继续之前，你应当完成本节下面这组四道复习题。在这些复习题中，符号 \(\epsilon\) 用来表示 空串 。当 \(\epsilon\) 出现在某条产生式的右端时，它意味着该产生式左端非终结符的一种可能是推导出空串，也就是不含任何字符的字符串。当被分析语言的语法允许该非终结符完全不出现时，通常会用到它。对于递归的产生式，它常常提供一种让递归触底的方式，类似于递归算法中递归终止条件所起的作用。

下面的第一道题是关于给定一个文法和一个字符串，构造其语法分析树的。

1.2. 由文法生成的字符串¶

下面这道题是关于判断给定字符串能否由给定文法生成的。

1.3. 刻画一个语言：例 1¶

下面这道题是关于识别由给定文法所定义语言中所有字符串的性质。

1.4. 刻画一个语言：例 2¶

下面这道题是关于精确刻画由给定文法生成的整个语言。