“编译原理”课程实验教学研究与探索

吴海涛

摘要:为促进学生更好地掌握“编译原理”课程内容,激发学生学习兴趣,并通过实践对编译程序的功能有清晰的理解,使教学既要面向多数学生,又要涵盖更多内容,本文提出一种“编译原理”课程实验教学方案,通过让学生实现一个非负整数四则运算的多遍编译程序,说明该方案在具体实施后的教学效果以及在实施过程中应注意的问题。

关键词:编译原理;实验教学;课堂教学

中图分类号:G642 文献标识码:B

“编译原理”课程是高校计算机专业的一门重要专业基础课程,在专业课程体系中处于一个极其重要的地位。但是,“编译原理”课程综合性比较强,涉及的先修课程比较多,包括离散数学、程序设计、数据结构、汇编语言等,对学生专业知识掌握情况要求比较高,是一门公认比较难学、比较难教的课程。因此,如何使学生学好这门课是任课教师要用心解决的问题。

计算机学科是一门对实践性要求比较高的学科,很多东西不能认为听懂看懂就是理解、掌握,需要编程去实现才能说是真正理解、掌握。因此,在考虑如何使学生学好“编译原理”课程时,就考虑着如何把理论和实践结合起来,促进学生对课程的学习。国内不少学者对“编译原理”实践教学以及如何把理论与实践结合起来提出了自己的观点、思路,并通过教学实践进行探索。国外教材也有不少范例可供参考。Alfred V. Aho等人编著的《编译原理》先给出一个小的编译程序范例,给读者一个对编译程序的直观感受,然后再逐步展开来讲解编译的各项原理和技术。Andrew W. Appel等人编著的《现代编译原理》将MiniJava语言的实现贯穿于整本书之中。Kenneth C. Louden编著的《编译原理与实践》把Tiny语言编译程序作为范例,在讲解每章内容后,再讲解Tiny语言编译程序中的相关部分的实现方法。

但是,在具体实施教学时,由于授课对象不同,希望达到的教学目标和效果不同,因此在设计实验教学方案时,就有不同的考虑。为了促进学生更好地掌握课程内容,激发学生的学习兴趣,并通过实践对编译程序的功能有清晰的理解,既要面向多数学生,又要涵盖更多的教学内容,经过考虑,决定让学生实现一个非负整数四则运算的的多遍编译程序。这样的编译程序虽小,但五脏俱全。

四则运算是“编译原理”课程的经典范例,采用多遍编译的好处是整个编译程序的逻辑结构比较清晰,实验内容安排起来比较方便。在设计具体实验内容时,把课堂教学内容和实验内容紧密结合起来,这样一来,课堂教学内容的讲解可以为实验作准备,而实现实验内容可以进一步加深学生对课堂教学内容的理解。由于实验教学课时有限,为了在有限的时间内达到好的教学效果,尽可能地发挥实验教学的效能,在设计具体实验内容时,把每个实验要求学生做什么、具体完成什么功能、如何去做、需要用到什么数据结构、各个模块间如何衔接都作出了详细说明。文献[8]包含实验所需的各项技术。

下面首先介绍实验教学方案,然后说明实验教学效果以及应注意的问题,最后是结束语。

1实验教学方案

实验总体任务是,经过词法分析、语法分析、语义分析与中间代码生成、目标代码生成四个阶段,将给定的非负整数四则运算表达式翻译为汇编语言代码。每个阶段设置一个实验,共四个实验。当第四个实验完成时,应该得到一个符合实验总体任务的编译程序。

1.1语法和词法

语法分析部分采用递归子程序法。为使学生在编程时命名方便,非负整数四则运算表达式的文法采用如下形式:

::= + | -

|

::= * | /

|

::= () | num

消除左递归后的文法如下:

::=

::= +

| - |ε

::=

::= *

| / | ε

::= () | num

在如上文法中,、、、和为非终结符,+、-、*、/、(、)、num为终结符。

词法规则说明如下:

运算符有+、-、*、/;

界符有(、);

非负整数有num。

空白包括空格、换行符和水平制表符,用来分开运算符、界符和非负整数。空白也可以不包括换行符,这时换行符可以作为表达式的终结标志。

1.2词法分析

需要实现的词法分析程序的功能是,接受一个表达式,输出该表达式中的各类单词符号。测试词法分析程序时,可以按照一定格式输出各类单词符号。

单词符号的种类和所属类型可定义如下:

typedef enum Symbol { ERR = -1, END, NUM,

PLUS, MINUS, TIMES, SLASH,

LPAREN, RPAREN } Symbol;

在实现词法分析程序时,对运算符和界符只需处理种类编码,而对非负整数需要处理其对应的具体属性信息。ERR表示词法分析错,END表示表达式分析结束。例如,测试词法分析程序时,1+2*(3+4)所对应的单词符号序列的一种输出形式如下:

NUM: 1

+

NUM: 2

*

(

NUM: 3

+

NUM: 4

)

词法分析函数的原型如下:

Symbol gettoken();

实现的具体方法可参考文献[8]中的44-46页。另外,可以根据学生的具体情况,把一些要求进一步明确。

1.3语法分析

需要实现的语法分析程序的功能是,接受一个表达式,分析该表达式,并根据输入正确与否输出相应信息。测试时,如果输入的表达式分析正确,则输出表示分析正确的信息;否则,输出表示分析错误的信息。这里对出错处理不做太高要求,能达到在遇到错误时,输出错误提示,然后程序立即终止执行就可以了。当然,如果学生能力比较强,可以考虑更加细致的出错处理。

语法分析程序由一组递归过程组成,文法中每个非终结符对应一个过程。在分析过程中,语法分析程序需要调用词法分析实验中所实现的词法分析程序,这是个关键。

实现的具体方法可参考文献[8]中的74-76页。

1.4语义分析

需要实现的语义分析程序的功能是,接受一个表达式,分析该表达式,并在分析的过程中建立该表达式的抽象语法树,然后输出表达式所对应的四元式序列。严格来说,非负整数四则运算表达式的抽象语法树是一棵树,但不严格的说也可以看作是一棵二叉树,而看作二叉树时所得到的中序遍历序列应该和输入的表达式一样——除了没有括号之外。因此,可提示学生,通过输出中序遍历序列检测程序功能是否正确。如果每个分支节点用一个临时变量标记,则对四则运算表达式的抽象语法树进行后序遍历,可以得到输入表达式所对应的四元式序列。例如输入1+2*(3+4),对应的抽象语法树的中序遍历序列、四元式序列分别为:

1+2*3+4

和

+ 3 4 T1

* 2 T1T2

+ 1 T2T3

抽象语法树类型的一种定义为:

typedef int ValType;

typedef struct ASTNode {

Symbol sym;

ValType val;

struct ASTNode * arg1, *arg2;

} ASTNode, *AST;

创建节点的操作有两个,对应的函数头部和功能分别如下:

(1)ASTNode *mknode(Symbol op, ASTNode *arg1, ASTNode *arg2):返回新创建的一个运算节点,结点的sym域为op,表示运算,域arg1和arg2分别指向一棵子树。

(2)ASTNode *mkleaf(Symbol num, ValType val):返回新创建的一个数节点,结点的sym域为num,表示数,域val用于存放数的值。

建立抽象语法树的语义规则为:

E ::= E1 + T E.nptr := mknode( ‘+, E1.nptr, T.nptr )

E ::= E1 – T E.nptr := mknode( ‘-, E1.nptr, T.nptr )

E ::= T E.nptr := T.nptr

T ::= T1 * F T.nptr := mknode( ‘*, T1.nptr, F.nptr )

T ::= T1 / F T.nptr := mknode( ‘/, T1.nptr, F.nptr )

T ::= F T.nptr := F.nptr

F ::= (E) F.nptr := E.nptr

F ::= num F.nptr := mkleaf(num, num.val )

消除左递归的翻译模式为:

E ::= T {E'.i:=T.nptr} E' {E.nptr:=E'.s}

E'::= + T {E'1.i:=mknode(‘+,E'.i,T.nptr)}

E'1 {E'.s:=E1.s}

E'::= - T {E'1.i:=mknode(‘-,E'.i,T.nptr)}

E'1 {E'.s:=E1.s}

E'::= ε {E'.s:= E'.i}

T ::= F {T'.i:=F.nptr} T' {T.nptr:=T'.s}

T'::= * F {T'1.i:=mknode(‘*,T'.i,F.nptr)}

T'1 {T'.s:=T1.s}

T'::= / F {T'1.i:=mknode(‘/,T'.i,F.nptr)}

T'1 {T'.s:=T1.s}

T' ::= ε {T'.s:= T'.i}

F ::= (E) {F.nptr:=E.nptr}

F ::= num {F.nptr:=mkleaf(num,num.val)}

语义分析部分的核心是递归下降翻译器的设计,可参考文献[8]中的156-158页。具体实现时,可以以语法分析实验中所实现的语法分析程序为基础进行修改,实现表达式的递归下降翻译器。

1.5代码生成

需要实现的代码生成程序的功能是,以语义分析实验中所实现的语义分析程序的四元式输出作为输入,输出汇编语言程序。例如1+2*(3+4)对应的输出为:

.386

.MODEL FLAT

ExitProcess PROTO NEAR32 stdcall,

dwExitCode:DWORD

INCLUDE io.h ; header file for input/output

cr EQU 0dh ; carriage return character

Lf EQU 0ah ; line feed

.STACK 4096 ; reserve 4096-byte stack

.DATA ; reserve storage for data

t DWORD 40 DUP (?)

label1 BYTE cr, Lf, "The result is "

result BYTE 11 DUP (?)

BYTE cr, Lf, 0

.CODE ; start of main program code

_start:

mov eax, 3

add eax, 4

mov t+0, eax

mov eax, 2

mov ebx, t+0

mul ebx

mov t+4, eax

mov eax, 1

add eax, t+4

mov t+8, eax

mov eax, t+8

dtoa result, eax ; convert to ASCII characters

outputlabel1 ; output label and sum

INVOKE ExitProcess,0 ; exit with

; return code 0

PUBLIC _start ; make entry point public

END ; end of source code

输出的汇编代码借鉴了文献[9]中的格式,并使用了文献[9]所提供的输入输出例程。

在所生成的汇编代码中,tDWORD40 DUP (?)定义了40个双字(每个双字占4字节大小),用作临时变量,可根据需要调整大小,当然更好的方法是在栈中分配临时变量。

生成代码时,学生只需考虑如何生成_start:和dtoaresult, eax之间的汇编码。开头到_start:部分和dtoaresult, eax到结尾部分的汇编码可以按所给的例子原样输出。

翻译时,采用将四元式直译为汇编码的方法。在学生实现四元式到汇编码的翻译时,提示学生通过分析、对比1+2*(3+4)的四元式序列和汇编码的对应关系,考虑如何将四元式翻译为汇编码。需要特别注意寻址方式、乘法和除法的翻译问题。

所给汇编程序例子中各个成分的含义,可让学生参考文献[9]。

一般来说,讲汇编语言时,通常讲的是16位实模式汇编,16位实模式汇编程序在Windows命令提示符下运行有些小问题,文献[9]中给出的32位汇编程序没有那些问题,所以在此采用。

2实验教学效果及问题

2.1实验教学效果

本实验教学方案是在本系2008～2009学年下学期开设的编译原理课程的教学中开展实施的(使用文献[8]做教材),学生的积极性很高,不少学生开动脑筋,发挥自己的聪明才智努力完成各个实验。相对而言,词法分析和语法分析两个实验完成较好,程序有一二十种写法,但是语义分析和代码生成两个实验就遇到了不少问题。最终能够独立完成全部实验的有五、六位同学,其中有位学生在刚过一般实验学时时就已经完成全部实验。从学生完成实验情况来看,学生的个体能力差异有些偏大。

期末考试卷面成绩也在一定程度上体现出实验教学的效果。表1是本人所教过的各个年级“编译原理”课程卷面成绩的基本情况,从中可以看出,实验教学新方案的实施对学生成绩的提高有明显作用。这说明,虽然学生在完成实验过程中遇到了不少困难,但学生还是认真地考虑了如何完成实验,因此强化了学生对相关内容的掌握。

2.2 问题

(1) 虽然在实验指导书中已经详细地给出了实验指导,但是有些同学对一些内容还是产生了误解。例如在词法分析部分说到测试词法分析程序时,可以按照一定格式输出各类单词符号,但有些学生把这个要求理解成词法分析程序本身的功能了。尽管这些学生能够完成词法分析,却在完成语法分析部分时遇到了麻烦,不知道如何把词法分析和语法分析衔接起来。

(2) 有些学生虽然能够理解各个原理,明白各项技术,并且作业完成得也比较好,但是,在做实验时,却不能熟练编程实现所要求的功能,这反映了理论与实践脱节的问题。另外,有些学生对各个原理理解不清,对各项技术把握不好,妨碍了实验的完成。

(3) 不少学生缺乏实现具有一定规模程序的能力。按自己实际完成的符合实验总体任务的编译程序估算,学生完成的最终编译程序大致应该有500行左右的代码量,这个编程量应该基本合适,但现实情况却有些不太理想。

(4) 学生运用数据结构和算法解决问题的能力方面还有所欠缺。事实上,整个实验的难点应该在语义分析上,那里涉及数据结构和算法比较多,学生容易出现问题。语义分析部分完成得不好也影响到代码生成部分的完成。

(5) 一些学生一看到实验题目,不是想如何自己去完成,而是马上上网去找答案。在网上通常比较容易找到词法分析、语法分析程序做参考,但比较难找到符合或接近实验要求的语义分析、代码生成程序。因此,学生在完成词法分析、语法分析部分时也许还能应付,但是在完成语义分析、代码生成部分时就不知道如何做了,结果最后实验不能取得好的效果。

3结语

这次实验教学探索基本达到了预期目的,虽然在实施过程中遇到了一些问题,但为以后能够达到更好的教学效果积累了经验。笔者对实验方案做进一步改进、完善,以期更好地发挥实验教学效果,提高“编译原理”课程教学质量。

参考文献:

[1] 蒋宗礼.“编译原理”教学设计[J]. 计算机教育,2008(3):26-30.

[2] 李冬梅,施海虎.“编译原理”课程的教学研究与探索[J]. 计算机教育,2008(8):103-104.

[3] 温敬和.“编译原理”课程教学研究和教材编写[J]. 计算机教育,2006(5):77-79.

[4] 胡学联. 编译原理课程的调态与转型[J]. 计算机教育,2006(11):38-41.

[5] Alfred V.Aho, Ravi Sethi, Jeffrey D.Ullman. 编译原理 技术与工具(英文版)[M]. 北京:人民邮电出版社,2002.

[6] Andrew W.Appel, Jens Palsberg. 现代编译程序实现——Java语言(影印版)[M]. 2版. 北京:高等教育出版社,2003.

[7] Kenneth C.Louden. 编译原理与实践(英文影印版)[M]. 北京:机械工业出版社,2002.

[8] 陈火旺,刘春林,谭庆平,等. 程序设计语言编译原理 [M]. 3版. 北京:国防工业出版社,2000.

[9] Richard C. Detmer. 80x86汇编语言与计算机体系结构(英文版)[M]. 北京:机械工业出版社,2004.