如何实现自己动手开发的编译器（七）中的递归下降语法分析器？

本文共计3284个文字，预计阅读时间需要14分钟。

回顾我们讨论到的语法分析，使用的上下文无关语言无关，描述上下文无关文法产生的语法分析树等概念。今天我们来探讨实际编写语法分析器的方法。

上回我们说到语法分析使用的上下文无关语言，以及描述上下文无关文法的产生式、产生式推导和语法分析树等概念。今天我们就来讨论实际编写语法分析器的方法。今天介绍的这种方法叫做递归下降（recursive descent）法，这是一种适合手写语法编译器的方法，且非常简单。递归下降法对语言所用的文法有一些限制，但递归下降是现阶段主流的语法分析方法，因为它可以由开发人员高度控制，在提供错误信息方面也很有优势。就连微软C#官方的编译器也是手写而成的递归下降语法分析器。

使用递归下降法编写语法分析器无需任何类库，编写简单的分析器时甚至连前面学习的词法分析库都无需使用。我们来看一个例子：现在有一种表示二叉树的字符串表达式，它的文法是：

N → a ( N, N )
N → ε

其中终结符a表示任意一个英文字母，ε表示空。这个文法的含义是，二叉树的节点要么是空，要么是一个字母开头，并带有一对括号，括号中逗号左边是这个节点的左儿子，逗号右边是这个节点的右儿子。例如字符串 A(B(,C(,)),D(,))就表示这样一棵二叉树：

注意，文法规定节点即使没有儿子（儿子是空），括号和逗号也是不可省略的，所以只有一个节点的话也要写成A(,)。现在我们要写一个解析器，输入这种字符串，然后在内存中建立起这棵二叉树。