层次化精准编译原理实践教学

来源:用户上传      作者:

　　摘要：《编译原理》作为计算机专业一门重要的专业课，理论性强且较为抽象。实践教学可以辅助理论教学，训练学生思维，加强学生对理论知识的深度了解及设计编译程序的能力。针对现有实践教学体系的问题，在编译原理核心算法和编泽器的设计两方面，分别对教学内容及实践难度进行了层次化创新，从而对学生进行步步引导，提高编译原理的教学质量。
　　关键词：编译原理;实践教学;词法分析;语法分析;语法制导翻译
　　中图分类号：C642 文献标识码：A
　　文章编号：1009-3044（2020）20-0158-02
　　Hierarchical and Precise Experiment Teaching of Principle Practical
　　WANG Zhong-qing， ZHU Pei-pei
　　（School of Computer Science and 'l'echnology， Soochow U niversity， Suzhou 215006， China）
　　Abstract： As an important professional course for computer maj ors，¨ C ompilation Principle "is highly theoretical and abstract. Practi-cal teaching can assist theoretical teaching， train students' thinking， and strengthen students' deep understanding of theoreticalknowledge and the ability to design compilers. Aiming at the problems of the existing practical teaching system， this paper makesthe teaching content and practice difficulty hierarchical in two aspects： the compilation principle core algorithms and compiler de-sign， so as to guide students step hy step and improve the teaching quality of compilation principle.
　　Key words： compilation principle; practical teaching; lexical analysis; grammatical analysis; grammatical guidance translation
　　1引言
　　編译原理课程是高校计算机及信息类相关专业的基础及核心课程，该课程涵盖数据结构、算法等多方面的知识，有着很强的逻辑推理性和高度概括的抽象性，同时也将实践和理论高度结合[1]，是计算机专业课中最具有挑战力的课程之一，在语言处理、软件工程、软件自动化等诸多领域有着广泛的应用[2]。在编译原理理论教学中有限自动机、语法制导等知识都比较抽象，理解难度较大，学生只能片面的了解编译器的相关知识，且难以运用。其次理论教学模式单一，很难激起学生的学习兴趣，影响学生创新和创造思维的发展，因此衍生了一系列改革理论教学的方法[3-4]。本文认为理论教学还需要借助实践课程来帮助学生进一步熟悉编译原理技术，培养设计实现编译程序等能力。
　　编译原理的实践教学可以分为两个方面：一方面是编译原理相关算法的实践[5]，包括词法分析部分的MYT算法和子集构造法，语法分析部分的LL文法和LR文法等;另外一方面是编译器的设计[6-7]，包括从词法分析到语法制导翻译的整个流程，以及每一个模块的设计。两部分是相辅相成的，编译原理相关算法的实现是整个编译器设计的基础，而编译器的设计又可以帮助理解编译原理中的每个算法的思想。以往的相关实践教学研究多偏重于其中一方面的教学，而这两方面对于编译原理实践课都很重要[8]，本文将分别从这两个方面介绍层次化编译原理实践课的具体设计方案。
　　2编译原理核心算法的实现
　　本节着重介绍编译原理核心算法的实现，相关算法主要集中于词法分析与语法分析部分。
　　2.1词法分析的实验设计
　　在词法分析部分，着重于分析如何将正则表达式转换为自动机，具体包含三方面的内容：正则表达式的应用，从正则表达式到不确定的有限自动机（NFA）的实现（MYT算法），从不确定的有限自动机（NFA）到确定的有限自动机（DFA）的实现（子集构造法）。
　　首先设计简单实验让学生熟悉编程语言的环境，了解正则表达式的基本用法，例如匹配日期，提取超链接，提取文档标题与正文等。进一步的可设计实验利用正则表达式进行LaTex源文件解析，从而提高学生的学习兴趣，让学生了解正则表达式如何与编译原理结合。
　　熟悉正则表达式之后，可设计实验基于MYT算法将正则表达式转换为对应的NFA状态转换表。实验中可以给出识别字母表中一个字符、主运算符为闭包正则式的NFA状态转换表的构建，让学生以此为例，实现主运算符为选择，连接等正则式的NFA状态转换表的构建。
　　最后设计基于子集构造法的实验将NFA状态转换表转换成对应的DFA状态转换表，其中主要让学生实现ε-closure（S）、ε-closure（T）和move（T，a）函数，及验证一个字符串是否能够被DFA接受，从而提高学生对于从NFA到DFA转换的理解。
　　2.2语法分析的实验设计
　　在语法分析部分，由于计算机主要是基于自下而上的方式进行语法分析，因此主要要求学生实现两个自下而上的语法分析算法：CYK算法和SLR语法分析方法。该部分的实验有助于学生开拓算法知识，提高运用不同方法解决问题的能力。 　　CYK算法是一个基于动态规划思想，用于测试串w对于一个上下文无关文法L的成员性的一个算法。该算法采用并行算法，用逐次推进的办法获得最优的结构，学生要定义语法规则并计算相关概率推算最可能的句子结构。
　　SLR语法分析方法由从左向右处理输入字符串，遵循最右边优先派生的推导顺序，并解决相关冲突，该实验要求学生构建SLR文法的可行前缀的DFA。
　　3编译器的设计与实现
　　本节着重介绍编译器的设计与实现过程中涉及的相关模块的实现。整个实现过程需要利用编译器构建工具PLY（Py-thon Lex-Yacc），该工具已经封装了基本的词法分析与语法分析模块，基于PLY能够使学生很快的构建相关的编译器模块。
　　为了能够更好地进行编译器的设计与实现，本文将整个实现过程分为两个部分：一是对于一些简单的语法处理器的实现，二是构建一个完整的基于程序设计语言的编译器。在下面的小节将分别进行描述。
　　3.1简单的语法处理器的实验设计
　　为了让学生能够对编译器有一个形象的理解，首先让学生构建一些简单的语法处理器，包括：化学表达式的解析，SQL语言的解析和LaTex源文件的解析。这些实验循序渐进，从简单到复杂，可以让学生熟悉PLY工具，理解词法分析模块（lex）如何与语法分析模块（yacc）联系在一起、如何定义没有二义性的语法规则以及如何处理移进和归约冲突。
　　1）化学表达式的解析
　　化学分子式的解析主要为了考察学生对于单个语法单元的解析。化学分子式由元素符号和数字组成，本实验要求学生计算化学分子式中元素的数目，例如“H2S04”中元素的数目为7。
　　2）SQL语言的解析
　　SQL语言的解析主要考察学生对于单行语句的解析。首先让学生熟悉示例程序中的解析SQL语言的程序，然后让学生扩展示例程序中的语法，使其能完全适应SQL查询语句，并完成相关SQL文件的查询（包括，where、order by、group等）。该实验要求学生写出相应的正则式提取及语法规则的定义。
　　3）LaTex源文件的解析
　　LaTex源文件的解析主要是考察学生对于多行语句的解析。该实验需要学生定义LaTex中各个标签的语法规则，输出相应的语法树，并转化为PDF格式。语法分析中会运用到递归思想，能锻炼学生的逻辑思维能力，且该实验能加强学生对La-Tex文本的认识。
　　3.2基于Python--的编译器的实验设计
　　当学生实现了上述简单的语法处理器之后，本节将继续指导学生实现一个基于Python——语法的编译器。所谓Python——是指一个比Python更简单的程序设计语言。整个编译器的实现包括：赋值语句，输出语句，条件与循环语句，函数，类的实现等。
　　首先需要实现的是简单四则运算的程序，例如c=a+b，其中包括赋值语句和输出语句，该实验要求学生先构造语法树，然后为每一条Python语句所对应的语法树结点没置一个属性并为每一个产生式实现语法制导翻译。
　　其次是实现循环与条件语句的解析，包括while，for，if等语句。并基于这些语句实现复杂的算法的编译，例如：二分查找和选择排序，从而帮助学生不断优化细节，使程序具有更好的鲁棒性。
　　然后是函数的解析，该实验需要通过一个函数表来保存每个函数的信息，然后通过函数表实现函数的调用。在该实验中，学生要考虑到函数定义、函数调用、返回语句等的解析与翻译。
　　最后就是类的解析，该实验需要实现类中变量和函数的翻译等，要注意类中成员函数、成员变量和一般函数、变量的区别以及构造函数的解析。
　　整个基于Python-语法编译器的实现过程从简单的语句到函数再到类，一步一步指导学生优化Python——语法的体系，帮助学生熟悉从词法分析到语法分析再到语法制导翻译的过程，有利于培养学生将理论转化为实践的能力。
　　4结束语
　　在编译原理实践教学过程中，文章针对现有教学进行了一些创新研究。实践教学改变了传统理论教学单一的模式，提高了学生的兴趣，且实践内容由算法到编译器的实现，实践难度由浅入深，均具有层次性，循序渐进，一步一步引导学生深入了解编译程序，不仅锻炼了学生的编程能力，为之后大型程序的开发奠定了基础，还提高了教学的质量。关于层次化实践教学这个课题，还需要和更多相关课程的教师一起探讨研究。
　　参考文献：
　　[1]余芳，王晓明，赵森.基于创新思维培养的编译原理实验教学改革[J].大学教育，2019（12）：45-47.
　　[2]余月，李凤霞，陈宇峰，计卫星.计算机编译原理课程虚拟实验设计与实践[J].实验技术与理，2019，36（8）：123-126.
　　[3]杨旭.新工科背景下基于混合式教学的编译原理课程教学改革探析[J].计算机产品与流通，2019（12）：225.
　　[4]于双元，徐金安，丁丁，陈钰枫.基于层次递进模式的“编译原理”课程教学研究与实践[J].工业和信息化教育，2019（3）：51-55.
　　[5]万新燕，时招军.编译原理实验教学设计[J].教育教学论坛，2019（8）：261-262.
　　[6]李春娥.编译原理实验教学设计的改进[J].计算机产品与流通，2018（11）：225.
　　[7]侯书东，常家琦，刘恒.编译原理课程教学实践探究[J].安徽工业大学学报（社会科学版），2018，35（04）：91-92.
　　[8]孙守卿.基于工程教育专业认證的《编译原理》课程改革[J].电脑知识与技术，2019，15（29）：104-106.
　　【通联编辑：王力】
　　收稿日期：2020-01-19
　　基金项目：面向杜交网络的中文事件抽取与预测研究，国家自然科学基金（ 61806137）;基于文本和社交网络的突发事件发现研究，江苏省高等学校自然科学研究面上项目（18KJB520043）
　　作者简介：王中卿（1987-），男，江苏苏州人，讲师，博士，主要研究方向为自然语言处理;朱培培（1995-），女，江苏省徐州人，硕士研究生，主要研究方向为自然语言处理，
转载注明来源:https://www.xzbu.com/8/view-15300131.htm