语法分析器完整程序

1、/#include <stdafx.h>/*int _tmain(int argc, _TCHAR* argv) return 0;*/*/*pas.c/* 高级语言到四元式*/*/*#include "iostream"#include "stdio.h"#include "string.h"#include "time.h"#include "conio.h" void my_delay(unsigned long ms)double start_time = (double)c

2、lock() / CLOCKS_PER_SEC * 1000;while ( (double)clock() / CLOCKS_PER_SEC * 1000 - start_time < ms ) ; #define ACC-2/*/#define sy_if0#define sy_then1#define sy_else2#define sy_while3#define sy_begin4#define sy_do5#define sy_end6#define a7#define semicolon8#define e9#define jinghao10#define S11#defi

3、ne L12#define tempsy15#define EA18 /*E and*/#define EO19 /*E or*/#define plus35 / 添加 减号的关键字#define minus#define times#define division #define becomes #define op_and #define op_or #define op_not#define rop3637 /添加 除号的关键字3839404142#define lparent#define rparent#define ident#define intconst48495657/*/c

4、har ch='0'/* 当前字符 */ int count=0;static char spelling10=""/* 存放识别的字 */ static char line81=""/* 一行字符缓冲区 */ char *pline;/* 字符缓冲区指针 */ char ch_exit;static char ntab110010; struct ntabint tc;int fc; ntab2200;int label=0;/* 存放临时变量的表的定义 */ struct rwordschar sp10; int sy;/* 存放文件

5、的结构 */ struct rwords reswords10="if",sy_if,"do",sy_do, "else",sy_else, "while",sy_while, "then",sy_then, "begin",sy_begin, "end",sy_end, "and",op_and, "or",op_or, "not",op_not;struct aaint sy1;int pos

6、;buf1000,/* 词法分析结果缓冲区 */n,/* 当前字符 */n1,/* 当前表达式中的字符 */E,/* 非终结符 */ sstack100,/* 符号栈 */ ibuf100, stack1000;struct aa oth;struct fourexpchar op10; struct aa arg1; struct aa arg2; int result; fexp200;/* 四元式的结构 */intssp=0;/* 指向 sstack100*/struct aa *pbuf=buf;/* 指向词法分析缓冲区 */ intnlength=0;int lnum=0;/* 源程

7、序长度 */int tt1=0;FILE *cfile;FILE *mfile;/*/ int newt=0;/* 临时变量 */int nxq=100;/*nxq 指向下一个形成的四元式的地址 */int lr;int lr1;int sp=0;/* 状态栈定义 */int stack1100;int sp1=0;/*状态栈 1的定义 */int num=0;struct llint nxq1;int tc1;int fc1;labelmark10;int labeltemp10;int pointmark=-1,pointtemp=-1;int sign=0;/*sign = 1，表达式为

8、赋值语句；sig n = 2，表达式为布尔表达式。/*/static int/*0*/*/*1*/*2*/*3*/*4*/*5*/*6*/*7*/*8*/*9*/*10*/*11*/*12*/*13*/*14*/*15*/*16*/*17*/*18*/action1913= 2,-1,-1,3,4,-1,-1,5,-1,-1,10,1,-1, -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,ACC,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,-1,6,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,-1,7,-1,-1,-1, 2,-1,-1,

9、3,4,-1,-1,5,-1,-1,-1,9,8, -1,-1,104,-1,-1,-1,104,-1,104,-1,104,-1,-1, -1,10,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,11,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,12,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,105,-1,13,-1,-1,-1,-1, 2,-1,-1,3,4,-1,-1,5,-1,-1,-1,14,-1, 2,-1,-1,3,4,-1,-1,5,-1,-1,-1,15,-

10、1, -1,-1,103,-1,-1,-1,103,-1,103,-1,103,-1,-1, 2,-1,-1,3,4,-1,-1,5,-1,-1,-1,9,16, -1,-1,17,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, -1,-1,102,-1,-1,-1,102,-1,102,-1,102,-1,-1, -1,-1,-1,-1,-1,-1,106,-1,-1,-1,-1,-1,-1, 2,-1,-1,3,4,-1,-1,5,-1,-1,-1,18,-1, -1,-1,101,-1,-1,-1,101,-1,101,-1,101,-1,-1;/下面的是添加了减法和除法的

11、算术表达式SLR 矩阵static int action1149=3,-1,-1,-1,-1,2,-1,-1,1, -1,4,5,6,7,-1,-1,ACC,-1, 3,-1,-1,-1,-1,2,-1,-1,8, -1,106,106,106,106,-1,106,106,-1, 3,-1,-1,-1,-1,2,-1,-1,9, 3,-1,-1,-1,-1,2,-1,-1,10, 3,-1,-1,-1,-1,2,-1,-1,11, 3,-1,-1,-1,-1,2,-1,-1,12, -1,4,5,6,7,-1,13,-1,-1, -1,101,5,101,7,-1,101,101,-1, -

12、1,102,102,102,102,-1,102,102,-1, -1,103,5,103,7,-1,103,103,-1, -1,104,104,104,104,-1,104,104,-1, -1,105,105,105,105,-1,105,105,-1;/*0*/*1*/*2*/*3*/*4*/*5*/*6*/*7*/*8*/*9*/ /*10*/ /*11*/*12*/*13*/static int action21611=/*0*/1,-1,4,-1,5,-1,-1,-1,13,7,8,/*1*/-1,2,-1,101,-1,101,101,101,-1,-1,-1,/*2*/3,-

13、1,-1,-1,-1,-1,-1,-1,-1,-1,-1,/*3*/-1,-1,-1,102,-1,102,102,102,-1,-1,-1,/*4*/1,-1,4,-1,5,-1,-1,-1,11,7,8,/*5*/1,-1,4,-1,5,-1,-1,-1,6,7,8,/*6*/-1,-1,-1,104,-1,9,10,104,-1,-1,-1,/*7*/1,-1,4,-1,5,-1,-1,-1,14,7,8,/*8*/1,-1,4,-1,5,-1,-1,-1,15,7,8,/*9*/105,-1,105,-1,105,-1,-1,105,-1,-1,-1,/*10*/107,-1,107,

14、-1,107,-1,-1,107,-1,-1,-1,/*11*/-1,-1,-1,12,-1,9,10,-1,-1,-1,-1,/*12*/-1,103,-1,103,-1,103,103,103,-1,-1,-1,/*13*/-1,-1,-1,-1,-1,9,10,ACC,-1,-1,-1,/*14*/-1,-1,-1,106,-1,9,10,106,-1,-1,-1,/*15*/-1,-1,-1,108,-1,9,10,108,-1,-1,-1;/*从文件读一行到缓冲区 *void readline()*/char ch1;pline=line;ch1=getc(cfile);while

15、(ch1!='n')/my_delay(50);printf("%c",ch1);/*pline=ch1;pline+;ch1=getc(cfile);/ 取下一个字符 *pline='0'pline=line;printf("n");从缓冲区读一个字符*/* void readch()if (ch='0')readline(); lnum+; ch=*pline; pline+;/*标志符和关键字的识别 */int find(char spel)int ss1=0;int ii=0;while(ss1=0

16、)&&(ii<nlength)if (!strcmp(spel,ntab1ii) ss1=1;ii+;if (ss1=1) return ii-1;else return -1;void identifier()int iii=0,j,k;int ss=0;k=0; do spellingk=ch; k+; readch();while(ch>='a')&&(ch<='z')|(ch>='0')&&(ch<='9'); pline-;spellingk=

17、'0' while(ss=0)&&(iii<10)if (!strcmp(spelling,reswordsiii.sp) ss=1; iii+;/* 关键字匹配 */if(ss=1)bufcount.sy1=reswordsiii-1.sy; elsebufcount.sy1=ident; j=find(spelling);if (j=-1)bufcount.pos=tt1; strcpy(ntab1tt1,spelling); tt1+;nlength+;else bufcount.pos=j;count+;for(k=0;k<10;k+) sp

18、ellingk='0'*数字的识别 *void number()int ivalue=0; int digit;dodigit=ch-'0' ivalue=ivalue*10+digit; readch();while(ch>='0')&&(ch<='9'); bufcount.sy1=intconst; bufcount.pos=ivalue; count+;pline-;/*扫描主函数 */void scan()int i; while(ch!='')switch (ch) case

19、 ' ':break; case 'a': case 'b': case 'c': case 'd':case 'e':case 'f':case 'g':case 'h':case 'i':case 'j':case 'k':case 'l':case 'm':case 'n':case 'o':case 'p':case

20、'q':case 'r':case 's':case 't':case 'u':case 'v':case 'w':case 'x':case 'y':case 'z':identifier(); break;case '0':case '1':case '2':case '3':case '4':case '5':case '6&#

21、39;:case '7':case '8':case '9':number(); break;case '<': readch(); if(ch='=') bufcount.pos=0;elseif(ch='>') bufcount.pos=4;elsebufcount.pos=1; pline-;bufcount.sy1=rop;count+;break;case '>':readch();if(ch='=')bufcount.pos=2;else

22、bufcount.pos=3;pline-;bufcount.sy1=rop;count+;break;case '(':bufcount.sy1=lparent;count+;break;case ')':bufcount.sy1=rparent;count+;break;case '#':bufcount.sy1=jinghao;count+;break;case '+':bufcount.sy1=plus;count+;break;case '-': /exbufcount.sy1=minus;count+;

23、break;/excase '/':bufcount.sy1=division;count+;break;case '*':bufcount.sy1=times;count+;break;case ':':readch();if (ch='=') bufcount.sy1=becomes; count+;break;case '=':bufcount.sy1=rop; bufcount.pos=5; count+;break;case '': bufcount.sy1=semicolon; coun

24、t+; break;readch();bufcount.sy1=-1;/* void readnu()if (pbuf->sy1>=0)n.sy1=pbuf->sy1;n.pos=pbuf->pos; pbuf+;*中间变量的生成 *int newtemp()newt+; return newt;/*生成四元式 */ int gen(char op1,struct aa arg11,struct aa arg22,int result1) strcpy(fexpnxq.op,op1);fexpnxq.arg1.sy1=arg11.sy1; fexpnxq.arg1.po

25、s=arg11.pos; fexpnxq.arg2.sy1=arg22.sy1; fexpnxq.arg2.pos=arg22.pos; fexpnxq.result=result1; nxq+;return nxq-1;/* 布尔表达式的匹配 */ int merg(int p1,int p2)int p;if(p2=0) return p1; elsep=p2;while(fexpp.result!=0) p=fexpp.result;fexpp.result=p1;return p2;void backpatch(int p,int t)int tempq; int q; q=p; wh

26、ile(q!=0) tempq=fexpq.result; fexpq.result=t; q=tempq;/*/ int change1(int chan) switch (chan)case ident:case intconst:return 0; case plus:return 1;case times:return 2;case minus:/ 返回减号在 算术表达式 SLR 表中的 列号return 3;case division:/ 返回除号在 算术表达式 SLR 表中的 列号return 4;case lparent:return 5;case rparent:return

27、6;case jinghao:return 7;case tempsy:return 8; int change2(int chan)switch (chan)case ident:case intconst:return 0;case rop:return 1;case lparent:return 2;case rparent:return 3;case op_not:return 4;case op_and:return 5;case op_or:return 6;case jinghao:return 7;case tempsy:return 8;case EA:return 9;ca

28、se EO:return 10; *赋值语句的的分析*void lrparse1(int num) lr1=action1stack1sp1change1(n1.sy1);if (lr1=-1)printf("n 算术表达式或赋值语句出错！ n"); getch();exit(0);if(ibuf0.sy1!=ident) /对赋值表达式的检查printf("n 赋值语句出错！赋值号的左边不是变量名 getch();exit(0);if (lr1<14)&&(lr1>=0)/14 标记算术表达式sp1+; stack1sp1=lr1;i

29、f (n1.sy1!=tempsy) ssp+; num+;sstackssp.sy1=n1.sy1;sstackssp.pos=n1.pos; n1.sy1=ibufnum.sy1; n1.pos=ibufnum.pos;lrparse1(num); if(lr1>=100)&&(lr1<107)switch(lr1)case 100:n");SLR 表中的状态数break;case 101:printf("nE->E+E 归约 n");E.pos=newtemp();gen("+",sstackssp-2,

30、sstackssp,E.pos+100);ssp=ssp-2;sstackssp.sy1=tempsy;sstackssp.pos=E.pos;sp1=sp1-3;break;/*E->E+E*/case 102:printf("nE->E*E 归约 n");E.pos=newtemp(); gen("*",sstackssp-2,sstackssp,E.pos+100); ssp=ssp-2;sstackssp.sy1=tempsy;sstackssp.pos=E.pos;sp1=sp1-3;break;/*E->E*E*/case

31、103: / 添加的 对减法归约的语义代码 printf("nE->E-E 归约 n");E.pos=newtemp(); gen("-",sstackssp-2,sstackssp,E.pos+100); ssp=ssp-2;sstackssp.sy1=tempsy;sstackssp.pos=E.pos;sp1=sp1-3;break;/*E->E-E*/case 104: / 添加的 对除法归约的语义代码 printf("nE->E/E 归约 n");E.pos=newtemp(); gen("/&q

32、uot;,sstackssp-2,sstackssp,E.pos+100); ssp=ssp-2;sstackssp.sy1=tempsy;sstackssp.pos=E.pos;sp1=sp1-3;break;/*E->E/E*/case 105:printf("nE->(E) 归约 n");E.pos=sstackssp-1.pos;ssp=ssp-2;sstackssp.sy1=tempsy;sstackssp.pos=E.pos;sp1=sp1-3;break;/*E->(E)*/case 106:printf("nE->i 归约

33、n"); E.pos=sstackssp.pos; sp1-;break;/*E->i*/n1.sy1=tempsy;/* 规约后为非终结符 */n1.pos=E.pos;lrparse1(num);if (lr1=ACC)&&(stack1sp1=1)/* 归约 A->i:=E*/ printf("nA->i:=E 归约 n");gen(":=",sstackssp,oth,ibuf0.pos);ssp=ssp-3;sp1=sp1-3;*布尔表达式的分析*int lrparse2(int num)int te

34、mplabel; lr1=action2stack1sp1change2(n1.sy1);if (lr1=-1)if (sign=2) printf("nwhile 语句出错！ n");if (sign=3) printf("nif 语句出错！ n");getch();exit(0);if (lr1<16)&&(lr1>=0)sp1+; stack1sp1=lr1;ssp+;sstackssp.sy1=n1.sy1;sstackssp.pos=n1.pos;if (n1.sy1!=tempsy)&&(n1.sy

35、1!=EA)&&(n1.sy1!=EO) num+; n1.sy1=ibufnum.sy1;n1.pos=ibufnum.pos;lrparse2(num);if(lr1>=100)&&(lr1<109)switch(lr1)case 100:break;case 101:ntab2label.tc=nxq; ntab2label.fc=nxq+1; gen("jnz",sstackssp,oth,0); gen("j",oth,oth,0);sp1-;ssp-;label+;n1.sy1=tempsy;bre

36、ak;/*E->i*/case 102:ntab2label.tc=nxq; ntab2label.fc=nxq+1;switch (sstackssp-1.pos)case 0: gen("j<=",sstackssp-2,sstackssp,0); break;case 1: gen("j<",sstackssp-2,sstackssp,0); break;case 2: gen("j>=",sstackssp-2,sstackssp,0); break;case 3: gen("j>&qu

37、ot;,sstackssp-2,sstackssp,0); break;case 4: gen("j<>",sstackssp-2,sstackssp,0); break;case 5: gen("j=",sstackssp-2,sstackssp,0); break;gen("j",oth,oth,0);ssp=ssp-3; sp1=sp1-3; label+; n1.sy1=tempsy;break;/*E->i rop i*/case 103: label=label-1; ssp=ssp-3; sp1=sp1

38、-3; label+; n1.sy1=tempsy; break;/*E->(E)*/case 104:label=label-1;templabel=ntab2label.tc; ntab2label.tc=ntab2label.fc;ntab2label.fc=templabel; ssp=ssp-2; sp1=sp1-2;label+;n1.sy1=tempsy;break;/*E->not E*/case 105:backpatch(ntab2label-1.tc,nxq); label=label-1;ssp=ssp-2;sp1=sp1-2;label+;n1.sy1=E

39、A;break;/*EA->E(1)and*/case 106: label=label-2; ntab2label.tc=ntab2label+1.tc; ntab2label.fc=merg(ntab2label.fc,ntab2label+1.fc); ssp=ssp-2;sp1=sp1-2;label+;n1.sy1=tempsy; break;/*E->EA E(2)*/case 107: backpatch(ntab2label-1.fc,nxq); label=label-1; ssp=ssp-2; sp1=sp1-2; label+; n1.sy1=EO; brea

40、k;case 108: label=label-2; ntab2label.fc=ntab2label+1.fc; ntab2label.tc=merg(ntab2label.tc,ntab2label+1.tc); ssp=ssp-2;sp1=sp1-2; label+; n1.sy1=tempsy; break; lrparse2(num);if (lr1=ACC) return 1; (不包括 "")*/* 测试字符是否为表达式中的值 int test(int value)switch (value)case intconst:case ident:case plus

41、:case times:case minus: /减号 是否是表达式中的符号 case division: /除号 是否是表达式中的符号 case becomes:case lparent:case rparent:case rop:case op_and:case op_or:case op_not:return 1;default:return 0;/*/ int lrparse()int i1=0;int num=0;/* 指向表达式缓冲区 */if (test(n.sy1)if(stacksp.sy1=sy_while) sign=2;elseif (stacksp.sy1=sy_if

42、) sign=3; else sign=1; doibufi1.sy1=n.sy1;ibufi1.pos=n.pos; readnu();i1+;while(test(n.sy1);/* 把表达式放入缓冲区 */ibufi1.sy1=jinghao;pbuf-;/* 指针后退 1，需要吗？ */sstack0.sy1=jinghao;ssp=0;/* 符号栈底的初始化 */if (sign=1)sp1=0;stack1sp1=0;/*状态栈 1 的栈底初始化 */ num=2;/*指向 :=*/ n1.sy1=ibufnum.sy1; n1.pos=ibufnum.pos; lrparse1(

43、num);/* 处理赋值语句 */n.sy1=a;/*当前文法符号置为 a （赋值语句）*/if (sign=2)|(sign=3)pointmark+;labelmarkpointmark.nxq1=nxq;sp1=0;stack1sp1=0;num=0;n1.sy1=ibufnum.sy1;n1.pos=ibufnum.pos;lrparse2(num);labelmarkpointmark.tc1=ntab2label-1.tc;labelmarkpointmark.fc1=ntab2label-1.fc;/* 处理布尔语句 */*在处理完E,要回填真值链*/backpatch(labe

44、lmarkpointmark.tc1,nxq);n.sy1=e;/*当前文法符号置为e (赋值语句)*/lr=actionstacksp.posn.sy1;printf("stack%d=%dttn=%dttlr=%dn",sp,stacksp.pos,n.sy1,lr);if (lr<19)&&(lr>=0)sp+;stacksp.pos=lr;stacksp.sy1=n.sy1;readnu();lrparse();if (lr<=106)&&(lr>=100)switch (lr)case 100:break;/

45、*S'->S*/case 101:printf("S->if e then S else S 归约 n");sp=sp-6;n.sy1=S;/*归约完if后，填then后面的无条件转移语句*/fexplabeltemppointtemp.result=nxq;pointtemp-;if(stacksp.sy1=sy_then)gen("j",oth,oth,0); backpatch(labelmarkpointmark.fc1,nxq); pointtemp+;labeltemppointtemp=nxq-1;pointmark-;

46、if(stacksp.sy1=sy_do) gen("j",oth,oth,labelmarkpointmark.nxq1); backpatch(labelmarkpointmark.fc1,nxq);break;/*S->if e then S then S else S*/case 102:printf("S->while e do S 归约 n");sp=sp-4;n.sy1=S;pointmark-;if(stacksp.sy1=sy_do) gen("j",oth,oth,labelmarkpointmark.

47、nxq1); backpatch(labelmarkpointmark.fc1,nxq);if(stacksp.sy1=sy_then) gen("j",oth,oth,0); fexplabelmarkpointmark.fc1.result=nxq; pointtemp+; labeltemppointtemp=nxq-1;break;/*S->while e do S*/case 103:printf("S->begin L end 归约 n");sp=sp-3;n.sy1=S;if(stacksp.sy1=sy_then)gen(&q

48、uot;j",oth,oth,0); backpatch(labelmarkpointmark.fc1,nxq); pointtemp+;labeltemppointtemp=nxq-1;if(stacksp.sy1=sy_do)gen("j",oth,oth,labelmarkpointmark.nxq1); backpatch(labelmarkpointmark.fc1,nxq);getch();break;/*S->begin L end*/case 104:printf("S->a 归约 n");sp=sp-1;n.sy1

49、=S;if(stacksp.sy1=sy_then)gen("j",oth,oth,0); backpatch(labelmarkpointmark.fc1,nxq); pointtemp+;labeltemppointtemp=nxq-1;if(stacksp.sy1=sy_do)gen("j",oth,oth,labelmarkpointmark.nxq1); backpatch(labelmarkpointmark.fc1,nxq);break;/*S->a*/case 105:printf("L->S 归约 n")

50、;sp=sp-1;n.sy1=L;break;/*L->S*/case 106:printf("L->S;L 归约 n");sp=sp-3;n.sy1=L;break;/*L->S;L*/getch();pbuf-;lrparse();if (lr=ACC)printf(" 分析成功！文法正确！ n");lr=-100;/ 添加的语句 可能导致错误产生！ ！return ACC;else if(lr=-1)printf(" 分析失败！文法错误！ n");lr=-200; / 添加的语句 可能导致错误产生！ ！ * *

51、disp1 *void disp1()int temp1=0;printf("n*词法分析结果*n");for(temp1=0;temp1<count;temp1+)printf("%dt%dn",buftemp1.sy1,buftemp1.pos);if (temp1=20)printf("Press any key to continuen");getch(); getch();*void disp2()int temp1=100; printf("n*四元式分析结果 *n");for(temp1=100;temp1<nxq;temp1+)if(temp1>100)fprintf(mfile,"n"); fprintf(mfile,"%dt",temp1); fprintf(mfile,"(%st,",fexptemp1.op);if (fexptemp1.arg1.sy1=ident)fprintf(mfile,"%st,",ntab1fexptemp1.arg1.pos);elseif (fexptemp1