编译原理经典算法的可视化实现

编译原理经典算法的可视化实现I编译原理经典算法的可视化实现摘要在计算机教学中，编译原理这门课程在计算机科学中占有非常重要的地位，每个计算机专业的同学都需要学习它。而通过学习编译原理，能更好的了解高级程序语言的运行机制，并能编写出更加高效的程序。但是编译原理中的算法比较抽象，学习起来困难，而本系统能够动态演示编译原理中的词法分析阶段和语法分析阶段的LL(1)文法，而词法分析器将输出每个单词对应的二元组，这将有利于我们对词法分析器的理解，而LL(1)文法的动态演示使我们能够更好的理解并运用LL(1)文法中的各种算法。所以这种算法可视化技术能加深人们对程序行为的理解和认识，准确地了解和分析程序执行过程所反映的逻辑含义和功能。本程序是在vs2012平台下用C#语言实现的。本程序界面简洁，能实现词法分析器的可视化和LL(1)文法的演示。关键词：词法分析;LL(1)文法;可视化技术编译原理经典算法的可视化实现IITHEVISUALIMPLEMENTATIONofCLASSICALGORITHMofCOMPILATIONPRINCIPLEAbstractInthecomputercourse,Compilationprincipleplaysaveryimportantroleincomputerscience,eachstudentwholearnscomputersciencehastolearnit.Throughthestudyoftheseprinciples,wecanbemoreeasytounderstandtheoperationmechanismofvarioushigh-levellanguage,andwecanproducemoreefficientcode.Butthecompilationprincipleisabstract,it’sverydifficulttolearnit.ThesystemcandynamicdemothecompilationprincipleoflexicalanalysisandLL(1)ofgrammargrammaranalysisphase,andthelexicalanalyzerwilloutputeachwordtwotuples,whichwillhelpustoanalysisoflexicalunderstanding,LL(1)dynamicdemogrammarenablesustobetterunderstandandusetheLL(1)algorithmsinthegrammar.Sothiskindofalgorithmvisualizationtechnologycanhelppeopletounderstandprogrambehavior,understandthereflectionaccuratlyandanalysisofprogramexecutionlogicmeaningandfunction.ThisprocedureisusedC#languageundervs2012platform.Theprogram’sinterfaceissimple,anditachievesvisualoflexicalanalyzerandthedemoofLL(1)algorithms.Keywords:lexicalanalysis;LL(1);visualizationtechnology编译原理经典算法的可视化实现III目录1绪论…………………………………………………………………………………………………………………….11.1背景..................................................................................................................11.2本课题研究的目的和意义..............................................................................11.3国内外研究现状..............................................................................................21.4主要工作..........................................................................................................21.5本系统的设计思想.........................................................................................22词法分析概述……………………………………………………………………………………………….…….42.1词法分析器的作用.........................................................................................42.2词法分析中的问题..........................................................................................52.3词法分析中的术语.........................................................................................52.4词法错误.........................................................................................................72.5词法分析生成工具.........................................................................................83词法分析器动态演示的设计与实现…………………………………………………………..…….103.1词法分析器描述语言...................................................................................103.1.1Lex说明………………………………………………………………………………………………………..103.1.2超前扫描操作………………………………………………………………………….………………….113.1.3Lex编程………………………………………………………………………………………………………..123.2词法分析器动态演示的事件实现................................................................124语法分析……………………………………………………………………………………………….…….…….174.1语法分析的基本概念...................................................................................174.2语法分析的任务...........................................................................................174.3语法分析基础...............................................................................................175LL(1)文法可视化的设计与实现………………………………………………………………………235.1程序界面的实现............................................235.2程序关键功能的实现。.......................................25编译原理经典算法的可视化实现IV5.2.1FIRST和FOLLOW………………………………………………………………………………..……255.2.2预测分析表的构造.....................................27致谢…………………………………………………………………………………………………………………………29参考文献………………………………………………………………………………………………………………….30附录………………………………………………………………………………………………………………………….31附件1开题报告附件2译文及原文影印件编译原理经典算法的可视化实现11绪论1.1背景在计算机发展历程中，编译器的产生对计算机科学技术的发展起到了巨大作用，是开发计算机程序不可缺少的重要工具。而编译器的原理和技术具有非常普遍的意义。编译器[2]的编写涉及到计算机体系结构、程序设计语言、语言理论和算法和软件工程等学科，是计算机科学技术的重要基础。编译原理在计算机学科中是一门基础性很强的课程，每个学习计算机技术的学生都要去了解学习它。通过这些原理，就能更加了解各种高级语言的运行机制，就能编写出更为高效的程序。如今，我们知道在课堂上很多教师设计良好的算法动画演示来有效帮助学生学习算法，而且这种方法已基本被人们普遍接受。但是，我们知道，动画演示给定的初试条件是固定的，只能观看算法执行过程，并不能通过修改参数控制算法的演示过程，这远远达不到灵活展示的效果，对学生来说，取得的效果也不是特别突出，达不到人们的期望值。而编译原理的每个阶段，从词法分析、语法分析，直到中间代码的生成，每个阶段都包含大量的算法。而这些算法过程较为复杂，比如语法分析中的LL(1)文法分析过程包含很多动作，求FIRST集和FOLLOW集，构成分析表，然后根据分析表来进行最左推导，涉及的数据结构包括堆栈、表等，而要形象地展示这些元素，使学生更加容易地接受这些知识，这是一项具有挑战的事情。可视化技术[8]就是利用计算机图形学和图像处理技术，将数据转换成图形或图像后在屏幕上显示出来，并进行交互处理的理论、方法和技术。在编译算法的可视化中[3]，它将一个程序的数据、操作和语义提取出来并进行动态演示，利用诸如图形、文本、颜色、声音等工具来描述算法。这和清华大学严蔚敏教授编著的《数据结构》系列教材专门配备的数据结构演示算法有点类似。1.2本课题研究的目的和意义《编译原理》是计算机专业一门重要的课程，讲述了将高级编程语言翻译为机器易编译原理经典算法的可视化实现2于执行的低级语言的编译过程和原理，而针对编译原理这门课程存在的知识和概念繁多算法抽象并且难于理解的情况，本课题实现了编译原理经典算法的可视化，将词法分析器的实现作为典型示范，也将LL(1)文法演示过程实现出来。为便于学生观察和分析编译过程，可以设置系统的播放速度，此系统不仅有利于帮助学生理解编译器的工作过程，原理及其具体实现方法，还有助于促进学生将大学所学的多种专业知识综合运用，促发他们的学习兴趣，将这一计算机学科中非常重要的基础课程学好。1.3国内外研究现状近年来，随着多媒体技术的兴起，在各种场合，我们可以见到每次演示编译原理里面的算法时，一般是借助于flash等这种动画演示文件，但是这种文件不能改变他的初始值，也看不到算法的执行过程。算法可视化技术的研究始于90年代。现在，算法可视化开始在国家级研究中心，高水平的大学，大公司的研究开发中心进行研究和应用。而随着PC