论文部分内容阅读
摘 要：编译原理课程是计算机专业最能锻炼学生计算思维能力的一门课程。但截至到目前编译原理的课堂教学还是采用传统满堂灌的教学方式，学生没有参与到课堂中来。因此作者提出采取“以问题为中心、学生为主体的自主學习方式”即PBL的教学方法，并将其应用于编译原理LR 类语法分析方法的教学实践中，取得了较好的教学效果。
关键词：编译原理；问题导向；LR类分析法
中图分类号：G642 文献标志码：A 文章编号：2096-000X（2016）20-0125-02
Abstract： The compilation principle is the most suitable course to exercise the students' computational thinking ability. But at present， the classroom teaching of compiling principle still adopts the traditional teaching way and students are not involved in the classroom. Therefore， the author puts forward an autonomic learning way which centered on problems and takes students as subject， that is the PBL teaching method and applies it to the teaching practice of LR syntax analysis in compiling principle， which has achieved good teaching effect.
Keywords： compilation principle； problem oriented； LR analysis
一、 PBL的涵义
为了提高学生的学习能力，英美一些发达国家被广泛采用“以问题为中心、学生为主体的自主学习方式”即PBL（Problem-Based Learning，问题式学习）的教学方法，教师通过设立问题，在课前引导学生查阅相关资料，采取自主学习或分组讨论的形式解决问题，课堂上可以让学生分组讲等方式完成教学内容，目的是通过知识的主动建构，激发学生的学习激情，挖掘学生的学习潜力。文章针对以往编译原理课程教学特点，在编译原理LR类语法分析大胆采用PBL教学方法进行改革和教学实践，取得了良好的教学效果。
二、编译原理课程教学现状
《编译原理》是计算机专业的一门很重要的课程，集中体现了计算机的思维方式。但该课程涉及的理论抽象，算法复杂：几乎每一章都有很多知识点，很多新的理论算法思想，很多需要学生动手实践的环节等。但目前编译原理教学缺少互动，效果差，学生如果上课能认真听讲，可以按照老师课堂讲的内容，回答大部分问题，但如果学生不会去思考“为什么”“如何做”等问题，学生的这种学习方式就是一种被动的接受知识的过程，学生学完这门课程，不知道一个编译器到底应该怎么设计？怎样实现？在设计的过程中到底应该选取哪种语法分析方法，生成的代码优化到什么程度就达到最优等。因此如何改变目前《编译原理》课程死板的教学模式，提高教学效果，改善教学质量，让学生积极主动地投身到编译原理的课程学习中，获得更多更有用的编译原理课程的理论知识，提高学生发现问题、分析问题、解决问题的能力，是各位编译原理教师应该思考和关注的问题。针对目前在编译原理课程教学中存在的问题，作者将PBL教学方法引入到编译原理课程教学中，文章将以LR类语法分析为类进行介绍。
三、基于PBL的教学方法在编译原理课程教学中的应用 按照PBL教学方法，教师在具体实施中可以按照以下步骤来进行教学设计，最终帮助学生解决问题：发现问题→引导学生分析问题→组织并帮助学生进行小组讨论或自主学习→知识建构→自我反思，最后进行教师进行内容总结并补充。
通过课程的合理设计及问题的巧妙提出，让同学通过问题的引导明确本节课的教学目标，通过教师的引导学生明确问题的解决思路，通过问题的解决让学生理解课程知识体系，采用循序渐进引导启发的方式让学生主动的学习，掌握编译原理课程知识。文章以LR语法分析法为例来帮助大家理解。
（一）创设问题
问题不能来的太突然，因此需创设情境，进行带入。可以先给出一个文法如下：
G：（0）S'→S （1）S→aAd （2）S→bAc （3）S→aec （4）S→bed （5）A→e
1. 先要求学生采用已学过的LR（0）分析法进行分析。由于前面学生学习过LR（0）分析法，学生就可以完成此题。在构造LR（0）识别活前缀的确定化有限自动机过程中出现了项目集： I7={ A→e.，S→ae.c }中，按照LR（0）分析法构造分析表时对于第I7状态，遇到超前搜索符c时可以进行移进，在分析表中填S9，同时对于项目A→e.，需要在这个表中填R5， 即在一个表格中填两个动作，即状态I7中出现了归约-移进冲突，当对符合串进行分析的时候，查到这个状态I7遇到符号c时，不知道改采用哪个动作，这时可以让学生按照两种动作分别做一下，识别出为什么一种正确，而另外一种不行呢？学生通过思考发现采用LR（0）分析法显然不行。重新审视这种方法。
2. 引导学生进一步思考采用SLR（1）分析法，对于移进项目跟LR（0）完全相同，对于归约项目需求归约项目产生式左部非终结符号的Follow集，即求项目A→e.产生式左部非中介符号A的Follow集，Follow（A）={c，d}，很明显A的Follow集中还有c，说明冲突解决不了。 3. 引导学生进行思考：为什么不行？显然当栈里边的符号为ae，输入符号c时，如果对把栈顶符号e归约为A，当前符号串就变为aAc，而它不是一个规范句型，A后面可以跟c，因为有规范句型bAc，这也就是SLR（1） 分析法求Follow集的原因。很自然地让学生自己发现采用SLR（1）分析法显然不行。情境带入学生主动思考采用哪种方法解决该问题，给学生这次课到下次课之间的思考时间。
（二）引导学生分析问题
经过思考之后学生深入理解采用前两种方法不行的原因，组织学生分组讲解原因，教师进行归纳补充。考虑LR（0）分析表的造表算法规则（2），对于归约项目A→？琢·，不管下一输入符号是谁，均进行归约。这显然是一个武断的决定。若Ii中同时含有[B→？琢·b？茁及C→？琢· ]两类项目时，上述填表方法必然得到冲突的分析表。一般地，Ii={A1→？琢·a1？茁1，…，Am→？琢·am？茁m，B1→？琢·，…，Bn→？琢·}如果能根据下一输入符号a对上述冲突加以区分，则冲突可解决。当Follow（Bk）（1？艽k？艽n）与{a1，a2，…，am}两两互不相交时，则可按下述方法解决冲突：從SLR（1）解决问题的方法看，对于归约项目A→？琢·，只要是Follow（A）中的符号均可按此产生式进行归约，这也有一定的片面性，因为没有考虑？琢所在的“环境”。当？琢在栈顶形成时（设此时栈内容为#？啄？琢，输入符为a），若强行将？琢归约为A（栈内容： #？啄A），但#？啄Aa又不是任何规范句型的前缀时，这个归约就是无效的。
（三）自主学习或分组讨论
知道了什么是LR（1）分析法，分组讨论如何采用LR（1）分析法做题，就需要构造LR（1）识别活前缀的DFA，构造的过程跟LR（0）、SLR（1）进行比较，找到不同处：每个项目都有超前搜索字符，如何确定LR（1）每个项目集，显然跟LR（0）或SLR（1）一样，基本项目为[S′→.S]，LR（1）需要考虑超前搜索字符，文法开始符号的超前搜索字符为#，因此确定[S′→.S，#]为LR（1）的基本项目，其他项目的确定方法的难点就是确定每个项目的超前搜索字符。根据以下定义确定：
LR（1）项目[A→？琢·？茁，？琢]对活前缀？酌=？啄？琢有效，iff 存在规范推导S？圯？觹？啄Ay？圯？啄？琢？茁y y∈VT？觹且满足条件：
（1）当y≠？着时，a∈FIRST（y）； （2）当y=？着时，a=#.
这样可以求出每个项目集的闭包。
（四）知识主动建构
通过阅读教材和小组讨论，教师引导启发，学生主动学习运用比较分析法掌握LR（1）语法分析方法，从而完成了对知识的主动建构。LR（0）只要出现归约项目，不管当前识别符号是什么，就无条件归约，这样可能出现归约-移进，归约-归约冲突；SLR（1）在有归约-归约冲突，归约-移进冲突，需要看向前搜索一次，求归约项目产生式左部非终结符号的Follow集，有些冲突解决不了，因为这种方法只注意到归约之后该非结符号后面可以跟的符号，不考虑归约后能否构成规范句型。
LR（1）分析法通过求超前搜索符号，归约的时候看超前搜索符号，能够保证每次归约之后栈里面的符号串是规范句型的活前缀。这种分析方法的取得，不是教师通过讲课学生掌握的，是学生通过查阅资料分析讨论主动建构得到的，这就是研究性自主学习的过程，即PBL教学方法的重现。把科研的思路应用到具体的教学环节中，学生们主动思考、主动讨论、主动掌握知识。
（五）自我思考
在这个阶段教师要对学生所做的工作进行归纳总结，根据需要进行补充。最后组织学生对本次学习过程进行有意识的总结和反思。例如LR分析法学完之后让学生大胆思考，考虑当前的有限自动机跟词法分析过程中有限自动机之间的联系，能不能先构造非确定化的有限自动机再对其进行确定化，确定化的方法跟以前词法分析一样还是不一样，词法分析与语法分析的衔接之处。这种反思有利于发展学生的高层次思维能力。
四、结束语
根据编译原理课程教学特点：抽象、逻辑性强，知识点多、算法复杂。学生学习状态一直处于被动获取知识的方式，教学效果很不理想。经过大胆改革，尝试采用基于PBL教学方法，并在编译原理LR类分析中进行了具体应用，从问题的提出、分析、讨论、知识主动建构和自我反思等环节进行了论述。这种方法非常适合编译原理教学过程，相信以后的教学实践中能够取得了较好的教学效果，提高学生的主动获取知识、探索知识、解决实际问题的能力，达到提升学生计算思维能力，达到在计算机专业中理想就业的目的。
参考文献
[1]周汝雁，张云，韩彦岭.计算机专业课程PBL教学方法探究与实践——以“编译原理”课程为例[J].工业和信息化教育，2014（5）：39-43.
[2]冯阿芳.PBL在编译原理课程教学中的应用研究[J].哈尔滨职业技术学院学报，2008（4）：94.
关键词：编译原理；问题导向；LR类分析法
中图分类号：G642 文献标志码：A 文章编号：2096-000X（2016）20-0125-02
Abstract： The compilation principle is the most suitable course to exercise the students' computational thinking ability. But at present， the classroom teaching of compiling principle still adopts the traditional teaching way and students are not involved in the classroom. Therefore， the author puts forward an autonomic learning way which centered on problems and takes students as subject， that is the PBL teaching method and applies it to the teaching practice of LR syntax analysis in compiling principle， which has achieved good teaching effect.
Keywords： compilation principle； problem oriented； LR analysis
一、 PBL的涵义
为了提高学生的学习能力，英美一些发达国家被广泛采用“以问题为中心、学生为主体的自主学习方式”即PBL（Problem-Based Learning，问题式学习）的教学方法，教师通过设立问题，在课前引导学生查阅相关资料，采取自主学习或分组讨论的形式解决问题，课堂上可以让学生分组讲等方式完成教学内容，目的是通过知识的主动建构，激发学生的学习激情，挖掘学生的学习潜力。文章针对以往编译原理课程教学特点，在编译原理LR类语法分析大胆采用PBL教学方法进行改革和教学实践，取得了良好的教学效果。
二、编译原理课程教学现状
《编译原理》是计算机专业的一门很重要的课程，集中体现了计算机的思维方式。但该课程涉及的理论抽象，算法复杂：几乎每一章都有很多知识点，很多新的理论算法思想，很多需要学生动手实践的环节等。但目前编译原理教学缺少互动，效果差，学生如果上课能认真听讲，可以按照老师课堂讲的内容，回答大部分问题，但如果学生不会去思考“为什么”“如何做”等问题，学生的这种学习方式就是一种被动的接受知识的过程，学生学完这门课程，不知道一个编译器到底应该怎么设计？怎样实现？在设计的过程中到底应该选取哪种语法分析方法，生成的代码优化到什么程度就达到最优等。因此如何改变目前《编译原理》课程死板的教学模式，提高教学效果，改善教学质量，让学生积极主动地投身到编译原理的课程学习中，获得更多更有用的编译原理课程的理论知识，提高学生发现问题、分析问题、解决问题的能力，是各位编译原理教师应该思考和关注的问题。针对目前在编译原理课程教学中存在的问题，作者将PBL教学方法引入到编译原理课程教学中，文章将以LR类语法分析为类进行介绍。
三、基于PBL的教学方法在编译原理课程教学中的应用 按照PBL教学方法，教师在具体实施中可以按照以下步骤来进行教学设计，最终帮助学生解决问题：发现问题→引导学生分析问题→组织并帮助学生进行小组讨论或自主学习→知识建构→自我反思，最后进行教师进行内容总结并补充。
通过课程的合理设计及问题的巧妙提出，让同学通过问题的引导明确本节课的教学目标，通过教师的引导学生明确问题的解决思路，通过问题的解决让学生理解课程知识体系，采用循序渐进引导启发的方式让学生主动的学习，掌握编译原理课程知识。文章以LR语法分析法为例来帮助大家理解。
（一）创设问题
问题不能来的太突然，因此需创设情境，进行带入。可以先给出一个文法如下：
G：（0）S'→S （1）S→aAd （2）S→bAc （3）S→aec （4）S→bed （5）A→e
1. 先要求学生采用已学过的LR（0）分析法进行分析。由于前面学生学习过LR（0）分析法，学生就可以完成此题。在构造LR（0）识别活前缀的确定化有限自动机过程中出现了项目集： I7={ A→e.，S→ae.c }中，按照LR（0）分析法构造分析表时对于第I7状态，遇到超前搜索符c时可以进行移进，在分析表中填S9，同时对于项目A→e.，需要在这个表中填R5， 即在一个表格中填两个动作，即状态I7中出现了归约-移进冲突，当对符合串进行分析的时候，查到这个状态I7遇到符号c时，不知道改采用哪个动作，这时可以让学生按照两种动作分别做一下，识别出为什么一种正确，而另外一种不行呢？学生通过思考发现采用LR（0）分析法显然不行。重新审视这种方法。
2. 引导学生进一步思考采用SLR（1）分析法，对于移进项目跟LR（0）完全相同，对于归约项目需求归约项目产生式左部非终结符号的Follow集，即求项目A→e.产生式左部非中介符号A的Follow集，Follow（A）={c，d}，很明显A的Follow集中还有c，说明冲突解决不了。 3. 引导学生进行思考：为什么不行？显然当栈里边的符号为ae，输入符号c时，如果对把栈顶符号e归约为A，当前符号串就变为aAc，而它不是一个规范句型，A后面可以跟c，因为有规范句型bAc，这也就是SLR（1） 分析法求Follow集的原因。很自然地让学生自己发现采用SLR（1）分析法显然不行。情境带入学生主动思考采用哪种方法解决该问题，给学生这次课到下次课之间的思考时间。
（二）引导学生分析问题
经过思考之后学生深入理解采用前两种方法不行的原因，组织学生分组讲解原因，教师进行归纳补充。考虑LR（0）分析表的造表算法规则（2），对于归约项目A→？琢·，不管下一输入符号是谁，均进行归约。这显然是一个武断的决定。若Ii中同时含有[B→？琢·b？茁及C→？琢· ]两类项目时，上述填表方法必然得到冲突的分析表。一般地，Ii={A1→？琢·a1？茁1，…，Am→？琢·am？茁m，B1→？琢·，…，Bn→？琢·}如果能根据下一输入符号a对上述冲突加以区分，则冲突可解决。当Follow（Bk）（1？艽k？艽n）与{a1，a2，…，am}两两互不相交时，则可按下述方法解决冲突：從SLR（1）解决问题的方法看，对于归约项目A→？琢·，只要是Follow（A）中的符号均可按此产生式进行归约，这也有一定的片面性，因为没有考虑？琢所在的“环境”。当？琢在栈顶形成时（设此时栈内容为#？啄？琢，输入符为a），若强行将？琢归约为A（栈内容： #？啄A），但#？啄Aa又不是任何规范句型的前缀时，这个归约就是无效的。
（三）自主学习或分组讨论
知道了什么是LR（1）分析法，分组讨论如何采用LR（1）分析法做题，就需要构造LR（1）识别活前缀的DFA，构造的过程跟LR（0）、SLR（1）进行比较，找到不同处：每个项目都有超前搜索字符，如何确定LR（1）每个项目集，显然跟LR（0）或SLR（1）一样，基本项目为[S′→.S]，LR（1）需要考虑超前搜索字符，文法开始符号的超前搜索字符为#，因此确定[S′→.S，#]为LR（1）的基本项目，其他项目的确定方法的难点就是确定每个项目的超前搜索字符。根据以下定义确定：
LR（1）项目[A→？琢·？茁，？琢]对活前缀？酌=？啄？琢有效，iff 存在规范推导S？圯？觹？啄Ay？圯？啄？琢？茁y y∈VT？觹且满足条件：
（1）当y≠？着时，a∈FIRST（y）； （2）当y=？着时，a=#.
这样可以求出每个项目集的闭包。
（四）知识主动建构
通过阅读教材和小组讨论，教师引导启发，学生主动学习运用比较分析法掌握LR（1）语法分析方法，从而完成了对知识的主动建构。LR（0）只要出现归约项目，不管当前识别符号是什么，就无条件归约，这样可能出现归约-移进，归约-归约冲突；SLR（1）在有归约-归约冲突，归约-移进冲突，需要看向前搜索一次，求归约项目产生式左部非终结符号的Follow集，有些冲突解决不了，因为这种方法只注意到归约之后该非结符号后面可以跟的符号，不考虑归约后能否构成规范句型。
LR（1）分析法通过求超前搜索符号，归约的时候看超前搜索符号，能够保证每次归约之后栈里面的符号串是规范句型的活前缀。这种分析方法的取得，不是教师通过讲课学生掌握的，是学生通过查阅资料分析讨论主动建构得到的，这就是研究性自主学习的过程，即PBL教学方法的重现。把科研的思路应用到具体的教学环节中，学生们主动思考、主动讨论、主动掌握知识。
（五）自我思考
在这个阶段教师要对学生所做的工作进行归纳总结，根据需要进行补充。最后组织学生对本次学习过程进行有意识的总结和反思。例如LR分析法学完之后让学生大胆思考，考虑当前的有限自动机跟词法分析过程中有限自动机之间的联系，能不能先构造非确定化的有限自动机再对其进行确定化，确定化的方法跟以前词法分析一样还是不一样，词法分析与语法分析的衔接之处。这种反思有利于发展学生的高层次思维能力。
四、结束语
根据编译原理课程教学特点：抽象、逻辑性强，知识点多、算法复杂。学生学习状态一直处于被动获取知识的方式，教学效果很不理想。经过大胆改革，尝试采用基于PBL教学方法，并在编译原理LR类分析中进行了具体应用，从问题的提出、分析、讨论、知识主动建构和自我反思等环节进行了论述。这种方法非常适合编译原理教学过程，相信以后的教学实践中能够取得了较好的教学效果，提高学生的主动获取知识、探索知识、解决实际问题的能力，达到提升学生计算思维能力，达到在计算机专业中理想就业的目的。
参考文献
[1]周汝雁，张云，韩彦岭.计算机专业课程PBL教学方法探究与实践——以“编译原理”课程为例[J].工业和信息化教育，2014（5）：39-43.
[2]冯阿芳.PBL在编译原理课程教学中的应用研究[J].哈尔滨职业技术学院学报，2008（4）：94.