编译原理经典算法的可视化实现 于执行的低级语言的编译过程和原理，而针对编译原理这门课程存在的知识和概念繁多算法抽象并且难于理解的情况，本课题实现了编译原理经典算法的可视化，将词法分析器的实现作为典型示范，也将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是一个词素，将被映射成词法单位
（2）赋值符号“=”是一个词素，经分析后会生成词法单元<=>。我们知道，这个词法单元不需要属性值，这里为在使用和阅读上方便，就把词素本身来作为抽象符号的名字。
（3）oldCount是一个词素，经分析后会生成词法单元
（4）“+”是一个词素，经分析后生成词法单元<+>.
（5）rate是一个词素，经分析后生成词法单元
6