自己动手开发编译器（七）递归下降的语法分析

你是否正在寻找关于递归下降的内容？让我把最有价值的东西奉献给你：

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

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

N → a ( N, N )
N → ε

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

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

class Node { public Node LeftChild { get; private set; } public Node RightChild { get; private set; } public char Label { get; private set; } public Node(char label, Node left, Node right) { Label = label; LeftChild = left; RightChild = right; } }

这是一道微软面试题，曾经难倒了不少参加面试的候选人。不知在座各位是否对写出这段程序有信心呢？不少参选者想到了要用栈，或者用递归，去寻找逗号的位置将字符串拆解开来等等方法。但是若是使用递归下降法，这个程序写起来非常容易。我们来看看编写递归下降语法分析器的一般步骤：

我们马上来试验一下。首先建立一个类，然后存放一个索引变量来保存当前扫描位置。然后要为每一个非终结符创建一个方法，我们的文法中只有一个非终结符N，所以只需创建一个方法：

class BinaryTreeParser { private string m_inputString; private int m_index; //初始化输入字符串和索引的构造函数，略 Node ParseNode() { } }

回到刚才的产生式，我们看到非终结符N有两个产生式，所以在ParseNode方法的一开始我们必须做出分支预测。分支预测的方法是超前查看（look ahead）。就是说我们先“偷窥”当前位置前方的字符，然后判断应该用哪个产生式继续分析。非终结符N的两个产生式其中一个会产生a(N, N)这个的结构，而另一个则直接产生空字符串。那现在知道，起码有一种可能就是会遇到一个字母，这时候应该采用N → a(N, N)这个产生式继续分析。那么什么时候应该采用N → ε进行分析呢？我们观察产生式右侧所有出现N的地方，倘若N是空字符串，那么N后面的字符就会直接出现，也就是逗号和右括号。于是这就是我们的分支预测：

转化成代码就是这样：

Node ParseNode() { int lookAheadIndex = m_index; char lookAheadChar = m_inputString[lookAheadIndex]; if (Char.IsLetter(lookAheadChar)) { //采用N → a(N, N)继续分析 } else if (lookAheadChar == ',' || lookAheadChar == ')' ) { //采用N → ε继续分析 } else { throw new Exception("语法错误"); } }

接下来我们分别来看两个分支怎么处理。先来看N → ε，这种情况下非终结符是个空字符串，所以我们不需要移动当前索引，直接返回null表示空节点。再来看N → a(N, N) 分支，倘若输入的字符串没有任何语法错误，那就应该依次遇到字母、左括号、N、逗号、N右括号。根据上面的规则，凡是遇到终结符，就移动当前索引，直接向前扫描；而要是遇到非终结符，就递归调用相应节点的方法。所以（不考虑语法错误）的完整方法代码如下：

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/shenmilingyu/article-1094-1.html