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

关键字 算术表达式 编译原理 语法分析 文法 产生式 终结符 非终结符 开始符 



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

本文包括以下内容： 
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; 
} 

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


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来进行推导的，不必进行错误处理。 
} 

大家看到，在if语句块中有一句E_AddSub();，这意味着在E_AddSub()函数中的语句可以调用自己本身，即函数中存在递归。然而在这里，我们完全可以节省一部分因递归占用的程序堆栈空间，在这同时也减少了因对程序堆栈进行push/pop操作耗费的时间。在这里我要用到的一种改进的方法是用循环代替if通过消除自身递归来削弱递归深度的方法，比如改进后的E_AddSub()函数如下： 

//清单7：改进后的产生式E -> T+E | T-E | T的分析函数 
void E_AddSub() 
{ 
T_MulDiv(); //调用非终结符T的产生式函数分析T 
while(ch==’+’ ||ch==’-‘) //如果当前字符是’+’或’-‘， 
//如果是’+’，则用产生式E -> T+E推导， 
//如果是’-‘，则用产生式E -> T-E推导。 
{ 
advance(); //则取下一个字符 
T_MulDiv(); //调用非终结符E的产生式函数分析T 
} //若当前指示器指示的符号是’+’或’-‘，则继续while循环 
//如果下一个字符不是不是’+’或’-‘， 
//则本函数是根据产生式E -> T来进行推导的，不必进行错误处理。 
} 

我们可以看到在清单7中，在把if变成while的同时，还把while语句块中的E_AddSub()变为T_MulDiv()，这意味着把产生式（其中op为’+’或’-‘）： 
E -> T op E 
转换为： 
E -> T op T op T op T op ……………… op T 
两者是等价的。显然对于型如i op i op i op i这样的句子，后者有更快的推导速度，而前者需要多进行3次递归堆栈。因此，改进后的产生式函数更高效。同样，T_MulDiv()也可以通过这种方法改进。 

然而，这种方法并不能完全消除递归，只是减少了递归的调用次数，削减了递归层次。每当分析到括号运算符时，因为F_Number()会被T_MulDiv()调用，T_MulDiv()会被E_AddSub()调用，所以会产生一个对开始符E的产生式函数的递归： 

void F_Number() 
{ 
if(ch==’(‘) //如果当前的指示器指示的字符是’(‘ 
{ //则根据产生式F -> (E)推导 
advance(); //跳过’(‘，指示器指向下一个字符 
E_AddSub(); //调用非终结符E的产生式函数分析E 
If(ch!=’)’) 
error(); //如果出错，则进行出错处理。 
Advance(); //如果有’)’，语法正确，跳过’)’ 
return; //返回 
} 
……………………………… 

return; //返回 
} 

按照这种方法只有在分析括号运算符内的算术表达式时才增加一个递归层次，可以有效地提高语法分析的执行效率。 

4． 语法分析中的出错处理 

进行出错处理也许是件很麻烦的事。想象一个设计良好的编译调试环境，比如Visual Studio，我们在用它开发编译程序时，不光可以知道哪一句错了，而且可以获得出错的原因。我们现在要做的是对一句算术表达式（如果出错的话）找出出错的原因，并把错误原因和相关信息提示给用户。这该怎么办呢？ 

《编译原理》的课本上大都讲过通过考察FIRST集和FOLLOW集构造语法分析表的方法来处理错误，这样可以把错误的处理方法填充到分析表中。然而在这里，既然我们已经构造好了文法产生式函数，简单地，这样，我们仅仅通过在函数中出现error()函数调用的地方进行分析一下即可逐步实现对错误的处理。 

考察清单5中产生式F -> (E) | i的函数： 

void F_Number() 
{ 
if(ch==’(‘) 
{ 
advance(); 
E_AddSub(); 
If(ch!=’)’) //如果当前指示器指示的字符不是’)’ ，则产生错误， 
error(); //错误号：1 
advance(); 

return; 
} 
if(ch是数字) 
{ 
advance(); 
} 
else //如果当前指示器指示的字符不是数字，则产生错误 
error(); //错误号：2 

return; 
} 

在上述代码中可以看到有两处可能产生错误的地方，其中1号错误产生的原因很容易看出来，是“缺少与左括号匹配的右括号”。2号错误产生的原因是“当前指示器指示的字符不是数字”，即在算术表达式中该出现数字的地方没有出现数字，比如当指示器指到非法表达式“23+#b”中的“#”、“1-（+”中的“+”和“2+*3”中的“*”时都属于这种情况。2号错误还有两种情况，一种是当括号内无表达式（即括号内表达式为空时），比如“3+（）”，这样需要判断当前指示的字符是否为’）’；第二种是表达式不完整（即表达式提前结束），比如“4*(2+3)+”，这需要判断当前指示的字符是否为’\0’（字符串结束符）。 

再考察一下清单6中的主函数： 

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

然而，根据我们的设计，当E_AddSub() 函数返回（分析结束）时，在指示器所指字符的后面有可能还有未被分析的字符，凡此时存在未被指示器扫描过的字符的表达式均为错误的表达式。比如当指示器指到非法表达式“2*（3+4）5”中的“5”、“2+3（4+5）”中的“（”和“23a”中的“a”时都属于这种错误情况。 

5． 自上而下语法分析程序的实现 

经过上面4步精心的准备，最令人激动的时刻到了。一般《编译原理》课本上的代码大都是无法在机器上运行的伪代码，在这里，你将要看到的是一个实用的可以检查错误的可以执行求值的基于自上而下语法分析算法的计算算术表达式的程序。 

不失一般性，我们规定算术表达式只可以进行整数的四则运算（含括号），这样我们需要扩充下面3个函数： 
int E_AddSub(); //对应于非终结符E的产生式 
int T_MulDiv(); //对应于非终结符T的产生式 
int F_Number(); //对应于非终结符F的产生式 
大家看到，上面的函数有返回值int，我们需要让这3个函数返回计算出的结果的值。为了计算出每个函数中子表达式的值，在E_AddSub()和T_MulDiv()函数中，我用一个变量rtn来存储运算符左部的值，用opr2来存储运算符右部的值，根据运算符进行相应的运算。 

为了保存输入的算术表达式，我用全局静态字符数组expr来表示输入字符缓冲区，用pos来表示字符指示器的值，这样，指示器取下一个字符的advance()操作可以用pos++来代替，而指示器所指示的字符可以就是expr[pos]。 

为了表示错误，我用宏定义了6种错误的错误代码，而且定义了对应的6条错误信息的字符串。同时把error()函数改造为： 
void Error(int ErrCode); 
这样通过传递错误代码可以使程序对错误进行相应的反应，包括指示错误位置、显示错误信息、发出提示音等。此外，我声明了出错跳转缓冲区静态变量errjb，errjb是一个std::jmp_buf类型的结构，可以通过setjmp()宏把当前程序的运行状态记录到errjb中，错误返回时，可以通过longjmp()函数;直接跳转到main()主程序setjmp()被调用的位置，而不是出错的函数体中。 

这样，一个功能齐全的算术表达式分析执行器构造完毕，注意，这样构造的程序不能识别一元运算符，比如输入“-1+1”会报错。 

下面是运行结果片段： 

1+( 
^ 语法错误 ！！！ 表达式非法结束或表达式不完整！ 
请重新输入! 
请输入一个算术表达式（输入“Q”或“q”退出）： 
2-() 
^ 语法错误 ！！！ 括号内无表达式或表达式不完整！ 
请重新输入! 
请输入一个算术表达式（输入“Q”或“q”退出）： 
2+(3+ 
^ 语法错误 ！！！ 表达式非法结束或表达式不完整！ 
请重新输入! 
请输入一个算术表达式（输入“Q”或“q”退出）： 
2+(3*9)+ 
^ 语法错误 ！！！ 表达式非法结束或表达式不完整！ 
请重新输入! 
请输入一个算术表达式（输入“Q”或“q”退出）： 
2*(2+4)4 
^ 语法错误 ！！！ 右括号后连接非法字符！ 
请重新输入! 


程序清单如下： 

/****算术表达式的分析和计算，文件名：Exp_c.cpp，代码/注释：hifrog**** 
***** 在VC6和Dev-C下调试通过 ****/ 
#include 
#include 
#include 
#include 
#include 

#define EXP_LEN 100 //定义输入字符缓冲区的长度 

/*------------出错代码的宏定义--------------*/ 
#define INVALID_CHAR_TAIL 0 //表达式后跟有非法字符 
#define CHAR_AFTER_RIGHT 1 //右括号后连接非法字符 
#define LEFT_AFTER_NUM 2 //数字后非法直接连接左括号 
#define INVALID_CHAR_IN 3 //表达式中含有非法字符 
#define NO_RIGHT 4 //缺少右括号 
#define EMPTY_BRACKET 5 //括号内无表达式 
#define UNEXPECTED_END 6 //预期外的算术表达式结束 

using namespace std; 

const string ErrCodeStr[]= //表达式出错信息 
{ 
"表达式后跟有非法字符！", 
"右括号后连接非法字符！", 
"数字后非法直接连接左括号！", 
"表达式中含有非法字符！", 
"缺少右括号！", 
"括号内无表达式或表达式不完整！", 
"表达式非法结束或表达式不完整！" 
}; 

static char expr[EXP_LEN]; //算术表达式输入字符缓冲区 
static int pos; //字符指示器标志：用来保存正在分析的字符的位置 
static jmp_buf errjb; //出错跳转缓冲器 

//********以下是函数声明********* 
//产生式“E -> T+E | T-E | T”的函数，用来分析加减算术表达式。 
int E_AddSub(); 
//产生式“T -> F*T | F/T | F”的函数，用来分析乘除算术表达式。 
int T_MulDiv(); 
//产生式“F -> i | (E)”的函数，用来分析数字和括号内的表达式。 
int F_Number(); 
//出错处理函数，可以指出错误位置，出错信息。 
void Error(int ErrCode); 

int main() 
{ 
int ans; //保存算术表达式的计算结果 
bool quit=false; //是否退出计算 

do 
{ 
//在此设定一个跳转目标，如果本程序的其他函数调用longjmp， 
//执行指令就跳转到这里，从这里继续执行。 
if(setjmp(errjb)==0) //如果没有错误 
{ 
pos=0; //初始化字符指示器为0，即指向输入字符串的第一个字符。 

cout<<"请输入一个算术表达式（输入“Q”或“q”退出）："< cin>>expr; //输入表达式，填充表达式字符缓冲区。 

if(expr[0]=='q'||expr[0]=='Q') 
//检查第一个字符，是否退出？ 
quit=true; 

else 
{ 
//调用推导式“E -> T+E | T-E | T”的函数， 
//从起始符号“E”开始推导。 
ans=E_AddSub(); 

//此时，程序认为对表达式的语法分析已经完毕，下面判断出错的原因： 

//如果表达式中的某个右括号后直接跟着数字或其他字符， 
//则报错，因为数字i不属于FOLLOW(）)集。 
if(expr[pos-1]==')'&&expr[pos]!='\0') 
Error(CHAR_AFTER_RIGHT); 

//如果表达式中的某个数字或右括号后直接跟着左括号， 
//则报错，因为左括号不属于FOLLOW(E)集。 
if(expr[pos]=='(') 
Error(LEFT_AFTER_NUM); 

//如果结尾有其他非法字符 
if(expr[pos]!='\0') 
Error(INVALID_CHAR_TAIL); 

cout<<"计算得出表达式的值为："< } 
} 
else 
{ 
//setjmp(errjb)!=0的情况： 
cout<<"请重新输入!"< } 
} 
while(!quit); 

return 0; 
} 

//产生式“E -> T+E | T-E | T”的函数，用来分析加减算术表达式。 
//返回计算结果 
int E_AddSub() 
{ 
int rtn=T_MulDiv(); //计算加减算术表达式的左元 

while(expr[pos]=='+'||expr[pos]=='-') 
{ 
int op=expr[pos++]; //取字符缓冲区中当前位置的符号到op 
int opr2=T_MulDiv();//计算加减算术表达式的右元 

//计算求值 
if(op=='+') //如果是"+"号 
rtn+=opr2; //则用加法计算 
else //否则（是"-"号） 
rtn-=opr2; //用减法计算 
} 
return rtn; 
} 

//推导式“T -> F*T | F/T | F”的函数，用来分析乘除算术表达式。 
//返回计算结果 
int T_MulDiv() 
{ 
int rtn=F_Number(); //计算乘除算术表达式的左元 

while(expr[pos]=='*'||expr[pos]=='/') 
{ 
int op=expr[pos++]; //取字符缓冲区中当前位置的符号到op 
int opr2=F_Number();//计算乘除算术表达式的右元 

//计算求值 
if(op=='*') //如果是"*"号 
rtn*=opr2; //则用乘法计算 
else //否则（是"\"号） 
rtn/=opr2; //用除法计算 
} 
return rtn; 
} 

//产生式“F -> i | (E)”的函数，用来分析数字和括号内的表达式。 
int F_Number() 
{ 
int rtn; //声明存储返回值的变量 

//用产生式F->(E)推导： 
if(expr[pos]=='(') //如果字符缓冲区当前位置的符号是"(" 
{ 
pos++; //则指示器加一指向下一个符号 
rtn=E_AddSub(); //调用产生式“E -> T+E | T-E | T”的分析函数 

if(expr[pos++]!=')')//如果没有与"("匹配的"" 
Error(NO_RIGHT);//则产生错误 

return rtn; 
} 


if(isdigit(expr[pos]))//如果字符缓冲区中当前位置的字符为数字 
{ 
//则用产生式F -> i推导 
//把字符缓冲区中当前位置的字符串转换为整数 
rtn=atoi(expr+pos); 
//改变指示器的值，跳过字符缓冲区的数字部分，找到下一个输入字符。 
while(isdigit(expr[pos])) 
pos++; 
} 
else //如果不是数字则产生相应的错误 
{ 
if(expr[pos]==')') //如果发现一个"" 
Error(EMPTY_BRACKET); //则是括号是空的，即括号内无算术表达式。 
else if(expr[pos]=='\0') //如果此时输入串结束 
Error(UNEXPECTED_END); //则算术表达式非法结束 
else 
Error(INVALID_CHAR_IN); //否则输入字符串中含有非法字符 
} 

return rtn; 
} 

//出错处理函数，输入错误代码，可以指出错误位置，出错信息。 
void Error(int ErrCode) 
{ 
cout<<'\r'; //换行 
while(pos--) 
cout<<' '; //打印空格，把指示错误的"^"移到输入字符串的出错位置 
cout<<"^ 语法错误 ！！！ " 
< < 
longjmp(errjb,1); //跳转到main()函数中的setjmp调用处，并设置setjmp(errjb)的返回值为1 
}