编译实验指导书(04年3月)

编译原理实验指导编译原理实验指导书----1----前言编译原理是计算机专业的主干课和必修课，由于这门课程相对抽象且内容较复杂，一直是比较难学的一门课程。在编译原理的学习过程中，实验非常重要，只有通过上机实验，才能使学生对比较抽象的课程内容产生一个具体的感性认识。本书实验环境主要为C环境，在C环境下手动生成词法分析器及语法分析器，通过这些实验，能使学生对这些部份的工作机理有一个详细的了解。由于这门课实验难度较大，所以希望在实验前学生要做好预习工作。在上机前写好实验预习报告。编译原理实验指导书----2----目录实验一手工生成PL/0语言词法分析器-----------------1实验二用算符优先法进行表达式分析------------------16编译原理实验指导书----3----实验一手工生成PL/0语言词法分析器(1)实验目的1、掌握手工生成词法分析器的方法，了解词法分析器的内部工作原理。2、掌握C环境下工程文件的用法(2)实验要求1、手工编制PL/0语言词法分析函数intGetsym(void);每调用此函数一次，从当前待编译文件中识别出单词，并给出其类型和值。2、生成一工程文件，调用1中生成的函数Getsym()，对一指定的文件进行词法分析，要求分析出单词的类型和值，对于词法错误之处，要给出错误所在位置。并将分析结果存入一文件Mydata.dat中。3、实验前请仔细阅读实验预习提示，提示中程序仅供参考。4、本实验建议上机时间4学时。(3)实验预习提示1、词法分析器的功能和输出格式词法分析器的功能是输入源程序，输出单词符号。词法分析器的单词符号常常表示成以下的二元式(单词种别码，单词符号的属性值)。本实验中，采用的是一符一种别码的方式。单词种类有五种：基本字：也可称为保留字，如BEGIN，END，IF，THEN等；运算符：如+，-，*，/，:=，#，=，=等；标识符：用户定义的变量名、常数名、过程名；常数：如10，25，100等整数；界符：如“，”，“.”，“；”，“（”，“）”等。2、单词的EBNF（扩展巴科斯范式）表示下面是对PL/0进行词法分析所用到的部份EBNF。标识符→字母{字母|数字|下划线}无符号整数→数字{数字}加法运算符→+减法运算符→-...编译原理实验指导书----4----大于关系运算符→大于等于关系运算符→=...3、“超前搜索”方法词法分析时，常常会用到超前搜索方法。如当前待分析字符串为“a+”,当前字符为’’，此时，分析器倒底是将其分析为大于关系运算符还是大于等于关系运算符呢？显然，只有知道下一个字符是什么才能下结论。于是分析器读入下一个字符’+’，这时可知应将’’解释为大于运算符。但此时，超前读了一个字符’+’，所以要回退一个字符，词法分析器才能正常运行。在分析标识符，无符号整数等时也有类似情况。4、词法分析过程PL/0的词法分析程序Getsym（图1）是一个独立的过程，它把输入的字符串形式的源程序分割成一个个单词符号。为此PL/0编译程序设置了三个全程量的公用单元如下：Sym：存放每个单词的类别，用内部编码形式表示；Id：存放用户所定义的标识符的值，即标识符字符串的机内表示；Num：存放用户定义的数。如果我们把基本字、运算符、界符称为语言固有的单词，而对标识符、常数称为用户定义的单词，那么经词法分析程序分出的单词，对固有的单词只给出类别存放在sym中，而对用户定义的单词（标识符或常数）既给出类别又给值，其类别存放在sym中，值放在id或num中，全部单词种类由编译程序定义的纯量类型sumbol给出，也可称为语法的词汇表。如下面提到的ifsym，thensym，ident，number均属symbol中的元素。因此词法分析程序Getsym将完成下列任务：（1）滤空格：空格在词法分析时是一种不可缺少的界符，而在语法分析时则是无用的，必须滤掉；（2）识别保留字：设有一张保留字表。对每个字母打头的字母、数字串要查此表。若查到则为保留字，将对应的类别放在sym中，如IF对应值IFSYM，THEN对应为THENSYM。若查不到，则认为是用户定义的标识符；（3）识别标识符：对用户定义的标识符将IDENT放在SYM中，标识符本身的值放在ID中；（4）拼数：当所取单词是数字时，将数的类别NUMBER放在SYM中，数值本身的值存放在NUM中；（5）拼复合词：对两个字符组成的算符，如=，:=，=等单词，识别后将类别送SYM中；（6）输出源程序：边读入字符边输出（可输出在文件中）。编译原理实验指导书----5----由于一个单词往往是由一个或几个字符组成的，所以在词法分析过程Getsym中又定义了一个取字符过程GETCH（见图2），由词法分析需要取字符时调用。图1词法分析过程GETSYMGETCH所用单元说明：CH：存放当前读取的字符，初值为空；LINE：为一维数组，其数组元素是字符，界对为1：80。用于读入一行字符的缓冲区。LL和CC为计数器，初值为0；编译原理实验指导书----6----GETSYM流程图的工作单元说明：A：一维数组，数组元素为字符，界对1：10；ID：同A；WORD：保留字表，一维数组，数组元素为以字符为元素的一维数组，界对为1：13，查找方式采用二分法。图2取字符过程GETCH5、工程文件结构由于在以后的实验中，还会用到本次实验的结果。为提高代码的复用性，必须采用模块化设计的方法。本例中，用到了自编的四个文件，即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,运行之即可对指定的源文件进行词法分析。6、参考源程序[1]Basedata.h编译原理实验指导书----7----#ifndef_BASETYPE_H#define_BASETYPE_H#defineFALSE0#defineTRUE1#defineSPACE0x20#defineBACKSPACE0x08#defineENTER0x0d#defineESC0x1b#defineTABLE0x09#defineENDFILE-1#endif[2]Symbol.h#ifndef_SYMBOL_H#define_SYMBOL_H#includestdio.h#includestdlib.h#defineWORDLEN13//保留字个数#defineMAXIDLEN50//标识符最长长度#defineSYMBOLNUM32//种别码个数typedefenumSYMBOL{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;//定义种别码voidGetchar(void);//取下一个字符voidGetbc(void);//如当前字符为白字符，则读字符至不为白字符时停止编译原理实验指导书----8----voidConcat(void);//将当前字符加入token字voidRetract(void);//回退一字符intReserve(void);//判断token字中单词是否是保留字intGetsym(void);//从当前文件中识别出一单词，并给出其类型和值voidErrorsym(void);//打印错误信息#endif[3]Symbol.c#includebasedata.h#includesymbol.h#includeconio.h#includestring.h#includectype.hchar*WORD[WORDLEN]={BEGIN,CALL,CONST,DO,END,IF,ODD,PROCEDURE,READ,THEN,VAR,WHILE,WRITE};//保留字字符串表,用于将保留字种别码转为字符串输出SYMBOLWSYM[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,编译原理实验指导书----9----DOSYM,CALLSYM,CONSTSYM,VARSYM,PROCSYM};//单词字符串表,用于将保留字种别码转为字符串输出SYMBOLsym;//最近已识的单词种别码chartoken[MAXIDLEN+1];//最近已识别的单词intnum;//最近已识别的数字值charch;//最近已识别的字符intcol=1,row=1;//当前行和列值FILE*fd;//指向待编译文件externFILE*fout;//指向存放结果文件voidGetchar(void){ch=fgetc(fd);if(ch!=EOF&&ch!='\n')col++;return;}voidGetbc(void){while(ch==SPACE||ch==TABLE||ch=='\n'){if(ch=='\n'){row++;col=1;}Getchar();}//为空字符则一直读至不为空字符}voidRetract(void){fseek(fd,-1l,SEEK_CUR);col--;}voidConcat(void){编译原理实验指导书----10----chartemp[2];temp[0]=ch;temp[1]='\0';strcat(token,temp);}intReserve(void){inti,j;chartemp[60];j=strlen(token);for(i=0;ij;i++){temp[i]=toupper(token[i]);//将当前token字以大写形式存入temp中}temp[i]='\0';for(i=0;iWORDLEN;i++){if(!strcmp(WORD[i],temp))break;}//判断当前token是否是保留字if(i=WORDLEN)i=-1;returni;}voidErrorsym(void){fprintf(fout,Thereiserror@row:%5d,@col:%5d,row,col);}intGetsym(void){intk;intflag=TRUE;Getchar();编译原理实验指导书----11----Getbc();//滤掉白字符strcpy(token,);if(isalpha(ch)){//以字母开头则是标识符num=0;Conc