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

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

摘要

在计算机教学中，编译原理这门课程在计算机科学中占有非常重要的地位，每个计算机专业的同学都需要学习它。而通过学习编译原理，能更好的了解高级程序语言的运行机制，并能编写出更加高效的程序。但是编译原理中的算法比较抽象，学习起来困难，而本系统能够动态演示编译原理中的词法分析阶段和语法分析阶段的LL(1)文法，而词法分析器将输出每个单词对应的二元组，这将有利于我们对词法分析器的理解，而LL(1)文法的动态演示使我们能够更好的理解并运用LL(1)文法中的各种算法。所以这种算法可视化技术能加深人们对程序行为的理解和认识，准确地了解和分析程序执行过程所反映的逻辑含义和功能。

本程序是在vs2012平台下用C#语言实现的。本程序界面简洁，能实现词法分析器的可视化和LL(1)文法的演示。

关键词：词法分析;LL(1)文法;可视化技术

I

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

THE VISUAL IMPLEMENTATION of CLASSIC ALGORITHM

of COMPILATION PRINCIPLE

Abstract

In the computer course,Compilation principle plays a very important role in computer science, each student who learns computer science has to learn it. Through the study of these principles, we can be more easy to understand the operation mechanism of various high-level language, and we can produce more efficient code. But the compilation principle is abstract, it’s very difficult to learn it. The system can dynamic demo the compilation principle of lexical analysis and LL (1) of grammar grammar analysis phase, and the lexical analyzer will output each word two tuples, which will help us to analysis of lexical understanding, LL (1) dynamic demo grammar enables us to better understand and use the LL (1) algorithms in the grammar. So this kind of algorithm visualization technology can help people to understand program behavior, understand the reflection accuratly and analysis of program execution logic meaning and function.

This procedure is used C# language under vs2012 platform. The program’s interface is simple, and it achieves visual of lexical analyzer and the demo of LL(1) algorithms.

Key words: lexical analysis; LL (1); visualization technology

II

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

1 绪 论…………………………………………………………………………………………………………………….1

1.1背景 .................................................................................................................. 1 1.2本课题研究的目的和意义 .............................................................................. 1 1.3国内外研究现状 .............................................................................................. 2 1.4主要工作 .......................................................................................................... 2 1.5 本系统的设计思想 ......................................................................................... 2 2 词法分析概述……………………………………………………………………………………………….…….4

2.1 词法分析器的作用 ......................................................................................... 4 2.2词法分析中的问题 .......................................................................................... 5 2.3 词法分析中的术语 ......................................................................................... 5 2.4 词法错误 ......................................................................................................... 7 2.5 词法分析生成工具 ......................................................................................... 8 3 词法分析器动态演示的设计与实现…………………………………………………………..…….10

3.1 词法分析器描述语言 ................................................................................... 10

3.1.1 Lex说明………………………………………………………………………………………………………..10 3.1.2 超前扫描操作………………………………………………………………………….………………….11 3.1.3 Lex编程………………………………………………………………………………………………………..12 3.2词法分析器动态演示的事件实现 ................................................................ 12 4 语法分析……………………………………………………………………………………………….…….…….17

4.1 语法分析的基本概念 ................................................................................... 17 4.2 语法分析的任务 ........................................................................................... 17 4.3 语法分析基础 ............................................................................................... 17 5 LL(1)文法可视化的设计与实现………………………………………………………………………23

5.1 程序界面的实现 ......................................... ...23 5.2 程序关键功能的实现。 ....................................... 25

III

编译原理经典算法的可视化实现 5.2.1 FIRST和FOLLOW………………………………………………………………………………..……25 5.2.2 预测分析表的构造 .................................. ...27

致谢…………………………………………………………………………………………………………………………29 参考文献………………………………………………………………………………………………………………….30 附录………………………………………………………………………………………………………………………….31 附件1 开题报告 附件2 译文及原文影印件

IV

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

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

编译原理经典算法的可视化实现 词法分析器是编译器读入源程序的阶段，所以它还要完成另外一些与之相关的辅助任务。一个任务是将源程序中的空格、注释、换行符、制表符过滤掉；而另一个任务是让编译器将发现的错误信息与之相对应的出错位置显示出来，这样就能方便源程序的编写。例如，我们在词法分析器中设置一个变量来记录遇到的换行符的个数，这样就能将行号与出错信息关联起来。而在另外一些编译器中，词法分析器会拷贝一份源程序，而且将出错信息加入其中，这样就能直接在源程序中看到出错信息。如果要求词法分析阶段有预处理功能，我们就需要源语言支持宏预处理器功能才行。

有时，我们将词法分析器分为两个阶段：第一阶段是扫描阶段，而扫描程序就负责完成一些简单的任务。另外一个阶段则是词法分析阶段。

2.2词法分析中的问题

把编译过程的分析阶段划分为词法分析和语法分析的原因如下：

（1）最重要的考虑是怎样才能简化编译器的设计。而词法分析和语法分析这一分离可以简化它们的设计。例如，如果把空白符和注释等的处理放在在语法分析而不是由词法分析器来完成时，这样将会使设计语法分析器变得十分复杂。因此，从语法分析中分离出词法分析会有利于编译器的设计

（2）能有效提高编译器的工作效率。我们将词法分析独立出来，这样就能构造专门的更有效的处理器。而编译时间的大部分消耗在源程序的读入并将其切分为记号方面。并采用专用的缓存技术来读取输入字符串和处理记号，这样可以有效地提高编译器的性能。

（3）增强编译器的可移植性。与设备有关的特征以及语言的字符集的特殊性的处理可以被限制在词法分析器中。而把词法分析和语法分析分开后，可以借助很多工具来自动地构造它们。如lex和yacc工具。

2.3 词法分析中的术语

在词法分析的讨论中，我们使用术语 ”模式“﹑“记号“﹑”词素“表示规定的含义。通常，在输入的一组字符串中可能会产生一样的记号来作为输出，而一个与该记号相关联的称为模式的规则来描述这个字符串组成的集合。这个模式被说成匹配该集合中的每个字符串，词素是源程序的字符序列，由一个记号的模式来匹配。把记号作为源语

5

编译原理经典算法的可视化实现 言文法的终结符，有记号的模式所匹配的词素表示源程序的字符串，即词法单位，而记号的返回通常是通过传递代表这个记号的证书来实现的。我们将模式定义为描述源程序中表示特定记号的词素集合的规则。我们仅仅通过词法单元来表示词素是不够的，还必须指明词素内容是什么类型的，不同类型的词素对应不同类型的模式，所以模式往往有比较复杂的数据结构。而词素就是从源程序中提取出的一个字符的序列，源程序中往往会表明一个数据的类型，就对应在词法分析时的模式，而源程序通过类型匹配之后被拆分成一个一个的字符串就是词素。

由于不同的词素可能有着相同的类型，也就是它们能被同一个模式所匹配，这种情况下后面的编译阶段就无法区分这些词素了，所以词法分析器必须向编译器的后续阶段提供有关被匹配词素的附加信息。例如，1和2都能和词法单位number的模式匹配，但是对于代码生成器而言，至关重要的是知道在源程序中找到了哪个词素。所以，词法分析器如果仅仅只返回词法单元的名字是不够的，在这种情况下，我们给每个词法单元外附件属性值，词法单元的名字主要实在词法分析过程中构造语法分析树之时用到，而这个属性值则将在将语法分析树翻译成计算能够理解的底层程序语言时才用到。

词法分析作用举例如下：

假设在源程序中有这样的一条语句：newCount=oldCount+rate/50

当语句中的字符经过词法分析器分析之后将会被组合成以下的词素，并会映射成下面的词法单位。

（1）newCount是一个词素，将被映射成词法单位,其中id表示的是标识符的抽象符号，而1就是指向其在符号表中所对应的条目。当然，这个1为方便说明，自己给定的。但是经过分析后这个值就是固定的。一个标识符的有关信息将被存放在该标识符所对应的符号表的条目中。

（2）赋值符号“=”是一个词素，经分析后会生成词法单元<=>。我们知道，这个词法单元不需要属性值，这里为在使用和阅读上方便，就把词素本身来作为抽象符号的名字。

（3）oldCount是一个词素，经分析后会生成词法单元，同样，这里的2就是该词素所对应的符号表中的条目。

（4）“+”是一个词素，经分析后生成词法单元<+>.

（5）rate是一个词素，经分析后生成词法单元,同理，其中3表示的就是指向

6

编译原理经典算法的可视化实现 号以及后面的一串字母或数字，随后扫描到逗号才能够判断出这是不是一个合法的赋值语句。但只有超前扫描符前面的D和O才是与模式匹配的词素的部分。经过成功的匹配，yytext指针指向字符D并且yyleng=2.我们要意识到这个简单的超前扫描模式使得当DO后面跟着一些无意义的符号（如7Q）时也会识别出DO，但它绝不会把做为标识符一部分的DO识别为一个词素。 3.1.3 Lex编程

我们在Windows平台下下载安装flex工具并设置好它的环境变量，而由于我们使用的flex是GNU的工具，所以为了方便，采用的C/C++编译器也采用GNU的编译器GCC，当然我们需要的也是Windows版本的GCC。

至此我们已万事俱备，我们可以开始编写Flex的源文件了。

（1）新建文本文件，将其更名为lex.l，当然这名字无特别含义，你可以自己命名，然后在这个文件中写入Flex的源代码。

（2）打开Windows的控制命令台，如图3.1所示，我们对lex.l运行Flex命令,这时我们就可以看到此时文件夹多了一个文件，此文件即是Flex生成扫描器的C代码。

图3.1 Flex编译过程

（3）然后我们用gcc来编译和链接C代码，这样就生成可执行的扫描器。 在这里，我们为了接下来能动态演示词法分析器，我们在模式后面定义了自己的动作，就是匹配完成后，将该单词的类型码和属性值输出到一个文件中。

3.2词法分析器动态演示的事件实现

3.2.1 词法分析器动态演示的执行事件

在这个词法分析器动态演示程序中，当我们点击执行按钮时，程序就会对Richtextbox中的内容生成txt文件，然后用词法分析器对这个文件中的单词进行词法分

12

编译原理经典算法的可视化实现 析，并将分析出的结果也存储到另一个txt文件。将Richtextbox中内容保存成文件是在fileSave()函数中实现的，在这里我们是将其保存在a.txt中，如下所示： private void fileSave() {

if (File.Exists(\)) File.Delete(\);

FileStream fs = new FileStream(\, FileMode.OpenOrCreate,

FileAccess.Write);

StreamWriter m_streamWriter = new StreamWriter(fs); m_streamWriter.Flush();

m_streamWriter.BaseStream.Seek(0, SeekOrigin.Begin); m_streamWriter.Write(rtSource.Text); m_streamWriter.Flush(); m_streamWriter.Close(); }

而将a.txt中的内容进行词法分析是在函数cmdExcute()中执行的。这些动作都是在程序的后台执行，创建一个进程执行cmd程序，然后在cmd中输入将文件进行词法分析的命令，执行完后，我们将进程关闭，而这种过程我们是不能见到其执行过程。cmdExcute()函数代码如下所示： private void cmdExcute() {

System.Diagnostics.Process lexProcess = new System.Diagnostics.Process(); lexProcess.StartInfo.FileName = \; lexProcess.StartInfo.UseShellExecute = false; lexProcess.StartInfo.RedirectStandardInput = true; lexProcess.StartInfo.RedirectStandardOutput = true; lexProcess.StartInfo.RedirectStandardError = true; lexProcess.StartInfo.CreateNoWindow = true; lexProcess.Start();

13

编译原理经典算法的可视化实现 lexProcess.StandardInput.WriteLine(\); lexProcess.StandardInput.WriteLine(\); lexProcess.Close(); }

在词法分析的动态演示过程中，我们需要在richtextbox中移动的光标来指示程序分析到何处，而这个光标是在changcolor()函数中实现的，代码如下所示： private void changecolor() {

rtSource.SelectionStart = i-1; rtSource.SelectionLength = 1; rtSource.SelectionColor = Color.Red; i++; }

当richtextbox中的光标移动时，此时光标每移动一个字母或符号时，那么程序中的DFA也要有相关的动作，而这些动作是在drawDirectly()函数中用GDI+实现的。在每次光标移动时，我们就把将要画线的起始坐标和终点坐标传给这给函数。其中我们可以通过speed这个变量设置画线的播放速度。 void drawDirectly(Point start, Point end) {

Graphics g = this.CreateGraphics(); int length = end.X - start.X; int ave = length / 5; int len = start.X;

Pen pline = new Pen(Color.Red , 5);

pline.DashStyle = System.Drawing.Drawing2D.DashStyle.Solid; while (len < end.X) {

g.DrawLine(pline, start.X ,start.Y , len + ave-5, end.Y); System.Threading.Thread.Sleep(speed);//参数以毫秒为单位

14

编译原理经典算法的可视化实现 len += ave; }

Pen pline1 = new Pen(Color.Orange, 5);

pline1.DashStyle = System.Drawing.Drawing2D.DashStyle.Solid; pline1.EndCap = System.Drawing.Drawing2D.LineCap.ArrowAnchor; g.DrawLine(pline1, start, end);

}

3.2.2 词法分析器动态演示的暂停事件

当词法分析器正在对richtextbox中的内容进行词法分析，这时如果我们要求程序暂停，我们就可点击程序界面上的暂停按钮，为了方便实现暂停事件，我们将执行按钮的事件定义为一个线程，并声明一个AutoResetEvent变量和一个time变量，

AutoResetEvent允许线程通过发信号互相通信，通常，此通信涉及线程需要独占访问的资源，这此程序中，通信资源就是time,。 首先我们声明一个时间间隔引发事件的计时器，

private System.Windows.Forms.Timer tm = new System.Windows.Forms.Timer(); AutoResetEvent autoEvent = new AutoResetEvent(false);

我们在执行事件中设置autoevent的waitone方法，然后我们每隔一秒就引发事件

tm.Interval = 1000;

tm.Tick += new EventHandler(tm_Tick);

接下来我们如果单击暂停按钮，我们就将计时器停止，则此时autoevent事件就不会开启，执行事件的这个线程也就暂停了，然后再单击继续按钮时，计时器继续计时，此时执行事件的这个线程又能开始运行了。

private void toolStop_Click(object sender, EventArgs e) {

if (flag) {

tm.Stop(); flag = false;

this.toolStop.Text = \继 续\;

15

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

tm.Start(); flag = true;

this.toolStop.Text = \暂 停\; } }

3.2 程序界面的实现

在本程序中在左边我们提供一个输入原文件的文本框，需要用到GDI+来画出词法分析器的DFA，整个程序的界面顶端都是按钮，我们用listview来给出词法分析的的结果，即二元组，整体的界面如下图所示：

图3.2 程序的界面

16

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

4 语法分析

4.1 语法分析的基本概念

所谓语法分析就是对我们给定的符号串α，通过一定的算法来判断它是否是某个文法的合法句子，换句话说，就是检查语法是否错误的过程。

语法分析包括自顶向下的推导和自底向上的归约这两类。这两种方法都是通过构造语法树来模拟这个分析过程。

而在本演示系统中，我们只研究自顶向下的LL(1)文法的演示。

4.2 语法分析的任务

语法分析器就是执行语法分析的程序，它是编译器的核心部分。而它的主要任务就

是识别不同的语法成分，判断其语句是否符合该语法，并为语法分析和代码生成做必要的准备。它是以词法分析器生成的单词来作为分析对象或输入。其基本的任务是根据语法规则，分析源程序的语法结构（分析如何将这些词法单元组成各种语法，如各种表达式，语句，函数等），并在分析过程中，还要检查语法的正确性。它的分析结果是识别出没有错误语法的语法成分。

4.3 语法分析基础

4.3.1 上下文无关文法

程序设计语言的许多结构都包含固有的递归结构，这种递归结构可以用上下文无关文法定义。上下文无关文法由终结符、非终结符、开始符号和产生式组成.

（1）通俗的说，终结符就是语言中用到的基本元素，一般不能再分，而终结符也是组成字符串的基本符号。而在讨论程序设计语言时，“记号”和“终结符”是同义词。 （2）非终结符是语法中用到的元素。而非终结符所规定的字符串集合将对定义该文法所产生的语言有所帮助。非终结符给语言强加一种层次结构，而这种层次结构对语法分析和翻译都是非常有用的。

（3）有一个非终结符将在文法中被指定为开始符号。而开始符号所表示的字符串

17

编译原理经典算法的可视化实现 集合就会是该文法所定义的语言。

（4）文法的产生式说明了非终结符和终结符组合成串的方式。每个产生式将由非终结符开始，后面跟随一个箭头，然后是非终结符和终结符组成的串。例如有下述产生式的文法： expr→expr op expr expr→( expr ) expr→-expr expr→id op→ + op→- op→* op→/ op→↑

在这个文法中，我们定义了简单的算术表达式，文法的终结符包括id、+、-、*、/、↑、( 和 )，文法的非终结符包括expr和op,开始符号是expr。 4.3.2推导和分析树

推导是描述文法定义语言过程的有用方法，其核心思想是把产生式看成重写规则，即用产生式右部的串来代替左部的非终结符。而事实上，推导可以给出自顶向下构造分析树过程的精确描述。例如，有这样的算术表达式文法：

E→ E + E| E * E | ( E )｜－E | id

其中，非终结符E表示一个表达式。产生式E→-E意味着前面带有减号的表达式仍然是表达式。这个产生式允许用-E代替出现的任何E，以便从简单的表达式产生更复杂的表达式。如果用-E代替单个E，这个动作可以描述为E错误！未找到引用源。 -E，我们可以将它读为“E推导出-E“。产生式E→（E）表示可用（E）代替在文法符号串中出现的任何E。如E*E错误！未找到引用源。 (E)*E或E*E错误！未找到引用源。E*(E). 在上面的文法中，我们从E开始，不断地（以任何顺序）应用产生式，得到一个替换序列。例如，E错误！未找到引用源。-E错误！未找到引用源。-(E)错误！未找到引用源。-(id),这个替换序列被称为从E到-（id）的推导。

更抽象地说，αAβ=>αγβ,如果A→γ是产生式，而且α和β是任意的文法符号的串。

18

编译原理经典算法的可视化实现 如果α1错误！未找到引用源。α2错误！未找到引用源。…错误！未找到引用源。αn，则说α1推导出αn。符号错误！未找到引用源。表示“一步推导“。通常错误！未找到引用源。表示”零步或多步推导“，因此，

（1）对任何串α，α错误！未找到引用源。α。

（2）如果α错误！未找到引用源。β，而且β错误！未找到引用源。γ，则α错误！未找到引用源。γ。

类似地，我们也用错误！未找到引用源。表示“一步或多步推导“。对于开始符号为S的文法G,我们可以用错误！未找到引用源。关系来定义G所产生的语言L(G)。L(G)中的字符串只包含G的终结符。当且仅当S错误！未找到引用源。w时，那么终结符w在语言L(G)中。终结符w称为G的句子。由上下文无关文法产生的语言称为上下文无关语言。如果两个文法产生同样的语言，则称这个文法等价。而对于开始符号为S的文法G,如果S错误！未找到引用源。α,则称α为G的句型，其中α可能含有非终结符。而句子则是不含非终结符的句型。

在推导的每一步都有两个选择，首先需要选择被替换的非终结符，然后再选择用于替换该非终结符的候选式。而在推导的过程中，我们考虑每一步都替代最左非终结符的推导，这样的推导叫做最左推导。而如果我们考虑的是每步推导都替代最右非终结符的推导，则这样的推导就叫最右推导，

分析树可以看成是推导的图形表示，但它不能显示出替代顺序的选择。分析树的叶节点用非终结符或终结符来标记，它们从左到右构成一个句型，称为树的边界或果实。

对于推导和分析树之间的关系，我们考虑任意的推导α1错误！未找到引用源。α2错误！未找到引用源。…错误！未找到引用源。αn，其中α1是单个非终结符A。对推导中

的每个句型αi，构造产生αi的分析树。该过程是对i的归纳。α1=A对应的分析树是标有A的单个节点，是归纳的基础。为了完成这种归纳，假设我们已经构造了产生αi-1=X1X2…Xk(Xi代

表一个非终结符或终结符)的分析树，假设

αi是用β=Y1Y2…Yr代替αi-1中的非终结符

αi-1应用产生式Xj→β,推导出αi=

Xj所产生的，即在推导的第i步中，对X1X2…Xj-1βXj+1…Xk。

如果L(G)中存在一个具有两棵或两棵以上分析树的句子，或者是L(G)中存在一个

19

编译原理经典算法的可视化实现 具有两个或两个以上最左（或最右）推导的句子，则称G是二义性文法。 而有些二义性文法是可以通过改写来消除二义性。

4.3.3消除左递归

如果文法G具有一个非终结符A使得对某个字符串α存在推导A错误！未找到引用源。Aα,则称G是左递归的。自顶向下语法分析法不能处理左递归文法，而下面的算法能够系统地消除文法中的左递归。 输入：无循环推导和ε产生式的文法G 输出：与G等价的无左递归文法

方法：对文法G应用图4.1中的算法。注意，得到的非左递归文法可能含有ε产生式。

1.以某种顺序排列非终结符A1,A2,? An; 2.for i:=1 to n do begin for j :=1 to i-1 do begin 用产生式Ai→δ1γ|δ2γ|?|δkγ代替每个形如Ai→Ajγ的产生式。 其中，Aj→δ1|δ2|?|δk是所有的当前Aj产生式； end 消除Ai产生式中的直接左递归end

图4.1 从文法中消除左递归的算法

该算法对于所有无循环推导和ε产生式的文法都有效，循环推导和ε产生式都可以系统地从文法中消除掉。 4.3.4 提取左因子

我们想要构造有效的自上而下的分析器，就要消除回溯。而提取左因子是一种有效

的消除回溯的文法变换。提取左因子的基本思想是：当不清楚应该用两个或多个选择中的哪一个来替换非终结符A时，可通过改写A产生式这种方法来推迟这种决定，然后直到看见足够多的输入并且能做出正确的选择为止。提取左因子方法的算法思想描述如图所示：

20

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

图4.2提取左因子算法思想描述

其中A’是一个新的非终结符。反复应用这种变换，直到任一非终结符都没有两个候选式具有公共前缀为止。

4.4 LL(1)文法

4.4.1 LL(1)文法定义

对文法G的句子进行确定的自顶向下语法分析的充分必要条件是，G的任意两个具有相同左部的产生式A→α|β满足下列条件：

（1）如果α、β均不能推导出ε，则 FIRST(α) ∩ FIRST(β) = Φ。

（2）α 和 β 至多有一个能推导出 ε。

（3）如果 β错误！未找到引用源。 ε，则 FIRST(α) ∩ FOLLOW(A) = Φ。 我们就将满足上述条件的文法称为LL(1)文法。 4.4.2 LL(1)文法概要

LL(1)文法中的第一个L表示的是程序输入符号串的扫描是从左向右的，第二个L表示的是最左推导，而1表示的是在分析过程中每一步推导的执行都要向前查看一个输入符号—当前正在处理的输入符号。我们应该注意到LL(1)文法不含左递归也不是二义性的，可以用确定的自顶向下语法分析方法来分析LL(1)文法的所有句子。

另外我们应该注意到，并不是LL(1)文法可以用来描述所有的语言，而且也不能判定某语言是否符合LL(1)文法，因为这样的算法是不存在的。换句话说，确定的自顶向下分析不能完成所有的上下文无关语言的分析，而这些就是LL(1)文法所产生的语言。

21

编译原理经典算法的可视化实现 另外，在上述LL(1)文法的条件中，要求：至多只有ε ∈ FIRST(α1)，ε ∈ FIRST(α2)，…ε ∈ FIRST(αn) 这些条件中的一个成立。

22

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

5 LL(1)文法可视化的设计与实现

5.1 程序界面的实现

在此程序中，我们需要设置文法的符号集，文法的表达式，然后就可以通过第4章中的算法来计算FIRST集合，FOLLOW集合并构造分析表，然后就可以对句子进行文法分析了。

文法符号集设置页面如图5.1所示：

图5.1 文法符号集设置

在文法符号集设置页面中，我们可以在此页面中输入符号集即终结符和非终结符，也可以直接加载文法的符号集，如果我们输入的符号集以后还要用到，我们也可以保存此符号集，这样以后就方便使用。

接下来我们就将文法的产生式输入，语言设置界面如图5.2所示，在此页面中，我们如果要添加表达式，则我们只要将表达式输入到右侧的文本框中，然后点击页面中的

23

编译原理经典算法的可视化实现 添加按钮，则可以看到表达式会在左侧的表达式列表中显示，当然，如果我们要删除表达式，只需选中表达式列表中的表达式，然后点击删除即可将表达式删除。在这里如果要将以前的列表加载进表达式列表中，单击加载列表然后选中文件即可，如果这些表达式以后还要用到，我们就可以单击保存列表即可保存。

图

5.2 语言设置界面

当我们要对字符串进行分析时，只需在如图5.3所示的字符串分析界面输入字符串,然后点击检测即可，页面的右侧是FIRST，FOLLOW和构造分析表的算法思想。

图5.3 字符串输入界面

24

编译原理经典算法的可视化实现 在界面的左侧展示了文法的分析结果，从这里我们可以清楚的看到文法的FIRST集和FOLLOW集，分析表。

5.2 程序关键功能的实现。

5.2.1 FIRST和FOLLOW

在对文法进行LL(1)文法分析时，我们需要构造文法G的分析表，而这需要两个与G有关的函数FIRST和FOLLOW，通过这两个函数我们可以填写G的分析表的表项。

如果α是任意的文法符号串，我们定义FIRST（α）是从α推导出的串的开始符号的终结符集合，即FIRST（α）={a|α错误！未找到引用源。a…,a是终结符}。如果α错误！未找到引用源。ε，则ε也属于FIRST（α）。

而计算文法符号X的FIRST（X）时，我们应用一下规则，直到没有终结符或ε可加到某个FIRST集合为止，它的算法描述思想如图5.4所示：

图5.4 求FIRST集合算法思想描述 算法的代码实现如下：

public ArrayList FinishFirst(ArrayList[] FirstList,Queue queueFirst) { //初始化标记数组 bool [] FirstFinished=new bool[FirstList.Length]; for(int i=0 ; i

25

编译原理经典算法的可视化实现 } for(int i=0 ; i0 && iOutException!=100) { iOutException++; string strQueue=queueFirst.Dequeue().ToString(); //获取队列元素相关信息 int iPos1=getLeftIndex(strQueue.Substring(0,1)); int iPos2=getLeftIndex(strQueue.Substring(1,1)); //假如右部的FIRST集已经求出,那么就把右部的FIRST集加入到左部FIRST if(FirstFinished[iPos2]) { ArrayList nextArray=FirstList[iPos2]; if(strQueue.Length==3) { FirstList[iPos2].Remove(\); } FirstList[iPos1]=Tools.AddArrayList(FirstList[iPos1],FirstList[iPos2]); if(strQueue.Length==3 && this.CheckEmptySymbol(strQueue.Substring(1,1))) { FirstList[iPos2].Add(\); } if(Tools.IsQueueElement(strQueue,0,1,queueFirst)==false) FirstFinished[iPos1]=true; } else { queueFirst.Enqueue(strQueue); } } ArrayList aryFirst=new ArrayList(); foreach (ArrayList arylst in FirstList) { aryFirst.Add(arylst); 26

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

}

}

return aryFirst;

我们定义FOLLOW（A）是包含所有在句型中紧跟在A后面的终结符a的集合，即FOLLOW（A）={a|S错误！未找到引用源。αAaβ,a是终结符}。这里需注意的是，在推导的某一时刻，在A和a之间可能有符号，但如果是这样，它们将推导出ε并消失。如果A是某个句型的最右符号，那么$属于FOLLOW（A）。

而计算所有非终结符A的后继符号集合FOLLOW(A),我们可以应用如下规则，直到每个FOLLOW集合都不能再加入任何符号或$为止，它的算法思想描述如图5.5所示：

图5.5 FOLLOW集合算法思想描述

5.2.2 预测分析表的构造

接下来，我们就借助FIRST和FOLLOW来构造预测分析表。而它的算法思想描述如图5.6所示：

图5.6 构造分析表算法思想描述

算法的实现如下：

27

编译原理经典算法的可视化实现 public Hashtable BuildAnalysis(ArrayList select) { Hashtable hashAnalysis= new Hashtable(); if(!IsLL1(select))return hashAnalysis; //用嵌套的循环来构建 for(int i=0 ; i

}

28

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

大学论文我选择的题目是编译原理经典算法的可视化实现。《编译原理》这门课程是计算机专业一门重要的专业基础课，计算机知识通过它相互联系。通过综合运用大学四年的专业知识，实现了编译阶段中的词法分析器和语法分析阶段LL(1)文法中各种算法的可视化。编译原理这门课程本身就比较抽象，所以开发出这样的系统，难度比较大，这就需要有耐心和毅力来学习知识，发现问题并解决问题。有时碰到我不能解决的问题，我就查资料，求助于互联网，当然我也向老师和同学请教。从这次论文设计的东西，相信会对我们日后的学习工作起到很大的指导作用。但也体现了我的种种不足，以后必当再接再厉。大学四年的生活一下子就要过完了，在这里，我感谢每位授课老师，，正是你们孜孜不倦的教诲使我能够顺利完成学业，你们的认真工作的态度是我们意识到人必须要求知欲，做什么事都应认真对待。当然我也要感谢陪伴我四年的同学们，他们给予了我无言的帮助。最后，我要感谢在这次毕业论文对我帮助很大的周书仁老师。周老师在这次毕设中给予我细心的指导，在毕设的每个阶段都监督我们的进度，正是他的这种认真的态度，才使得我们能够顺利完成这次毕业设计。

29

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

参考文献

[1]蒋立源，席慕宁.编译原理[M].西安：西北工业大学出版社，2005:10-40. [2]陈火旺，等.程序设计语言编译原理[M].北京：国防工业出版社，2000:20-60. [3]蒋秀锋，任志雄.可视编译器的设计与实现[J].计算机与现代化，2010(10),63-70. [4]李冬梅，施海虎.“编译原理”课程的教学研究与探索[J],计算机教育，2008(9):100-130. [5]赵国庆，黄荣怀，陆志坚.知识可视化的理论与方法[J],开发教育研究，2005(14):67-90. [6] JonL.Bentley and BrianW.Kernighan.A System for A lgorithm Animation,Com Puting Systems[C],Vol.4 No.l,Winter 1991.5一30. [7]

Cheng,J.Y.,Shen,Y.Z.,Ding,Z.L.

and

Mai,S.Q.Program

Animation

and

its

ImPlementation[C].Proc.5th National Academic Confereneeon CAD/CAM一Advances in CAD/CAM of China,Oct.1993:474一482.

[8]王强，冯雁.编译原理算法的形象教学[J],计算机教育，2010(17):120-140. [9]蒋秀峰，任志雄.可视编译器的设计与实现[J], 计算机与现代化，2010(11):60-80. [10] : Alfred V. Aho / Monica S.Lam / Ravi Sethi / Jeffrey D. Ullman著，赵建华，郑涛，戴

新宇译，编译原理[M]，机械工业出版社，2008.

[11]唐培和，徐奕奕，王日凤.基于可视化运行平台的数据结构课程教学[J],计算机教育，

2012(20):69-72.

[12]孙永新，闫大顺.动画演示与算法教学研究J],现代计算机（专业版），2009(18):89-130.

30

编译原理经典算法的可视化实现 附录 源程序

using System;

using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Text;

using System.Threading.Tasks; using System.Windows.Forms; using System.IO;

using System.Threading; namespace hust_liwangpeng {

public partial class mainForm : Form {

public bool flag = true; public int count=0; public int speed = 100; public int i = 1;

private System.Windows.Forms.Timer tm = new System.Windows.Forms.Timer(); AutoResetEvent autoEvent = new AutoResetEvent(false); private void CreateHeadersAndFillListView() {

ColumnHeader colHead;

colHead = new ColumnHeader(); colHead.Text = \单 词\; colHead.Width = 100;

this.listShow.Columns.Add(colHead); colHead = new ColumnHeader(); colHead.Text = \类型码\; colHead.Width = 100;

this.listShow .Columns.Add(colHead); colHead = new ColumnHeader(); colHead.Text = \属性值\; colHead.Width = 100;

this.listShow.Columns.Add(colHead);

31

编译原理经典算法的可视化实现 } public mainForm() { InitializeComponent(); CreateHeadersAndFillListView(); tm.Interval = 1000; tm.Tick += new EventHandler(tm_Tick); } void tm_Tick(object sender, EventArgs e) { autoEvent.Set(); } private void toolClear_Click(object sender, EventArgs e) { this.rtSource.Clear(); listShow.Items.Clear(); this.toolStop.Enabled = false; paint(); this.toolExcute.Enabled = false; this.toolRecovery.Enabled = false;

}

private void toolExit_Click(object sender, EventArgs e) {

System.Diagnostics.Process ps = System.Diagnostics.Process.GetCurrentProcess(); ps.Kill(); }

private void toolInput_Click(object sender, EventArgs e) {

string path = null;

if (openFile.ShowDialog() == DialogResult.OK) {

path = openFile.FileName;

using (StreamReader reader = File.OpenText(path)) {

32

编译原理经典算法的可视化实现 rtSource.Clear(); listShow.Items.Clear(); paint(); rtSource.Text = reader.ReadToEnd(); } } else {

return; }

}

private void rtSource_TextChanged(object sender, EventArgs e) {

rtSource.SelectionColor = Color.Black; if (this.rtSource.Text.Length == 0) {

this.toolExcute.Enabled = false; this.toolRecovery.Enabled = false; this.toolStop.Enabled = false; } else {

this.toolStop.Enabled = true; this.toolExcute.Enabled = true; this.toolRecovery.Enabled = true; } }

/*颜色改变*/

private void changecolor() {

rtSource.SelectionStart = i-1; rtSource.SelectionLength = 1;

rtSource.SelectionColor = Color.Red; i++; }

/*文件删除*/

33

编译原理经典算法的可视化实现 /*实现执行*/ private void fileSave() { if (File.Exists(\)) File.Delete(\); FileStream fs = new FileStream(\, FileMode.OpenOrCreate, FileAccess.Write); StreamWriter m_streamWriter = new StreamWriter(fs); m_streamWriter.Flush(); m_streamWriter.BaseStream.Seek(0, SeekOrigin.Begin); m_streamWriter.Write(rtSource.Text); m_streamWriter.Flush(); m_streamWriter.Close();

}

private void cmdExcute() {

System.Diagnostics.Process lexProcess = new System.Diagnostics.Process(); lexProcess.StartInfo.FileName = \; lexProcess.StartInfo.UseShellExecute = false; lexProcess.StartInfo.RedirectStandardInput = true; lexProcess.StartInfo.RedirectStandardOutput = true; lexProcess.StartInfo.RedirectStandardError = true; lexProcess.StartInfo.CreateNoWindow = true; lexProcess.Start();

lexProcess.StandardInput.WriteLine(\); System.Threading.Thread.Sleep(1000); lexProcess.StandardInput.WriteLine(\);

lexProcess.Close(); }

private void toolExcute_Click(object sender, EventArgs e) {

fileSave(); cmdExcute(); tm.Start();

this.toolExcute.Enabled = false; i = 1;

Thread thSeperate = new Thread(new ThreadStart(Seperate));

34

编译原理经典算法的可视化实现 listShow.Items.Clear(); thSeperate.Start(); // MessageBox.Show(thSave.ThreadState.ToString()); // MessageBox.Show(thSeperate.ThreadState.ToString()); } /*实现恢复*/ private void toolRecovery_Click(object sender, EventArgs e) { i = 1; paint(); listShow.Items.Clear(); this.toolExcute.Enabled = true ; } /*字符判别*/ private int judge( string str) { string str1, str2; int f=0; char[] charArray=new Char []{'('}; string[] strArray = str.Split(charArray); if (!str.Equals(\)) { str1 = strArray[0].Trim(); str2 = strArray[1].Trim(); f = int.Parse(str2); } if(str.Equals (\)) return 0; if ((258<=f&&f<285)||(f==297)) return 1; if(str.Equals (\)) return 3; return 2; } /*从文件中分离出二元组*/ private void Seperate() { 35

编译原理经典算法的可视化实现 string str1, str2,str3; string strLine; string[] strArray; char[] charArray=new Char []{' '}; while (!(File.Exists(\))) ; StreamReader sr = File.OpenText(\); str1 = null; str2 = null; str3 = null; while ((strLine = sr.ReadLine()) != null) { strArray = strLine.Split(charArray); str1 = strArray[0].Trim(); str2 = strArray[1].Trim(); str3 = strArray[2].Trim(); //数符 int length; if (judge(str2) == 0) { int j; length = str1.Length ; for (j = 0; j < length; j++) { changecolor(); if (j == 0) draw(4); else draw(5); autoEvent.WaitOne(); } changecolor(); draw(6); i--; inputListview(str1, str2,str3); 36

编译原理经典算法的可视化实现 } //标识符 if (judge(str2) ==1) { int j; length = str1.Length ; for (j = 0; j< length;j++) { changecolor(); if (j == 0) draw(1); else draw(2);

autoEvent.WaitOne(); }

changecolor(); draw(3); i--;

inputListview(str1, str2,str3); }

if (judge(str2) == 2) {

int j;

length = str1.Length ; for (j= 0; j < length; j++) {

changecolor();

autoEvent.WaitOne(); }

changecolor(); i--;

inputListview(str1, str2,str3);

}

if(judge(str2)==3) {

changecolor();

autoEvent.WaitOne(); }

37

编译原理经典算法的可视化实现 } sr.Close(); } /*输入二元组*/ private void inputListview(string str1,string str2,string str3) { ListViewItem item = new ListViewItem(); item.Text = str1; item.SubItems.Add(str2); item.SubItems.Add(str3); listShow.Items.Add(item); listShow.Update(); } /*画图*/ private void paint() { Graphics g = this.CreateGraphics(); Pen p = new Pen(Color.Black, 2); int x = rtSource.Location.X + rtSource.Width + 50; int y = rtSource.Location.Y; int width = this.Width - x - 100; int heigh = this.Height - listShow.Height - 220; Rectangle rect = new Rectangle(x, y, width, heigh); g.DrawRectangle(p, rect); //画S Rectangle rect1 = new Rectangle(x + 30, y + 45, 50, 50); g.DrawEllipse(p, rect1); Brush brush = new SolidBrush(Color.LawnGreen); Font font = new Font(\楷体GB-2312\, 25, FontStyle.Bold); g.DrawString(\, font, brush, x + 40, y + 55); //画A Rectangle rect2 = new Rectangle(x + 120, y + 45, 50, 50); g.DrawEllipse(p, rect2); Brush brush1 = new SolidBrush(Color.LawnGreen); Brush bru = new SolidBrush(Color.IndianRed); Font font1 = new Font(\楷体GB-2312\, 25, FontStyle.Bold); g.DrawString(\, font1, brush1, x + 130, y + 45); //画B Rectangle rect3 = new Rectangle(x + 200, y + 45, 50, 50); Rectangle rect31 = new Rectangle(x + 210, y + 55, 35, 35); g.DrawEllipse(p, rect3); 38

编译原理经典算法的可视化实现 g.DrawEllipse(p, rect31); Brush brush2 = new SolidBrush(Color.LawnGreen); Font font2 = new Font(\楷体GB-2312\, 25, FontStyle.Bold); g.DrawString(\, font2, brush2, x + 210, y + 55); //画C Rectangle rect4 = new Rectangle(x + 120, y + 140, 50, 50); g.DrawEllipse(p, rect4); Brush brush3 = new SolidBrush(Color.LawnGreen); Font font3 = new Font(\楷体GB-2312\, 25, FontStyle.Bold); g.DrawString(\, font3, brush1, x + 130, y + 150); //画D Rectangle rect5 = new Rectangle(x + 200, y + 140, 50, 50); Rectangle rect51 = new Rectangle(x + 210, y + 150, 35, 35); g.DrawEllipse(p, rect5); g.DrawEllipse(p, rect51); Brush brush5 = new SolidBrush(Color.LawnGreen); Font font5 = new Font(\楷体GB-2312\, 25, FontStyle.Bold); g.DrawString(\, font5, brush5, x + 210, y + 150); //画线 Pen pline = new Pen(Color.Black, 5); pline.DashStyle = System.Drawing.Drawing2D.DashStyle.Solid; pline.EndCap = System.Drawing.Drawing2D.LineCap.ArrowAnchor; //画s->A g.DrawLine(pline, x + 80, y + 70, x + 120, y + 70); g.DrawString(\, font, bru, x + 80, y + 35); //画s->c g.DrawLine(pline, x + 80, y + 70, x + 120, y + 155); g.DrawString(\, font, bru, x + 70, y + 90); //A->B g.DrawLine(pline, x + 170, y + 70, x + 200, y + 70); g.DrawString(\, font, bru, x + 170, y + 35); //C->D g.DrawLine(pline, x + 170, y + 165, x + 200, y + 165); g.DrawString(\, font, bru, x + 170, y + 130); //画A->A Point[] points = new Point[3]; points[0] = new Point(x + 124, y + 55); points[1] = new Point(x + 140, y + 25); points[2] = new Point(x + 165, y + 55); g.DrawString(\, font, bru, x + 100, y - 5); g.DrawCurve(pline, points); //画C->C Point[] point = new Point[3]; point[0] = new Point(x + 124, y + 150); 39

编译原理经典算法的可视化实现 point[1] = new Point(x + 140, y + 120); point[2] = new Point(x + 165, y + 150); g.DrawString(\, font, bru, x + 130, y + 90); g.DrawCurve(pline, point); } protected override void OnPaint(PaintEventArgs e) { Graphics g = e.Graphics; Pen p=new Pen(Color.Black ,2); int x = rtSource.Location.X + rtSource.Width + 50; int y=rtSource .Location .Y; int width = this.Width - x - 100; int heigh = this.Height - listShow.Height - 250; Rectangle rect = new Rectangle(x,y , width,heigh ); g.DrawRectangle(p, rect); //画S Rectangle rect1=new Rectangle (x+30,y+45,50,50); g.DrawEllipse(p, rect1); Brush brush = new SolidBrush(Color.LawnGreen); Font font = new Font(\楷体GB-2312\,25,FontStyle.Bold); g.DrawString(\, font, brush, x + 40, y + 55); //画A Rectangle rect2 = new Rectangle(x + 120, y + 45, 50, 50); g.DrawEllipse(p, rect2); Brush brush1 = new SolidBrush(Color.LawnGreen); Brush bru = new SolidBrush(Color.IndianRed); Font font1 = new Font(\楷体GB-2312\, 25, FontStyle.Bold); g.DrawString(\, font1, brush1, x + 130, y + 45); //画B Rectangle rect3 = new Rectangle(x + 200, y + 45, 50, 50); Rectangle rect31 = new Rectangle(x + 210, y + 55, 35, 35); g.DrawEllipse(p, rect3); g.DrawEllipse(p, rect31); Brush brush2 = new SolidBrush(Color.LawnGreen); Font font2 = new Font(\楷体GB-2312\, 25, FontStyle.Bold); g.DrawString(\, font2, brush2, x + 210, y +55); //画C Rectangle rect4 = new Rectangle(x + 120, y + 140, 50, 50); g.DrawEllipse(p, rect4); Brush brush3 = new SolidBrush(Color.LawnGreen); Font font3 = new Font(\楷体GB-2312\, 25, FontStyle.Bold); g.DrawString(\, font3, brush1, x + 130, y + 150); //画D 40

编译原理经典算法的可视化实现 Rectangle rect5 = new Rectangle(x + 200, y + 140, 50, 50); Rectangle rect51 = new Rectangle(x + 210, y + 150, 35, 35); g.DrawEllipse(p, rect5); g.DrawEllipse(p, rect51); Brush brush5 = new SolidBrush(Color.LawnGreen); Font font5 = new Font(\楷体GB-2312\, 25, FontStyle.Bold); g.DrawString(\, font5, brush5, x + 210, y + 150); //画线 Pen pline = new Pen(Color.Black, 5); pline.DashStyle = System.Drawing.Drawing2D.DashStyle.Solid; pline.EndCap = System.Drawing.Drawing2D.LineCap.ArrowAnchor; //画s->A g.DrawLine(pline, x + 80, y + 70, x + 120, y + 70); g.DrawString(\, font, bru, x +80, y + 35); //画s->c g.DrawLine(pline, x + 80, y + 70, x + 120, y + 155); g.DrawString(\, font, bru, x + 70, y + 90); //A->B g.DrawLine(pline, x + 170, y + 70, x + 200, y +70); g.DrawString(\, font, bru, x + 170, y + 35); //C->D g.DrawLine(pline, x + 170, y + 165, x + 200, y + 165); g.DrawString(\, font, bru, x + 170, y + 130); //画A->A Point[] points = new Point[3]; points[0] = new Point(x + 124, y + 55); points[1] = new Point(x + 140, y + 25); points[2] = new Point(x + 165, y + 55); g.DrawString(\, font, bru, x + 100, y-5 ); g.DrawCurve(pline, points); //画C->C Point[] point = new Point[3]; point[0] = new Point(x + 124, y + 150); point[1] = new Point(x + 140, y + 120); point[2] = new Point(x + 165, y + 150); g.DrawString(\, font, bru, x + 130, y +90); g.DrawCurve(pline, point);

//解释语句

Font fontt = new Font(\楷体GB-2312\, 10, FontStyle.Bold); Brush brush6 = new SolidBrush(Color.OrangeRed); g.DrawString(\单词\, fontt, brush6, x + 300, y +10); g.DrawString(\标识符\, fontt, brush6, x + 300, y +40); g.DrawString(\无符号整数\, fontt, brush6, x + 300, y +70);

41

编译原理经典算法的可视化实现 g.DrawString(\字母\, fontt, brush6, x + 300, y +100); g.DrawString(\数字\, fontt, brush6, x + 300, y +130); g.DrawString(\非字母数字\, fontt, brush6, x + 300, y +160); g.DrawString(\非数字\, fontt, brush6, x + 300, y +190); base.OnPaint(e); } protected override void OnResize(EventArgs e) { Invalidate(); base.OnResize(e); } //动态画线

void drawDirectly(Point start, Point end) {

Graphics g = this.CreateGraphics(); int length = end.X - start.X; int ave = length / 5; int len = start.X;

Pen pline = new Pen(Color.Red , 5);

pline.DashStyle = System.Drawing.Drawing2D.DashStyle.Solid; while (len < end.X) {

g.DrawLine(pline, start.X ,start.Y , len + ave-5, end.Y);

System.Threading.Thread.Sleep(speed);//参数以毫秒为单位 len += ave; }

Pen pline1 = new Pen(Color.Orange, 5);

pline1.DashStyle = System.Drawing.Drawing2D.DashStyle.Solid; pline1.EndCap = System.Drawing.Drawing2D.LineCap.ArrowAnchor; g.DrawLine(pline1, start, end); }

void draw2(Point []point) {

Graphics g = this.CreateGraphics(); Pen pline = new Pen(Color.Red, 5);

pline.DashStyle = System.Drawing.Drawing2D.DashStyle.Solid; pline.EndCap = System.Drawing.Drawing2D.LineCap.ArrowAnchor; g.DrawCurve(pline, point);

System.Threading.Thread.Sleep(speed); Pen pline1 = new Pen(Color.Orange, 5);

pline1.DashStyle = System.Drawing.Drawing2D.DashStyle.Solid; pline1.EndCap = System.Drawing.Drawing2D.LineCap.ArrowAnchor;

42

编译原理经典算法的可视化实现 g.DrawCurve(pline1, point); // g.DrawCurve(pline, point); } void draw4(Point start, Point end) { Graphics g = this.CreateGraphics(); Pen pline = new Pen(Color.Red, 5); pline.DashStyle = System.Drawing.Drawing2D.DashStyle.Solid; int avex = (end.X - start.X) / 5; int avey = (end.Y - start.Y) / 5; for (int i = 1; i <= 5; i++) {

g.DrawLine(pline, start.X, start.Y,start.X +(i*avex),start.Y+(i*avey)); System.Threading.Thread.Sleep(speed);//参数以毫秒为单位 }

Pen pline1 = new Pen(Color.Orange, 5);

pline1.DashStyle = System.Drawing.Drawing2D.DashStyle.Solid; pline1.EndCap = System.Drawing.Drawing2D.LineCap.ArrowAnchor; g.DrawLine(pline1, start, end);

}

43

本文来源：https://www.bwwdw.com/article/9y2r.html