编译原理之路（三）递归下降的语法子程序设计

要想设计语法解析器，我们必须首先设计一种子程序，能够解析任何一个产生式，比如对于

A->TE’|BC| <math> <semantics> <mrow> <mi> ϵ </mi> </mrow> <annotation encoding="application&#47;x&#45;tex"> \epsilon </annotation> </semantics> </math>ϵ

这样的表达式，如果我们写一个程序来检测他，应该怎么办呢？

PROCEDURE A;
BEGIN
	IF SYM IN FIRST(TE') THEN
		BEGIN T;E' END
	ELSE IF SYM IN FIRST(BC) THEN
		BEGIN B;C END
	ELSE IF SYM IN FOLLOW(A) THEM 
		BEGIN END
	ELSE ERROR

由代码可以轻易理解，这是一个判断A的子程序，SYM表示当前指针指向的字符，如果在TE‘中，就执行T E的子程序，在BC 中，就执行BC的子程序
如果在 <math> <semantics> <mrow> <mi> ϵ </mi> </mrow> <annotation encoding="application&#47;x&#45;tex"> \epsilon </annotation> </semantics> </math>ϵ中，也就是A为空，那么直接跳过到下一个字符，就等同于在FOLLOW(A)中
如果三者都不是，就会报错

对于A的推导，一定是以上四种情况之一，执行完毕后，A推导完成

有趣的是，我们的语法是自顶向下递归的，但我们写程序可以按自己的相符顺序来写。
以下是较复杂的文法的子程序设计（来自中国大学mooc国防科技大学的ppt，讲得很不错，推荐！）

ADVANCE指的是指针往前指向下一个字符，比如在F的子程序设计中，如果SYM指向了i或者),那么F就推导完成，可以直接往下走了

下面图中
左下角的程序是E的，比较简单

右边两个程序，上面蓝色背景部分是精简版，和下面等价

绿字部分SYM!=’#’ AND SYM!=’)‘其实表示的就是不指向 <math> <semantics> <mrow> <mi> ϵ </mi> </mrow> <annotation encoding="application&#47;x&#45;tex"> \epsilon </annotation> </semantics> </math>ϵ的意思，
开头已经解释，所谓指向 <math> <semantics> <mrow> <mi> ϵ </mi> </mrow> <annotation encoding="application&#47;x&#45;tex"> \epsilon </annotation> </semantics> </math>ϵ就是指向自己的follow()，E’的follow()是’)‘和’#’，因为指向 <math> <semantics> <mrow> <mi> ϵ </mi> </mrow> <annotation encoding="application&#47;x&#45;tex"> \epsilon </annotation> </semantics> </math>ϵ什么都没做，所以判定省略了，直接判定不指向 <math> <semantics> <mrow> <mi> ϵ </mi> </mrow> <annotation encoding="application&#47;x&#45;tex"> \epsilon </annotation> </semantics> </math>ϵ的情况，返回error，

接下来是判定T和T’的，同一个模式，同一个答案

最后是主程序

小结：总体思路是确定当前的字符，然后继续往下，难点在于一个非终结符可以有多个产生式，此时就要多个if进行判定，如果为空，则可以跳过