编译演示系统的开发-计算机论文

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

 

指导教师   孙永新

 

 

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

 

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

 

 

Development of the Compiling Algorithm Animation System

 

Zhang Hao-sheng  College of Computer Science and Engineering

 

Faculty adviser  Sun Yong-xin

 

 

Abstract: It is very difficult to understand compiling algorithms because of their abstractness. Visualization technology can be used to make the learning process for these algorithms easier. A compiling algorithm animation system was designed to meet this need. The system, which consisted of web pages and Java Applet programs, implemented the basic algorithms in lexical analysis and grammatical analysis. The Java Applet programs simulated the algorithms by showing the dynamic data with graphs and tables. Web-based implementation makes the system easily deployed and accessible with a web browser like IE.

 

Keyword: Compiling Principle; Algorithm Animation; Lexical analysis; Grammatical analysis; Java Applet

 

1　前言

 

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

 

2　Java Applet概述

 

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

 

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

 

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

 

3　系统设计

 

3.1　总体设计

 

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

 

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的主要结构结构图如下：

 

 

 

图1　Automaton类结构图

 

 

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

 

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

 

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

 

Grammar的主要结构如下：

 

 

 

图2　Grammar类结构图

 

 

4.2　演示类结构说明

 

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

 

 

 

图3　BaseDemo类结构图

 

 

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

 

 

 

图4　演示效果图

 

 

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

 

 

 

图5　MinimizeDFADemo类结构图

 

 

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

 

 

 

图6　MinimizePane类对象图

 

 

 

图7　MinimizePane类结构图

 

 

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

 

5　总结

 

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

 

参考文献：

 

[1](美)Alfred V.Aho,Ravi Sethi,Jeffrey D.Ullman. 编译原理（Compilers: Principles, Techniques, and Tools）[M]. 北京:机械工业出版社，2003.8.

 

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

 

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

 

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

 

[5]百度百科.　Applet　http://baike.baidu.com/view/150834.htm.

 

[6]豆瓣douban.　什么是XHTML　http://www.douban.com/group/topic/2703758/.

 

[7]JFLAP.　JFLAP　http://www.jflap.org/.