《编译原理》的教学与实际相结合的再探讨

陈意云张昱(中国科学技术大学计算机科学技术系,安徽合肥230026)摘要:本文介绍我们在《编译原理》课程中联系编程语言实际和改进课程设计的经验或尝试.
在联系编程语言方面,主要是引导学生用编译的原理和技术来分析典型程序在编译(包括连接)和运行时被发现的错误,分析典型程序的目标代码和运行时的输出;在课程设计方面,主要是让学生合作完成一个简单的编译器,并采用教师主导、同学参与、公开评比的评分方式.
通过这两方面的努力,激发了学生的学习兴趣,帮助他们牢固地掌握了理论和技术,还提高了他们的软件工程意识、质量意识和团队意识.

关键词:编译原理;程序设计语言;课程实践;教学经验1引言编程语言的编译原理是计算机专业一门非常有用的核心课程,又是一门需要较大投入的课程.
怎样激发学生的学习热情,努力学好本课程我们的策略主要有如下三点:1、首先是引导学生注重对编译原理和技术的宏观理解和全局把握,不把学生的注意力分散到一些枝节的算法上.

2、其次,在课堂上和习题中准备了许多从实际程序的编译和运行时碰到的问题中抽象出来的例子,鼓励学生用所学的知识去分析、解决、理解实际编程中遇到的问题和发生的现象,激发学生学习编译原理和技术的积极性.

在"《编译原理》的教学与实际相结合的探讨"[1]一文中我们已经做过一些这方面的探讨,本文进一步介绍我们的经验,以供国内同行参考与切磋.

3、最后,恢复了要求学生完成一个简单编译器的课程设计.
通过正反两方面的经验,我们认为一定规模的课程设计是使学生牢固掌握本课程的理论和技术,融会贯通书本知识的重要手段.

我们调研了国外一些知名大学的编译原理课程设计,以加州大学伯克利分校的编译课程设计[2]为基础,改编出适用于我们学生的课程设计.
针对学生中存在的轻视和拷贝课程设计的不良现象,我们加强课程设计的管理,并采用教师主导、同学参与、公开评比的评分方式,调动学生自己完成课程设计的热情,降低抄袭现象.

本文介绍我们在加强课程设计的过程管理和改进考评方式上的经验和体会.
该课程设计的完整介绍已另外行文"编译原理课程实践改革探索",可见网页http://staff.
ustc.
edu.
cn/~yuzhang/compiler/.

2教学联系编程语言实际的探讨基于下面几点考虑,我们选择C语言作为实例语言.
1、程序设计的教学大都采用C语言,C语言是本科生最熟悉的编程语言.
2、C语言编译器一般都以汇编语言作为目标语言,这便于分析源程序所对应的目标代码.

3、C不是类型安全的语言,C程序很容易出现难以捉摸的错误.
编译知识有助于分析这些错误.

4、通过编译原理课堂上和习题中展示和分析的例子,学生对C语言的掌握能达到一个新的高度.

下面介绍我们所采用的一些典型小程序,这些例子及更多的例子在我们编写的教材[3]、习题解答[4]和网页http://staff.
ustc.
edu.
cn/~yiyun/中可以找到.
所使用的编译器是X86/Linux上的GCC.

2.
1类型系统类型系统的设计是现代编程语言设计的核心,掌握语言的类型系统也是学好编程语言的重要一环.
但是国内编译原理大部分教材对类型系统的介绍比较简单,难以让学生体会到它在编程语言中的重要性.
我们使用例1和例2这样的小程序,用类型系统的观点解释其中的问题,学生很快领会到了类型系统的重要作用.

例1编译图1的C语言程序时,GCC报告最后一行(程序列成左右两栏)有错误:incompatibletypesinreturnC语言的数组和结构体都是构造类型,为什么函数fun2有类型错误,而函数fun1没有typedefintA1[10]A2*fun1()typedefintA2[10]return(&a);}A1a;typedefstruct{inti;}S1;S2fun2()typedefstruct{inti;}S2;return(s);}S1s;图1结构等价与名字等价的例子结构等价和名字等价是许多教材都提到的概念,但学生认为它们离自己很遥远,无需关心和掌握.
C语言对除结构体类型以外的其它类型都使用结构等价,而对结构体类型使用名字等价,因此可用这样的例子来解释这两个概念的区别和重要性.

(1)文件1|(2)文件2typedefintA[10][20]typedefintA[10][20];Aa;Aa;A*fun(){return(a)A*fun(){return(&a);}编译该函数时,报告的类型错误如下:编译该函数时,没有类型方面的错误.

warning:returnfromincompatiblepointertype||(4)文件4(3)文件3|typedefintA[10][20];typedefintA[10][20]Aa;typedefintB[20]fun(){printf("%d,%d,%d\n",a,a+1,&a+1);}Aa;main(){fun();}B*fun(){return(a)该程序的运行结果是:编译该函数时,没有类型方面的错误.
134518112,134518192,134518912图2数组名a和&a的例子例2在C语言中,如果a是数组名,那么表达式a和&a的值都是数组a的首地址,但初学者很难掌握它们在使用上的区别,很多有关C语言的教材上也没有能把它们的区别讲透彻.
我们用图2中4个极简单例子,让学生分析编译时的出错信息和程序运行结果,由此总结出它们的区别.

通过分析,大家很快可以得出,对元素类型为t的数组a[i1][i2]来说,表达式a的类型是pointer(array(0.
.
i2–1,t)),而表达式&a的类型是pointer(array(0.
.
i1–1,array(0.
.
i2–1,t))).
2.
2局部和全局存储分配数据对齐(alignment)是由硬件特点所造成的对存储分配的一点约束,这个概念在教材上一带而过,学生不会留下深刻印象.
但是,它对编程时考虑节省空间和数据局部性,对构造编译器、对程序移植来说都是重要的,图3的例子用来让学生明白这个看似简单的概念的重要性.

例3在X86/Linux机器上,图3程序的运行结果是:Sizeofdouble,long,char=8,4,1Sizeofa,b=20,16而过去在SPARC/Solaris工作站上,该程序的运行结果是:Sizeofdouble,long,char=8,4,1Sizeofa,b=24,16为什么会有这样的区别typedefstruct_a{main()charc1;longi;charc2;doublef;}a;printf("Sizeofdouble,long,char=%d,%d,%d\n",typedefstruct_b{sizeof(double),sizeof(long),sizeof(char));charc1;charc2;longi;doublef;printf("Sizeofa,b=%d,%d\n",sizeof(a),sizeof(b));}b;图3数据对齐的例子该程序中结构体类型a和b的域名及类型都一样,仅次序不同,但是它们在同一机器上的存储分配字节数不一样,在不同机器上的情况也不一样.
这就让学生实实在在明白了这个概念的重要性.

main(){printf("%d,%d,%d\n");}图4活动记录中数据布局的例子例4图4的printf调用仅含格式控制字符串1个参数,程序运行时输出3个整数.
试从运行时存储空间的组织和printf的实现来分析,为什么该程序会有3个整数输出在讲活动记录中数据布局的特点时,我们用例4来提问学生.
很多学生认为编译器在编译该程序时会报错,也有学生认为该程序能通过编译,但运行时报错.
当得知有3个整数输出时,大家乐于知道其中缘由.
这时再解释活动记录中各类数据的安排、把参数区放在调用者和被调用者都摸得着的地方等问题时就很快被接受了.
下面的例5进一步让同学理解全局栈式分配策略的特点.

例5图5程序的运行结果是120,120,1和Segmentationfault(coredumped),请解释第2个fact调用的结果为什么没有受参数过多的影响第3个fact调用以浮点数5.
0为参数,为什么结果变成1第4个fact调用没有提供参数,为什么会出现Segmentationfaultintfact(i)inti;main(){if(i==0)printf("%d\n",fact(5));return1;printf("%d\n",fact(5,10,15));else|printf("%d\n",fact(5.
0));returni*fact(i-1)printf("%d\n",fact());图5全局栈式分配的例子2.
3编译和连接了解预处理器、汇编器和连接器等与编译器有关的工具,有助于掌握从源程序到可执行目标程序的实际处理全过程.
用编译器符号表管理的知识对连接过程稍加解释就能明白下面的例6和例7.

例6某软件开发项目的一个程序员自己编写了两个函数库libuser1.
a和libuser2.
a,当用命令cctest.
clibuser1.
alibuser2.
a编译和连接时,报告有未定义的符号,而改用命令cctest.
clibuser2.
alibuser1.
a时,能得到可执行程序.
试分析原因.
例7某软件开发项目的两个程序员分别编写了函数库libuser1.
a和libuser2.
a.
当用命令cctest.
clibuser1.
alibuser2.
a编译和连接时,报告有重复定义的符号.
而改用命令cctest.
clibuser2.
alibuser1.
a时,能得到可执行程序.
试分析原因.
上面列举了我们使用的部分例子.
有些同学说,正是这些实例激发起他们学习编译原理的兴趣.

3课程设计改革探索从2007年起,我们恢复了编译原理课程设计,并且以更开阔的视野来看待课程实验和课程设计.
我们认为,计算机专业各课程的实验和设计(软件方面)要有整体规划、相互配合,才能使学生在同样的投入下获得最佳的效果.

1、各实验和设计针对单课程局部知识点、单课程综合知识、还是覆盖多课程,要有合理布局.

2、各实验和设计使用的开发语言、工具和环境,也同实验和设计内容一样,要逐步提升.

3、根据实验和设计的特点,要求学生个人、合作、甚至竞赛方式完成,同时注重对学生工程意识、质量意识、团队意识的培养.

我们把编译原理的课程设计作为一个覆盖多课程,让学生全面锻炼的课程设计.
要求学生用Java语言为SkipOOMiniJOOL语言(见网页http://staff.
ustc.
edu.
cn/~yuzhang/compiler/)开发编译器.
每个学生完成编译器的前端(或后端),并自行选择完成后端(或前端)的合作伙伴;要求前端完成词法分析、语法分析、语义检查并生成抽象语法树;要求后端由抽象语法树生成x86汇编码,生成的汇编码应能直接用gcc汇编并连接得到可执行文件,不要求代码优化;前后端接口是抽象语法树,实现前后端的同学相互不得开放源码.

下面重点介绍我们在加强过程管理和改进考评方式上的一些经验和体会.

首先,规定截止时间,评测只对截止时间前的最新程序版本进行,避免后评测同学根据先前评测情况来完善程序,以保证评测的公平性和易评比性.

其次,安排多次发布和提交,规定的时间节点有:提交设计文档、提交源代码、发布测试程序、发布评测环境、提交最终版本和测试文档(这是首次尝试后的改进方案).
这样做有助于培养学生的工程意识,大体了解企业开发过程中一些主要环节及其重要性;防止学生临时突击,甚至因突击失败而拷贝他人程序.
同时可以保证评测顺利进行,避免诸如在程序中使用绝对路径、开发环境与评测环境不一致等枝节问题而影响评测、过度影响得分,以提高评测效率和保证公平性.

最后,以4个小时考评10-12个学生的分组方式进行公开评比,评委由教师、助教和同组所有同学组成.
教师主导考评过程、学生按教师要求在投影屏幕上当众演示测试过程和结果;评委提问,被评者当场回答;问题主要围绕完成的设计和编程,以及测试中暴露出的设计或编程错误.
评分的主要策略是:每个评委给该组同学(学生评委包括给自己)排名次;排名依据整个编译器的优劣,而不是只考察被评同学所开发的前端或后端;所开发的前端或后端被越多的同学采用,则成绩越好.

绝大部分学生是公道的,保证了这种考评方式的公平性和大部分学生服气地接受最终排名和分数.
这种方式也避免了教师为保证分数的相对合理并拉开差距而需要过大的考评投入.

这样的过程管理和考评方式调动了学生投精力于课程设计的积极性,大大减少了拷贝他人程序的情况.
学生不断交流经验、关注开发质量、积极推销自己的开发成果,不仅巩固了理论知识、积累了开发经验,也培养了质量意识和团队精神.
一个能说明问题的统计是:自2007年5月11日起的一个半月中,学生在校bbs的CompilerTech版发了约300封帖子讨论该课程设计,一度改变了该版自2005年11月开版以来不太活跃的状况(该版自开版到2007年底的总帖数仅为978封).