07级_实验二_用算符优先分析法进行表达式分析

实验二 用算符优先分析法进行表达式分析

一、实验目的

了解用算符优先分析法进行语法分析的方法。

二、实验要求

从键盘输入表达式，利用算符优先分析法求出其值，如输入表达式有错，则给出报错提示。表达式以#结尾。例：以于如下的输入表达式串： 13+5*4#则应给出结果为33。

三、实验提示

1、 实验原理

为实现算符优先算法，可以使用两个工作栈。一个叫做OPTR，用以寄存运算符，一个叫OPND,用以寄存操作数或结果。算法描述如下：

[1]首先置操作数栈为空栈，将表达式起始符;作为运算符栈的栈底元素。

[2]依次读入表达式中每个单词，若是操作数则进OPND栈，若是运算符则转[3]。 [3]将此运算符θ1与OPTR栈顶元素θ2进行比较，即查上表， 若 θ1＞θ2，则：θ1进栈，转[2] 若 θ1＝θ2 ,如θ1为“#”，则分析成功，否则OPTR栈顶元素出栈，并转[2]

若 θ1<θ2,则出栈OPND栈顶元素至b，又出栈其栈顶元素至a，出栈OPTR栈顶元素至t，进行运算r=a t b(t 为运算符)，并将结果r存入栈OPND后转[3]。 若θ1和θ2之间无优先关系，则报错。

2、 源程序提示

利用以前实验进行单词识别，并自组织工程文件，关于算符优先算法要用到的部份函数提示如下。

[1]一些自定义的变量和函数的声明

#define MAX 255

SYMBOL title[7]= {PLUS,MINUS,TIMES,SLASH,LPAREN,RPAREN,SHAP}; //用来将相应的种别码与数组下标进行映射

char oo[7][7]={ {'>','>','<','<','<','>','>'}, {'>','>','<','<','<','>','>'}, {'>','>','>','>','<','>','>'}, {'>','>','>','>','<','>','>'}, {'<','<','<','<','<','=','!'}, {'>','>','>','>','!','>','>'}, {'<','<','<','<','<','!','='}

}; //算符优先矩阵，其中’!’表示两算符无优先关系

int OPND[MAX];//操作数栈 SYMBOL OPTR[MAX]; //算符栈 int topd,topr;// 两栈的指针

void PushOpnd (int a); int PopOpnd (void); int EmptyOpnd (void); int GetTopOpnd (void);

void PushOptr (SYMBOL a); SYMBOL PopOptr (void); int EmptyOptr (void);

SYMBOL GetTopOptr (void); //上面为栈函数

int Position(SYMBOL c); //将c映射至数组下标 int IsOpnd(SYMBOL c); //判断c是否是操作数 int IsOptr(SYMBOL c); //判断c是否是操作符

char Precede(SYMBOL c1,SYMBOL c2);

//查算符优先矩阵，求出c1和c2之间的优先矩阵 int Operate(int a,int b,SYMBOL o); //求出a o b char First();

//算符优先分析函数

[2]部份函数实现的源代码 /***********************/ int Position(SYMBOL c) { int i;

for(i=0;i<7;i++) if(c==title[i]) return i; return -1; }

/********************************/ char Precede(SYMBOL c1,SYMBOL c2) { int i,j;

i=Position(c1); j=Position(c2) if(i!=-1 && j!=-1) {return oo[i][j]} else

return ('*'); }

/**********************************/ int Operate(int a,int b,SYMBOL o) {

switch (o) {

case PLUS: return a+b; case MINUS: return a-b; case TIMES: return a*b; case SLASH: return a/b; default: return 0; } }

/****************************************/ char First()

{

int a,b,r; char c; a=b=r=0; topd=-1; topr=-1;

PushOptr(SHAP); Getsym();

while(sym!=SHAP || GetTopOptr()!=SHAP) {

if (IsOpnd(sym)) {

PushOpnd(num); Getsym(); }

else if(IsOptr(sym)) {

switch(c=Precede(GetTopOptr(),sym)) {

case '<': PushOptr(sym); Getsym(); break; case '=': PopOptr(); Getsym(); break; case '>': b=PopOpnd(); a=PopOpnd(); r=Operate(a,b,PopOptr()); PushOpnd(r); break;

default : printf("\nSomething wrong with expression"); exit(0);

} }

else {

printf("\nExpression Error,exit"); exit(0); }

}/*end of while*/ }

/***********************************/ void main() {

printf("\nPlease input your expression,end with ;\n"); First();

printf("\nResult is %d",GetTopOpnd()); }