计算机专业本科生计算思维实验环节

计算机专业本科生计算思维实验环节

陈文宇　吴祖峰　罗宗粉　陈　昆

（电子科技大学计算机科学与工程学院　成都　610054）

摘要：计算思维能力是形式化描述和抽象思维能力以及逻辑思维方法。计算思维能力在形式语言与自动机课程中得到集中体现；其基本理论和方法在编译原理课程中得到了具体的应用，而编译原理课程本身的重要内容关系到程序设计与实现能力培养。提出理论课程实践环节的重要性，设计了相关课程的实践环节。使得理论和实际相结合，促进了理论课程的教学，增强了学生实践能力的培养。

关键词：计算思维能力　形式语言与自动机　编译原理　实践教学

一、计算思维能力

计算机科学与技术学科强调4个方面的专业能力：计算思维能力、算法设计与分析能力、程序设计与实现能力、计算机系统的认知、分析、设计和运用能力。这也是计算机科学与其他学科的重要区别。相关的理论是计算机学科的基础。

计算机科学与技术学科要求学生具有形式化描述和抽象思维能力，要求掌握逻辑思维方法。这种能力就是计算思维能力。

计算思维能力的培养，不是靠一两门课程就可以实现的，它需要系列课程的学习，并且通过长期的修养才能实现。

计算思维能力的培养主要是通过基础理论系列课程实现的，该系列是由数学和抽象度较高的理论课程组成，包括数学分析、集合和图论、离散数学、数学建模、形式语言与自动机理论。它们构成了对学生计算思维能力培养的一个阶梯训练系统。

在此系统中，连续数学、离散数学、计算模型三部分内容按阶段分开。三个阶段对应计算机学科的学生在本科学习期间的思维方式和能力变化的三个步骤。使得学生的计算思维能力不断提高。

本科生的适应能力以及创新能力在很大程度上取决于坚实的理论基础和专业基础知识，这是高质量本科生教育的重要特征之一。在当今计算机科学技术突飞猛进，专业知识日新月异的时代，只有扎实掌握专业的计算机理论基础，才有可能从事这个专业所进行的科研、教学和其他专业技术工作，才能打好进行创造性研究的基础。因此理论课程的学习就显得尤为重要。

理论方面的知识是计算机的真正灵魂。理论是从计算机应用当中抽象出来的，目的在于使用抽象出来的理论去更好地指导实践。

编译原理是计算机学科中少有的从实践到理论，再从理论到实践的一门专业课程。编译技术不断进步，已经成为计算机科学中发展最迅速、最成熟的一个重要分支。编译技术集中体现了计算机科学发展的重要成果与精华。ACM图灵奖是授予在计算机技术领域作出突出贡献的科学家的最高奖励，自1966年设立以来，程序设计语言、编译理论与方法的方面的得奖成果约占总数的1/3。可见，程序语言及其编译的研究在计算机科学中的始终处于非常重要的地位。

计算思维能力在形式语言与自动机课程中得到集中体现；其基本理论和方法在编译原理课程中得到了具体的应用，而编译原理课程本身的重要内容关系到程序设计与实现能力培养。

形式语言与自动机课程是编译原理课程的前沿课程，对形式语言与自动机课程实践环节除对本课程重点和难点进行实验内容的设计，还必须考虑到对编译原理的延续性。

二、形式语言与自动机课程的实践环节

形式语言课程实验要求学生深入理解和掌握形式语言与自动机理论中的重点和难点内容，包括文法的存储和应用，基本的词法分析方法，自动机模型的实现方法等；同时兼顾程序设计的基本方法和技能。通过本课程实验，是学生掌握实际问题的抽象方法；掌握判断算法优劣的一般准则和设计高效算法的常用技巧，理解算法设计的重要性，了解算法设计方法的初步知识。在协助形式语言与自动机理论课程学习的同时，也为编译原理的学习奠定牢固的理论和实践基础。

在具体实践环节中，结合计算机专业的多门课程内容，包括离散数学、数据结构、形式语言与自动机理论、算法分析与设计、高级程序设计语言（C、C++和JAVA语言）；要求学生在理解本课程基本原理的基础上，设计良好的数据结构存储文法的产生式和有限状态自动机的状态转换函数；设计良好的算法，结合高级编程语言进行实验的实现；并对算法进行分析。

形式语言与自动机课程的实验环节设计了三个实验，包括：

实验1　EXCEL公式的扩展

结合实际应用，对EXCEL公式进行了扩展；利用文法形式进行公式的描述。是学生掌握了上下文无关文法的构造方法；上下文无关文法在计算机中的存储方法。加深对文法工作模式的理解，也为编译理论中的文法检测做准备。

实验2　基本单词符号的识别方法

理解词法分析的要求，对于典型的单词——标识符和浮点型常数，构造状态转换图，将每个状态对应到程序设计语言的一个子程序。加深对DFA工作模式的理解，也为编译理论中的词法分析做准备。

实验3　PDA的实现模型

对于简单的算术表达式（只包含+、*，仅3个浮点型常数做操作数的算术表达式），设计PDA进行计算，加深对PDA工作模式的理解，也为编译理论中的语法分析做准备。

三、编译原理课程的实践环节

在对编译理论与技术进行充分分析的基础上，通过分层实验，使学生从需求分析到方案设计，从程序设计到工程实现等多方面进行训练，加深对编译原理的理解。为此，将本课程的实践教学环节分为两个层次，即，课程实验和综合设计实验。其中，课程实验主要解决学生对《编译原理》中主要技术原理、算法的理解和设计问题。综合性设计实验主要训练学生对典型编译技术的工程实现过程和具体实现技术的掌握。通过分类分层实践，加强了学生对《编译原理》课程中各知识点的理解，培养了学生的实际动手能力、分析能力、编程能力和综合设计、解决问题的能力。同时培养了独立科研工作的能力和团结协作的团队协作精神。

通过编译实验课程的学习和实践工作，学生可以初步了解编译原理与技术在实际项目开发中的应用过程，从而更加清楚的理解计算机高级语言的编译原理与方法，掌握高级语言编译程序的设计原理与构造技术。

编译原理课程的重点和难点包括有限状态自动机、下推自动机的相关模型，词法分析技术、语法分析技术，语法制导翻译技术，目标代码生成技术。因此，实践环节也围绕它们进行设计，包括利用有限状态自动机生成词法分析程序，利用下推自动机生成语法分析程序，语法制导翻译方法进行语义分析，生成8086系列汇编代码。

1．课程实验

针对编译原理的5个逻辑阶段，分析各个阶段的关键技术，设计相应的课程实验，同时还要涉及编译的出错处理和表格管理操作。

课程实验包括：

实验项目1　词法分析器的设计与实现

了解和掌握词法分析的方法，实现一个通用的词法规则分析器，可根据不同的词法规则，对源语言程序的字符串进行扫描，识别出单词符号作为输出，发现其中的词法错误。

实验项目2　文法检测程序的设计与实现

了解和掌握合法文法的构成和表现形式，编程实现给定文法的合法性检测程序。对不符合规范的文法，输出文法检测的结果。对符合规范，但不合法的文法，对它进行文法的合法性改造，使之成为一个合法文法。

实验项目3　预测分析表构造程序的设计与实现

了解和掌握预测分析方法，编程实现预测分析表的构造程序。该程序可根据不同的文法规则生成相应的预测分析表，为后续的预测分析过程提供依据。

预测分析是一种表驱动方法，其控制程序的执行依赖于预测分析表。针对不同的文法，预测分析控制程序是相同的，不同的只是预测分析表的内容。本实验项目的内容包括：分析用户输入的文法，构造FIRST集和FOLLOW集，构造预测分析表。

实验项目4　算符优先关系表构造程序的设计与实现

了解和掌握算符优先分析方法，编程实现算符优先关系表的构造程序。该程序可根据不同的文法规则生成相应的算符优先关系表，为后续的算符优先分析过程提供依据。

算符优先分析也是一种表驱动方法，其控制程序的执行依赖于算符优先关系表。针对不同的文法，预测分析控制程序是相同的，不同的只是算符优先关系表的内容。本实验项目的内容包括：分析用户输入的文法，构造FIRSTVT集和LASTVT集，构造预算符优先关系表。

实验项目5　语法制导的语义分析程序的设计与实现

针对高级语言语句级的分支控制结构（包括单选、二选一的分支结构）和循环控制结构，构造语义分析模型，生成语义分析程序，在预测分析或算符优先分析的同时（语法制导），生成对应的抽象机指令形式的中间代码，完成编译过程中的基本翻译。本实验还可以扩展到对嵌套的分支语句和多选一的分支控制语句的语义分析。

实验项目6　代码生成程序的设计与实现

对于抽象机指令形式的中间代码，改造为等价为80386指令形式的汇编代码，完成编译过程的最终翻译。

2．综合实验

设计与实现一个编译原理实验系统——CPEP（Compiler Principle Experiment Platform）。本系统展示编译原理课程中的重点内容——语法分析和语义分析的基本原理的全过程。

本实验课程针对《编译原理》中语法分析、语义分析的概念抽象、内容繁杂和理解难度大等特点，对两种语法分析和语义分析的全过程与具体的实现方案结合起来，通过多媒体形式直观地展示中间分析步骤和分析结果，提供了语法分析、语义分析的交互式实验平台。

通过实验，学生可对语法分析、语义分析中难于理解的概念和算法产生一个感性的认识，与课堂讲授的理论结合起来，达到知其然也知其所以然的效果，从而加深对编译原理中抽象概念的理解，更快速、更深刻地掌握语法分析、语义分析的教学内容。

综合实验结合了编译理论中的综合知识，涉及计算机专业的多门课程的内容，对学生理解整个编译理论的全貌，掌握计算机软件开发的方法，培养计算思维能力起到了积极的作用。

四、实验考核

将实验考核内容加入到整个课程的考核当中（一般占到20%～30%），实验考核内容包括：

（1）书面问题考核

每项实验都附有问题与思考题，要求学生在完成实验报告的同时根据实验原理或方法进行总结和回答。

（2）实验报告考核

每项实验的实验结果以单独实验报告的形式提交，实验报告要求包括：

设计报告（包公式、算法，函数调用及实现方式说明、流程图、算法分析等内容）；

源程序和可执行程序代码；

实验中遇到的问题及解决的办法说明。

（3）实验结果考核

要求学生实际上机操作，针对教师设计的输入，上机运行，对实际的输出进行考核。

五、总结

在计算机专业两门重要课程的教学活动中，注重实践环节，结合计算机专业的多门课程内容，包括离散数学、数据结构、算法分析与设计、高级程序设计语言（C、C++和JAVA语言）；要求学生在理解本课程基本原理的基础上，设计良好的数据结构和良好的算法，结合高级编程语言进行实验，并对算法进行了分析，学生增长了学习兴趣，使得计算思维能力得到大幅度的提高。

在实验环节中，遵循学生创新能力培养的整体规划，结合课程设计和综合实验加强学生能力培养；并根据综合实验的课题情况，拓展到毕业设计、课外研究性学习、学科竞赛和科研项目，让学生体验较大型课题和实际科研项目开发的工作，受到学生普遍欢迎。

参考文献

[1] 蒋宗礼，姜守旭. 形式语言与自动机理论. 北京：清华大学出版社，2003.

[2] 龚天富. 语言及编译（第2版）[M]. 北京：电子工业出版社，2003.

[3]　Andrew W Apple. 现代编译器的Java实现[M]. 北京：电子工业出版社，2004.

[4]　Dick Grune etc. Modern Compiler Design[M]. JOHN WILEY&SONS，LTD，2002.

[5] 余胜泉，张建伟. 信息时代的教学与实践[M]. 北京：高等教育出版社，2005.