（转载）算术表达式的自上而下语法分析及其实现（上）

学过编译原理的同学大概都知道对一个句子进行自上而下语法分析的方法。我参考了陈火旺院士的《高级程序设计语言编译原理》，在这篇文章里我主要是站在编译原理的角度讲述一种语法分析程序的实现的方法，通过对一个典型的例子——算术表达式的分析，从而使大家了解构造一个实用的语法分析程序的方法，同时，也为广大程序员提供一种解决实际问题的思路。

本文包括以下内容：
1． 算术表达式的产生式；
2． 自上而下语法分析的算法和的产生式函数的构造；
3． 产生式函数的改进；
4． 语法分析中的出错处理；
5． 自上而下语法分析程序的实现。


1． 算术表达式的产生式

我在这里要实现的算术表达式要实现5种运算：加、减、乘、除和括号。比如一个简单的算术表达式的文法G1中包含以下产生式：
G1:
E -> E+E | E-E | E*E | E/E | (E) | i
为了明确运算符的优先权（括号的优先权高于乘除法，乘除法的优先权高于加减法），可改写文法G1如下：
改写后的文法G2:
E -> T+E | T-E | T
T -> F*T | F/T | F
F -> (E) | i
任何具有加、减、乘、除和括号运算优先权的算术表达式都可以通过上述文法中的产生式推导出来，比如对于行如i-i*(i+i)的算术表达式，有如下推导过程(其中i是数字或变量标示符，推导需要从开始符E开始推导，以下是最左推导)：

E=> T-E => F-E => i-E => i-T => i-F*T => i-i*T => i-i*F => i-i*(E) => i-i*(T+E) =>i-i*(F+E) => i-i*(i+E) => i-i*(i+T) => i-i*(i+F) => i-i*(i+i)

在本文中，我们就使用文法G2中的产生式构造语法分析程序。

2．自上而下语法分析的算法和的产生式函数的构造

我们可以把一个对句子从开始符E到终结符的推导过程转化为一棵语法树，根节点（即开始符）在上、叶节点（即终结符）在下，自上而下的语法分析就是对这样一棵语法树“自上而下”地遍历过程。即，每次遍历从根节点（开始符）开始，通过各个中间节点（除开始符外非终结符）到达叶节点（终结符）。如果把每一个产生式做成一个函数，那么我们可以方便地通过对这些函数的递归调用和回溯来实现对语法树的遍历。那么对于文法G2中的3个产生式，我们需要3个函数：
void E_AddSub();            //对应于非终结符E的产生式
void T_MulDiv();               //对应于非终结符T的产生式
void F_Number();             //对应于非终结符F的产生式

我们通过对输入字符流的分析来实现自上而下的语法分析。在语法分析的过程中，我们需要一个输入字符缓冲区，用来存放输入的算术表达式字符串，需要一个字符指示器来指示当前正在分析的字符，还需要一个出错处理模块。在算法设计实现中，我们用到了3个全局成员：ch、advance和error，它们的含义如下：

ch                  当前指示器所指的字符
advance()     使指示器指向输入字符缓冲器中的下一个字符的函数
error()            出错处理程序函数

由此可以构造自上而下语法分析算法，首先分析产生式E -> T+E | T-E | T，不妨先把它分解成以下3个产生式：
E -> T+E
E -> T-E
E -> T
下面首先写出E -> T+E个语法分析函数：

//清单1：产生式E -> T+E的语法分析函数
void E_AddSub()
{
T_MulDiv();           //调用非终结符T的产生式函数分析T
If(ch==’+’)       //如果当前字符是’+’，
{
  advance();           //则取下一个字符
  E_AddSub();       //调用非终结符E的产生式函数分析E
}
else                     //如果不是’+’号
  error();                //则进行出错处理
}

看到上面函数中的算法，你大概已经可以想到产生式E -> T-E 的自上而下语法分析算法了，即把If(ch==’+’) 一句中的’+’改成’-‘号即可。下面是产生式E -> T 的算法，很简单：

//清单2：产生式E -> T的语法分析函数
void E_AddSub()
{
T_MulDiv();     //调用非终结符T的产生式函数分析T
}

大家可以看到，为每一个产生式写一个分析函数，通过它们之间的相互调用，即可实现对语法树的遍历，从而实现对句子的推导。由于E -> T+E、E -> T-E、E -> T三个产生式可以合并成E -> T+E | T-E | T，我们也可以把对应的三个产生式的函数合并成一个函数，由于有产生式E -> T ，所以在E的产生式函数中只调用非终结符T的分析函数就可以了，即使下一个字符不是’+’或’-‘也不必做错误处理，而E -> T+E | T-E的合并用一句分支语句if(ch==’+’||ch==’-‘)判断即可，这样，合并后E产生式的函数如下：

//清单3：产生式E -> T+E | T-E | T的分析函数
void E_AddSub()
{
T_MulDiv();                        //调用非终结符T的产生式函数分析T
If(ch==’+’ ||ch==’-‘)   //如果当前字符是’+’或’-‘，
                                         //如果是’+’，则用产生式E -> T+E推导，
                                         //如果是’-‘，则用产生式E -> T-E推导。
{
  advance();                        //则取下一个字符
  E_AddSub();                    //调用非终结符E的产生式函数分析E
}                                      //此时产生式E -> T+E | T-E的推导算法结束
                                        //如果下一个字符不是不是’+’或’-‘，
                                        //则本函数是根据产生式E -> T来进行推导的，不必进行错误处理。
}

同理，你也可以容易地写出产生式T -> F*T | F/T | F和F -> (E) | i的自上而下语法分析函数：

//清单4：产生式T -> F*T | F/T | F的分析函数
void T_MulDiv()
{
F_Number();                      //调用非终结符F的产生式函数分析F
If(ch==’*’ ||ch==’/‘)   //如果当前字符是’*’或’\‘，
                                        //如果是’*’，则用产生式T -> F*T推导，
                                        //如果是’\‘，则用产生式T -> F/T推导。
{
  advance();                       //则取下一个字符
  T_MulDiv();                      //调用非终结符T的产生式函数分析T
}                                      //此时产生式T -> F*T | F/T 的推导算法结束
                                        //如果下一个字符不是不是’*’或’/‘，
                                        //则本函数是根据产生式T -> F 来进行推导的，不必进行错误处理。
}

//清单5：产生式F -> (E) | i的分析函数
void F_Number()
{
if(ch==’(‘)                   //如果当前的指示器指示的字符是’(‘
{                                    //则根据产生式F -> (E)推导
  advance();                     //跳过’(‘，指示器指向下一个字符
  E_AddSub();                 //调用非终结符E的产生式函数分析E
  If(ch!=’)’)                  //判断下一个字符是否是’)’，
                                     //必须保证有右括号与左括号配对使用
   error();                        //如果出错，则进行出错处理。
  Advance();                   //如果有’)’，语法正确，跳过’)’
 
  return;                         //返回
}
if(ch是数字)                  //如果当前指示器指示的字符是数字
{                                  //则根据产生式F -> i推导
  advance();                   //跳过该数字，指示器指向下一个字符
}                                 //语法正确，完成F -> i推导
else                            //如果当前指示器指示的字符不是数字也不是’(‘
  error();                       //则出错，转向出错处理程序

return;                        //返回
}

由于，符合语法的句子的推导是从开始符E开始的，所以在进行语法分析时，需要在主程序中这样实现：

//清单6：主程序
int main()
{
………………………………
//对输入字符缓冲区和字符指示器初始化
//调用开始符E的分析函数开始自上而下语法分析：
E_AddSub();
//分析结束
………………………………
return 0;
}

按照此方法实现的上述函数实现了对语法树的自上到下的遍历，从而展示了自上而下语法分析的过程，然而，这些函数并没有实现具体的功能，比如执行算术表达式或计算求值的功能，在下面的几节里我会陆续考虑这些问题。