编译实验语法分析.doc

语法分析器实验报告院 系： 专 业： 小组成员： 学 号： 日 期： 一、实验目的根据给出的文法编制LR（1）分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对LR（1）分析法的理解。二、实验内容对已给语言文法，构造LR(1)分析表，编制语法分析程序，要求将错误信息输出到语法错误文件中，并输出分析句子的过程（显示栈的内容）LR（1）分析法的功能 ：LR（1）分析法的功能是利用LR（1）分析表，对输入符号串自下而上的分析过程。 LR（1）分析表的构造及分析过程。三实验文法 := . := := const ; | := = | , = := var ; | := | , := procedure ; ; | := := | call | begin end | if then | while do | := | ; := odd | := = | | | = := | | := + | - := | := * | / := | | ( ) 注意： (1) 表示空串。. (2) 和 分别表示标识符和数。 简化0 PP1 PB2 BVS3 VaL;4 V5 Li6 LL,i7 Si_E8 SbTe9 SfDtS10 SwDdS11 S12 TS13 TT;S14 DERE15 Ri17 En18 E (E)P B V S E L T D Ravar bbegin eend _:= I Fif Tthen Wwhile ddo n 空串的文法:实验环境：Microsoft Windows 7Microsoft Visual Studio 2010实验原理:构造LR（1）项集族的方法Setofltems CLOSURE(I)repeat for （I中的每个项AB，a for(G中的每个产生式B) for（FIRST（a）中的每个终结符号b） 将B，b加入到集合I中；Until不能向I中加入更多的项；return ISetofltems GOTO (I,X) 将J初始化为空集；for（I中的每一个项AX，a ） 将项AX，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中；语法分析表： 实验流程图:实验结果：输入：beginwhile ab do b:=cend.输出：输入：beginwhile ab do b:=cend.输出：心得体会：完成本次实验，我们首先要根据题目中给出的文法，构造LR(1)项集族，之后构造LR(1)语法分析表。题目中给出的是pascal语言版的文法，实验开始时我们也稍微学习了一下pascal语言的风格和定义方法。开发的C程序，把构造好的LR(1)语法分析表存入，用数组模拟栈的功能。对词法分析输出的语句，语法分析中，模拟字符的入栈，之后匹配语法分析表匹配出相应的ACTION动作，分析是移入操作还是归约操作。当为移入操作时需要更新栈中栈顶符号和栈顶状态号；当为归约操作时，要根据相应的产生式，把产生式右边的字符弹出栈，出栈字符的个数要根据产生式的长度来判断，状态号的出栈个数也要匹配出栈字符的个数。同时归约之后，要把产生式左边的终结符入栈，终结符入栈之后还要进行GOTO跳转。所谓的入栈操作就是数组的个数增加操作，出栈操作就是数组的减法操作。当时栈操作是从栈顶开始的，所以每一个数组的最后一位（栈顶）要十分明确的处理好，以免发生模拟入栈、出栈错误。关键代码：class actionspublic:char action;/记录s或r等int num;/记录下标act8030;void fenxibiao()int i = 0, j ;/先全部赋值为e,代表错误for(i = 0; i = 78; i +)for(j = 0; j = 24; j +)actij.action = e;act00.action = s , act00.num = 4; act01.action = r , act01.num = 4; act04.action = r , act04.num = 4;act05.action = r , act05.num = 4; act07.action = r , act07.num = 4; act015.action = r , act015.num = 4;act016.action = , act016.num = 1; act017.action = , act017.num = 2; act018.action = , act018.num = 3;act115.action = a , act115.num = 100; /a代表接收状态 act215.action = r , act215.num = 1;act31.action = s , act31.num = 7; act34.action = s , act34.num = 6; act35.action = s , act35.num = 8; act37.action = s , act37.num = 9; act315.action = r , act315.num = 11; act319.action = , act319.num = 5;act44.action = s , act44.num = 11;act421.action = , act421.num = 10;act515.action = r , act515.num = 2;act63.action = s , act63.num = 12;act71.action = s , act71.num = 16;act72.action = r , act72.num = 11;act74.action = s , act74.num = 15;act75.action = s , act75.num = 17;act77.action = s , act77.num = 18;act710.action = r , act70.num = 11;act719.action = , act719.num = 14;act722.action = , act722.num = 13; act84.action = s , act84.num = 21;act812.action = s , act812.num = 23;act814.action = s , act814.num = 22;act820.action = , act820.num = 20;act823.action = , act823.num = 19;act94.action = s , act94.num = 21;act912.action = s , act912.num = 23;act914.action = s , act914.num = 22;act920.action = , act920.num = 25;act923.action = , act923.num = 24;act109.action = s , act109.num = 27;act1010.action = s , act1010.num = 26;act119.action = r , act119.num = 5;act1110.action = r , act1110.num = 5;act124.action = s , act124.num = 29;act1212.action = s , act1212.num = 31;act1214.action = s , act1214.num = 30;act1220.action = , act1220.num = 28;act132.action = s , act132.num = 32;act1310.action = s , act1310.num = 33;act142.action = r , act142.num = 12;act1410.action = r , act1410.num = 12;act153.action = s , act153.num = 34;act161.action = s , act161.num = 16;act162.action = r , act162.num = 11;act164.action = s , act164.num = 15;act165.action = s , act165.num = 17;act167.action = s , act167.num = 18;act1610.action = r , act160.num = 11;act1619.action = , act1619.num = 14;act1622.action = , act1622.num = 35;act174.action = s , act174.num = 21;act1712.action = s , act1712.num = 23;act1714.action = s , act1714.num = 22;act1720.action = , act1720.num = 20;act1723.action = , act1723.num = 36;act184.action = s , act184.num = 21;act1812.action = s , act1812.num = 23;act1814.action = s , act1814.num = 22;act1820.action = , act1820.num = 25;act1823.action = , act1823.num = 37;act196.action = s , act196.num = 38;act2011.action = s , act2011.num = 40;act2024.action = , act2024.num = 39;act2111.action = r , act2111.num = 16;act2211.action = r , act2211.num = 17;act234.action = s , act234.num = 42;act2312.action = s , act2312.num = 44;act2314.action = s , act2314.num = 43;act2320.action = , act2320.num = 41;act246.action = s , act246.num = 45;act2511.action = s , act2511.num = 40;act2524.action = , act2524.num = 46;act261.action = r , act261.num = 3; act264.action = r , act264.num = 3;act265.action = r , act265.num = 3; act267.action = r , act267.num = 3; act2615.action = r , act2615.num = 3;act274.action = s , act274.num = 47;act2815.action = r , act2815.num = 7;act2915.action = r , act2915.num = 16;act3015.action = r , act3015.num = 17;act314.action = s , act314.num = 42;act3112.action = s , act3112.num = 44;act3114.action = s , act3114.num = 43;act3120.action = , act3120.num = 48;act3215.action = r , act3215.num = 8;act331.action = s , act331.num = 16;act332.action = r , act332.num = 11;act334.action = s , act334.num = 15;act335.action = s , act335.num = 17;act337.action = s , act337.num = 18;act3310.action = r , act330.num = 11;act3319.action = , act3319.num = 49;act3315.action = r , act3315.num = 28;act344.action = s , act344.num = 51;act3412.action = s , act3412.num = 53;act3414.action = s , act3414.num = 52;act3420.action = , act3420.num = 50;act352.action = s , act352.num = 54;act3510.action = s , act3510.num = 33;act366.action = s , act366.num = 55;act378.action = s , act378.num = 56;act381.action = s , act381.num = 7; act384.action = s , act384.num = 6; act385.action = s , act385.num = 8; act387.action = s , act387.num = 9; act3815.action = r , act3815.num = 11; act3819.action = , act3819.num = 57;act394.action = s , act394.num = 59;act3912.action = s , act3912.num = 61;act3914.action = s , act3914.num = 60;act3920.action = , act3920.num = 58;act404.action = r , act404.num = 15;act4012.action = r , act4012.num = 15;act4014.action = r , act4014.num = 15;act4113.action = s , act4113.num = 62;act4213.action = r , act4213.num = 16;act4313.action = r , act4313.num = 17;act444.action = s , act444.num = 42;act4412.action = s , act4412.num = 44;act4414.action = s , act4414.num = 43;act4420.action = , act4420.num = 62;act451.action = s , act451.num = 7; act454.action = s , act454.num = 6; act455.action = s , act455.num = 8; act457.action = s , act457.num = 9; act4515.action = r , act4515.num = 11; act4519.action = , act4519.num = 64;act464.action = s , act464.num = 66;act4612.action = s , act4612.num = 68;act4614.action = s , act4614.num = 67;act4620.action = , act4620.num = 65;act479.action = r , act479.num = 6; act4710.action = r , act4710.num = 6;act4813.action = s , act4813.num = 69;act492.action = r , act492.num = 13;act4910.action = r , act4910.num = 13;act502.action = r , act502.num = 7;act5010.action = r , act5010.num = 7;act512.action = r , act512.num = 16;act5110.action = r , act5110.num = 16;act522.action = r , act522.num = 17;act5210.action = r , act5210.num = 17;act534.action = s , act534.num = 42;act5312.action = s , act5312.num = 44;act5314.action = s , act5314.num = 43;act5320.action = , act5320.num = 70;act542.action = r , act542.num = 8;act5410.action = r , act540.num = 8;act551.action = s , act551.num = 16;act552.action = r , act552.num = 11;act554.action = s , act554.num = 15;act555.action = s , act555.num = 17;act557.action = s , act557.num = 18;act5510.action = r , act550.num = 11;act5519.action = , act5519.num = 71;act561.action = s , act561.num = 16;act562.action = r , act562.num = 11;act564.action = s , act564.num = 15;act565.action = s , act565.num = 17;act567.action = s , act567.num = 18;act5610.action = r , act560.num = 11;act5619.action = , act5619.num = 72;act5715.action = r , act5715.num = 9;act586.action = r , act586.num = 14;act596.action = r , act596.num = 16;act606.action = r , act606.num = 17;act614.action = s , act614.num = 42;act6112.action = s , act6112.num = 44;act6114.action = s , act6114.num = 43;act6120.action = , act6120.num = 72;act6211.action = r , act6211.num = 18;act6313.action = s , act6313.num = 74;act6415.action = r , act6415.num = 10;act658.action = r , act658.num = 14;act668.action = r , act668.num = 16;act678.action = r , act678.num = 17;act684.action = s , act684.num = 42;act6812.action = s , act6812.num = 44;act6814.action = s , act6814.num = 43;act6820.action = , act6820.num = 75;act6915.action = r , act6915.num = 18;act7012.action = s , act7012.num = 76;act712.action = r , act712.num = 9;act7110.action = r , act710.num = 9;act722.action = r , act722.num = 10;act7210.action = r , act720.num = 10;act7313.action = s , act7313.num = 77;act7413.action = r , act7413.num = 18;act7513.action = s , act7513.num = 78;act762.action = r , act762.num = 18;act7610.action = r , act760.num = 18;act776.action = r , act776.num = 18;act788.action = r , act788.num = 18;/初始化终结状态和非终结状态的编号，用colnum(分析表中列号)标记void searchcol()colnum = -1;if(col0 = a)colnum = 0;else if(col0 = b)colnum = 1;else if(col0 = e)colnum = 2;else if(col0 = _)colnum = 3;else if(col0 = i)colnum = 4;else if(col0 = f)colnum = 5;else if(col0 = t)colnum = 6;else if(col0 = w)colnum = 7;else if(col0 = d)colnum = 8;else if(col0 = ,)colnum = 9;else if(col0 = ;)colnum = 10;else if(col0 = )colnum = 11;else if(col0 = ()colnum = 12;else if(col0 = )colnum = 13;else if(col0 = n)colnum = 14;else if(col0 = $)colnum = 15;else if(col0 = P)colnum = 16;else if(col0 = B)colnum = 17;else if(col0 = V)colnum = 18;else if(col0 = S)colnum = 19;else if(col0 = E)colnum = 20;else if(col0 = L)colnum = 21;else if(col0 = T)colnum = 22;else if(col0 = D)colnum = 23;else if(col0 = R)colnum = 24;return ;/oper模拟栈进行移入和归约操作int oper(int no)int i, j;actions tmp = actnumstacknumstacktopcolnum;/移入if(tmp.action = s)for(i=0;i=statenumtop;i+)printf(%d ,statenumi);/输出当前栈中状态号/printf(n);for(; i 10; i +)printf( );for(i = 0; i numstacktop; i +)printf(%c, instacki);/输出当前栈中元素for(; i 21; i +)printf( );printf(%s, left);/输出当前剩余未入栈的元素printf( 移动进栈n);leftno - 1 = ;numstacktop +, instacktop +,statenumtop+;instackinstacktop = col0;numstacknumstacktop = tmp.num;statenumstatenumtop=tmp.num;/入栈return 1;else if(tmp.action = r)for(i=0;i=statenumtop;i+)printf(%d ,statenumi);/输出当前栈中状态号statenumtop=statenumtop-strlen(protmp.num);/归约的时候根据产生式右边长度，减去相应的值。模拟出栈。for(; i 10; i +)printf( );for(i = 0; i numstacktop; i +)printf(%c, instacki);/输出当前栈中元素for(j = numstacktop; j 21; j +)printf( );printf(%s, left);/输出当前剩余未入栈的元素printf( 用产生式%s归约n, producttmp.num);int k = strlen(producttmp.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;instackinstacktop = producttmp.num0;if(instackinstacktop = P)numstacknumstacktop = actnumstacknumstacktop - 116.num;statenum+statenumtop=actnumstacknumstacktop - 116.num;else if(instackinstacktop = B)numstacknumstacktop = actnumstacknumstacktop - 117.num;statenum+statenumtop=actnumstacknumstacktop - 117.num;else if(instackinstacktop = V)numstacknumstacktop = actnumstacknumstacktop - 118.num;statenum+statenumtop=actnumstacknumstacktop - 118.num;else if(instackinstacktop = S)numstacknumstacktop = actnumstacknumstacktop - 119.num;statenum+statenumtop=actnumstacknumstacktop - 119.num;else if(instackinstacktop = E)numstacknumstacktop = actnumstacknumstacktop - 120.num;statenum+statenumtop=actnumstacknumstacktop - 120.num;else if(instackinstacktop = L)numstacknumstacktop = actnumstacknumstacktop - 121.num;statenum+statenumtop=actnumstacknumstacktop - 121.num;else if(instackinstacktop = T)numstacknumstacktop = act