2.1.2 语法分析
词法分析器的输入是文本字符串，语法分析器的输入则是词法分析器识别的词法记号序列。语法分析器的输出不再是一串线性符号序列，而是一种树形的数据结构，通常称之为抽象语法树。见图2-4。
继续前面赋值语句的例子，我们可以先看看它可能对应的抽象语法树，如图2-5所示。
图2-5 抽象语法树示例
从图2-5中可以看出，所有的词法记号都出现在树的叶子节点上，我们称这样的叶子节点为终结符。而所有的非叶子节点，都是对一串词法记号的抽象概括，我们称之为非终结符，可以将非终结符看作一个单独的语法模块（抽象语法子树）。其实，整个源程序是一棵完整的抽象语法树，它由一系列语法模块按照树结构组织起来。语法分析器就是要获得源程序的抽象语法树表示，这样才能让编译器具体识别每个语法模块的含义，分析出程序的整体含义。
在介绍语法分析器的工作之前，需要先获得高级语言语法的形式化表示，即文法。文法定义了源程序代码的书写规则，同时也是语法分析器构造抽象语法树的规则。如果要定义赋值语句的文法，一般可以表达成如下产生式的形式：
<赋值语句> => 标识符 等号 <表达式> 分号
被“< >”括起来的内容表示非终结符，终结符直接书写即可，上式可以读作“赋值语句推导出标识符、等号、表达式和分号”。显然，表达式也有相关的文法定义。根据定义好的高级语言特性，可以设计出相应的高级语言的文法，使用文法可以准确地表达高级语言的语法规则。
有了高级语言的文法表示，就可以构造语法分析器来生成抽象语法树。在编译原理教材中，描述了很多的文法分析算法，有自顶向下的LL（1）分析，也有自底向上的算符优先分析、LR分析等。其中最常使用的是LL（1）和LR分析。相比而言，LR分析器能力更强，但是分析器设计比较复杂，不适合手工构造。我们设计的高级语言文法，只要稍加约束便能使LL（1）分析器正常工作，因此本书采用LL（1）分析器来完成语法分析的工作。递归下降子程序作为LL（1）算法的一种便捷的实现方式，非常适合手工实现语法分析器。
递归下降子程序的基本原则是：将产生式左侧的非终结符转化为函数定义，将产生式右侧的非终结符转化为函数调用，将终结符转化为词法记号匹配。例如前面提到的赋值语句对应的子程序的伪代码大致是这样的。
void 赋值语句()
{
match(标识符);
match(等号);
表达式();
match(分号);
}
每次对子程序的调用，就是按照前序的方式对该抽象语法子树的一次构造。例如在构造赋值语句子树时，会先构造“赋值语句”根节点，然后依次匹配标识符、等号子节点。当遇到下一个非终结符时，会进入对应的“表达式”子程序内继续按照前序方式构造子树的子树。最后匹配当前子程序的最后一个子节点，完成“赋值语句”子树的构造。整个语法分析就是按照这样的方式构造“程序”树的一个过程，一旦在终结符匹配过程中出现读入的词法记号与预期的词法记号不吻合的情况，便会产生语法错误。
在实际语法分析器实现中，并不一定要显式地构造出抽象语法树。递归下降子程序实现的语法分析器，使得抽象语法树的语法模块都蕴含在每次子程序的执行中，即每次子程序的正确执行都表示识别了对应的语法模块。因此，可以在语法分析子程序中直接进行后续的工作，如语义分析及代码生成。
