2022年编译原理实验三语义分析 .pdf

编译原理实验三语法分析并进行语义分析输入：经过词法分析后形成的token和 tokenstring 输出：检查有无语法错误，形成语法树，并检查是否符合语义。样例程序已经能对变量声明填符号表、进行类型检查。文法：stmt_seq -statement ; stmt_seq | statement statement-decl_stmt | assign_stmt decl_stmt-type var_list type-int |float var_list-id , var_list | id assign_stmt- id := exp exp-exp + term | exp - term |term term- term * factor | term * factor | factor factor-id | num | ( exp )要求掌握理解程序设计方法。样例程序#include #include typedef enum MINUS,PLUS,TIMES,OVER,LPAREN,RPAREN,SEMI,ASSIGN,NUM,ID,INT,FLOAT,COMMA,DOLLAR tokentype;/*记号 */ typedef enum stmtk,expk nodekind; typedef enum ifk,assignk,declk stmtkind; typedef enum opk,constk,idk expkind; typedef enum integer,real exptype; typedef struct treenode struct treenode * child3; struct treenode * sibling; nodekind nodek; exptype dtype ; union stmtkind stmt; expkind exp; kind; union tokentype op; int val; char * name; attr; treenode; typedef struct bucket 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 8 页 - - - - - - - - - char * name; exptype dtype; struct bucket * next; bucket; bucket * hashtable211; /*tokentype token6=ID,ASSIGN,NUM,PLUS,NUM,INT,FLOAT,COMMA,DOLLAR; char tokenstring630=ab,:=,12,+,5,$;*/ tokentype token=INT,ID,COMMA,ID,SEMI, ID,ASSIGN,NUM,PLUS,NUM,TIMES,NUM,SEMI,ID,ASSIGN,NUM,DOLLAR; char tokenstring30=int,ab,xy,;,ab,:=,12,+,5,*,3,;,xy,:=,34,$; int wordindex=0; /*以上两个数组的索引*/ treenode * decl(); treenode * factor(); treenode * term(); treenode * exp(); treenode * assign_stmt(); treenode * stmt_seq(); pretraverse(treenode *); int hash ( char * ); void st_insert( char * ,exptype); int st_lookup ( char * ); void buildsymtab(treenode * ); void setnodetype(treenode * ); main() treenode * t; t=stmt_seq(); /* 语法分析建语法树*/ buildsymtab(t); /*建符号表 */ pretraverse(t); /*遍历语法树 */ setnodetype(t); /*类型检查设置*/ treenode * stmt_seq() treenode * t; treenode * p; if( tokenwordindex=INT)|(tokenwordindex=FLOAT) t=decl(); if(tokenwordindex=ID) t=assign_stmt(); p=t; while( (tokenwordindex=SEMI)& (tokenwordindex!=DOLLAR) treenode * q; wordindex+; q=assign_stmt(); p-sibling=q; p=q; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 8 页 - - - - - - - - - return t; treenode * assign_stmt() treenode * t=(treenode *)malloc(sizeof(treenode); if(tokenwordindex=ID) t-nodek=stmtk; t-kind.stmt=assignk; t-attr.name=tokenstringwordindex; wordindex+; else printf(error); exit(1); if(tokenwordindex=ASSIGN) wordindex+; else printf(error); exit(1); t-child0=exp(); t-child1=NULL; t-child2=NULL; t-sibling=NULL; return t; treenode * exp() treenode * t; t=term(); while(tokenwordindex=PLUS)|(tokenwordindex=MINUS) treenode * p=(treenode *)malloc(sizeof(treenode); p-nodek=expk; p-kind.exp=opk; p-attr.op=tokenwordindex; p-child0=t; t=p; wordindex+; t-child1=term(); t-child2=NULL; t-sibling=NULL; return t; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 8 页 - - - - - - - - - treenode * term() treenode * t=factor(); while(tokenwordindex=TIMES)|(tokenwordindex=OVER) treenode * p=(treenode *)malloc(sizeof(treenode); p-nodek=expk; p-kind.exp=opk; p-attr.op=tokenwordindex; p-child0=t; t=p; wordindex+; t-child1=factor(); t-child2=NULL; t-sibling=NULL; return t; treenode * factor() treenode * t; switch(tokenwordindex) case LPAREN : wordindex+; t=exp(); if(tokenwordindex=RPAREN) wordindex+; else printf(error); exit(1); break; case NUM : t=(treenode *)malloc(sizeof(treenode); t-nodek=expk; t-kind.exp=constk; t-attr.val=atoi(tokenstringwordindex); t-child0=NULL; t-child1=NULL; t-child2=NULL; t-sibling=NULL; wordindex+; break; case ID : t=(treenode *)malloc(sizeof(treenode); t-nodek=expk; t-kind.exp=idk; t-attr.name=tokenstringwordindex; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 8 页 - - - - - - - - - wordindex+; break; default: printf(error); return t; pretraverse(treenode * t) if (t!=NULL) if (t-nodek=stmtk) printf(stmt-id:%sn,t-attr.name); if (t-nodek=expk & t-kind.exp=idk) printf(exp-id:%sn,t-attr.name); if (t-nodek=expk & t-kind.exp=opk) printf(exp-op:%dn,t-attr.op); if (t-nodek=expk & t-kind.exp=constk) printf(exp-val:%dn,t-attr.val); if(t-child0!=NULL) pretraverse(t-child0); if(t-child1!=NULL) pretraverse(t-child1); if(t-child2!=NULL) pretraverse(t-child2); if(t-sibling!=NULL) pretraverse(t-sibling); treenode * decl() treenode * p,* q,* t1; treenode * t=(treenode *)malloc(sizeof(treenode); t-nodek=stmtk; t-kind.stmt=declk; t-attr.name=tokenstringwordindex; t-child1=NULL; t-child2=NULL; wordindex+; if(tokenwordindex=ID) t1=(treenode *)malloc(sizeof(treenode); t-child0=t1; t1-nodek= expk; t1-kind.exp=idk; t1-attr.name=tokenstringwordindex; t1-child0=NULL; t1-child1=NULL; t1-child2=NULL; t1-sibling=NULL; wordindex+; p=t1; while( tokenwordindex=COMMA) wordindex+; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 8 页 - - - - - - - - - q=(treenode *)malloc(sizeof(treenode); q-nodek= expk; q-kind.exp=idk; q-attr.name=tokenstringwordindex; q-child0=NULL; q-child1=NULL; q-child2=NULL; q-sibling=NULL; p-sibling=q; wordindex+; p=q; return t; int hash ( char * key ) int temp = 0; int i = 0; while (keyi != 0) temp = (temp name) != 0) l = l-next; if (l = NULL) /* variable not yet in table */ l = (bucket *) malloc(sizeof(bucket); l-name = name; l-dtype=datatype; l-next = NULL; l-next = hashtableh; hashtableh = l; int st_lookup ( char * name ) int h = hash(name); bucket * l = hashtableh; while (l != NULL) & (strcmp(name,l-name) != 0) l = l-next; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 8 页 - - - - - - - - - if (l = NULL) return -1; else return 1; void buildsymtab(treenode * t) exptype datatype; treenode * q; if (t!=NULL) if (t-nodek=stmtk & t-kind.stmt=declk) if (strcmp(t-attr.name,int)=0) datatype=integer; if(t-attr.name=float) datatype=real; q=t-child0; while(q!=NULL) st_insert(q-attr.name,datatype); q=q-sibling; if(t-nodek!=stmtk & t-kind.stmt!=declk & t-child0!=NULL) buildsymtab(t-child0); if(t-child1!=NULL) buildsymtab(t-child1); if(t-child2!=NULL) buildsymtab(t-child2); if(t-sibling!=NULL) buildsymtab(t-sibling); void setnodetype(treenode * t) if(t!=NULL) if(t-child0!=NULL) setnodetype (t-child0); if(t-child1!=NULL) setnodetype (t-child1); if (t-nodek=expk & t-kind.exp=idk) int h = hash(t-attr.name); bucket * l = hashtableh; while (l != NULL) & (strcmp(t-attr.name,l-name) != 0) l = l-next; if (l=NULL) printf(no declare);exit(1); else t-dtype=l-dtype; if (t-nodek=expk & t-kind.exp=constk) t-dtype=integer; if (t-nodek=expk & t-kind.exp=opk) if(t-child1=NULL) t-dtype=t-child0-dtype; else if(t-child0-dtype=t-child1-dtype ) t-dtype=t-child0-dtype; else printf(type no match);exit(1); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 8 页 - - - - - - - - - if (t-nodek=stmtk) t-dtype=t-child0-dtype; if(t-sibling!=NULL) setnodetype (t-sibling); 查看主要内存变量：t-attr.name t-attr.val t-child0-attr.name t-child0-attr.val t-child1-attr.name t-child1-attr.val t-sibling-attr.name t-sibling-attr.val 语法树样例：declk (int) idk (ab) idk (ab) assignk (ab) assignk (xy) opk (+) constk (12) opk (*) constk (5) constk (3) constk (34) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 8 页 - - - - - - - - -