院 系：
专 业：
小组成员：
学 号：
日 期：
一、实验目的
根据给出的文法编制LR（1）分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对LR（1）分析法的理解。
二、实验内容
对已给语言文法，构造LR(1)分析表，编制语法分析程序，要求将错误信息输出到语法错误文件中，并输出分析句子的过程（显示栈的内容）
LR（1）分析法的功能 ：LR（1）分析法的功能是利用LR（1）分析表，对输入符号串自下而上的分析过程。
LR（1）分析表的构造及分析过程。
三．实验文法
| | call | begin | if | while |ε | 注意： (1) "ε" 表示空串。. (2) 简化0 P'—>P 1 P—>B 2 B—>VS 3 V—>aL; 4 V—>@ 5 L—>i 6 L—>L,i 7 S—>i_E 8 S—>bTe 9 S—>fDtS 10 S—>wDdS 11 S—>@ 12 T—>S 13 T—>T;S 14 D—>ERE 15 R—>< 16 E—>i 17 E—>n 18 E—> (E) P—> B—> V—> S—> E—> L T—> D—> R—> a—>var b—>begin e—>end _—>:= I—> F—>if T—>then W—>while d—>do n—> 空串—>@ 的文法: 实验环境： Microsoft Windows 7 Microsoft Visual Studio 2010 实验原理: 构造LR（1）项集族的方法 Setofltems CLOSURE(I) { repeat for （I中的每个项[A—>α·Bβ，a] for(G中的每个产生式B—>γ) for（FIRST（βa）中的每个终结符号b） 将[B—>·γ，b]加入到集合I中； Until不能向I中加入更多的项； return I } Setofltems GOTO (I,X){ 将J初始化为空集； for（I中的每一个项[A—>α·Xβ，a] ） 将项[A—>α·Xβ，a]加入到集合J中； return CLOSURE(J)： } Void items(G) { 将C初始化为{ CLOSURE}({[ S’ —>·S，$]})； repeat for（C中的每一个项集I） for（每一个文法符号X） if（GOTO（I,X）非空且不在C中） 将GOTO（I，X）加入C中； until 不再有新的项集加入到C中； } 语法分析表： 实验流程图: 实验结果： 输入： begin while aend. 输出： 输入： begin while aend. 输出： 心得体会： 完成本次实验，我们首先要根据题目中给出的文法，构造LR(1)项集族，之后构造LR(1)语法分析表。题目中给出的是pascal语言版的文法，实验开始时我们也稍微学习了一下pascal语言的风格和定义方法。开发的C程序，把构造好的LR(1)语法分析表存入，用数组模拟栈的功能。对词法分析输出的语句，语法分析中，模拟字符的入栈，之后匹配语法分析表匹配出相应的ACTION动作，分析是移入操作还是归约操作。当为移入操作时需要更新栈中栈顶符号和栈顶状态号；当为归约操作时，要根据相应的产生式，把产生式右边的字符弹出栈，出栈字符的个数要根据产生式的长度来判断，状态号的出栈个数也要匹配出栈字符的个数。同时归约之后，要把产生式左边的终结符入栈，终结符入栈之后还要进行GOTO跳转。所谓的入栈操作就是数组的个数增加操作，出栈操作就是数组的减法操作。当时栈操作是从栈顶开始的，所以每一个数组的最后一位（栈顶）要十分明确的处理好，以免发生模拟入栈、出栈错误。 关键代码： class actions { public: char action;//记录s或r等 int num;//记录下标 { int i = 0, j ; //先全部赋值为e,代表错误 for(i = 0; i <= 78; i ++) { for(j = 0; j <= 24; j ++) act[i][j].action = 'e'; } act[0][0].action = 's' , act[0][0].num = 4; act[0][1].action = 'r' , act[0][1].num = 4; act[0][4].action = 'r' , act[0][4].num = 4; act[0][5].action = 'r' , act[0][5].num = 4; act[0][7].action = 'r' , act[0][7].num = 4; act[0][15].action = 'r' , act[0][15].num = 4; act[0][16].action = ' ' , act[0][16].num = 1; act[0][17].action = ' ' , act[0][17].num = 2; act[0][18].action = ' ' , act[0][18].num = 3; act[1][15].action = 'a' , act[1][15].num = 100; //'a'代表接收状态 act[2][15].action = 'r' , act[2][15].num = 1; act[3][1].action = 's' , act[3][1].num = 7; act[3][4].action = 's' , act[3][4].num = 6; act[3][5].action = 's' , act[3][5].num = 8; act[3][7].action = 's' , act[3][7].num = 9; act[3][15].action = 'r' , act[3][15].num = 11; act[3][19].action = ' ' , act[3][19].num = 5; act[4][4].action = 's' , act[4][4].num = 11; act[4][21].action = ' ' , act[4][21].num = 10; act[5][15].action = 'r' , act[5][15].num = 2; act[6][3].action = 's' , act[6][3].num = 12; act[7][1].action = 's' , act[7][1].num = 16; act[7][2].action = 'r' , act[7][2].num = 11; act[7][4].action = 's' , act[7][4].num = 15; act[7][5].action = 's' , act[7][5].num = 17; act[7][7].action = 's' , act[7][7].num = 18; act[7][10].action = 'r' , act[7][0].num = 11; act[7][19].action = ' ' , act[7][19].num = 14; act[7][22].action = ' ' , act[7][22].num = 13; act[8][4].action = 's' , act[8][4].num = 21; act[8][12].action = 's' , act[8][12].num = 23; act[8][14].action = 's' , act[8][14].num = 22; act[8][20].action = ' ' , act[8][20].num = 20; act[8][23].action = ' ' , act[8][23].num = 19; act[9][4].action = 's' , act[9][4].num = 21; act[9][12].action = 's' , act[9][12].num = 23; act[9][14].action = 's' , act[9][14].num = 22; act[9][20].action = ' ' , act[9][20].num = 25; act[9][23].action = ' ' , act[9][23].num = 24; act[10][9].action = 's' , act[10][9].num = 27; act[10][10].action = 's' , act[10][10].num = 26; act[11][9].action = 'r' , act[11][9].num = 5; act[11][10].action = 'r' , act[11][10].num = 5; act[12][4].action = 's' , act[12][4].num = 29; act[12][12].action = 's' , act[12][12].num = 31; act[12][14].action = 's' , act[12][14].num = 30; act[12][20].action = ' ' , act[12][20].num = 28; act[13][2].action = 's' , act[13][2].num = 32; act[13][10].action = 's' , act[13][10].num = 33; act[14][2].action = 'r' , act[14][2].num = 12; act[14][10].action = 'r' , act[14][10].num = 12; act[15][3].action = 's' , act[15][3].num = 34; act[16][1].action = 's' , act[16][1].num = 16; act[16][2].action = 'r' , act[16][2].num = 11; act[16][4].action = 's' , act[16][4].num = 15; act[16][5].action = 's' , act[16][5].num = 17; act[16][7].action = 's' , act[16][7].num = 18; act[16][10].action = 'r' , act[16][0].num = 11; act[16][19].action = ' ' , act[16][19].num = 14; act[16][22].action = ' ' , act[16][22].num = 35; act[17][4].action = 's' , act[17][4].num = 21; act[17][12].action = 's' , act[17][12].num = 23; act[17][14].action = 's' , act[17][14].num = 22; act[17][20].action = ' ' , act[17][20].num = 20; act[17][23].action = ' ' , act[17][23].num = 36; act[18][4].action = 's' , act[18][4].num = 21; act[18][12].action = 's' , act[18][12].num = 23; act[18][14].action = 's' , act[18][14].num = 22; act[18][20].action = ' ' , act[18][20].num = 25; act[18][23].action = ' ' , act[18][23].num = 37; act[19][6].action = 's' , act[19][6].num = 38; act[20][11].action = 's' , act[20][11].num = 40; act[20][24].action = ' ' , act[20][24].num = 39; act[21][11].action = 'r' , act[21][11].num = 16; act[22][11].action = 'r' , act[22][11].num = 17; act[23][4].action = 's' , act[23][4].num = 42; act[23][12].action = 's' , act[23][12].num = 44; act[23][14].action = 's' , act[23][14].num = 43; act[23][20].action = ' ' , act[23][20].num = 41; act[24][6].action = 's' , act[24][6].num = 45; act[25][11].action = 's' , act[25][11].num = 40; act[25][24].action = ' ' , act[25][24].num = 46; act[26][1].action = 'r' , act[26][1].num = 3; act[26][4].action = 'r' , act[26][4].num = 3; act[26][5].action = 'r' , act[26][5].num = 3; act[26][7].action = 'r' , act[26][7].num = 3; act[26][15].action = 'r' , act[26][15].num = 3; act[27][4].action = 's' , act[27][4].num = 47; act[28][15].action = 'r' , act[28][15].num = 7; act[29][15].action = 'r' , act[29][15].num = 16; act[30][15].action = 'r' , act[30][15].num = 17; act[31][4].action = 's' , act[31][4].num = 42; act[31][12].action = 's' , act[31][12].num = 44; act[31][14].action = 's' , act[31][14].num = 43; act[31][20].action = ' ' , act[31][20].num = 48; act[32][15].action = 'r' , act[32][15].num = 8; act[33][1].action = 's' , act[33][1].num = 16; act[33][2].action = 'r' , act[33][2].num = 11; act[33][4].action = 's' , act[33][4].num = 15; act[33][5].action = 's' , act[33][5].num = 17; act[33][7].action = 's' , act[33][7].num = 18; act[33][10].action = 'r' , act[33][0].num = 11; act[33][19].action = ' ' , act[33][19].num = 49; act[33][15].action = 'r' , act[33][15].num = 28; act[34][4].action = 's' , act[34][4].num = 51; act[34][12].action = 's' , act[34][12].num = 53; act[34][14].action = 's' , act[34][14].num = 52; act[34][20].action = ' ' , act[34][20].num = 50; act[35][2].action = 's' , act[35][2].num = 54; act[35][10].action = 's' , act[35][10].num = 33; act[36][6].action = 's' , act[36][6].num = 55; act[37][8].action = 's' , act[37][8].num = 56; act[38][1].action = 's' , act[38][1].num = 7; act[38][4].action = 's' , act[38][4].num = 6; act[38][5].action = 's' , act[38][5].num = 8; act[38][7].action = 's' , act[38][7].num = 9; act[38][15].action = 'r' , act[38][15].num = 11; act[38][19].action = ' ' , act[38][19].num = 57; act[39][4].action = 's' , act[39][4].num = 59; act[39][12].action = 's' , act[39][12].num = 61; act[39][14].action = 's' , act[39][14].num = 60; act[39][20].action = ' ' , act[39][20].num = 58; act[40][4].action = 'r' , act[40][4].num = 15; act[40][12].action = 'r' , act[40][12].num = 15; act[40][14].action = 'r' , act[40][14].num = 15; act[41][13].action = 's' , act[41][13].num = 62; act[42][13].action = 'r' , act[42][13].num = 16; act[43][13].action = 'r' , act[43][13].num = 17; act[44][4].action = 's' , act[44][4].num = 42; act[44][12].action = 's' , act[44][12].num = 44; act[44][14].action = 's' , act[44][14].num = 43; act[44][20].action = ' ' , act[44][20].num = 62; act[45][1].action = 's' , act[45][1].num = 7; act[45][4].action = 's' , act[45][4].num = 6; act[45][5].action = 's' , act[45][5].num = 8; act[45][7].action = 's' , act[45][7].num = 9; act[45][15].action = 'r' , act[45][15].num = 11; act[45][19].action = ' ' , act[45][19].num = ; act[46][4].action = 's' , act[46][4].num = 66; act[46][12].action = 's' , act[46][12].num = 68; act[46][14].action = 's' , act[46][14].num = 67; act[46][20].action = ' ' , act[46][20].num = 65; act[47][9].action = 'r' , act[47][9].num = 6; act[47][10].action = 'r' , act[47][10].num = 6; act[48][13].action = 's' , act[48][13].num = 69; act[49][2].action = 'r' , act[49][2].num = 13; act[49][10].action = 'r' , act[49][10].num = 13; act[50][2].action = 'r' , act[50][2].num = 7; act[50][10].action = 'r' , act[50][10].num = 7; act[51][2].action = 'r' , act[51][2].num = 16; act[51][10].action = 'r' , act[51][10].num = 16; act[52][2].action = 'r' , act[52][2].num = 17; act[52][10].action = 'r' , act[52][10].num = 17; act[53][4].action = 's' , act[53][4].num = 42; act[53][12].action = 's' , act[53][12].num = 44; act[53][14].action = 's' , act[53][14].num = 43; act[53][20].action = ' ' , act[53][20].num = 70; act[54][2].action = 'r' , act[54][2].num = 8; act[54][10].action = 'r' , act[54][0].num = 8; act[55][1].action = 's' , act[55][1].num = 16; act[55][2].action = 'r' , act[55][2].num = 11; act[55][4].action = 's' , act[55][4].num = 15; act[55][5].action = 's' , act[55][5].num = 17; act[55][7].action = 's' , act[55][7].num = 18; act[55][10].action = 'r' , act[55][0].num = 11; act[55][19].action = ' ' , act[55][19].num = 71; act[56][1].action = 's' , act[56][1].num = 16; act[56][2].action = 'r' , act[56][2].num = 11; act[56][4].action = 's' , act[56][4].num = 15; act[56][5].action = 's' , act[56][5].num = 17; act[56][7].action = 's' , act[56][7].num = 18; act[56][10].action = 'r' , act[56][0].num = 11; act[56][19].action = ' ' , act[56][19].num = 72; act[57][15].action = 'r' , act[57][15].num = 9; act[58][6].action = 'r' , act[58][6].num = 14; act[59][6].action = 'r' , act[59][6].num = 16; act[60][6].action = 'r' , act[60][6].num = 17; act[61][4].action = 's' , act[61][4].num = 42; act[61][12].action = 's' , act[61][12].num = 44; act[61][14].action = 's' , act[61][14].num = 43; act[61][20].action = ' ' , act[61][20].num = 72; act[62][11].action = 'r' , act[62][11].num = 18; act[63][13].action = 's' , act[63][13].num = 74; act[][15].action = 'r' , act[][15].num = 10; act[65][8].action = 'r' , act[65][8].num = 14; act[66][8].action = 'r' , act[66][8].num = 16; act[67][8].action = 'r' , act[67][8].num = 17; act[68][4].action = 's' , act[68][4].num = 42; act[68][12].action = 's' , act[68][12].num = 44; act[68][14].action = 's' , act[68][14].num = 43; act[68][20].action = ' ' , act[68][20].num = 75; act[69][15].action = 'r' , act[69][15].num = 18; act[70][12].action = 's' , act[70][12].num = 76; act[71][2].action = 'r' , act[71][2].num = 9; act[71][10].action = 'r' , act[71][0].num = 9; act[72][2].action = 'r' , act[72][2].num = 10; act[72][10].action = 'r' , act[72][0].num = 10; act[73][13].action = 's' , act[73][13].num = 77; act[74][13].action = 'r' , act[74][13].num = 18; act[75][13].action = 's' , act[75][13].num = 78; act[76][2].action = 'r' , act[76][2].num = 18; act[76][10].action = 'r' , act[76][0].num = 18; act[77][6].action = 'r' , act[77][6].num = 18; act[78][8].action = 'r' , act[78][8].num = 18; } void searchcol() { colnum = -1; if(col[0] == 'a')colnum = 0; else if(col[0] == 'b')colnum = 1; else if(col[0] == 'e')colnum = 2; else if(col[0] == '_')colnum = 3; else if(col[0] == 'i')colnum = 4; else if(col[0] == 'f')colnum = 5; else if(col[0] == 't')colnum = 6; else if(col[0] == 'w')colnum = 7; else if(col[0] == 'd')colnum = 8; else if(col[0] == ',')colnum = 9; else if(col[0] == ';')colnum = 10; else if(col[0] == '<')colnum = 11; else if(col[0] == '(')colnum = 12; else if(col[0] == ')')colnum = 13; else if(col[0] == 'n')colnum = 14; else if(col[0] == '$')colnum = 15; else if(col[0] == 'P')colnum = 16; else if(col[0] == 'B')colnum = 17; else if(col[0] == 'V')colnum = 18; else if(col[0] == 'S')colnum = 19; else if(col[0] == 'E')colnum = 20; else if(col[0] == 'L')colnum = 21; else if(col[0] == 'T')colnum = 22; else if(col[0] == 'D')colnum = 23; else if(col[0] == 'R')colnum = 24; return ; } int oper(int no) { int i, j; actions tmp = act[numstack[numstacktop]][colnum]; //移入 if(tmp.action == 's'){ for(i=0;i<=statenumtop;i++) printf("%d ",statenum[i]);//输出当前栈中状态号 //printf("\\n"); for(; i < 10; i ++) printf(" "); for(i = 0; i < numstacktop; i ++) printf("%c", instack[i]);//输出当前栈中元素 for(; i < 21; i ++) printf(" "); printf("%s", left);//输出当前剩余未入栈的元素 printf(" 移动进栈\\n"); left[no - 1] = ' '; numstacktop ++, instacktop ++,statenumtop++; instack[instacktop] = col[0]; numstack[numstacktop] = tmp.num; statenum[statenumtop]=tmp.num;//入栈 return 1; } else if(tmp.action == 'r'){ for(i=0;i<=statenumtop;i++) printf("%d ",statenum[i]);//输出当前栈中状态号 statenumtop=statenumtop-strlen(pro[tmp.num]);//归约的时候根据产生式右边长度，减去相应的值。模拟出栈。 for(; i < 10; i ++) printf(" "); for(i = 0; i < numstacktop; i ++) printf("%c", instack[i]);//输出当前栈中元素 for(j = numstacktop; j < 21; j ++) printf(" "); printf("%s", left);//输出当前剩余未入栈的元素 printf(" 用产生式%s归约\\n", product[tmp.num]); int k = strlen(product[tmp.num]); if(k == 7) instacktop -= 2,numstacktop -= 2; else if(k==6) instacktop-=1,numstacktop-=1; else if(k==8) instacktop-=3,numstacktop-=3; else if(k==4) instacktop+=1,numstacktop+=1; instack[instacktop] = product[tmp.num][0]; if(instack[instacktop] == 'P') {numstack[numstacktop] = act[numstack[numstacktop - 1]][16].num; statenum[++statenumtop]=act[numstack[numstacktop - 1]][16].num; } else if(instack[instacktop] == 'B') {numstack[numstacktop] = act[numstack[numstacktop - 1]][17].num; statenum[++statenumtop]=act[numstack[numstacktop - 1]][17].num; } else if(instack[instacktop] == 'V') {numstack[numstacktop] = act[numstack[numstacktop - 1]][18].num; statenum[++statenumtop]=act[numstack[numstacktop - 1]][18].num; } else if(instack[instacktop] == 'S') {numstack[numstacktop] = act[numstack[numstacktop - 1]][19].num; statenum[++statenumtop]=act[numstack[numstacktop - 1]][19].num; } else if(instack[instacktop] == 'E') {numstack[numstacktop] = act[numstack[numstacktop - 1]][20].num; statenum[++statenumtop]=act[numstack[numstacktop - 1]][20].num; } else if(instack[instacktop] == 'L') {numstack[numstacktop] = act[numstack[numstacktop - 1]][21].num; statenum[++statenumtop]=act[numstack[numstacktop - 1]][21].num; } else if(instack[instacktop] == 'T') {numstack[numstacktop] = act[numstack[numstacktop - 1]][22].num; statenum[++statenumtop]=act[numstack[numstacktop - 1]][22].num; } else if(instack[instacktop] == 'D') {numstack[numstacktop] = act[numstack[numstacktop - 1]][23].num; statenum[++statenumtop]=act[numstack[numstacktop - 1]][23].num; } else if(instack[instacktop] == 'R') {numstack[numstacktop] = act[numstack[numstacktop - 1]][24].num; statenum[++statenumtop]=act[numstack[numstacktop - 1]][24].num; } return 0; } else if(tmp.action == 'a'){ for(i=0;i<=statenumtop;i++) printf("%d ",statenum[i]); for(; i < 10; i ++) printf(" "); for(i = 0; i < numstacktop; i ++) printf("%c", instack[i]); for(j = numstacktop; j < 21; j ++) printf(" "); printf("%s", left); printf(" 接受\\n"); return 1; } else if(tmp.action == 'e') return -1; return 1; } { char tp; int i; if ((fp=fopen("source.txt printf("无法打开!\\n"); else { tp =fgetc(fp); while (tp!=EOF) //文件结束标志 { if (isalpha(tp)!=0) tp=isletter(tp); else { if (isdigit(tp)!=0) tp=isnumber(tp); else tp=isother(tp); } } printf("要分析表达式："); for(i=0;i printf("\\n"); } //语法分析 fenxibiao(); //对分析表进行赋值 instacktop = -1, numstacktop = 0,statenumtop=0; //statenumtop是栈顶元素下标 numstack[0] = 0; statenum[0]=0; i=0; int q, len; len = strlen(left); left[len] = '$'; //以美元符作为标记，读入到此标记为止 len ++; left[len] = '\\0'; //作为数组真正的终结符 while(i < len){ col[0] = left[i]; searchcol(); if(colnum == -1){ printf("error\\n"); return 0; } q= oper(i); if(q== 1){ //处理完一个元素之后就把它位置置空，否则出错 left[i] = ' '; i ++; } else if(q== -1){ printf("error\\n"); return 0; } } printf("\\n"); return 0; }}act[80][30]; void fenxibiao() //初始化终结状态和非终结状态的编号，用colnum(分析表中列号)标记 //oper模拟栈进行移入和归约操作 int main()
