用java语言编写的递归下降语法分析器是一种适用于手写语法分析器的方法，非常简单。 递归下降法在语言语法中存在一些限制，但递归下降是目前主流的语法分析方法。 这对于提供错误消息也是有利的，因为开发者可以高度控制。 甚至微软c#公式的编译器也是手写的递归下降语法分析器。
使用递归下降法创建语法分析器不需要类库，如果要创建简单的分析器，则不需要使用先前学习的词法分析器库。 请看一个例子。 现在有表示二叉树的字符串表示。 其语法为na(n，n )
N
但是，终端符号a表示任意的英文字母，表示空。 这个语法的意思是二叉树的节点为空，或者以文字开头，带有一对括号。 括号中逗号的左侧是此节点的左儿子，逗号的右侧是此节点的右儿子。 例如，字符串a(b )、c )、d )、d ) )表示这样的二叉树。
注意
语法规定即使节点没有儿子，也不能省略括号和逗号，所以如果只有一个节点，就写a (，)。 在这里写解析器，输入这个字符串，在内存中制作这个二叉树。
其中的二叉树由一个名为class Node的类表示
{
公共节点左倾{ get； 私有集； }
公共节点权限池{ get； 私有集； }
公共字符标签{ get； 私有集； }
公共节点(charlabel、Node left、Node right ) )。
{
标签=标签；
LeftChild=left；
RightChild=right；
}
}
这是微软的面试问题，很难打败很多参加面试的候选人。 在座的各位对写这个程序有信心吗？ 很多参加者考虑了使用堆栈，或者使用递归查找逗号位置并分解字符串等方法。 但是，使用递归下降法，这个程序非常容易写。
一般步骤：
使用索引记录当前扫描的位置。 通常是整数字段。
为每个非终结符创建方法。
如果一个非终结符有一个以上的生成式，则该方法分支预测采用哪个生成式。
处理单个生成表达式时，如果检测到正确的终结器，则在第一步中创建的扫描索引的位置将向前移动。 如果检测到非终结符，请调用在步骤2中创建的相应方法。
如果需要类似于本示例中二叉树的分析结果，请在方法返回之前对其进行结构化。
马上试试吧。 首先创建类，保存索引变量并保存当前扫描位置。 然后，要为每个非终结符创建方法，只需创建名为class BinaryTreeParser的方法，因为语法中只有一个非终结符n
{
私有字符串m _ input string；
私有int m _ index；
//初始化输入字符串和索引的构造函数，缩写为
节点珀斯节点(
{
}
}
返回刚才的生成公式，因为非终结符号n有两个生成公式，所以必须在ParseNode方法的开头进行分支预测。 分支预测的方法是前瞻(look ahead )。 我们首先“窥视”当前位置前方的文字，判断应该用哪个生成式继续分析。 不是终结符n的两个生成式之一生成a(n，n )的结构，另一个直接生成空字符串。 那我知道现在至少有一个可能会遇到字母。 此时，应该使用na(n，n )的生成式继续分析。 那么，应该什么时候用N 进行分析呢？ 观察生成式右侧出现n的所有地方，如果n是空字符串，则直接出现n之后的字符，即逗号和方括号。 这是我们的分歧预测
超前观察遇到英文字母时，预测分支na(n，n )
逗号，遇到方括号预测分支N 时
转换成代码就是这样的。 节点珀斯节点()。
{
int lookAheadIndex=m_index；
charlookaheadchar=m _ input string [ look ahead index ]；
if(char.isletter(lookAheadchar ) )
{
//n采用a (n，n )继续分析
}
elseif(lookaheadchar=='，'|| lookAheadChar==' ) )
{
//n继续分析
}
else
{
throw new Exception (“语法错误”)；
}
}
接下来，我们来看看两个分支是如何处理的。 先看看N 吧。 这种情况下
下非终结符是个空字符串，所以我们不需要移动当前索引，直接返回null表示空节点。再来看N → a(N, N) 分支，倘若输入的字符串没有任何语法错误，那就应该依次遇到字母、左括号、N、逗号、N右括号。根据上面的规则，凡是遇到终结符，就移动当前索引，直接向前扫描；而要是遇到非终结符，就递归调用相应节点的方法。所以(不考虑语法错误)的完整方法代码如下：Node ParseNode(){
int lookAheadIndex = m_index;
char lookAheadChar = m_inputString[lookAheadIndex];
if (Char.IsLetter(lookAheadChar))
{
//采用N → a(N, N)继续分析
char label = m_inputString[m_index++]; //解析字母
m_index++; //解析左括号，因为不需要使用它的值，所以直接跳过
Node left = ParseNode(); //非终结符N，递归调用
m_index++; //解析逗号，跳过
Node right = ParseNode(); //非终结符N，递归调用
m_index++; //解析右括号，跳过
return new Node(label, left, right);
}
else if (lookAheadChar == ',' || lookAheadChar == ')')
{
//采用N → ε继续分析
//无需消耗输入字符，直接返回null
return null;
}
else
{
throw new Exception("语法错误");
}
}
因为存在语法约束，所以一旦我们完成了分支预测，就能清楚地知道下一个字符或非终结符一定是什么，无需再进行任何判断(除非要进行语法错误检查)。因此根本就不需要寻找逗号在什么位置，我们解析到逗号时，逗号一定就在那，这种感觉是不是很棒？只需要寥寥几行代码就已经写出了一个完整的Parser。大家感兴趣可以继续补全一些辅助代码，然后用真正的字符串输入试验一下，是否工作正常。前面假设输入字符串的语法是正确的，但真实世界的程序总会写错，所以编译器需要能够帮助检查语法错误。在上述程序中加入语法错误检查非常容易，只要验证每个位置的字符，是否真的等于产生式中规定的终结符就可以了。这就留给大家做个练习吧。
上面我们采用的分支预测法是“人肉观察法”，编译原理书里一般都有一些计算FIRST集合或FOLLOW集合的算法，可以算出一个产生式可能开头的字符，这样就可以用自动的方法写出分支预测，从而实现递归下降语法分析器的自动化生成。ANTLR就是用这种原理实现的一个著名工具。有兴趣的同学可以去看编译原理书。其实我觉得“人肉观察法”在实践中并不困难，因为编程语言的文法都特别有规律，而且我们天天用编程语言写代码，都很有经验了。
下面我们要研究一下递归下降法对文法有什么限制。首先，我们必须要通过超前查看进行分支预测。支持递归下降的文法，必须能通过从左往右超前查看k个字符决定采用哪一个产生式。我们把这样的文法称作LL(k)文法。这个名字中第一个L表示从左往右扫描字符串，这一点可以从我们的index变量从0开始递增的特性看出来；而第二个L表示最左推导，想必大家还记得上一篇介绍的最左推导的例子。大家可以用调试器跟踪一遍递归下降语法分析器的分析过程，就能很容易地感受到它的确是最左推导的(总是先展开当前句型最左边的非终结符)。最后括号中的k表示需要超前查看k个字符。如果在每个非终结符的解析方法开头超前查看k个字符不能决定采用哪个产生式，那这个文法就不能用递归下降的方法来解析。比如下面的文法：F → id
F → ( E )
E → F * F
E → F / F
当我们编写非终结符E的解析方法时，需要在两个E产生式中进行分支预测。然而两个E产生式都以F开头，而且F本身又可能是任意长的表达式，无论超前查看多少字符，都无法判定到底应该用乘号的产生式还是除号的产生式。遇到这种情况，我们可以用提取左公因式的方法，将它转化为LL(k)的文法：F → id
F → ( E )
G → * F
G → / FE → FG
我们将一个左公因式F提取出来，然后将剩下的部分做成一个新的产生式G。在解析G的时候，很容易进行分支预测。而解析E的时候则无需再进行分支预测了。在实践中，提取左公因式不仅可以将文法转化为LL(k)型，还能有助于减少重复的解析，提高性能。
下面我们来看LL(k)文法的第二个重要的限制——不支持左递归。所谓左递归，就是产生式产生的第一个符号有可能是该产生式本身的非终结符。下面的文法是一个直截了当的左递归例子：F → id
E → E + F
E → F
这个表达式类似于我们上篇末尾得到的无歧义二元运算符的文法。但这个文法存在左递归：E产生的第一个符号就是E本身。我们想像一下，如果在编写E的递归下降解析函数时，直接在函数的开头递归调用自己，输入字符串完全没有消耗，这种递归调用就会变成一种死循环。所以，左递归是必须要消除的文法结构。解决的方法通常是将左递归转化为等价的右递归形式：F → id
E → FG
G → + FG
G → ε
大家应该牢牢记住这个例子，这不仅仅是个例子，更是解除大部分左递归的万能公式！我们将要在编写miniSharp语法分析器的时候一次又一次地用到这种变换。