1.2
语法

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

L _Int 语言抽象语法的第一条语法规则是说Int结构体的实例是一个表达式：

每条规则都有左侧和右侧。如果有一个与规则右侧相匹配的AST节点，那么可以根据左侧对其进行分类。式中打字机字体的符号，如Int，是 终结 符号，必须直接出现在程序中才能适用该规则。我们的语法没有提到 空白 ，即像空格、制表符和新行这样的分隔符。符号之间可以插入空白以消除歧义并提高可读性。由语法规则定义的名称（比如 exp ）是非终结符。 int 也是一个 非终结符 ，但是我们没有使用语法规则来定义它，而是用下面的解释来给出定义。 int 是一个数字序列（0到9），可能以“-”开始（对于负整数），这个数字序列表示一个范围在-2 ⁶² 到2 ⁶² -1之间的整数。这一范围就允许使用63位表示整数，从而简化了编译的几个方面。因此，这些整数对应于64位机器上的Racket中的fixnum数据类型。

第二个语法规则是读取操作，它从程序用户那里接收一个输入整数。

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

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

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

现在我们可以证明（1.1）中的AST是 L _Int 语言中的一个 exp 。根据规则（1.3），我们知道（Prim ' read（））是一个 exp ，并且我们已经将（Prim '-（（Int 8）））分类归约为 exp ，因此我们应用规则（1.6）可证明

是 L _Int 语言中的 exp 。

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

L _Int 语言的最后一条语法规则声明有一个Program节点来标记整个程序的顶部：

程序结构Program定义如下：

其中body是一个表达式。在后面的章节中，info部分用于存储辅助信息，但现在它只是一个空列表。

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

L _Int 语言的具体语法见图1.1，它的抽象语法见图1.2。utilities.rkt包中提供了读程序read-program函数，它从文件（具体的Racket语法中的字符序列）中读取程序，并将其分析成为抽象语法树。有关详细信息，请参阅A.2节中对read-program函数的描述。