编译原理实验指导书(新)

<<编译原理>>实验指导书 前 言 编译原理是计算机科学与技术、软件工程等专业的主干课和必修课，由于这门课程相对抽象且内容较复杂，一直是比较难学的一门课程。在编译原理的学习过程中，实验非常重要，只有通过上机实验，才能使学生对比较抽象的课程内容产生一个具体的感性认识。但是，目前国内市场上很少有较详细且比较适合我院实际的实验指导书，为此，我们特编了这份指导书，希望能对我院的《编译原理》教学工作有所帮助。 本书实验环境主要为C环境(由于兼容性问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 ，建议使用Turboc2.0)及一个词法分析器自动生成工具FLEX和一个语法分析器自动生成工具BISON。书中给出的参考源程序也是C源程序，但由于实验者熟悉精通的语言工具不尽相同，因而强求采用统一的编程语言编程是不现实的。实验者在掌握了编译程序各个阶段的功能和原理之后，不难借助使用其他自己熟悉的语言实现相关功能。 实验者在实验过程中应该侧重写出自己在算法分析、 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 思路、实现功能或程序代码等方面的特色，写出设计和实现过程中遭遇到的难点和解决办法，可以不拘泥于实验指导给出的参考性设计思路，尽可能在深度和广度上加以拓展。只有这种各具特色的实验报告，才将更有利于体现实验者在创新思维和动手能力上的差异。 通过这些实验，能使学生对这些部份的工作机理有一个详细的了解，达到“知其然，且知其所以然”的目的。并可在C环境下对自动生成工具生成的词法、语法分析器进行编译调试。 由于手工生成词法和语法分析器的工作量太大，在实际中常用自动生成工具来完成之。这些工具中最著名的当属贝尔实验室的词法分析器生成工具LEX和语法分析器生成工具YACC。它们现已成为UNIX的标准应用程序同UNIX一起发行。与此同时GNU推出与LEX完全兼容的FLEX，与YACC完全兼容的BISON。这两个程序都在Internet上以源代码的形式免费发行，所以很容易在其它操作系统下重新编译安装。我们实验采用的就是for dos的FLEX和BISON。本书有关的编译工具及其源程序例子，可到BISON的网站上下载。关于FLEX和BISON的用法简介，参见附录，如需更详细的介绍，请参阅编译工具中帮助文件。 关于实验学时和安排，任课教师可根据实际情况，选做其中的一部份。由于这门课实验难度较大，所以希望任课教师在实验前安排好学生的预习工作。在上机前要求学生写好实验预习报告。 本书中c程序均在Turboc2.0下调试通过.LEX和YACC源程序均在FLEX和BISON下调试通过. 由于编者水平有限，本书中必然存在着不少缺点，在此恳请大家给予批评和指正，我们将尽力纠正。在此特对关心支持编写本书的院系领导表示感谢。 本书中关于LEX和YACC的部份大量参考引用了何炎祥老师主编，华中理工大学出版社出版的《编译原理》一书，在此表示衷心的感谢。 　　　　　　　　　　　　　　　　　　　　　　　　 周鹏　杨亚会 梅琴 赵榕 2006年8月 目 录 1 实验一　词法分析器设计 10 实验二　熟悉FLEX使用 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 11 实验三　用FLEX自动生成PL/0词法分析器 18 实验四　用递归下降法进行表达式分析 20 实验五　用算符优先法进行表达式分析 24 实验六　利用BISON生成逆波兰表示计算器 25 实验七　利用BISON生成中缀表示计算器 26 附录一 词法分析器生成工具FLEX简介 33 附录二 语法分析器生成工具YACC简介 实验一　词法分析器设计 【实验目的】 掌握生成词法分析器的方法，加深对词法分析原理的理解。 掌握设计、编制并调试词法分析程序的思想和方法。 本实验是高级语言程序设计、数据结构和编译原理中词法分析原理等知识的综合。 【实验内容及要求】 选择一种熟悉的高级语言（如C语言，C++，VB或VC等），设计、编写、调试一个词法分析子程序。 待分析的源程序为一个简单的C语言程序，如下所示： main() { int x,a,b; float y,c,d; x = a + b; y=c / d; if(x>y) x = 10; else y=100; } 将该源程序的源文件经词法分析后输出以二元组形式表示的单词符号序列。 编写的程序具有一定的查错能力。提交的实验报告中要有实验名称、实验目的、实验内容、实验程序清单、调试过程和运行结果，程序的主要部分作出功能说明，并有实验收获体会或改进意见等内容。 实验前请仔细阅读实验预习提示，提示中程序仅供参考。 本实验建议学时数为4学时。 【实验预习提示】 1.词法分析器的功能和输出格式 词法分析器的功能是输入以字符串表示的源程序，输出单词符号或单词符号序列。词法分析器的单词符号常常表示成以下的二元组(单词的种别码，单词符号的属性值)。本实验中，采用的是一符一种种别码的方式。 2.调试程序文法的EBNF（扩展巴科斯范式）表示如下 <程序>::= main()<语句串> <语句串>::= <语句> {；<语句>} <语句>::= <赋值语句>|<条件语句>|<循环语句> <赋值语句>::= <变量>=<表达式> <条件语句>::= if<条件>then<语句> <循环语句>::= while<条件><语句串> <条件>::= <表达式><关系运算符><表达式> <表达式>::= <项>{+<项>|—<项>} <项>::= <因子>{*<因子>|/<因子>} <因子>::= <变量>|<无符号整数>|<表达式> <无符号整数>::= <数字>{<数字>} <变量>::= <标识符> <标识符>::= <字母>{<字母>|<数字>|<下划线>} <关系运算符>::= >|<|>=|<=|==|!= <字母>::= A|B|C|……|Z|a|b|c|……|z (要求不区分大小写) <数字>::= 0|1|2|3|4|5|6|7|8|9 3.“超前搜索”方法 　　词法分析时，常常会用到超前搜索方法。如当前待分析字符串为“a>+”,当前字符为’>’，此时，分析器倒底是将其分析为大于关系运算符还是大于等于关系运算符呢？显然，只有知道下一个字符是什么才能下结论。于是分析器读入下一个字符’+’，这时可知应将’>’解释为大于运算符。但此时，超前读了一个字符’+’，所以要回退一个字符，词法分析器才能正常运行。在分析标识符，无符号整数等时也有类似情况。 4.词法分析程序主程序的算法思想 算法的基本思想是根据扫描到单词符号的第一个字符的种类，拼写出相应的单词符号，其实 现的基本任务是从字符串表示的源程序中识别出相应的具有独立意义的单词符号。主程序示 意图如图1.1所示。 图1.1 词法分析主程序示意图 其中设置初始值包括两个方面： （1）关键字表的初值 关键字作为特殊标识符处理，把它们预先安排在一张表中，称这张表为关键字表，当扫描程序 识别出标识符时，查关键字表，若能查找到匹配的单词，则该单词是关键字，否则为一般标识 符。关键字表为一个字符串数组，其描述为： char *KEY_WORDS[8]={“main”,”int”, ”char”,”if”,”else”,”while”,”for”}; （2）程序中需要用到的主要变量为syn，token和sum。 5.参考部分源程序 [1] globals.h /*本头文件定义分析器需要的一些数据结构和宏等*/ #ifndef _GLOBALS_H #define _GLOBALS_H #include #include #include #define _SYN_MAIN 1 #define _SYN_INT 2 #define _SYN_CHAR 3 #define _SYN_IF 4 #define _SYN_ELSE 5 #define _SYN_FOR 6 #define _SYN_WHILE 7 /*以上为关键字的单词种别码*/ #define _SYN_ID 10 /*标识符的单词种别码*/ #define _SYN_NUM 11 /*整数的单词种别码*/ #define _SYN_PLUS 13 /* 算术运算符“+”的单词种别码 */ #define _SYN_MINUS 14 /* 算术运算符“-”的单词种别码 */ #define _SYN_TIMES 15 /* 算术运算符“*”的单词种别码 */ #define _SYN_DIVIDE 16 /* 算术运算符“/”的单词种别码 */ #define _SYN_ASSIGN 17 /* = */ #define _SYN_SEMICOLON 18 /* ; */ #define _SYN_LT 20 /* < */ #define _SYN_NE 21 /* ！= */ #define _SYN_LE 22 /* <= */ #define _SYN_LG 23 /* > */ #define _SYN_ME 24 /* >= */ #define _SYN_EQ 25 /* = */ #define _SYN_LPAREN 28 /* ( */ #define _SYN_RPAREN 29 /* ) */ #define _SYN_OVER 0 /* # 即源程序结束标志*/ #define MAXLENGTH 255 /* 一行允许的字符个数 */ union WORDCONTENT { /*存放单词内容的联合*/ char T1[MAXLENGTH]; int T2; char T3; }; typedef struct WORD { /*单词二元组*/ int syn; union WORDCONTENT value; }WORD; #endif [2]scan.h /*本头文件定义词法分析器的接口*/ #ifndef _SCAN_H #define _SCAN_H #define _TAB_LEGNTH 4 /*一个TAB占用的空格数*/ #define _KEY_WORD_END "waiting for expanding" /*关键字结束标志*/ void Scaner(void); /*函数scaner得到源程序里的下一个单词符号*/ #endif [3]Symbol.c #include "basedata.h" #include "symbol.h" #include #include #include char *WORD[WORDLEN]={"BEGIN","CALL","CONST","DO", "END","IF","ODD","PROCEDURE", "READ","THEN","VAR","WHILE", "WRITE" };//保留字字符串表,用于将保留字种别码转为字符串输出 SYMBOL WSYM[WORDLEN]={BEGINSYM,CALLSYM,CONSTSYM, DOSYM,ENDSYM,IFSYM,ODDSYM, PROCSYM,READSYM,THENSYM, VARSYM,WHILESYM,WRITESYM};//保留字种别码表 char* SNAME[SYMBOLNUM]= {"NOL","IDENT","NUMBER","PLUS","MINUS","TIMES", "SLASH","ODDSYM","EQL","NEQ","LSS","LEQ","GTR", "GEQ","LPAREN","RPAREN","COMMA","SEMICOLON", "PERIOD","BECOMES","BEGINSYM","ENDSYM","IFSYM", "THENSYM","WHILESYM","WRITESYM","READSYM", "DOSYM","CALLSYM","CONSTSYM","VARSYM","PROCSYM"}; //单词字符串表,用于将保留字种别码转为字符串输出 SYMBOL sym;//最近已识的单词种别码 char token[MAXIDLEN+1];//最近已识别的单词 int num;//最近已识别的数字值 char ch;//最近已识别的字符 int col=1,row=1;//当前行和列值 FILE *fd;//指向待编译文件 extern FILE *fout;//指向存放结果文件 void Getchar(void) { ch=fgetc(fd); if(ch!=EOF && ch!='\n') col++; return; } void Getbc(void) { while(ch==SPACE ||ch==TABLE ||ch=='\n') { if(ch=='\n') {row++;col=1;} Getchar(); }//为空字符则一直读至不为空字符 } void Retract(void) { fseek(fd,-1l,SEEK_CUR); col--; } void Concat(void) { char temp[2]; temp[0]=ch;temp[1]='\0'; strcat(token,temp); } int Reserve(void) { int i,j; char temp[60]; j=strlen(token); for(i=0;i=WORDLEN) i=-1; return i; } void Errorsym(void) { fprintf(fout, "There is error @row: %5d, @col: %5d", row,col); } int Getsym(void) { int k; int flag=TRUE; Getchar(); Getbc();//滤掉白字符 strcpy(token,""); if(isalpha(ch)) { //以字母开头则是标识符 num=0; Concat(); Getchar(); while(isalnum(ch)) { Concat(); Getchar(); } Retract();//由于超前搜索了，所以回退一个字符 k=Reserve();//判断此标识符是否是保留字 if(k!=-1) { sym=WSYM[k];//将保留字种别码存入sym中 } else { sym=IDENT;//将一般标识符种别码存入sym中 }//end else k!=-1; }//end of if isalpha else if(isdigit(ch)) { //以数字开头则为无符号整数 Concat(); Getchar(); while(isdigit(ch)) { Concat(); Getchar(); } if(isalpha(ch)) { flag=FALSE; while(isalnum(ch)) { Concat(); Getchar(); } }//end of flag=FALSE Retract();//回退 if(flag)//若是无符号整数，则将整数值存于num中 {sym=NUMBER;num=atoi(token);} }//end of if isdigit else { num=0; switch (ch) { case '+':Concat();sym=PLUS;break; case '-':Concat();sym=MINUS;break; case '*':Concat();sym=TIMES;break; case '/':Concat();sym=SLASH;break; case '(':Concat();sym=LPAREN;break; case ')':Concat();sym=RPAREN;break; case '=':Concat();sym=EQL;break; case '#':Concat();sym=NEQ;break; /* ODDSYM,EQL,NEQ,LSS,LEQ,GTR,GEQ,LPAREN, RPAREN,COMMA,SEMICOLON,PERIOD,BECOMES, */ case ',':Concat();sym=COMMA;break; case '.':Concat();sym=PERIOD;break; case ';':Concat();sym=SEMICOLON;break; case '>': Concat();Getchar(); if(ch!='=')//若后不跟'=',则回退 {sym=GTR;Retract();} else {Concat();sym=GEQ;} break; case '<':Concat();Getchar(); if(ch!='=') {sym=LSS;Retract();} else {Concat();sym=LEQ;} break; case ':':Concat();Getchar(); if(ch!='=') {flag=FALSE;Retract();} else {Concat();sym=BECOMES;} break; default :Concat();flag=FALSE;break; }//end of switch else char }//end of else char return flag; } [4]Testsym.c #include "basedata.h" #include "symbol.h" #include extern char *WORD[WORDLEN]; extern int WSYM[WORDLEN]; extern char* SNAME[SYMBOLNUM]; extern SYMBOL sym;//last readed word type; extern char token[MAXIDLEN+1];//last readed word extern int num;//last readed num; extern char ch;//last readed char; extern int col,row; extern FILE *fd; FILE *fout; void Init(void); void Quit(void); void main() { int flag; Init(); fprintf(fout,"\n TOKEN SYM NUM"); do{ flag=Getsym(); if(flag) { fprintf(fout,"\n%10s %10s %d",token,SNAME[sym],num); } else if(ch!=EOF) { fprintf(fout,"\n%10s",token); Errorsym(); } }while(ch!=EOF);//反复调用Getsym()识别单词，将输出结果存入fout中 Quit(); } //====================================== void Init(void) { char temp[30]; printf("\nPlease input your file name:"); gets(temp); if ((fd = fopen(temp,"rt")) == NULL) { fprintf(stderr, "Cannot open input file %s.\n",temp); getch(); return ; }//将fd指针指向待分析源文件 if ((fout = fopen("mydata.dat", "wt")) == NULL) { fprintf(stderr, "Cannot open input file.\n"); getch(); return ; }//将fout指向文件mydata.dat } void Quit(void) { fclose(fd); fclose(fout); } 实验二　熟悉FLEX使用方法 【实验目的】 掌握FLEX基本使用方法 掌握如何将通过FLEX生成的C语言模块加入到自已的程序中 【实验要求】 1．编制FLEX源程序,分别统计文本文件a.txt中出现的标识符和整数个数,并显示之。标识符定义为字母开头，后跟若干个字母，数字或下划线。整数可以带+或-号，也可不带，且不以0开头。非单词和非整数则忽略不记，将之滤掉不显示。 2．编制一FLEX源程序,分别求出文件hh.c中字母,数字,回车符的个数。 思考：若main函数不在FLEX中实现，应该如何实现？ 本次实验建议学时2学时。 【实验预习提示】 参见附录一。在看懂的基础上将之调试通过。 实验三　用FLEX自动生成PL/0词法分析器 【实验目的】 熟练掌握FLEX，并通过其生成一个词法分析器 【实验要求】 通过FLEX生成一词法分析器函数int Getsym()，其功能同实验一中词法分析器函数类似。 生成一工程文件，调用1中生成的函数Getsym()，对一指定的文件进行词法分析，要求分析出单词的类型和值。并将分析结果存入一文件Mydata.dat中。 本实验建议学时4学时。 【实验预习提示】 FLEX可自动生成函数int yylex()，则int Getsym()可通过调用yylex()实现。 由于FLEX生成的C程序模块lex.yy.c过于复杂，基本不可读，所以不要直接修改它，可将它看成一个“黑箱”，即不需要清楚知道其内部结构，只需要知道其接口即可。可通过修改FLEX源程序间接修改之。关于lex.yy.c中常用变量和函数，在附录中有详细说明。 编制一FLEX源程序，不妨取名为sym.l，通过FLEX生成lex.yy.c，并将之加入到工程文件中。 工程文件结构 生成一工程文件，不妨取名为test.prj，将文件Symbol.c,lex.yy.c,testsym.c加入之。源程序参考如下： [1]Basedata.h 同实验一中Basedata.h [2]Symbol.h #include #include #define WORDLEN 13 /*保留字个数*/ #define MAXIDLEN 50 /*标识符最长长度*/ #define SYMBOLNUM 32 /*种别码个数*/ typedef enum SYMBOL {NOL,IDENT,NUMBER,PLUS,MINUS,TIMES,SLASH, ODDSYM,EQL,NEQ,LSS,LEQ,GTR,GEQ,LPAREN, RPAREN,COMMA,SEMICOLON,PERIOD,BECOMES, BEGINSYM,ENDSYM,IFSYM,THENSYM,WHILESYM, WRITESYM,READSYM,DOSYM,CALLSYM,CONSTSYM, VARSYM,PROCSYM} SYMBOL;/*定义种别码*/ int Reserve(void); /*判断token字中单词是否是保留字*/ int Getsym(void); /*从当前文件中识别出一单词，并给出其类型和值*/ void MyError(void); /*打印错误信息*/ #endif [3]symbol.c #include "Basedata.h" #include "Symbol.h" #include #include #include char *WORD[WORDLEN]={"BEGIN","CALL","CONST","DO", "END","IF","ODD","PROCEDURE", "READ","THEN","VAR","WHILE", "WRITE" };/*保留字字符串表,用于将保留字种别码转为字符串输出*/ SYMBOL WSYM[WORDLEN]={BEGINSYM,CALLSYM,CONSTSYM, DOSYM,ENDSYM,IFSYM,ODDSYM, PROCSYM,READSYM,THENSYM, VARSYM,WHILESYM,WRITESYM};/*保留字种别码表*/ char* SNAME[SYMBOLNUM]= {"NOL","IDENT","NUMBER","PLUS","MINUS","TIMES", "SLASH","ODDSYM","EQL","NEQ","LSS","LEQ","GTR", "GEQ","LPAREN","RPAREN","COMMA","SEMICOLON", "PERIOD","BECOMES","BEGINSYM","ENDSYM","IFSYM", "THENSYM","WHILESYM","WRITESYM","READSYM", "DOSYM","CALLSYM","CONSTSYM","VARSYM","PROCSYM"}; /*单词字符串表,用于将保留字种别码转为字符串输出*/ SYMBOL sym;/*最近已识的单词种别码*/ char token[MAXIDLEN+1];/*最近已识别的单词*/ int num;/*最近已识别的数字值*/ char ch;/*最近已识别的字符*/ int col=1,row=1;/*当前行和列值*/ int k; int flag; extern FILE *yyin, *yyout; extern int yylex(void); int Reserve(void) { int i,j; char temp[60]; j=strlen(token); for(i=0;i=WORDLEN) i=-1; return i; } void MyError(void) { fprintf(yyout, "There is error @row: %5d, @col: %5d", row,col); } int Getsym(void) { return yylex(); } [4]Testsym.c #include "Basedata.h" #include "Symbol.h" #include extern char *WORD; extern SYMBOL WSYM[WORDLEN]; extern char* SNAME[SYMBOLNUM]; extern SYMBOL sym; extern char token[MAXIDLEN+1]; extern int num; extern char ch; extern int col,row; extern int k; extern int flag; extern FILE *yyin,*yyout; void Init(void); void Quit(void); void main() { int flag; Init(); if(!yyin) return; fprintf(yyout,"\n TOKEN SYM NUM"); do{ flag=Getsym(); if(flag==ENDFILE) return; if(flag) { fprintf(yyout,"\n%10s %10s %d",token,SNAME[sym],num); } else { fprintf(yyout,"\n%10s",token); MyError(); } }while(ch!=EOF);/*反复调用Getsym()识别单词，将输出结果存入fout中*/ Quit(); } /*======================================*/ void Init(void) { char temp[30]; printf("\nPlease input your file name:"); gets(temp); if ((yyin = fopen(temp,"rt")) == NULL) { fprintf(stderr, "Cannot open input file %s.\n",temp); getch(); return ; }/*将fd指针指向待分析源文件*/ if ((yyout = fopen("mydata.dat", "wt")) == NULL) { fprintf(stderr, "Cannot open input file.\n"); getch(); return ; }/*将fout指向文件mydata.dat*/ } void Quit(void) { fclose(yyin); fclose(yyout); } [5]FLEX 源程序sym.l %{ #include "Basedata.h" #include "Symbol.h" #include #include #include extern char *WORD; extern SYMBOL WSYM[WORDLEN]; extern char* SNAME[SYMBOLNUM]; extern SYMBOL sym; extern char token[MAXIDLEN+1]; extern int num; extern char ch; extern int col,row; extern int k; extern int flag; %} %% [\t] {col+=8;} [\n] {row+=1;col=1;} [ ] { col+=1;/*空格则列位置加1*/ } [a-zA-Z][a-zA-Z_0-9]* { num=0; strcpy(token,yytext); /*将当前识别出字符串转为大写形式后存入token*/ k=Reserve();/*判断此标识符是否是保留字*/ if(k!=-1) { sym=WSYM[k];/*将保留字种别码存入sym中*/ } else { sym=IDENT;/*将一般标识符种别码存入sym中*/ }/*end else k!=-1; */ col+=strlen(token);/*改变列位置*/ flag=TRUE; return flag; /*识别出一个单词，退出yylex,下次再调用时*/ /*从当前位置再继续分析 */ } [0-9][0-9]* { strcpy(token,yytext); sym=NUMBER;num=atoi(token); /*若是无符号整数，则将整数值存于num中*/ col+=strlen(token);/*改变列位置*/ flag=TRUE; return flag; } [+] {strcpy(token,yytext);num=0;sym=PLUS;flag=TRUE;col++;return flag;} [-] {strcpy(token,yytext);num=0;sym=MINUS;flag=TRUE;col++;return flag;} [*] {strcpy(token,yytext);num=0;sym=TIMES;flag=TRUE;col++;return flag;} \( {strcpy(token,yytext);num=0;sym=LPAREN;flag=TRUE;col++;return flag;} [/] {strcpy(token,yytext);num=0;sym=SLASH;flag=TRUE;col++;return flag;} \) {strcpy(token,yytext);num=0;sym=RPAREN;flag=TRUE;col++;return flag;} [=] {strcpy(token,yytext);num=0;sym=EQL;flag=TRUE;col++;return flag;} [#] {strcpy(token,yytext);num=0;sym=NEQ;flag=TRUE;col++;return flag;} [,] {strcpy(token,yytext);num=0;sym=COMMA;flag=TRUE;col++;return flag;} [.] {strcpy(token,yytext);num=0;sym=PERIOD;flag=TRUE;col++;return flag;} [;] {strcpy(token,yytext);num=0;sym=SEMICOLON;flag=TRUE;col++;return flag;} [>] {strcpy(token,yytext);num=0;sym=GTR;flag=TRUE;col++;return flag;} ">=" {strcpy(token,yytext);num=0;sym=GEQ;flag=TRUE;col+=2;return flag;} [<] {strcpy(token,yytext);num=0;sym=LSS;flag=TRUE;col++;return flag;} "<=" {strcpy(token,yytext);num=0;sym=LEQ;flag=TRUE;col+=2;return flag;} ":=" {strcpy(token,yytext);num=0;sym=BECOMES;flag=TRUE;col+=2;return flag;} <> {flag=ENDFILE;return flag;} . { strcpy(token,yytext); col+=strlen(yytext);/*改变列位置*/ flag=FALSE; return flag;/*其它情况则报错*/ } %% int yywrap() { return 1; } 实验四　用递归下降法进行表达式分析 【实验目的】 1.掌握用递归下降分析法进行语法分析的方法。加深对自顶向下语法分析原理的理解。 2.掌握设计、编制并调试自顶向下语法分析程序的思想和方法。 3.本实验是高级语言程序设计、数据结构和编译原理中词法分析、自顶向下语法分析原理等知 识的综合。由于语法分析是在词法分析的基础上进行的，且词法分析器输出的结果即单词符号 或单词符号序列是语法分析的输入。 【实验要求】 已知表达式文法的扩充巴克斯范式为 S->E# E->T{+T | -T} T->F{*F | /F} F->(E) | i 上式中，#可用文件结束符Ctrl+z代替。i 为整数。 从键盘输入表达式，利用递归下降法求出其值，如输入表达式有错，则给出报错提示。例：输入表达式串为：13+5*4则应给出结果为33。 本实验建议学时2学时。 【实验预习提示】 词法分析器可用以前所编的的int Getsym(void)函数。 自编工程文件，仿照前面几次实验对要用到的文件进行组织。 对表达式文法中每一非终结符均可通过一个函数进行识别，现就非终结符S和E的函数提示如下。其它非 终结符对应的函数自编之。 int S(void) { int a; a=E(); if(flag==ENDFILE) return a; else Derror(); } int E(void) { int a,b; SYMBOL t; a=T(); while (sym==PLUS || sym==MINUS) { t=sym; flag=Getsym(); if(!flag) { MyError(); exit(0); } b=T(); if (t==PLUS) a=a+b; else a=a-b; } return a; } 实验五　用算符优先法进行表达式分析 【实验目的】 1.掌握用算符优先分析法进行语法分析的方法。加深对自底向上语法分析原理的理解。 2.掌握设计、编制并调试自底向上语法分析程序的思想和方法。 3.本实验是高级语言程序设计、数据结构和编译原理中词法分析、自底向上语法分析原理等知 识的综合。由于语法分析是在词法分析的基础上进行的，且词法分析器输出的结果即单词符 号或单词符号序列是语法分析的输入。 【实验要求】 从键盘输入表达式，利用递归下降法求出其值，如输入表达式有错，则给出报错提示。表达式以；结尾。例：以于如下的输入表达式串： 13+5*4；则应给出结果为33。 【实验提示】 1．实验原理 我们要分析的表达式满足下面的算符优先矩阵 θ2 θ1 + - * / ( ) ; + > > < < < > > - > > < < < > > * > > > > < > > / > > > > < > > ( < < < < < = ) > > > > > > ; < < < < < = 为实现算符优先算法，可以使用两个工作栈。一个叫做OPTR，用以寄存运算符，一个叫OPND,用以寄存操作数或结果。算法描述如下： [1] 首先置操作数栈为空栈，将表达式起始符;作为运算符栈的栈底元素。 [2] 依次读入表达式中每个单词，若是操作数进OPND栈，若是运算符则转[3]。 [3] 将此运算符θ1与OPTR栈顶元素θ2进行比较，即查上表， 若θ1＞θ2，则：θ1进栈，转[2] 若θ1＝θ2 ,如θ1为；，则分析成功，否则OPTR栈顶元素出栈，并转[2] 若θ1<θ2,则出栈OPND栈顶元素至b，又出栈其栈顶元素至a，出栈OPTR栈顶元素至t，进行运算r=a t b(t 为运算符)，并将结果r存入栈OPND后转[3]。 若θ1和θ2之间无优先关系，则报错。 2．源程序提示： 利用以前实验生成的Getsym（）进行单词识别，并自组织工程文件，关于算符优先算法要用到的部份函数提示如下。 [1]一些自定义的变量和函数的声明 #define MAX 255 SYMBOL title[7]= {PLUS,MINUS,TIMES,SLASH,LPAREN,RPAREN,SEMICOLON};//用来将相应的种别码与数组下标进行映射 char oo[7][7]={ {'>','>','<','<','<','>','>'}, {'>','>','<','<','<','>','>'}, {'>','>','>','>','<','>','>'}, {'>','>','>','>','<','>','>'}, {'<','<','<','<','<','=','!'}, {'>','>','>','>','!','>','>'}, {'<','<','<','<','<','!','='} };//算符优先矩阵，其中’!’表示两算符无优先关系 int OPND[MAX];//操作数栈 SYMBOL OPTR[MAX]; //算符栈 int topd,topr;// 两栈的指针 void PushOpnd (int a); int PopOpnd (void); int EmptyOpnd (void); int GetTopOpnd (void); void PushOptr (SYMBOL a); SYMBOL PopOptr (void); int EmptyOptr (void); SYMBOL GetTopOptr (void); //上面为栈函数 int Position(SYMBOL c); //将c映射至数组下标 int IsOpnd(SYMBOL c); //判断c是否是操作数 int IsOptr(SYMBOL c); //判断c是否是操作符 char Precede(SYMBOL c1,SYMBOL c2); //查算符优先矩阵，求出c1和c2之间的优先矩阵 int Operate(int a,int b,SYMBOL o); //求出a o b char First(); //算符优先分析函数 [2]部份函数实现的源代码 /***********************/ int Position(SYMBOL c) { int i; for(i=0;i<7;i++) if(c==title[i]) return i; return -1; } /********************************/ char Precede(SYMBOL c1,SYMBOL c2) { int i,j; i=Position(c1); j=Position(c2) if(i!=-1 && j!=-1) {return oo[i][j]} else return ('*'); } /**********************************/ int Operate(int a,int b,SYMBOL o) { switch (o) { case PLUS: return a+b; case MINUS: return a-b; case TIMES: return a*b; case SLASH: return a/b; default: return 0; } } /****************************************/ char First() { int a,b,r; char c; a=b=r=0; topd=-1; topr=-1; PushOptr(SEMICOLON); Getsym(); wh