语法分析-预测分析方法

《语法分析-预测分析方法》由会员分享，可在线阅读，更多相关《语法分析-预测分析方法（13页珍藏版）》请在装配图网上搜索。

1、实验2-1 语法分析预测分析方法一、实验目的使用预测分析方法编制分析程序，实现对词法分析程序所提供的单词序列的语法检查和结构分析。了解预测分析法和递归子程序法的区别和联系，培养动手实践的能力。二、实验内容使用预测分析法分析一段程序代码。如果符合文法定义，程序输出“是”，否则输出“否”。由于预测分析和递归子程序都是自顶向下的分析方法，这里给出无回溯的和无左公因子的文法。无左递归和无左公因子的BNF如下：.PROGRAM 标识符;CONST;|标识符=无符号整数, |VAR|标识符:;,标识符|INTEGER|LONG;|PROCEDURE 标识符:(标识符:)|;|标识符:=|()|IFTHEN

2、WHILEDOREAD (标识符)WRITE (表达式), |BEGIN END; | |ODD+|-|标识符|无符号整数|（）+|-*|/=|=为了将非终结符和终结符一起存入栈，将非终结符的内码从128开始标记。其对照表如下： 表1 终结符种别码对照表种别码单词种别码单词种别码单词种别码单词1PROGRAM2CONST3VAR4INTEGER5LONG6PROCEDURE7IF8THEN9WHILE10DO11READ12WRITE13BEGIN14END15ODD16+17-18*19/20=21222325=26.27.28;29:30:=31(32)33无符号整数34标识符35#表2

3、非终结符及函数名对照表非终结符函数名非终结符函数名programprogheadblockconsexplconsdefivarexplconssuffvardefivarssuffprocdefitypeilprocedhprocsuffassiprosentencesuffixifsentreadwhilesentidsuffWritecompsentExprsuffsentsuffConditiotermsuffExpresstermFactsuffargumentFactoraddoperMuloperrespoper三、完整源程序代码#include#include#include#

4、include#include#define lenth1 15#define lenth2 18/*规则表*/int rule6=0,/空129,130,26,0,/程序首部分程序.1,34,28,0,/program 标识符；131,134,138,150,0,/常量说明部分变量说明部分过程说明部分复合语句2,132,133,28,0,/const 常量定义常量定义后缀；0,34,20,33,0,/标识符= 无符号整数27,132,133,0,/，常量定义常量定义后缀3,135,136,0,/var 变量定义变量定义后缀34,147,29,137,28,0,/标识符标识符后缀：类型；27,

5、34,147,0,/，标识符标识符后缀135,136,0,/变量定义变量定义后缀4,0,/integer5,0,/long139,130,28,140,0,/过程首部分程序；过程说明部分后缀6,34,158,28,0,/procedure 标识符参数部分；142,0,/赋值或调用语句144,0,/条件语句145,0,/当型循环语句146,0,/读语句148,0,/写语句150,0,/符合语句34,143,0,/标识符后缀30,153,0,/：=表达式7,152,8,141,0,/if 条件then 语句9,152,10,141,0,/while 条件do 语句11,31,34,147,32,0

6、,/read （标识符标识符后缀）12,31,153,149,32,0,/write （表达式表达式后缀）27,153,149,0,/，表达式表达式后缀13,141,151,14,0,/begin 语句语句后缀end28,141,151,0,/；语句语句后缀153,161,153,0,/表达式关系运算符表达式15,153,0,/odd 表达式16,155,154,0,/+ 项项后缀17,155,154,0,/- 项项后缀155,154,0,/项项后缀159,155,154,0,/加型运算符项项后缀157,156,0,/因子因子后缀160,157,156,0,/乘型运算符因子因子后缀34,0,/

7、标识符33,0,/无符号整数31,153,32,0,/（表达式）26,33,0,/. 无符号整数16,0,/+17,0,/-18,0,/*19,0,/ /20,0,/=21,0,/22,0,/23,0,/25,0,/=31,34,29,137,32,0/ 标识符：类型）;/*预测分析表的非零元素*/int pretable3=128,1,1,129,1,2,130,2,3,130,3,3,130,6,3,130,34,3,130,7,3,130,9,3,130,11,3,130,12,3,130,13,3,130,26,3,130,28,3,131,2,4,131,3,5,131,6,5,13

8、1,34,5,131,7,5,131,9,5,131,11,5,131,12,5,131,13,5,131,26,5,131,28,5,132,34,6,133,27,7,133,28,5,134,3,8,134,6,5,134,34,5,134,7,5,134,9,5,134,11,5,134,12,5,134,13,5,134,26,5,134,28,5,135,34,9,136,6,5,136,13,5,136,34,11,136,28,5,137,4,12,137,5,13,138,6,14,138,34,5,138,7,5,138,9,5,138,11,5,138,12,5,138,

9、13,5,138,26,5,138,28,5,139,6,15,140,6,14,140,34,5,140,7,5,140,9,5,140,11,5,140,12,5,140,13,5,140,26,5,140,28,5,141,34,16,141,7,17,141,9,18,141,11,19,141,12,20,141,13,21,141,14,5,141,26,5,141,28,5,142,34,22,143,30,23,143,31,41,143,28,5,143,28,5,143,14,5,143,26,5,143,14,5,144,7,24,145,9,25,146,11,26,1

10、47,27,10,147,29,5,147,32,5,148,12,27,149,27,28,149,32,5,150,13,29,150,26,5,150,28,5,151,28,30,151,14,5,151,26,5,151,28,30,152,34,31,152,16,31,152,17,31,152,34,31,152,33,31,152,31,31,152,15,32,153,34,35,153,16,33,153,17,34,153,34,35,153,33,35,153,31,35,154,16,36,154,17,36,154,8,5,154,10,5,154,14,5,15

11、4,20,5,154,21,5,154,22,5,154,23,5,154,24,5,154,25,5,154,26,5,154,27,5,154,28,5,154,32,5,155,34,37,155,33,37,155,31,37,156,18,38,156,19,38,156,8,5,156,10,5,156,14,5,156,16,5,156,17,5,156,20,5,156,21,5,156,22,5,156,23,5,156,24,5,156,25,5,156,26,5,156,27,5,156,28,5,156,32,5,157,34,39,157,33,40,157,31,4

12、1,158,31,53,158,28,5,159,16,43,159,17,44,160,18,45,160,19,46,161,20,47,161,21,48,161,22,49,161,23,50,161,24,51,161,25,52,0,0,0;struct st char name21;int code;sym;struct char name21;int type; int addr;indent1000; /*为标识符表*/int table3435;FILE *f1; /*f1为输入文件指针*/int line=1,row=1,val;int lenth=0;void gets

13、ym();char getchr();void error(int n);void main(int argc,char *argv)if (f1=fopen(C:Documents and SettingsAdministrator桌面编译测试.txt,r)=NULL)printf(cannot open the filen);exit(0); int stack2000;int i,j,x,top=-1,flag=1;i=0;while(pretablei0)/*对于非零元素置预测分析表*/tablepretablei0-128pretablei1=pretablei2;i+;/*把#号和

14、识别符号程序入栈*/ -补充执行语句stack+top=35;stack+top=128;/ -补充执行语句getsym();while(flag)x=stacktop-; /*取栈顶符号*/if(x=128) /*x为非终结符*/if(tablex-128sym.code)/*如果该预测分析表的元素不为空,则计算规则的长度,并将规则反序入栈*/i=0;while(ruletablex-128sym.codei)i+;for(j=i-1;j=0;j-)stack+top=ruletablex-128sym.codej;else error(100); else if(x=35) /*x为终结符

15、或#*/if(x=sym.code) /*栈顶元素和输入元素匹配*/if(x=35)/-补充判断条件/*如栈顶元素和输入元素匹配时,判断是否是#,若是结束,否则继续*/flag=0;elsegetsym();else error(101);else error(102); /*栈顶元素和输入元素不匹配时,出错*/fclose(f1);printf(the program is rightn);system(pause);void getsym()static char alenth110=program,const,var,integer,long,procedure,if,then,whil

16、e,do,read,write,begin,end,odd,dlenth23=+,-,*,/,=,=,.,;,:,:=,(,),str21,ch= ;int i,n;while(isspace(ch)ch=getchr();if(isalpha(ch)n=0;while(isalpha(ch)|isalnum(ch)if(isalpha(ch)ch=tolower(ch);if(n20)strn+=ch;ch=getchr();strn=0;for(i=0;ilenth1;i+)if(!strcmp(str,ai)break;if(ilenth1)strcpy(sym.name,ai);sym

17、.code=i+1;else/*否则为标识符并检查标识符表中是否已登记该标识符，若没有登记则填表*/for(i=0;ilenth;i+)if(!strcmp(str,indenti.name)break;if(i=lenth)strcmp(indenti.name,str);strcpy(sym.name,indenti.name);/ -补充执行语句sym.code=34;else if(isalnum(ch)val=0;n=0;while(isalnum(ch)val=val*10+ch-0;sym.namen+=ch;ch=getchr();sym.namen=0;sym.code=33

18、;elseif(ch=+|ch=-|ch=*|ch=/|ch=|ch=.|ch=,|ch=;|ch=(|ch=)str0=ch;str1=0;ch=getchr();for(i=0;i|ch=:)strn+=ch;if(ch=getchr()=)strn+=ch;ch=getchr();elseif(ch=)strn+=ch;ch=getchr();else if(ch=-1)strcpy(sym.name,);sym.code=35;return;elseerror(1);strn=0;for(i=0;ib then a:=6;end.# 输出：There are 100 error（5）输入：program s;beginif sym=+ thenbegins;advance;endelse error 输出：There are 100 error五、两种方法比较分析所谓递归下降法，是指对文法的每一非终结符号，都根据相应产生式各候选式的结构，为其编写一个子程序 (或函数)，用来识别该非终结符号所表示的语法范畴。而预测分析方法要求文法必须是LL（1）文法，相比较递归下降分析方法来说更难一些。吴雨霜1108140222计算机111班