1.2 语法

编程语言可以被认为是程序的 集合 。这个集合是无限的（也就是说，人们总是可以创建更大的程序），所以不能简单地通过列出语言中的所有程序来描述一种语言。相反，我们写下了一组规则，即 上下文无关的语法 ，据此构建程序。语法通常用于定义语言的具体语法，但也可用于描述抽象语法。我们用Backus-Naur范式（BNF）（Backus et al.1960；Knuth 1964）的一种变体来写出语言规则。作为一个例子，我们描述了一个名为 L _Int 的小语言，它由整数和算术运算组成。

L _Int 抽象语法的第一条语法规则是：Constant（常量类）的实例是一个表达式：

每条规则都有左侧和右侧。如果有一个与右侧匹配的AST节点，那么可以根据左侧对其进行分类。采用代码字体的符号，如Constant，是 终结符 ，必须字面上出现在程序中才能适用该规则。我们的语法没有提到 空白 符号，即像空格、制表符和新行这样的分隔符。符号之间可以插入空白以消除歧义并提高可读性。由语法规则定义的名称（如 exp ）是 非终结符 。 int 也是一个非终结符，但是我们没有使用语法规则来定义它，而是用下面的解释来定义它。 int 是一个数序列（0到9），可能以“-”开始（表示负整数），这个数序列表示一个范围在-2 ⁶³ 到2 ⁶³ -1之间的整数。这里允许使用64位表示整数，从而会在几个方面简化编译。相比之下，Python语言中的整数具有无限精度，但处理无限精度所需的具体技术超出了本书的范围。

第二个语法规则是input_int操作，它接收程序的用户输入的整数。

第三条规则可归类为将 exp 节点取负仍为 exp 。

我们可以应用这些规则对 L _Int 语言中的AST进行分类。例如，根据规则（1.2），Constant（8）是一个 exp ，然后根据规则（1.4），下面的AST是一个 exp 。

下面两个语法规则是关于加法和减法表达式的：

现在我们可以证明规则（1.1）中的AST是 L _Int 中的一个 exp 。我们知道，根据规则（1.3），Call（Name（'input_int'）,[]）是表达式 exp ，并且我们已知道UnaryOp（USub（）, Constant（8））分类为 exp ，因此根据规则（1.6）可以证明

是 L _Int 语言中的一个 exp 。

如果你有一个不适用于这些规则的AST，那么这个AST就不在 L _Int 语言中。例如，程序input_int（）* 8不在 L _Int 中，因为没有“*”操作符的规则。当我们用语法定义一种语言时，该语言就只包括那些被语法规则证明正确的程序。

语言 L _Int 为定义语句包含了第二个非终结符 stmt 。有一条语句用于打印表达式的值：

以及对表达式求值但忽略结果的语句：

L _Int 语言的最后一个语法规则指出，有一个Module节点标记整个程序的顶部：

其中星号“*”表示前面语法项的列表，在本例中是语句列表。Module类定义如下：

其中body是语句列表。

在语法中，许多语法规则的左侧相同但右侧不同，这是很常见的，例如 L _Int 语法中的 exp 规则。作为简单记法，竖线可以用来将几个右侧组合在一个语法规则中。

L _Int 语言的具体语法见图1.1，抽象语法见图1.2。我们建议使用Python的ast模块中的parse函数将具体语法转换为抽象语法树。