编译原理经典算法的可视化实现 编译原理经典算法的可视化实现
摘要
在计算机教学中，编译原理这门课程在计算机科学中占有非常重要的地位，每个计算机专业的同学都需要学习它。而通过学习编译原理，能更好的了解高级程序语言的运行机制，并能编写出更加高效的程序。但是编译原理中的算法比较抽象，学习起来困难，而本系统能够动态演示编译原理中的词法分析阶段和语法分析阶段的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