龙书 第二章

构造一个语法制导翻译器要从源语言的文法开始。一个文法描述了程序的层次结构。文法的定义使用了称为终结符号的基本符号和称为非终结符号的变量符号。这些符号代表了语言的构造。一个文法的规则，即产生式，由一个作为产生式头或产生式左部的非终结符，以及称为产生式体或产生式右部的终结符号/非终结符号序列组成。文法中有一个非终结符被指派为开始符号。
在描述一个翻译器时，在程序构造中附加属性是非常有用的。属性是指一个程序构造关联的任何量值。因为程序构造是使用文法符号来表示的，因此属性的概念也被扩展到文法符号上。属性的例子包括与一个表示数字的终结符号num相关联的整数值，或一个表示标识符的终结符号id相关联的字符串。
词法分析器从输入中逐个读取字符，并输出一个词法单元的流，其中词法单元由一个终结符号以及以属性值形式出现的附加信息组成。在图2-46中，词法单元被写成用<>括起的元组。词法单元<id, "peek">由终结符号id和一个指向包含字符串"peek"的符号表条目的指针构成。翻译器使用符号表来存放保留字和已经遇到的标识符。
语法分析要解决的问题是指出如何从一个文法的开始符号推导出一个给定的终结符号串。推导的方法是反复将某个非终结符替换为它的某个产生式体。从概念上讲，语法分析器会创建一棵语法分析树。该树的根结点的标号为方法的开始符号，每个非叶子结点对应于一个产生式，每个叶子结点的标号为一个终结符号或空串。语法分析树推导出由它的叶子结点从左到右组成的终结符号串。
使用被称为预测语法分析法的自顶向下（从语法分析树的根结点到叶子结点）方法可以手工建立高效的语法分析器。预测分析器有对应于每个非终结符的子过程。该过程的过程体模拟了这个非终结符号的各个产生式。只要在输入流中向前看一个符号，就可以无二义地确定该过程体中的控制流。
语法制导翻译通过在文法中添加规则或程序片段来完成。在此只考虑了综合属性。任意结点x上的一个综合属性的值只取决于x的子结点（如果有的话）上的属性值。语法制导定义将规则和产生式相关联，这些规则用于计算属性值。语法制导的翻译方案在产生式体中嵌入了称为语义动作的程序片段。这些语义动作按照语法分析中产生式的使用顺序执行。
语法分析的结果是源代码的一种中间表示形式，称为中间代码。抽象语法树中的各个结点代表了程序构造，一个结点的子结点给出了该构造有意义的子构造。另一种表示方法是三地址代码，它是一个由三地址指令组成的序列，其中每个指令只执行一个运算。
符号表是存放有关标识符的信息的数据结构。当分析一个标识符的声明的时候，该标识符的信息被放入符号表中。当在后来使用这个标识会时，比如它作为一个表达式的因子使用时，语义动作将从符号表中获取这些信息。