语法分析 实验报告

《编译系统设计实践》 实验项目二：语法分析 指导老师： 陈晖 组长： 030902336 组员： 030902246 030902335 实验目的 根据给出的文法编制LR（1）分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对LR（1）分析法的理解。 实验内容 对已给语言文法，构造LR(1)分析表，编制语法分析程序，要求将错误信息输出到语法错误文件中，并输出分析句子的过程（显示栈的内容）。 程序设计与实现 1.功能描述： 根据给定的文法，由程序生成项集族和语法分析表，对输入的源程序进行词法分析，得到语法分析的输入串，经过语法分析后得到三个栈，它们分别是状态栈，字符栈，输入栈，从而分析出输入的源程序是否有语法错误。 2．重要过程描述： 1）本实验有两个输入文件：一个为源代码输入文件“in_code.txt”,一个为文法的输入文件“in_gram.txt”,三个输出文件：一个为词法的输出和语法的输入文件“out_in.txt”，一个为项目集族和分析表的输出文件“out_items.txt”一个为语法分析结果的输出即栈的输出“result.txt”。 2) 重要数据结构：typedef struct production {//产生式 char suf[25]; //搜索符 char rear[30]; //产生式后部 char front; //产生式头部 unsigned point; //小圆点的位置 short seq; }prod; typedef struct statement {//状态i prod p[50];//产生式 int num; //产生式数量 }state; typedef struct collection{/状态集 state i[300]; int num; //状态个数 }coll; struct fstruct { //first集 char str[50];//first符号串 int num;//first符号串 字符个数 bool blank;//是否包含空符号 }firstx; short int anatab[300] 3．程序流程图：  SHAPE \* MERGEFORMAT  4. 重要函数说明 find(state &unclosure,int n)函数：功能：判断是否已包含某一产生式。在求闭包closure()函数中对其进行调用；参数说明：unclosure还没有求闭包的状态；n表示第几个产生式。 first(char tmp)函数：求各文法符号的first集，确定搜索符时使用到。在求闭包的函数中队其进行调用；参数说明：tmp为需要求first集的文法符号。 sign()函数：功能：提取文法符号序列，将所有的文法符号+’$’都存放在一个一维数组中，该数组在输出分析表及语法分析中对栈进行处理时是需要使用。 reloadtoken()函数：功能：词法分析的结果。从文件中读入字符到buff中，将得到的单词定义成相应的运算符、分隔符，关键字k，标识符i，实数f'，整数n；写入到out_in.txt文件中，该文件为词法分析的输出，语法分析的输入。 void items(coll &head)函数：功能：求LR(1)项目集族 void closure(state &unclosure)函数：功能：求LR(1)项目集族的闭包。 state mygoto(const state &cur,int k,int tmp)函数：功能：填写分析表anatab[][]，使用数字，空白用0，S移入为负数，r规约为正数，-32767表示acc接受。 关键代码 /*求LR(1)项目集族*/ void items(coll &head) { int i,j,k; //建立项集 memset(&head,0,LENCOLL); //初始化第一条增广文法 s->S,$; head.i[0].p[0].front = 's'; strcpy(head.i[0].p[0].rear,"S"); head.num++; head.i[0].num++; head.i[0].p[0].suf[0]='$'; //对增广文法求闭包 closure(head.i[0]); state pnext; int findi; for(i = 0;i < head.num; i++) for(j = 0;j < strnum; j++) //strnum为文法符号个数 { pnext = mygoto(head.i[i],i,j); if(pnext.num == 0) {continue;} //判断pnext状态是否已经存在 for(k = 0,findi = 0;k < head.num;k++) if(memcmp(&pnext,&head.i[k],LENSTATE) == 0) { anatab[i][j] = k; findi = 1;break; } if(findi == 0) { anatab[i][j] = head.num; head.i[head.num] = pnext; head.num++; } } }  /*求LR(1)项目集族的闭包*/ void closure(state &unclosure) { int i = 0,j = 0,k =0; char tmp; for(i = 0;i < unclosure.num;i++) { tmp = unclosure.p[i].rear[unclosure.p[i].point]; if( isupper(tmp) ) //isupper()用于求tmp是否是大写字母 { for(j = 0;j < gramnum;j++) { if(gram[j][0] == tmp) { memset(&firstx,0,sizeof(fstruct)); first(unclosure.p[i].rear[unclosure.p[i].point + 1]); f(firstx.blank) { strcat(firstx.str,unclosure.p[i].suf); } k = find(unclosure,j); if(k == -1)//该产生式未出现过，加入 { strcpy(unclosure.p[unclosure.num].rear,&gram[j][1]); unclosure.p[unclosure.num].front = gram[j][0]; unclosure.p[unclosure.num].point = 0; unclosure.p[unclosure.num].seq = j + 1; //第几条文法 strcpy(unclosure.p[unclosure.num].suf,firstx.str); unclosure.num++; } else{ strcat(unclosure.p[k].suf,firstx.str); /出现过，只加上后缀 } } } } } }  //语法分析，对栈进行处理 int stacktop,schrtop,bufftop; int row; char *sp; int len; int grami; int nextsta; stacktop = 0; schrtop = -1; memset(stack,-1,sizeof(stack)); memset(stackchar,0,sizeof(stackchar)); stack[0] = 0; printf(" 状态栈 | 字符栈 | 符号
"); printf("
"); while(gets(buffatt)!=NULL) { bufftop = 0; while(1) { if(bufftop > 100){break;} sp = strchr(strsign,buffatt[bufftop]); if(sp == NULL) { printf("%c not find
",buffatt[bufftop]); break; } else { row = sp - strsign; } nextsta = anatab[stack[stacktop]][row]; if(nextsta == 0) { printf("%d,%d,%c
",stacktop,row,buffatt[bufftop]); printf("error
"); break; } if(nextsta > 0) { for(i = 0;i < 50;i++) if(stack[i] > -1) { printf("%-4d",stack[i]); } else { printf(" "); } printf("|%-100s|%100s
",stackchar,(buffatt+bufftop)); stacktop++; stack[stacktop] = nextsta;//移进状态 schrtop++; stackchar[schrtop] = buffatt[bufftop]; //移进符号 bufftop++;//前移待分析串位置 } if(nextsta == -32767 && buffatt[bufftop] == '$') { for(i = 0;i < 50;i++) if(stack[i] > -1) { printf("%-4d",stack[i]); } else { printf(" "); } printf("|%-100s|%100s
",stackchar,(buffatt+bufftop)); printf("
acc
"); break; }