算术表达式的语法分析器.cpp

算术表达式的语法分析器

/****算术表达式的分析和计算，文件名：Exp_c.cpp，代码/注释：hifrog****
*****                  在VC6和Dev-C下调试通过                ****/
#include<iostream>
#include<string>
#include<cstdlib>
#include<cctype>
#include<csetjmp>
#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;                      //出错跳转缓冲器

//********以下是函数声明*********

int E_AddSub(); //产生式"E -> T+E | T-E | T"的函数，用来分析加减算术表达式。

int T_MulDiv(); //产生式"T -> F*T | F/T | F"的函数，用来分析乘除算术表达式。

int F_Number();//产生式"F -> i | (E)"的函数，用来分析数字和括号内的表达式。

void Error(int ErrCode);//出错处理函数，可以指出错误位置，出错信息。


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

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

   cout<<"请输入一个算术表达式（输入“Q”或“q”退出）："<<endl;
   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<<"计算得出表达式的值为："<<ans<<endl;
   }
  }
  else
  {
   //setjmp(errjb)!=0的情况：
   cout<<"请重新输入!"<<endl;
  }
 }
 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<<"^ 语法错误 ！！！  "
  <<ErrCodeStr[ErrCode] //输出错误信息
  <<endl<<'\a';

 longjmp(errjb,1);            //跳转到main()函数中的setjmp调用处，并设置setjmp(errjb)的返回值为1
}