論壇

本章我们呈现了一个简单的编程语言, 以作为之后章节的基础.

1.1 抽象句法树

我们的程序常以程序文本作为输入或输出, 实际上是程序文本的表示. 至于如何表示程序, 让我们回忆句法的定义. 句法描述了由较小的语言成分构造较大的语言成分之规则. 这暗示着, 在最理想的情况下, 程序文本具有上下文无关的树结构, 即抽象句法树. 将程序文本从字符序列的表面形式转换为抽象句法树的过程被称为句法分析. 我们没有涵盖句法分析, 鉴于它不是编程语言的最核心内容.

1.2 BNF文法

BNF文法是描述句法的标准工具.

鉴于BNF文法总以变种形式出现, 我们以一个例子刻画其用法.

以尖括号括起来的符号代表句法范畴, 即句法树的集合. 其余的符号代表字面本身. ::=的含义是定义,而|的含义近于或. 每个出现于右侧的句法范畴都意图被其一个元素替换以产生左侧的一个实例. 我们预先定义了一些范畴, <int>代表Scheme整数的集合, <bool>代表Scheme布尔的集合, <var>代表Scheme符号的集合.

1.3 解释器的风味

解释是赋予句法语义的过程. 一个解释器是一个程序, 其以程序文本为输入, 以值为输出. 于是, 解释器可以被视为对于其所解释的语言的语义的描述.

本节我们呈现了一个简单的解释器, 其为句法导向的结构递归. 为了方便地解构句法树, 我们引入了用于模式匹配的宏match, 其定义见附录.