编译原理实验教案

黄冈师范学院计算机系《编译原理》实验教案（2009·秋）授课对象：计科200701~03授课教师：张瑞红授课时间：2009~2010学年度第一学期实验一、词法分析一、授课内容：（一）授课科目：编译原理（二）授课内容：实验一词法分析（三）授课类型：实验（四）授课时间：8学时（五）主讲教师：张瑞红二、教学目的要求：1.目的：通过设计、编制、调试一个具体的词法分析程序加深对词法分析原理的理解，并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。2.要求：（1）选择在国际国内有代表性的高级程序设计语言的源程序作为词法分析对象。（2）根据数学要求和学生具体情况，从上列语言之一中选取一个适当大小的子集，可以选取一类典型单词，也可以尽可能使各种类型的单词都能兼顾到。（3）时间为6小时。时间分为三次：第一讲、介绍词法分析器的设计原理，以PASCAL子集为例；第二讲、根据学生时间上机情况，辅导学生设计；第三讲、先辅导，再进行上机操作检查。三、教学设想：1．教学方法设想：先以例子讲解，然后学生动手实验，实验为主。2．教具运用设想：多媒体。四、教学过程：1．题目试用直接分析方法编制PASCAL语言子集的词法分析程序。其BNF定义如下：〈PASCAL子集程序〉：：=〈变量说明〉BEGIN〈语句表〉ENG。〈变量说明〉：：=〈空〉|VAR〈变量表〉：〈类型〉〈变量表〉：：=〈变量〉|〈变量表〉，〈变量〉〈类型〉：：=〈标识符〉〈语句表〉：：=〈语句〉|〈语句表〉〈语句〉〈语句〉：：=〈赋值语句〉|〈条件语句〉|〈WHILE语句〉|〈复合语句〉|〈过程定义〉〈赋值语句〉：：=〈变量〉：：=〈算术表达式〉〈条件语句〉：：=〈IF〉〈布尔表达式〉THEN〈语句〉ELSE〈语句〉〈WHILE语句〉：：=WHILE〈布尔表达式〉DO〈语句〉〈复合语句〉：：=BEGIN〈语句表〉END〈过程定义〉：：=PROCEDURE〈标识符〉〈参数表〉BEGIN〈语句表〉END〈参数表〉：：=〈空〉|（〈标识符表〉）〈标识符表〉：：=〈标识符〉|〈标识符表〉，〈标识符〉〈算术表达式〉：：=〈项〉|〈算术表达式〉+〈项〉〈项〉：：=〈初等量〉|〈项〉*〈初等量〉〈初等量〉：：=〈无符号数〉|〈变量〉|（〈算术表达式〉）〈布尔表达式〉：：=〈算术表达式〉〈关系符〉〈算术表达式〉〈变量〉：：=〈标识符〉〈标识符〉：：=〈字母〉|〈标识符〉〈字母〉|〈标识符〉〈数字〉〈无符号数〉：：=〈数字〉|〈无符号数〉〈数字〉〈关系符〉：：=〈=|〈〉|〉〈字母〉：：=A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z〈数字〉：：=0|1|2|3|4|5|6|7|8|9〈空〉：：=词法分析是编译程序的第一个处理阶段。这里所谓直接分析方法，即自左至右扫描源程序，一旦发现有独立意义的字符串时，立即将其改造成长度统一的最小语法单位，同时查填各类单词表格并做一些语法检查，为以后的语法分析提供方便。具体的处理过程是，在扫描字符串时，一旦识别出关键字（K）、标识符（I）、常数（C）和界符（P）中之一，即以单词形式（剔去多余的空白符）输出。每次调用词法分析程序，它均能自动继续扫描下去，形成下一个单词，直至整个源程序全部扫描完毕，习惯年成相应的单词串。各类单词均有相同的结构和长度。每个单词由两部分组成：（t,i）其中t表示单词种类。共分四类，即K类、I类、C类和P类。每类对应一种表格，分别存放该类各个不同的单词。i为指向该类表格一个特定项目的指针。因此，（t,i）唯一地确定了一个单词。K，P两种表格的内容取决于所选语言的子集，而I，C两种表格则是根据临时输入的源程序字符串形成的。2．算法词法分析程序在扫描过程中，依次从源程序驱除源字符，并根据第一个字符（有时还需多读一个字符）判断属于K，I，C，P中的哪一类单词，确定单词的t和i。在词法分析过程中，K、P两表是固定不变的（由语言来确定），源程序字符串只能从其中选取。I、C两表是在分析过程中不断形成的。其词法分析的算法如图2-7-2所示。为了防止实习良过大，达不到实习的目的，实习时采用的数据结构在不同程度上均应作适当的简化，所选的关键字（K）和界符表（P）如表2-7-1和表2-7-2所示。表2-7-1K表表2-7-2P表BEGINDOELSEENDIFPROCEDURETHENVARWHILETo关键字表包括九个代表性的关键字。界符表包括关系运算符三种（其中小于等于和不等于均系由两个字符组成的符合字符），算术运算符和分隔符各两种，圆括号一对，加上赋值号共十一种。这两个表的内容表明，PASCAL语言的赋值语句、条件语句、WHILE型循环语句、复合语句过程及变量说明均可作为源程序例子输入给词法分析程序。标识符表中的每一项包含一个标识符。常数表中的每一项包含一个整常数。后两表都是在词法分析过程中产生的。3．程序及运行结果下面用PASCAL语言编出符合以上几项要求的一个具体的词法分析程序为：PROGRAMplexical(INPUT,OUTPUT);〈=〈〉〈（*：=：+）；，LABEL1;CONSTkeylen=10;identlen=10;TYPEtstring=ARRAY[1..identlen]OFCHAR;outreco=RECORDty:CHAR;point:INTEGER;END;{outreco}VARcip,ip,pint,i,j,l,m:INTEGER;CHAR1:CHAR;ci:ARRAY[1..10]OFINTEGER;k,id:ARRAY[1..keylen]OFtstring;token:tstring;outtoken:outreco;instring:ARRAY[1..10]OFCHAR;p:ARRAY[1..11]OFARRAY[1..2]OFCHAR;PROCEDURElexical;varl,m,num:INTEGER;b:BOOLEAN;PROCEDUREgetCHAR;BEGINCHAR1:=instring[pint];pint:=pint+1;END;{getCHAR}PROCEDUREerror;BEGINwriteln('error');pint:=pint+1END;{error}BEGINFORl:=1TOidentlenDOtoken[l]:='';getCHAR;whileCHAR1=''DOgetCHAR;IFCHAR1IN['a'..'z']THENBEGINm:=1;while(CHAR1IN['a'..'z'])OR(CHAR1IN['0'..'9'])DOBEGINIFm=identlenTHENBEGINtoken[m]:=CHAR1;m:=m+1;END;getCHAR;END;{while}pint:=pint-1;l:=1;b:=FALSE;while(l=keylen)AND(notb)DOBEGINb:=TRUE;i:=1;while(i=identlen)ANDbDOIFk[l][i]=token[i]THENi:=i+1ELSEb:=FALSE;IFnotbTHENl:=l+1END;IFl=keylenTHENBEGINouttoken.ty:='k';outtoken.point:=l;ENDELSEBEGINl:=1;b:=FALSE;while(l=ip)AND(notb)DOBEGINb:=TRUE;i:=1;while(i=identlen)ANDbDOIFid[l][i]=token[i]THENi:=i+1ELSEb:=FALSE;IFnotbTHENl:=l+1;END;IFlipTHENBEGINip:=ip+1;FORm:=1TOidentlenDOid[ip][m]:=TOken[m];END;outtoken.ty:='i';outtoken.point:=l;ENDENDELSEIFCHAR1IN['0'..'9']THENBEGINnum:=0;whileCHAR1IN['0'..'9']DOBEGINnum:=num*10+ORd(CHAR1)-ORd('0');getCHAREND;pint:=pint-1;l:=0;REPEATl:=l+1until(l=cip)OR(num=ci[l]);IFl=cipTHENBEGINci[cip]:=num;cip:=cip+1;END;outtoken.ty:='c';outtoken.point:=lEND{INTEGER}ELSEIFCHAR1IN['','(','*',':','+',')',';',',']THENBEGINouttoken.ty:='p';CASECHAR1OF'':BEGINgetCHAR;IF(CHAR1'=')AND(CHAR1'')THENBEGINouttoken.point:=3;pint:=pint-1ENDELSECASECHAR1OF'=':outtoken.point:=1;'':outtoken.point:=2END;END;'(':outtoken.point:=4;'*':outtoken.point:=5;':':BEGINgetCHAR;IFCHAR1='='THENouttoken.point:=6ELSEBEGINouttoken.point:=7;pint:=pint-1ENDEND;'+':outtoken.point:=8;')':outtoken.point:=9;';':outtoken.point:=10;',':outtoken.point:=11END{CASE}ENDELSEerrorEND;{lexical}BEGINwriteln('K-TABLE,INPUT!');FORl:=1TOkeylenDOFORm:=1TOidentlenDOREAD(k[l][m]);READLN;FORl:=1TOidentlenDOFORm:=1TOidentlenDOid[l][m]:='';writeln('P-TABLE,INPUT!');FORl:=1TO11DOFORm:=1TO2DOREAD(p[l][m]);READLN;ip:=0;cip:=1;1:pint:=1;writeln('source,input!');FORj:=1TOidentlenDOREAD(instring[j]);lexical;writeln(outtoken.ty);writeln(outtoken.point);FORl:=1TOidentlenDOwrite(token[l]);writeln;GOTO1;END.词法分析的过程名为lexical，它根据输入字符串第一个字符来划分单词类型。若第一个字符为字母，则属关键字类或标识符类（凡K表中查不到的为后者）；若第一个字符为数字，则为整数类；否则，为界符类或本例无定义字符。Lexical过程中嵌入两个小过程，一个名为gethar，其功能是从输入字符串instring[pint]中取出一个字符，同时指针pint加1，为下一个取字符作好准备。另一个过程名为error，负责出错处理。这里知识简单输出字符串error，通知外界作进一步的处理。实习时，可略加扩充，如指出出错的位置、原因和性质等。注意，主程序是以调试程序的形式给出的，它主要完成：（1）准备工作。给K表和P表置初值；（2）读入PASCAL源程序字符串，如合法的关键字、标识符、整常数和界符等；（3）调用词法分析程序，对输入字符串进行词法分析；（4）输出词法分析的结果，即单词的t和i，以及单词本身。其它表格的输出略去了。运行结果示例如下（输入时注意每个单词10个字符，在输入P表时每个字要占两个位置）：K-TABLE,INPUT!begindoelseendifprocedurethenvarwhileP-TABLE,INPUT!=