编译原理实验指导书.doc

编译原理上机指导编者：郭文宏二零零三年十月第一版实验指导书 前 言编译原理是计算机专业的主干课和必修课，由于这门课程相对抽象且内容较复杂，一直是比较难学的一门课程。在编译原理的学习过程中，实验非常重要，只有通过上机实验，才能使学生对比较抽象的课程内容产生一个具体的感性认识。但是，目前国内市场上很少有较详细且比较适合我院实际的实验指导书，为此，我们特编了这份指导书，希望能对我院的编译原理教学工作有所帮助。本书实验环境主要为C环境(由于兼容性问题，建议使用Turboc2.0)及一个词法分析器自动生成工具FLEX和一个语法分析器自动生成工具BISON。在C环境下的几个实验，让学生手动生成词法分析器及完成一些小的语法分析器，通过这些实验，能使学生对这些部份的工作机理有一个详细的了解，达到“知其然，且知其所以然”的目的。并可在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下调试通过.由于编者水平有限，本书中必然存在着不少缺点，在此恳请大家给予批评和指正，我们将尽力纠正。如对本书有批评指正，请Email至。在此特对关心支持编写本书的院系领导表示感谢。本书中关于LEX和YACC的部份大量参考引用了何炎祥老师主编，华中理工大学出版社出版的编译原理一书，在此表示衷心的感谢。 郭文宏2001年10月12日目 录实验一手工生成PL/0语言词法分析器 -1实验二熟悉FLEX使用方法 -11实验三用FLEX自动生成PL/0词法分析器-12实验四用递归下降法进行表达式分析-20实验五用算符优先法进行表达式分析-22实验六利用BISON生成逆波兰表示计算器-27实验七利用BISON生成中缀表示计算器-28附录一 词法分析器生成工具FLEX简介-29附录二 语法分析器生成工具YACC简介-37实验指导书 -43-实验一手工生成PL/0语言词法分析器(1) 实验目的1、 掌握手工生成词法分析器的方法，了解词法分析器的内部工作原理。2、 掌握C环境下工程文件的用法(2) 实验要求1、 手工编制PL/0语言词法分析函数int Getsym(void);每调用此函数一次，从当前待编译文件中识别出一单词，并给出其类型和值。关于PL/0的说明参见第二章(清华大学吕映芝编)。2、 生成一工程文件，调用1中生成的函数Getsym()，对一指定的文件进行词法分析，要求分析出单词的类型和值，对于词法错误之处，要给出错误所在位置。并将分析结果存入一文件Mydata.dat中。3、 实验前请仔细阅读实验预习提示，提示中程序仅供参考。4、 本实验建议上机时间4-6学时。(3) 实验预习提示1、 词法分析器的功能和输出格式词法分析器的功能是输入源程序，输出单词符号。词法分析器的单词符号常常表示成以下的二元式(单词种别码，单词符号的属性值)。本实验中，采用的是一符一种别码的方式。2、 单词的EBNF（扩展巴科斯范式）表示下面是对PL/0进行词法分析所用到的部份EBNF。:= |:= := +:= -.:= := =.3、“超前搜索”方法词法分析时，常常会用到超前搜索方法。如当前待分析字符串为“a+”,当前字符为，此时，分析器到底是将其分析为大于关系运算符还是大于等于关系运算符呢？显然，只有知道下一个字符是什么才能下结论。于是分析器读入下一个字符+，这时可知应将解释为大于运算符。但此时，超前读了一个字符+，所以要回退一个字符，词法分析器才能正常运行。在分析标识符，无符号整数等时也有类似情况。4、 工程文件结构由于在以后的实验中，还会用到本次实验的结果。为提高代码的复用性，必须采用模块化设计的方法。本例中，用到了自编的四个文件，即Basedata.h,Symbol.h,Symbol.c,Testsym.c。其中，两个.h头文件中存放的是一些宏定义和自定义数据类型，Symbol.h中还存放有词法分析器要用到的一些自定义函数的声明。在Symbol.c中存放的是对这些函数的定义部份。Testsym.c中存放的是主函数部份，在此处调用词法分析器对待分析PL/0文件进行分析。现建一工程文件，名为test.prj,将文件Basedata.h，Symbol.h，Symbol.c，Testsym.c加入工程文件中，编译链接后生成可执行文件Test.exe,运行之即可对指定的源文件进行词法分析。5、参考源程序1Basedata.h#ifndef _BASETYPE_H#define _BASETYPE_H#define FALSE 0#define TRUE 1#define SPACE 0x20#define BACKSPACE 0x08#define ENTER 0x0d#define ESC 0x1b#define TABLE 0x09 #define ENDFILE -1#endif2Symbol.h #ifndef _SYMBOL_H#define _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;/定义种别码void Getchar(void);/取下一个字符void Getbc(void);/如当前字符为白字符，则读字符至不为白字符时停止void Concat(void);/将当前字符加入token字void Retract(void);/回退一字符int Reserve(void);/判断token字中单词是否是保留字int Getsym(void);/从当前文件中识别出一单词，并给出其类型和值void Errorsym(void);/打印错误信息#endif3Symbol.c#include basedata.h#include symbol.h#include #include #include char *WORDWORDLEN=BEGIN,CALL,CONST,DO, END,IF,ODD,PROCEDURE, READ,THEN,VAR,WHILE, WRITE ;/保留字字符串表,用于将保留字种别码转为字符串输出SYMBOL WSYMWORDLEN=BEGINSYM,CALLSYM,CONSTSYM, DOSYM,ENDSYM,IFSYM,ODDSYM, PROCSYM,READSYM,THENSYM, VARSYM,WHILESYM,WRITESYM;/保留字种别码表char* SNAMESYMBOLNUM= 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 tokenMAXIDLEN+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 temp2; temp0=ch;temp1=0; strcat(token,temp);int Reserve(void) int i,j; char temp60; j=strlen(token); for(i=0;ij;i+) tempi=toupper(tokeni);/将当前token字以大写形式存入temp中 tempi=0; 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=WSYMk;/将保留字种别码存入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(); elseConcat();sym=GEQ; break; case :Concat();Getchar(); if(ch!=)sym=LSS;Retract(); elseConcat();sym=LEQ; break; case :Concat();Getchar(); if(ch!=)flag=FALSE;Retract(); elseConcat();sym=BECOMES; break; default :Concat();flag=FALSE;break; /end of switch else char /end of else char return flag; 4Testsym.c#include basedata.h#include symbol.h#include extern char *WORDWORDLEN;extern int WSYMWORDLEN;extern char* SNAMESYMBOLNUM;extern SYMBOL sym;/last readed word type;extern char tokenMAXIDLEN+1;/last readed wordextern 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); doflag=Getsym();if(flag) fprintf(fout,n%10s %10s %d,token,SNAMEsym,num); else if(ch!=EOF) fprintf(fout,n%10s,token); Errorsym(); while(ch!=EOF);/反复调用Getsym()识别单词，将输出结果存入fout中 Quit();/=void Init(void) char temp30; 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.datvoid Quit(void) fclose(fd); fclose(fout);实验二熟悉FLEX使用方法(1) 实验目的1、 掌握FLEX基本使用方法2、 掌握如何将通过FLEX生成的C语言模块加入到自已的程序中(2) 实验要求1、编制FLEX源程序,分别统计文本文件a.txt中出现的标识符和整数个数,并显示之。标识符定义为字母开头，后跟若干个字母，数字或下划线。整数可以带+或-号，也可不带，且不以0开头。非单词和非整数则忽略不记，将之滤掉不显示。2、编制一FLEX源程序,分别求出文件hh.c中字母,数字,回车符的个数。3、 思考：若main函数不在FLEX中实现，应该如何实现？4、 本次实验建议学时2学时。(3)实验预习提示参见附录一。在看懂的基础上将之调试通过。实验三用FLEX自动生成PL/0词法分析器(1) 实验目的熟练掌握FLEX，并通过其生成一个词法分析器(2) 实验要求1、 通过FLEX生成一词法分析器函数int Getsym()，其功能同实验一中词法分析器函数类似。2、 生成一工程文件，调用1中生成的函数Getsym()，对一指定的文件进行词法分析，要求分析出单词的类型和值。并将分析结果存入一文件Mydata.dat中。3、 本实验建议学时4学时。(3) 实验预习提示1、 FLEX可自动生成函数int yylex()，则int Getsym()可通过调用yylex()实现。2、 由于FLEX生成的C程序模块lex.yy.c过于复杂，基本不可读，所以不要直接修改它，可将它看成一个“黑箱”，即不需要清楚知道其内部结构，只需要知道其接口即可。可通过修改FLEX源程序间接修改之。关于lex.yy.c中常用变量和函数，在附录中有详细说明。3、 编制一FLEX源程序，不妨取名为sym.l，通过FLEX生成lex.yy.c，并将之加入到工程文件中。4、 工程文件结构生成一工程文件，不妨取名为test.prj，将文件Symbol.c,lex.yy.c,testsym.c加入之。源程序参考如下：1Basedata.h 同实验一中Basedata.h2Symbol.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);/*打印错误信息*/#endif3symbol.c#include Basedata.h#include Symbol.h#include #include #include char *WORDWORDLEN=BEGIN,CALL,CONST,DO, END,IF,ODD,PROCEDURE, READ,THEN,VAR,WHILE, WRITE ;/*保留字字符串表,用于将保留字种别码转为字符串输出*/SYMBOL WSYMWORDLEN=BEGINSYM,CALLSYM,CONSTSYM, DOSYM,ENDSYM,IFSYM,ODDSYM, PROCSYM,READSYM,THENSYM, VARSYM,WHILESYM,WRITESYM;/*保留字种别码表*/char* SNAMESYMBOLNUM= 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 tokenMAXIDLEN+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 temp60; j=strlen(token); for(i=0;ij;i+) tempi=toupper(tokeni);/*将当前token字以大写形式存入temp中*/ tempi=0; 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();4Testsym.c#include Basedata.h#include Symbol.h#include extern char *WORD;extern SYMBOL WSYMWORDLEN;extern char* SNAMESYMBOLNUM;extern SYMBOL sym;extern char tokenMAXIDLEN+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); doflag=Getsym();if(flag=ENDFILE)return;if(flag) fprintf(yyout,n%10s %10s %d,token,SNAMEsym,num); else fprintf(yyout,n%10s,token); MyError(); while(ch!=EOF);/*反复调用Getsym()识别单词，将输出结果存入fout中*/ Quit();/*=*/void Init(void) char temp30; 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);5FLEX 源程序sym.l%#include Basedata.h#include Symbol.h#include #include #include extern char *WORD;extern SYMBOL WSYMWORDLEN;extern char* SNAMESYMBOLNUM;extern SYMBOL sym;extern char tokenMAXIDLEN+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-Za-zA-Z_0-9* num=0; strcpy(token,yytext); /*将当前识别出字符串转为大写形式后存入token*/ k=Reserve();/*判断此标识符是否是保留字*/ if(k!=-1) sym=WSYMk;/*将保留字种别码存入sym中*/ else sym=IDENT;/*将一般标识符种别码存入sym中*/*end else k!=-1; */col+=strlen(token);/*改变列位置*/flag=TRUE;return flag;/*识别出一个单词，退出yylex,下次再调用时*/*从当前位置再继续分析 */ 0-90-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) 实验要求已知表达式文法的扩充巴克斯范式为S-E#E-T+T | -TT-F*F | /FF-(E) | I上式中，#可用文件结束符Ctrl+z代替。I 为整数。从键盘输入表达式，利用递归下降法求出其值，如输入表达式有错，则给出报错提示。例：输入表达式串为：13+5*4则应给出结果为33。本实验建议学时2学时。(3) 实验预习提示1、 词法分析器可用以前所编的的int Getsym(void)函数。2、 自编工程文件，仿照前面几次实验对要用到的文件进行组织。3、 对表达式文法中每一非终结符均可通过一个函数进行识别，现就非终结符S和E的函数提示如下。其它非4、 终结符对应的函数自编之。 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) 实验要求从键盘输入表达式，利用递归下降法求出其值，如输入表达式有错，则给出报错提示。表达式以；结尾。例：以于如下的输入表达式串： 13+5*4；则应给出结果为33。（3）实验提示1、 实验原理我们要分析的表达式满足下面的算符优先矩阵 21+-*/();+-*/(;= 为实现算符优先算法，可以使用两个工作栈。一个叫做OPTR，用以寄存运算符，一个叫OPND,用以寄存操作数或结果。算法描述如下：1首先置操作数栈为空栈，将表达式起始符;作为运算符栈的栈底元素。2依次读入表达式中每个单词，若是操作数则进OPND栈，若是运算符则转3。3将此运算符1与OPTR栈顶元素2进行比较，即查上表，若 12，则：1进栈，转2若 12 ,如1为；，则分析成功，否则OPTR栈顶元素出栈，并转2