编译演示系统的开发-计算机论文_计算机专业毕业论文-经管之家官网！

免费学术公开课,扫码加入

张豪生　计算机科学与工程学院

指导教师孙永新

摘要：由于编译原理的算法比较抽象，要理解它们很难。利用可视化技术可以使得这些算法的学习过程容易些。一个编译算法动画演示系统被设计出来以满足这方面的需要。该系统实现了词法分析和语法分析中的基本算法，由网页和JavaApplet程序构成。JavaApplet程序用图和表显示动态数据的方式模拟算法执行过程。由于采用了基于网页的方式实现系统，系统易部署且通过一个浏览器如IE即可访问。

关键词：编译原理　算法演示 词法分析 语法分析　JavaApplet

DevelopmentoftheCompilingAlgorithmAnimationSystem

ZhangHao-shengCollegeofComputerScienceandEngineering

FacultyadviserSunYong-xin

Abstract:Itisverydifficulttounderstandcompilingalgorithmsbecauseoftheirabstractness.Visualizationtechnologycanbeusedtomakethelearningprocessforthesealgorithmseasier.Acompilingalgorithmanimationsystemwasdesignedtomeetthisneed.Thesystem,whichconsistedofwebpagesandJavaAppletprograms,implementedthebasicalgorithmsinlexicalanalysisandgrammaticalanalysis.TheJavaAppletprogramssimulatedthealgorithmsbyshowingthedynamicdatawithgraphsandtables.Web-basedimplementationmakesthesystemeasilydeployedandaccessiblewithawebbrowserlikeIE.

Keyword:CompilingPrinciple;AlgorithmAnimation;Lexicalanalysis;Grammaticalanalysis;JavaApplet

1 前言

编译器是一个程序，它读入用某种语言（源语言）编写的程序并将其翻译成一个与之等价的以另一种语言（目标语言）编写的程序[1]。我们接触最多的高级语言，如JAVA、C++、VB等，要在计算机中运行都离不开编译器。世界上存在上千种源语言、上千种目标语言，同时也意味着存在上千种编译器。编译器虽然是多种多样的，但是它们所要完成的基本任务都是相同的。由于编译器的普遍性和重要性，学习编译器原理对深入理解计算机体系的意义就更为重大了。但是由于编译原理的理论及算法都比较抽象，要理解它们并不容易。但如果把这些算法的过程都以可视化技术[2-3]显示出来，就比较容易被理解了。想想看，如果把它作为辅助教学的，抽象的算法过程都以图形化的方式直接显示出来，学生就可以快速的理解算法的思想及过程，从而大大的提高学习效率以及教学效果。

2　JavaApplet概述

JavaApplet就是用Java语言编写的这样的一些小应用程序，它们可以直接嵌入到网页中，并能够产生特殊的效果。包含Applet的网页被称为Java-powered页，可以称其为Java支持的网页。

当用户访问这样的网页时,Applet被下载到用户的计算机上执行，但前提是用户使用的是支持Java的网络浏览器。由于Applet是在用户的计算机上执行的，因此它的执行速度不受网络带宽的限制。用户可以更好地欣赏网页上Applet产生的多媒体效果。

在JavaApplet中，可以实现图形绘制，字体和颜色控制，动画和声音的插入，人机交互及网络交流等功能。Applet还提供了名为抽象窗口工具箱（AbstractWindowToolkit，AWT）的窗口环境开发工具。AWT利用用户计算机的GUI元素，可以建立标准的图形用户界面，如窗口、按钮、滚动条等等。[5]

3 系统设计

3.1 总体设计

网页中提供演示程序算法的相关说明。演示程序利用了JFLAP[7]库中的一部分图形组件并使用JAVAApplet开发，最终嵌入到网页中。

3.2 网站设计

网站的所有的页面的宽度都是950像素，而演示程序的大小是900*600。网站分为五个栏目，分别是首页、词法分析、语法分析、帮助说明、相关链接。各栏目的内容如下：

首页：网站的总体说明，并提供演示的快捷链接。

词法分析：提供词法分析演示页的简要说明及链接。

语法分析：提供语法分析演示页的简要说明及链接。

帮助说明：提供演示程序及相关编译原理知识的说明。

相关链接：提供相关知识网站的链接。

3.3 演示程序设计

整个系统总共包括9个演示程序。分别为正规表达式生成NFA演示、NFA到DFA演示、DFA化简演示、正规表达式到最简DFA演示、蛮力分析演示、消除左递归公共左因子演示、LL(1)分析表构造演示、LR(0)分析表构造演示、SLR(1)分析构造演示。

4 详细设计

4.1 主要数据结构说明

系统主要使用到JFLAP的两个数据结构：Automaton和Grammar。

Automaton类是表示自动机数据的基类。系统中演示的是有限自动机，因此主要使用了它的派生类FiniteStateAutomaton。FiniteStateAutomaton与Automaton的功能基本上是一样的。

Automaton的主要结构结构图如下：

600)makesmallpic(this,600,1800);' src="file:///C:/DOCUME~1/ADMINI~1/LOCALS~1/Temp/ksohtml/wps_clip_image-32143.png" width="364" height="184" />

图1 Automaton类结构图

Automaton类中主要包含有一系列的Transition（弧）和State（状态），其中有一个初始状态和一组终止状态。类中还维护着两个关系：状态到以该状态为起点的弧的映射transitionFromStateMap；状态到以该状态为终点的弧的映射transitionToStateMap。

Grammar类是表示文法数据的抽象基类。主要使用了它的派生类ContextFreeGrammar（自由文法）。

Grammar类主要维护着一个Production（产生式）的列表、一个Variable（非终结符）的集合、一个Terminal（终结符）的集合和一个开始符号。所有的符号都以String（字符串）有存储。而产生式中的符号都在Variable或Terminal集合中。

Grammar的主要结构如下：

600)makesmallpic(this,600,1800);' src="file:///C:/DOCUME~1/ADMINI~1/LOCALS~1/Temp/ksohtml/wps_clip_image-15015.png" width="564" height="209" />

图2 Grammar类结构图

4.2 演示类结构说明

系统的所有的演示都继承于BaseDemo的演示基类。它的主要结构如下：

600)makesmallpic(this,600,1800);' src="file:///C:/DOCUME~1/ADMINI~1/LOCALS~1/Temp/ksohtml/wps_clip_image-18074.png" width="559" height="232" />

图3 BaseDemo类结构图

它维护着一个JTabbedPane类型的标签页对象来放置演示页对象。它派生出九个演示类，分别是REToNFADemo（正规表达式生成NFA演示）、NFAConvertDemo（NFA转DFA演示）、MinimizeDFADemo（DFA化简演示）、REToMinimizeDFADemo（正规表达式到最简DFA演示）、BruteParseDemo（蛮力分析演示）、TopDownOperationDemo（消除左递归公共左因子演示）、LL1TableCreationDemo（LL(1)分析表构造演示）、LR0TableCreationDemo（LR(0)分析表构造演示）、SLR1TableCreationDemo（SLR(1)分析表构造演示）。每个演示类就是一个演示小程序。而演示的效果如下图：

600)makesmallpic(this,600,1800);' src="file:///C:/DOCUME~1/ADMINI~1/LOCALS~1/Temp/ksohtml/wps_clip_image-32063.png" width="357" height="392" />

图4 演示效果图

这里以DFA化简演示来详细说明演示程序的结构。DFA化简演示以MinimizeDFADemo类来实现。它的主要结构如下：

600)makesmallpic(this,600,1800);' src="file:///C:/DOCUME~1/ADMINI~1/LOCALS~1/Temp/ksohtml/wps_clip_image-7493.png" width="468" height="290" />

图5 MinimizeDFADemo类结构图

该类拥有一个MinimizeDFADemo对象。MinimizeDFADemo类含有一系列的JButton按钮和一个EditorPane来提示生成DFA的功能。其中一个按钮可生成DFA识别符号串的演示对象FSAMatchPane。MinimizePane对象用于演示简化DFA的过程（图6），它的主要结构如图7所示：

600)makesmallpic(this,600,1800);' src="file:///C:/DOCUME~1/ADMINI~1/LOCALS~1/Temp/ksohtml/wps_clip_image-27469.png" width="481" height="321" />

图6 MinimizePane类对象图

600)makesmallpic(this,600,1800);' src="file:///C:/DOCUME~1/ADMINI~1/LOCALS~1/Temp/ksohtml/wps_clip_image-15637.png" width="518" height="312" />

图7 MinimizePane类结构图

该类含有MinimizeController和Minimizer对象。MinimizeController对象是MinimizePane的控制器，控制MinimizePane的各种行为；Minimizer用于简化DFA的对象。SelectionDrawer对象用于显示待简化的DFA；ControlPanel对象基本上就是一个工具栏；SelectTreeDrawer对象用于演示划分符号的集合的过程；而MinimizeNodeDrawer对象用于显示划分树的。

5 总结

本系统采用了JavaApplet+XHTML[6]的模式来编写，搭建了一个演示系统。系统采用了模块化设计方法，根据用户的需求及程序的应用与维护的易用性，将系统各个部分置于不同的模块当中，方便了程序的扩展与维护，同时建立了程序功能复用的基础。演示系统实现了算法计算过程及结果以图形化的形式输出，并根据用户的相互来演示。通过这种直观的演示方式，使得学习编译原理相关算法的效果有了很大的提高。该系统除了可用于辅助教学，还可以作为一个工具快速求解所涉及算法的结果。

参考文献：

[1](美)AlfredV.Aho,RaviSethi,JeffreyD.Ullman.编译原理（Compilers:Principles,Techniques,andTools）[M].北京:机械工业出版社，2003.8.

[2]刘孟仁，刘海庆.软件可视化技术及其应用研究[J].计算机应用研究,2002(6):26–28.

[3]袁国明，周宁.信息可视化和知识可视化的比较研究[J].科技情报开发与经济,2006(12):93–95.

[4]陈火旺，刘春林，谭庆平等.程序设计语言编译原理（第3版）[M].北京:国防工业出版社，2004.1.

「经管之家」APP：经管人学习、答疑、交友，就上经管之家！
免流量费下载资料----在经管之家app可以下载论坛上的所有资源，并且不额外收取下载高峰期的论坛币。
涵盖所有经管领域的优秀内容----覆盖经济、管理、金融投资、计量统计、数据分析、国贸、财会等专业的学习宝库，各类资料应有尽有。
来自五湖四海的经管达人----已经有上千万的经管人来到这里，你可以找到任何学科方向、有共同话题的朋友。
经管之家（原人大经济论坛），跨越高校的围墙，带你走进经管知识的新世界。
扫描下方二维码下载并注册APP