黄冈师范学院计算机系
《编译原理》实验教案
（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-1 K表 表2-7-2 P表
BEGIN DO ELSE END IF PROCEDURE THEN VAR WHILE To
〈 〈 〈 （ * ： ： + ） ； ， = 〉 = 关键字表包括九个代表性的关键字。界符表包括关系运算符三种（其中小于等于和不等于均系由两个字符组成的符合字符），算术运算符和分隔符各两种，圆括号一对，加上赋值号共十一种。这两个表的内容表明，PASCAL语言的赋值语句、条件语句、WHILE型循环语句、复合语句过程及变量说明均可作为源程序例子输入给词法分析程序。标识符表中的每一项包含一个标识符。常数表中的每一项包含一个整常数。后两表都是在词法分析过程中产生的。
3．程序及运行结果 下面用PASCAL语言编出符合以上几项要求的一个具体的词法分析程序为： PROGRAM plexical (INPUT,OUTPUT);
LABEL 1; CONST
keylen=10; identlen=10; TYPE
tstring=ARRAY[1..identlen] OF CHAR; outreco=RECORD ty:CHAR;
point:INTEGER; END;{outreco} VAR
cip,ip,pint,i,j,l,m:INTEGER; CHAR1:CHAR;
ci:ARRAY[1..10] OF INTEGER; k,id:ARRAY[1..keylen] OF tstring; token:tstring; outtoken:outreco;
instring:ARRAY[1..10] OF CHAR;
p:ARRAY[1..11] OF ARRAY[1..2] OF CHAR; PROCEDURE lexical; var
l,m,num:INTEGER; b:BOOLEAN;
PROCEDURE getCHAR; BEGIN
CHAR1:=instring[pint]; pint:=pint+1; END;{getCHAR} PROCEDURE error; BEGIN
writeln ('error'); pint:=pint+1 END;{error} BEGIN
FOR l:=1 TO identlen DO token[l]:=' '; getCHAR;
while CHAR1=' ' DO getCHAR;
IF CHAR1 IN ['a'..'z'] THEN BEGIN m:=1;
while (CHAR1 IN ['a'..'z']) OR (CHAR1 IN ['0'..'9']) DO BEGIN
IF m<=identlen THEN BEGIN
token[m]:=CHAR1; m:=m+1; END; getCHAR; END;{while} pint:=pint-1; l:=1;
b:=FALSE;
while (l<=keylen) AND (not b) DO BEGIN
b:=TRUE; i:=1;
while (i<=identlen) AND b DO IF k[l][i]=token[i] THEN i:=i+1 ELSE b:=FALSE; IF not b THEN l:=l+1 END;
IF l<=keylen THEN BEGIN
outtoken.ty:='k'; outtoken.point:=l; END ELSE BEGIN l:=1;
b:=FALSE;
while (l<=ip) AND (not b) DO BEGIN b:=TRUE; i:=1;
while (i<=identlen) AND b DO IF id[l][i]=token[i] THEN i:=i+1 ELSE b:=FALSE; IF not b THEN l:=l+1; END; IF l>ip THEN BEGIN ip:=ip+1;
FOR m:=1 TO identlen DO id[ip][m]:=TOken[m]; END;
outtoken.ty:='i'; outtoken.point:=l;
编译原理实验教案
