编译原理实验讲义.doc

编译原理实验书 2011年3月 实验目录 实验1：词法分析程序（3学时、第6、7周）2实验2：语法分析-递归子程序法（3学时，第7、8周）11实验3：语法分析-预测分析法（3学时，第9、10周）28实验4：语义分析和代码生成（15学时，第1017周）38 适用专业及实验总学时：2008级计算机科学与技术专业2008级计算机科学与技术专业(网络方向)24总学时 恭喜你！你将进入非常重要的专业课程的实践。编译原理的知识影响到专业人员的素质，除编译程序外有大量专业工作与编译技术相关 。你现在需要通过脚踏实地的实践学习，把自己的专业水平提高一个层次。如何才能把实验做好？实验课时非常有限，建议打印本学期的全部实验资料。如果可以，你的私人电脑安装Visual Studio C+开发环境，以便课余继续练习。上实验课之前，一定要仔细研究实验课相关程序，设计好解决方案。上实验课时，直接调试程序并获得结果，如有不懂之处，应该也必须及时提问、解决。实验课后，完成实验报告。每个实验必须提交实验报告。实验报告内容含：关键问题、设计思路、实现的关键代码、程序运行结果、总结及进一步改善建议。每个实验报告1500字2500字，约23页A4纸。实验报告打印出来后上交。不允许抄袭实验报告。实验报告内容超过60%相同，涉及人员均作为抄袭处罚。一份汗水，一份收获。只要你认真完成上述实验，你一定获得更加专业的自信。加油！实验1：词法分析程序（3学时、第6、7周）1 实验目的和内容：1） 实验目的：通过完成词法分析程序，了解词法分析的过程。2） 实验内容：用C实现对Pascal的子集程序设计语言的词法识别。3） 实验要求：要求修改文法和程序，增加浮点数处理功能。实验环境是Windows操作系统、Visual C+开发环境。2. 程序设计语言的描述：.PROGRAM ;CONST ,;标识符=无符号整数VAR ,;标识符,标识符:INTEGER|LONG;PROCEDURE 标识符;|PROCEDURE 标识符(标识符:);|标识符:=IF THEN WHILE DO 标识符|标识符()READ (标识符,标识符)WRITE (,)BEGIN ;END|ODD +|-标识符|无符号整数|()+|-*|/=|=其中： 用左右尖括号括起来的符号串表示非终结符 定义为 表示该语法成分可以重复0n次 表示方括号内为可选项，即0或1次3 程序设计语言单词的内部编码：(35个终结符) 内码单词内码单词内码单词内码单词1PROGRAM2CONST3VAR4INTEGER5LONG6PROCEDURE7IF8THEN9WHILE10DO11READ12WRITE13BEGIN14END15ODD16+17-18*19/20=21222325=26.27,28;29:30:=31(32)33无符号整数34标识符35#4. 词法分析程序的设计思想：为了使实现的编译程序实用，规定源程序可以采用自由书格式，即一行内可以书写多个语句，一个语句也可以写成多行；标识符的前20个字符有效；整数用2个字节表示；长整数用4个字节表示。这样，词法分析程序的主要工作为：1） 从源程序中读入字符。2） 统计行数和列数用于错误单词的定位。3） 删除空格类字符，包括回车、制表符空格。4） 对拼写的单词，用（内码，属性）二元式表示。5） 填写符号表。这里采用一遍扫描的方法，即从左到右只扫描一次源程序，词法分析作为语法分析的一个子程序，在编写词法分析程序时，用重复调用词法分析子程序取一单词方法，得到整个源程序的内码流。 5调试时可以使用下面的源程序作为下述词法分析程序的输入（当然，你也可以自己编写一个源程序），词法分析程序输出词法分析结果。PROGRAM MYPASCAL; CONST UNIT=100;VAR x:INTEGER;PROCEDURE subproc(i:INTEGER); BEGIN x:=i; END;BEGIN subproc(20); x:=x+UNIT;END. 6下面是一个词法分析程序，该程序能够将源程序，也就是相应字符流转换成内码，并输出到文件。程序的执行需要提供两个参数，第一个参数是源程序文件名，第二个参数是存放分析结果的文件名，第二个参数可以省略，可由程序自动生成。Vc+6程序参数的设置方法：菜单project下子菜单settings中的debug选项卡下program arguments对话框中，输入参数。 #include #include #include #include #define lenth1 15 /保留字表的长度#define lenth2 17 /运算符界符表长度struct char name21;int type;int addr;indent1000; /符号表struct stchar name21;int code;sym; /当前单词FILE *f1,*f2;int line=1,row=1,val; /行号、列号、数字串的值char ch= ; /当前字符int lenth3=0; /符号表中实际的标识符个数void getsym();char getchr();void error(int);main(int argc,char *argv) char ft12,*fc; if (f1=fopen(argv1,r)=NULL) /打开源程序文件 printf(can not open file.n);exit(0); if (argc=2) /如果没有提供第二个参数 strcpy(ft,argv1);if (fc=strchr(ft,.)!=NULL) /如果第一个参数即源文件名，有后缀 .xxxstrcpy(fc,.mid); /结果文件名：源文件名非后缀部分.midelsestrcat(ft,.mid); /结果文件名：源文件名.mid else strcpy(ft,argv2); if (f2=fopen(ft,w)=NULL) /打开结果文件 printf(cannot open file 2n); exit(0); while (!feof(f1) /只要没有遇到源文件的结尾，继续循环。 getsym(); /获取一个单词放到sym printf(%s %dn,,sym.code); /显示当前单词的名字及其内码 fprintf(f2,%s %dn,,sym.code); fclose(f1); fclose(f2);void getsym()static char alenth110=program,const,var,integer,long,procedure,if,then,while,do,read,write,begin,end,odd;/保留字表static char dlenth23=+,-,*,/,=,=,.,;,:,:=,(,); /运算符界符表char str21;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) /如果该字符串是保留字，将当前单词写入sym strcpy(,ai);sym.code=i+1; else /该单词不是保留字，而是标识符 for(i=0;ilenth3;i+) /在符号表里检查是否已经登记过该标识符 if (!strcmp(str,) break; /如果登记过，中断循环 if (i=lenth3) strcpy(,str);/如果没有登记过该标识符,登记它到符号表。lenth3+; strcpy(,); /当前标识符写入sym sym.code=34; else if (isalnum(ch) /如果当前字符是数字 val=0;n=0; while (isalnum(ch) val=val*10+ch-0; n+=ch; ch=getchr();n=0;sym.code=33; else /当前字符是运算符或者界符 if (ch=+ | ch=- | ch=* | ch=/ | ch= | ch=. | ch=, | ch=; | ch=( | ch=) str0=ch;str1=0;ch=getchr(); /从文件中读入一个字符 for (i=0;ilenth2;i+) /在运算符界符表查询，是否有此ch字符if (!strcmp(str,di) strcpy(,str); /有， sym.code=i+16; else /处理符号 = : := n=0;if (ch= | ch=:) strn+=ch; if (ch=getchr()=) / =或:= strn+=ch; ch=getchr(); else if (ch=) / =或 strn+=ch; ch=getchr(); else if (ch=-1) strcpy(,); sym.code=35; /#/else error(1); strn=0; /str为一个完整的单词 for (i=0;ilenth2;i+) /查运算符界符表，看是否有此符号串str if (!strcmp(str,di) strcpy(,str); sym.code=i+16; char getchr() char ch=fgetc(f1); if (ch=n) row=1; line+; else if (ch!= & ch!=t) row+; return (ch);void error(int n) printf(%d error happens.n,n); exit(0);词法分析程序 getsym()流程图读入下一个字符到chch的符号是空格？ Y Nch的符号是字母？ 标识符或者保留字 Y ch的符号是字母或数字？ N N Ych的符号是字母？ N Y将ch的字母变为小写字母将ch的符号加入到字符数组str尾读入下一个符号到ch在str尾增加0,构建一个字符串在保留字表a中查找str的位置ii或者:吗？构造str并读入符号到ch Y ch是=吗？ N N 或： Y =或:=构造str并读入符号到ch ch是吗？ N Y =或构造str并读入符号到ch登记#到sym，内码35 在str末尾加0,构建字符串在运算符界符表d查str位置i。查到？单词str?登记str到sym,内码i+16 Y N结束实验2：语法分析-递归子程序法（3学时，第7、8周）1 目的：通过完成语法分析程序，了解语法分析的过程和作用。2 实验内容：用递归子程序法实现对Pascal的子集程序设计语言的分析程序。下面分析程序对源程序的内码流进行分析，如果为文法定义的句子，则输出“是”，否则输出“否”。还能根据需要处理说明语句，填写相应的符号表，供以后生成代码时使用。3 实验要求：要求修改文法和程序，增加浮点数处理功能。4 改写实验一的文法，使其是无递归和无左公共因子的BNF，改变后文法如下（没有浮点数处理功能）：.PROGRAM ;CONST ;|标识符=无符号整数, |VAR |标识符:;, 标识符 | |INTEGER|LONG; |PROCEDURE 标识符;(标识符:) |; |标识符:=|()|IF THEN WHILE DO READ (标识符)WRITE (), |BEGIN END; |ODD +|-|标识符|无符号整数|()+|-*|/=|=5 非终结符和函数名对照表：（34个非终结符） 非终结符函数名非终结符函数名programprogheadblockconsexplconsdefivarexplconssuffvardefivarsuffprocdefitypilprocedhprocsuffassiprosentencesuffixifsentreadwhilsentidsuffwritecompsentexprsuffsentsuffconditiotermsuffexpresstermfactsuffargumentfactoraAddopermuloperrespoper6 递归子程序的设计思想：为每一个非终结符设计一个识别的子程序，寻找该非终结符也就是调用相应的子程序。由于单词在语法分析中作为一个整体，故在语法识别中仅使用其内码。这里将词法分析作为一个语法分析的子程序，当语法分析需要单词时，就调用相应的词法分析程序获得一个单词。语法分析的作用是识别输入符号串是否为文法上定义的句子，即判断输入符号串是否满足程序定义的要求。当一个非终结符对应有两个或者两个以上产生式时，可根据当前单词决定采用哪一个产生式进行右部分析。7 调试时可以使用下面的源程序作为语法分析程序的输入（当然，你也可以编写一个源程序）。 PROGRAM MYPASCAL; CONST UNIT=100;VAR x,y:INTEGER;PROCEDURE subproc(i:INTEGER); BEGIN x:=i; END;BEGIN subproc(20); x:=x+UNIT; y:=20; WHILE xy DO BEGIN IF y+20=y*(x-1)+20 THEN x:=20+(x+y)/3; READ(x,y); WRITE(x*y+1); ENDEND.8下面是一个递归子程序语法分析程序，程序的执行需要提供一个参数：源程序文件名。#include #include #include #include #define PROGRAM 1 /从这里开始宏定义终结符内码，为的是增加程序的易读性#define CONST 2#define VAR 3 #define INTEGER 4#define LONG 5#define PROCEDURE 6#define IF 7#define THEN 8#define WHILE 9#define DO 10#define READ 11#define WRITE 12#define BEGIN 13#define END 14#define ODD 15#define ADD 16#define SUB 17#define MUL 18#define DIV 19#define EQU 20#define NEQ 21#define LES 22#define LEQ 23#define LAG 24#define GEQ 25#define DOT 26#define COM 27#define SEM 28#define COL 29#define ASS 30#define LBR 31#define RBR 32#define INT 33#define ID 34 /标识符内码#define EIN 35#define lenth1 15 /保留字表长度#define lenth2 17 /运算符界符长度struct char name21;int type;int addr;indent 1000; /符号表struct stchar name21;int code;sym; /当前单词int lenth=0;FILE* f1;int line=0,row=0,val;void getsym();char getchr();void error(int);void program();void proghead();void block();void consexpl();void consdefi();void varexpl();void conssuff();void vardefi();void varsuff();void procdefi();void typeil();void procedh();void procsuff();void assipro();void sentence();void suffix();void ifsent();void read();void whilsent();void idsuff();void write();void compsent();void exprsuff();void sentsuff();void condition();void termsuff();void express();void term();void factsuff();void factor();void addoper();void muloper();void respoper();void argument();char ch= ; /当前字符int lenth3=0; /符号表中实际标识符个数void main(int argc,char* argv) if (f1=fopen(argv1,r)=NULL) /打开源程序文件 printf(cannot open filen); exit(0); getsym(); /获取第一个单词 program(); /程序的语法分析 printf(the program is rightn);/源程序正确 fclose(f1);void program() /非终结符的分析程序：-. proghead(); /非终结符的分析程序 block(); /非终结符的分析程序 if (sym.code=DOT) /DOT为.的内码表示，见文件首的宏定义。如果当前单词是. getsym(); /读取下一个单词到sym else error(2);void proghead() /非终结符的分析程序：-PROGRAM 标识符；if(sym.code=PROGRAM) getsym(); if (sym.code=ID) getsym(); if (sym.code=SEM) getsym(); else error(5); else error(4); elseerror(3);void block() /非终结符的分析程序 consexpl(); varexpl(); procdefi(); compsent();void consexpl() /非终结符CONST ;|if (sym.code=CONST) /如果当前单词不是CONST,则是分支，什么事情都不做。 / CONST ; getsym(); consdefi(); conssuff(); if (sym.code=SEM) getsym(); else error(6);void consdefi() /非终结符if (sym.code=ID) getsym(); if (sym.code=EQU) getsym();if (sym.code=INT)getsym();elseerror(9); else error(8); elseerror(7);void conssuff() /非终结符，| if (sym.code=COM) getsym(); consdefi(); conssuff();/* if (sym.code=SEM) getsym(); else error(10); */void varexpl() /变量说明部分 if (sym.code=VAR) getsym();vardefi();varsuff(); void vardefi() /非终结符if (sym.code=ID) getsym(); idsuff(); if (sym.code=COL) getsym(); typeil(); if (sym.code=SEM) getsym(); else error(12); else error(11);void varsuff() /非终结符if (sym.code=ID) vardefi(); varsuff();void typeil() /非终结符if (sym.code=INTEGER|sym.code=LONG) getsym();else error(13);void procdefi() /非终结符if (sym.code=PROCEDURE) procedh(); block(); if (sym.code=SEM) getsym(); procsuff(); else error(14);void procedh() /非终结符if (sym.code=PROCEDURE) getsym(); if (sym.code=ID) getsym(); argument(); if (sym.code=SEM) getsym(); else error(16); else error(15);void argument() /非终结符if (sym.code=LBR) getsym(); if (sym.code=ID) getsym(); if (sym.code=COL) getsym(); typeil(); if(sym.code=RBR) getsym(); else error(19); else error(18); else error(17);void procsuff() /非终结符if (sym.code=PROCEDURE) procedh(); block(); if (sym.code=SEM) getsym(); procsuff(); else error(20);void assipro() /赋值或调用语句 if (sym.code=ID) getsym();suffix(); else error(21);void sentence() /语句 if (sym.code=ID)assipro(); else if (sym.code=IF)ifsent(); else if (sym.code=WHILE)whilsent();else if (sym.code=READ)read();else if (sym.code=WRITE)write();else if (sym.code=BEGIN)compsent();void suffix() /非终结符if (sym.code=ASS) getsym(); express();elseif (sym.code=LBR) getsym(); express(); if (sym.code=RBR) getsym(); else error(22);void ifsent() /非终结符if (sym.code=IF) getsym(); condition(); if (sym.code=THEN) getsym(); sentence(); else error(24);elseerror(23);void whilsent() /while语句 if (sym.code=WHILE) getsym();conditio();if (sym.code=DO) getsym(); sentence();else error(26); else error(25);void read() /非终结符if (sym.code=READ) getsym(); if (sym.code=LBR) getsym(); if (sym.code=ID) getsym(); idsuff(); if (sym.code=RBR) getsym(); else error(27); else error(30); else error(29); elseerror(28);void idsuff() /非终结符if (sym.code=COM) getsym(); if (sym.code=ID) getsym(); idsuff(); else error(31);void write() /写语句 if (sym.code=WRITE) getsym();if (sym.code()=LBR) getsym(); express(); exprsuff(); if (sym.code=RBR) getsym() else error(34);else error(33); else error(32); void compsent() /非终结符if (sym.code=BEGIN) getsym(