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

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
}


（全文完）



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