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

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”时都属于这种错误情况。

（待续）



本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/hifrog/archive/2004/01/30/21641.aspx