算符优先文法及语义分析程序设计

1、算符优先文法及语义分析程序设计设计目的掌握算符优先文法进行语法分析，通过设计、编制、调试一个算术表达式的语法及语义分析程序，加深对语法及语义分析原理的理解，并实现词法分析程序对单词序列的词法检查和分析。进一步培养编译器设计的思想，加深对编译原理和应用程序的理解，针对编译过程的重点和难点内容进行编程，独立完成有一定工作量的程序设计任务，综合使用程序设计语言、数据结构和编译原理的知识。设计要求用算符优先文法进行二-十进制的语法分析及语义分析程序设计，编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。设计方案3.1算符优先分析方法原理：算符优先分析方法是根据算符之间的优先关系而设计的一

2、种自下而上的分析方法。算符优先分析的基本思想是只规定算符之间的优先关系，也就是只考虑终结符之间的优先关系。算符优先分析过程是自下而上的归约过程，所谓的算符优先分析就是定义算符之间（确切地说，终结符之间）的某种优先关系，借助于这种优先关系寻找“可归约串”和进行归约。该文法必须满足以下条件：文法它的任一产生式的右部都不含两个相继（并列）的非终结符，即不含如下产生式右部：QR；首先求出该文法的优先关系表，在程序中用2维数组表示，-1表示小于或者等于，大于为1，其它为0表示错误。在输入一串字符串以后进行按照文法一步一步的进行规约，我所进行的是直接规约到文法的符号而不是规约到N。数据结构使用的是链表，用

3、一个STRUCT来表示一个元素，其中包含符号和下一个符号的指针。3.2算法描述：首先建立一个符号栈S,既用它寄存终结符，也用它寄存非终结符。以下给出分析算法，其中k代表符号栈S的深度。k:=1;Sk:=#;REPEAT把下一个输入符号读进a中；IFSk属于firstVTTHENj:=kELSEj:=k-l;WHILESjaDOBEGINREPEATQ:=Sj;IFSj-1属于firstVTTHENj:=j-1ELSEj:=j-2UNTILSjQ;把Sj+lSk归约为某个N;K:=j+1;Sk:=NENDOFWHILE;IFSjiiUiJtKJtKJtKJtKJtKJtKJtKJtKJtKJtK

4、JtKJtKJtKJtKJtKICKICKICKICKICKICKICKICKICKICKICKICKICJCT:i：C：!*!+!：I:null11111111null1111!11null111111C!1111null1111!11null111111mJ1111null111111null1111null111111null1111null11null11null11#includevtchar.h#includemalloc.hvoidpush(charpchar);charpop(void);intCharToInt(charch);voidGoBreakTo();voiddoso

5、me(void);voidpush(charpchar);charpop(void);intCharToInt(charch);voidGoBreakTo();voiddosome(void);出栈函数将字符转为数字，以得到算符优先值归约开始识别constinttable77=0,1,1,1,0,1,1,-1,1,0,-1,-1,1,1,-1,-1,0,-1,-1,0,1,-1,1,0,1,-1,1,1,-1,-1,0,-1,-1,0,0,0,1,0,1,0,1,1,-1,0,-1,0,0,0,-1;constcharfuhao7=),(,!,*,+,:,|;voiddisplay().jf*

6、!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!、VU-WVB*肓首f111*11|*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!、VU-WVB*肓首f111*11|printf(i);for(inti=0;i7;i+)for(intj=0;jt);elseif(tabl

7、eij=-1)printf(|*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!-*肓首f1/存储算符优先关系表，大于为1，小于或等于为-1，其它为0表示出错charcurchar;charcurcmp;intright;/*设置开关项，当出错时为0*/inti,j;intk;/*比较字符在栈的位置*/structLcharcharchar_ch;structLchar*next;LLchar,*p,*h,*temp,*top,*base;voi

8、dmain(void)charch;right=1;base=(Lchar*)malloc(sizeof(LLchar);base-next=NULL;base-char_ch=#;top=base;h=(Lchar*)malloc(sizeof(LLchar);h-next=NULL;p=h;printf(”本文法为算符优先5);printf(SAnAV:=EnEE+TITnTT*FIFnF(E)IinVin);display();printf(请输入待比较字符串，以#结束n);printf(例如:i=i+i*i#n);do/*输入待比较字符串，以#结束*/ch=getchar();putc

9、har(ch);if(ch=iIIch=+IIch=IIch=*IIch=(IIch=)IIch=#)temp=(Lchar*)malloc(sizeof(LLchar);temp-next=NULL;temp-char_ch=ch;h-next=temp;h=h-next;elsetemp=p-next;printf(nInputawrongchar!Inputagain:n);for(;)if(temp!=NULL)printf(%c,temp-char_ch);elsebreak;temp=temp-next;while(ch!=#);/*输入待比较字符串，以#结束*/p=p-next;

10、h=p;dosome();/*开始识别*/if(right)printf(n归约成功!n);elseprintf(n归约失败!n);getchar();getchar();voidpush(charpchar)temp=(Lchar*)malloc(sizeof(LLchar);temp-char_ch=pchar;temp-next=top;top=temp;charpop(void)charc;c=top-char_ch;if(top-char_ch!=#)top=top-next;returnc;intCharToInt(charch)/*将字符转为数字，以得到算符优先值*/intt;s

11、witch(ch)casei:t=0;break;case+:t=1;break;case=:t=2;break;case*:t=3;break;case(:t=4;break;case):t=5;break;case#:t=6;returnt;voidGoBreakTo()chartempc;chartempc1;chartempc2;chartempc3;charpopc;tempc=pop();tempc1=pop();if(tempc=i)if(tempc1=#)push(V);k=1;elseswitch(tempc1)case+:popc=T;break;case*:popc=F;

12、break;case=:popc=E;push(tempc1);push(popc);k=1;elseif(tempc=F)tempc2=pop();if(tempc1=*&tempc2=T)push(T);elseright=0;elseif(tempc=T)tempc2=pop();if(tempc1=+&tempc2=E)push(E);elseright=0;elseif(tempc=E)tempc2=pop();if(tempc1=&tempc2=V)push(A);elseright=0;elseif(tempc=A)tempc2=pop();if(tempc2!=#)right=

13、0;elseif(tempc=)tempc2=pop();if(tempc1=V&tempc2=E)push(A);elseright=0;voiddosome(void)k=1;for(;)curchar=h-char_ch;temp=top;if(temp-char_ch=A)break;elsefor(;)if(temp-char_ch=V|temp-char_ch=E|temp-char_ch=T|temp-char_ch=F|temp-char_ch=A|temp-char_ch=S)temp=temp-next;k+;elsecurcmp=temp-char_ch;break;printf(n%dt%dt,tableij,k);temp=top;for(;)/*打印栈*/printf(%c,temp-char_ch);if(temp-char_ch=#)break;elsetemp=temp-next;printf(t);temp=h;for(;)/*打印待比较的字符*/printf(%c,temp-char_ch);if(temp-char_ch=#)break;els