发布时间 : 星期五 文章编译原理经典算法的可视化实现 - 图文更新完毕开始阅读
编译原理经典算法的可视化实现
1 绪 论
1.1背景
在计算机发展历程中，编译器的产生对计算机科学技术的发展起到了巨大作用，是开发计算机程序不可缺少的重要工具。而编译器的原理和技术具有非常普遍的意义。编译器[2]的编写涉及到计算机体系结构、程序设计语言、语言理论和算法和软件工程等学科，是计算机科学技术的重要基础。编译原理在计算机学科中是一门基础性很强的课程，每个学习计算机技术的学生都要去了解学习它。通过这些原理，就能更加了解各种高级语言的运行机制，就能编写出更为高效的程序。如今，我们知道在课堂上很多教师设计良好的算法动画演示来有效帮助学生学习算法，而且这种方法已基本被人们普遍接受。但是，我们知道，动画演示给定的初试条件是固定的，只能观看算法执行过程，并不能通过修改参数控制算法的演示过程，这远远达不到灵活展示的效果，对学生来说，取得的效果也不是特别突出，达不到人们的期望值。
而编译原理的每个阶段，从词法分析、语法分析，直到中间代码的生成，每个阶段都包含大量的算法。而这些算法过程较为复杂，比如语法分析中的LL(1)文法分析过程包含很多动作，求FIRST集和FOLLOW集，构成分析表，然后根据分析表来进行最左推导，涉及的数据结构包括堆栈、表等，而要形象地展示这些元素，使学生更加容易地接受这些知识，这是一项具有挑战的事情。
可视化技术[8]就是利用计算机图形学和图像处理技术，将数据转换成图形或图像后在屏幕上显示出来，并进行交互处理的理论、方法和技术。在编译算法的可视化中[3]，它将一个程序的数据、操作和语义提取出来并进行动态演示，利用诸如图形、文本、颜色、声音等工具来描述算法。这和清华大学严蔚敏教授编著的《数据结构》系列教材专门配备的数据结构演示算法有点类似。
1.2本课题研究的目的和意义
《编译原理》是计算机专业一门重要的课程，讲述了将高级编程语言翻译为机器易
1
编译原理经典算法的可视化实现 于执行的低级语言的编译过程和原理，而针对编译原理这门课程存在的知识和概念繁多算法抽象并且难于理解的情况，本课题实现了编译原理经典算法的可视化，将词法分析器的实现作为典型示范，也将LL(1)文法演示过程实现出来。为便于学生观察和分析编译过程，可以设置系统的播放速度，此系统不仅有利于帮助学生理解编译器的工作过程，原理及其具体实现方法，还有助于促进学生将大学所学的多种专业知识综合运用，促发他们的学习兴趣，将这一计算机学科中非常重要的基础课程学好。
1.3国内外研究现状
近年来，随着多媒体技术的兴起，在各种场合，我们可以见到每次演示编译原理里面的算法时，一般是借助于flash等这种动画演示文件，但是这种文件不能改变他的初始值，也看不到算法的执行过程。算法可视化技术的研究始于90年代。现在，算法可视化开始在国家级研究中心，高水平的大学，大公司的研究开发中心进行研究和应用。而随着PC功能的提高，各种图型显卡以及可视化软件的发展，可视化技术已经扩展到科学研究、医学、工程、军事、经济等各个领域。但是，市场上的编译原理教学辅助软件很少，国内的像北京航空大学教学用的PL/o编译系统的可视化跟踪软件，国外的如纽约大学计算机系的算法可视化项目。国内的大多数编译原理教学都是通过动画演示，它们只能观看算法执行过程的动画演示，并不能通过修改参数控制算法的演示过程，这样的软件并不能满足编译原理的需要。
1.4主要工作
本论文主要完成了以下工作：
(1)了解程序设计语言的编译过程，并对编译的词法分析阶段进行了详尽的分析和学习。
(2)学习目前存在的一些主要的词法分析器并了解其发展历程
(3)学习目前存在的词法分析自动生成工具，学习并用它生成词法分析器
(4)在VS2012开发平台下用C#完成词法分析的动态演示，并生成词法分析的单元组，实现LL(1)文法的实现。
1.5 本系统的设计思想
本系统是动态演示词法分析器，它的功能不只是得到一个分析结果，而且也要给出
2
编译原理经典算法的可视化实现 中间分析步骤。本系统也实现了LL(1)文法。
本软件中的词法分析器借助文本保存分析过程，不仅要在输出时给出分析结果，更为重要的是要输出中间分析步骤，方便查看分析结果，这样我们就会对编译过程有一个直观的认识，加深对编译原理中各种方法 的了解，激发我们的学习兴趣。
3
编译原理经典算法的可视化实现
2 词法分析概述
2.1 词法分析器的作用
词法分析作为编译的第一个阶段。它的主要任务是将读入的源代码组成字符流，并且将字符流中的词素按照其意义组织成序列。而对于每个词素，词法分析器产生并输出下述形式的词法单元（token），然后将这些词法单元传递给语法分析器：
在这个词法单元中，第一个分量token-name是在语法分析阶段所使用的一个抽象符号，第二个分量attribute-value则是指向源代码符号表中跟这个词法单元相关的条目。
下图中描述了词法分析器、语法分析器和符号表是如何工作的。首先词法分析器读入源程序并按照上面的表达式生成一个词法单元，在此交互过程中词法分析器需要与符号表进行交互以记录词法单元中的词素所对应的的符号表中的条目。之后词法分析器将生成的词法单元输入到语法分析器中，这一过程语法分析器需要调用getNextToken命令来从词法分析器中不断地读入词法单元，并且从符号表中读取其对应的id，再结合相应的文法，然后输出至语义分析。整个过程是一个不断循环读取并输出的过程。而这种交互我们通常将词法分析器做成语法分析器的协作程序或子进程。当语法分析器给词法分析器发出“取下一个标记“的命令时，词法分析器将从源程序中读入字符，这个过程将持续到识别出另一个记号。
词法单元源程序词法分 析器语法分析器输出至语义分析getNextToken符号表
图2.1 词法分析与语法分析的交互过程
4