可视化语法分析器设计论文.doc

可视化语法分析器设计可视化语法分析器设计 院（系）：计算机学院 专 业：计算机科学与技术 班 级：1401112 学 号：20013011456 姓 名： 指导教师： 2005年6月 沈阳航空工业学院毕业设计论文 -I- 摘摘 要要 编译程序是采用了编译技术将高级语言翻译成低级语言的翻译工具。编译程 序本身也是一种软件开发工具，有了它人们才能使用编程效率高的高级语言来编 写程序。 可视化语法分析器的设计同样采用了编译技术中最简单，最基础的知识，将 文件的编辑、词法分析、语法分析等功能联系在一起。读者通过阅读本文可以了 解到编译器设计的最新动态，及编译器的发展趋势，更可以了解到编译器的工作 原理及步骤。通过对可视化语法分析器的使用，可以提高用户对高级语言的认识， 更可以加深用户对编译器的理解。 可视化语法分析器采用 Delphi 环境开发，操作简单。通过直观的显示，用户 可以更加快捷的完成分析器开发的全部任务，避免了在各个开发工具间频繁切换。 大大方便了各类用户。 关键词： 编译 词法分析 语法分析 可视化 沈阳航空工业学院毕业设计论文 -II- Abstract The compiler is a translation tool that adopted to compile the technique to translate high-level language into the low level language. The compiler is also a kind of software development tool; the people can use the high level language of the programming efficiency higher to write procedure. The design of the visualization parser adopts to compile the technique equally in simple, the most basal knowledge, contact the edit, morpheme analysis of the document, and parse etc. function together. The reader pass read originally the text can understand the compiler to design of latest dynamic state, and the development trend of the compiler, even can understand the work principle and steps of the compiler. Pass the understanding to the usage of the visualization parser, can raise the consumer to the high level language, and even can deepen the consumer to the comprehension of the compiler. The visualization parser adoption Delphi environment development, operate in brief. Pass the display of keep the view, the consumer can complete all tasks of the development of analyzer more and fastly, avoiding between the each development tool multifarious cutover. Consumedly convenient each kind of consumer. Key words： Compile；Morpheme analysis；Parse analysis；Visualization 沈阳航空工业学院毕业设计论文 -I- 目目 录录 第第 1 章章 概概 述述 .1 1.1 编译器的发展状况.1 1.2 编译过程.1 1.3 项目功能及特点.2 第第 2 章章 文法及语言文法及语言 .4 2.1 文法的定义.4 2.1.1 文法.4 2.1.2 语言.6 2.2 单词符号的定义.7 第第 3 章章 分析器设计分析器设计 .8 3.1 可行性分析.8 3.2 设计方法.8 3.3 用户界面设计.10 第第 4 章章 系统实现系统实现 .12 4.1 编码语言的选择.12 4.2 算法实现.12 4.3 编码中的问题.18 第第 5 章章 测试测试 .19 5.1 测试方法.19 5.2 测试方案的设计.19 5.3 测试结果分析.20 结结 论论 .24 结结 束束 语语 .25 附附 录录 .26 参考文献参考文献 .27 致致 谢谢 .28 沈阳航空工业学院毕业设计论文 第 1 章 概述 -1- 第 1 章 概 述 1.1 编译器的发展状况编译器的发展状况 编译器是将一种语言翻译成为另一种语言的计算机程序。编译器将源程序编 写的程序作为输入，而产生用目标语言编写的等价程序。通常地，源程序为高级 语言，如 Pascal、C 或 C+，而目标语言则是目标机器的目标代码，也就是写在 目标机器中的用于运行的代码。 世界上第一个编译程序FORTRAN 编译程序是 20 世纪 50 年代中期研制成功 的。当时，人们普遍认为设计和实现编译程序是一件十分困难、令人生畏的事情。 经过 40 年的努力，编译理论与技术已经得到了迅速发展，现在已经形成了一套 比较成熟的、系统化的理论与方法，并且开发出了一些好的编译程序的实现语言、 环境与工具。在此基础上设计并实现一个编译程序不再是高不可攀的事情，编译 器的开发已越来越普遍。 编译器设计最近的发展包括：首先，编译器包括了更为复杂的算法的应用程 序，它用于推断和简化程序中的信息；这又与更为复杂的程序设计语言的发展结 合在一起。其中典型的有用于函数语言编译的 Hindley-Milner 类型检查的统一 算法。其次，编译器已越来越成为基于窗口的交互开发环境的一部分，它包括了 编译器、链接程序、调试程序以及项目管理程序。这样的 IDE 的标准并没有多少， 但是已沿着这一方向对标准的窗口环境进行开发了。尽管近年来对此进行了大量 的研究，但是基本的编译器设计在近 20 年中都没有多大的改变。 1.2 编译过程编译过程 编译程序的工作，从输入源程序开始到输出目标程序为止的整个过程，是非 常复杂的。但就其过程而言，它与人们进行自然语言之间的翻译有许多相近之处。 当我们把一种文字翻译成另一种文字，例如把一段英文翻译为中文时，通常需经 过下列步骤： 沈阳航空工业学院毕业设计论文 第 1 章 概述 -2- （1） 识别出句子中的一个个单词； （2） 分析句子的语法结构； （3） 根据句子的含义进行初步翻译； （4） 对译文进行修饰； （5） 写出最后的译文。 类似地，编译程序的工作过程一般也可以划分为五个阶段：词法分析、语法 分析、语义分析与中间代码产生、优化、目标代码生成。 第一阶段，词法分析。词法分析的任务是：输入源程序，对构成源程序的字 符串进行扫描和分解，识别出一个个的单词（亦称单词符号或简称符号） ，如基 本字，标识符、常数、算符和界符。 第二阶段，语法分析。语法分析的任务是：在词法分析的基础上，根据语言 的语法规则，把单词符号串分解成各类语法单位，如“短语” 、 “子句” 、 “句子” 、 “程序段”和“程序”等。通过语法分析，确定整个输入串是否构成语法上正确 的“程序” 。 第三阶段，语义分析与中间代码产生。这一阶段的任务是：对语法分析所识 别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码） 。这一阶 段通常包括两个方面的工作。首先，对每种语法范畴进行静态语义检查，如果语 义正确，则进行另一方面的工作，即进行中间代码的翻译。 第四阶段，优化。优化的任务在于对前段产生的中间代码进行加工变换，以 期在最后阶段能产生出更为高效（省时间和空间）的目标代码。优化的主要方面 有：公共子表达式的提取、循环优化、删除无用代码等等。 第五阶段，目标代码生成。这一阶段的任务是：把中间代码（或经优化处理 之后）变换成特定机器上的低级语言代码。这阶段实现了最后的翻译，它的工作 有赖于硬件系统结构和机器指令含义。 1.3 项目功能及特点项目功能及特点 可视化语法分析器集成开发环境是一个可视化的编译系统，也即为可视化的 编译器。利用编译器可以实现对高级语言的编译及执行。 沈阳航空工业学院毕业设计论文 第 1 章 概述 -3- 本项目便是要针对 PL/0（Pascal 语言的子集） ，设计一个用 Windows 环境下 运行的语法分析器。其功能基本包括： 1）有编译前端的功能（包括词法分析、语法分析及语义分析中间代码生成） ； 2）基本的文件及编辑功能，可用于对源文件的处理； 3）具有对各步骤作独立运行的功能，并对其运行的输入/输出结果给出直观、 友好的显示； 4）要求软件结构好，作到易修改，易扩充，易维护； 5）辅助功能：说明该软件及与分析相关的一些理论的说明等。 项目特点： 区别于传统的编译器，如：Turbo Pascal、Turbo c 等。可视化语法分析器 具有更好的操作界面，更直观的过程及结果显示。在该集成环境下即可完成分析 器开发的全部任务，避免了在各个开发工具间频繁切换。大大提高了编译的工作 效率，方便了各类用户的使用。 沈阳航空工业学院毕业设计论文 第 2 章 文法及语言 -4- 第 2 章 文法及语言 2.1 文法的定义文法的定义 2.1.1 文法文法 PL/0 语言采用 LL(1)分析方法（第一个 L 表示从左到右扫描输入串，第二个 L 表示最左推导，1 表示分析时每一步只需向前查看一个符号） ，其语法图和扩充 的 BNF 表示如下： 沈阳航空工业学院毕业设计论文 第 2 章 文法及语言 -5- 图 2.1 PL/0 的语法图 :=； 沈阳航空工业学院毕业设计论文 第 2 章 文法及语言 -6- :=； :=const,； :=； :=； :=|； :=var,； :=;； :=procedure； :=|； :=:=； :=+|-； :=； :=|()； :=+|-； :=*|/； :=|odd； :=|=； :=ifthen； :=whiledo； :=call； :=begin;end； :=read()； :=write(,)； :=a|b|c|d|.x|y|z； :=0|1|2|3|.8|9； 2.1.2 语言语言 由于 PL/0 语言是 Pascal 语言的子集，因此其在语言用法上也类似于 Pascal 沈阳航空工业学院毕业设计论文 第 2 章 文法及语言 -7- 语言。例如： CONST a=10;为基本的赋值语句，通过该语句，变量 x 被定义为整数 10； VAR b,c;为变量定义语句，通过该语句，字母 b,c 被定义为变量； READ(b), WRITE(c);为读和写语句（或输入、输出语句） ，通过该语句，可 以读取变量 b 及输出 c 的值，另外，当输出语句为 WRITE(by)时,输出的是字 符串 by； If A then B; 为条件语句，用户可通过该语句对条件进行定义，该语句含 义为：当条件 A 成立时执行 B 语句，否则，执行下一条语句； While D do E;为循环语句，该语句的含义为：当条件 D 满足时，执行 E 语 句，并继续判断 D 条件是否满足，直到当 D 不满足时，退出循环语句，并执行下 一条语句； BEGIN END; 为语句部分的开始和结束, 语句部分以 BEGIN 为开始, 以 END 为结束, 中间是一些用分号分开的语句； PROCEDURE lay;为过程定义语句,其中,lay 为过程名称,过程的内容由基本语 句组成。过程的调用由 CALL 语句完成,格式为 CALL lay； 2.2 单词符号的定义单词符号的定义 终结符号：所谓终结符号乃是组成语言的基本符号，从语法分析的角度来看， 终结符号是一个语言的不可再分的基本符号。 PL/0 文法中终结符号有: const,var,procedure,begin,if,call,then,odd,do,while,read,write,end,标 识符，无符号整数，运算符+，-，*，/，关系运算符=，,0 do 将 do 改为 then Begin Call swap; Call mod End; g: =y; m: =a*b/g; 改为 g=y Write (g, m); 去掉右括号 END. （2）对程序做部分改动（如中所改）并进行调试。 5.3 测试结果分析测试结果分析 （1）对于上面给出的测试程序，系统分析后给出的结果如下： 1JMP 0 22 ：无条件转移到指令 22，即无条件转移到主程序； 2JMP 0 3：无条件转移到指令 3，即无条件转移到过程； 3INT 0 4 ：数据栈栈顶指针增加 4； 4LOD 1 3 ：取相对地址为 3，层次差为 1 的变量放到数据栈栈顶； 5STO 0 3 ：将数据栈栈顶内容存入变量，其中相对地址为 3，层次差为 0； 6LOD 1 4 ：取相对地址为 4，层次差为 1 的变量放到数据栈栈顶； 7STO 1 3 ：将数据栈栈顶内容存入变量，其中相对地址为 3，层次差为 1； 8LOD 0 3 ：取相对地址为 3，层次差为 0 的变量放到数据栈栈顶； 9STO 1 4 ：将数据栈栈顶内容存入变量，其中相对地址为 4，层次差为 1； 10JMP 0 0 ：无条件转移到指令 0，即无条件结束过程； 11JMP 0 12 ：无条件转移到指令 12，即无条件转移到过程； 12INT 0 3 ：数据栈栈顶指针增加 3； 沈阳航空工业学院毕业设计论文 第 5 章 测试 -22- 13LOD 1 3 ：取相对地址为 3，层次差为 1 的变量放到数据栈栈顶； 14LOD 1 3 ：取相对地址为 3，层次差为 1 的变量放到数据栈栈顶； 15LOD 1 4 ：取相对地址为 4，层次差为 1 的变量放到数据栈栈顶； 16OPR 0 5 ：执行运算（5 代表执行除法运算）并将运算结果存入数据栈栈 顶； 17LOD 1 4 ：取相对地址为 4，层次差为 1 的变量放到数据栈栈顶； 18OPR 0 4 ：执行运算（4 代表执行乘法运算）并将运算结果存入数据栈栈 顶； 19OPR 0 3 ：执行运算（3 代表执行减法运算）并将运算结果存入数据栈栈 顶； 20STO 1 3 ：将数据栈栈顶内容存入变量，其中相对地址为 3，层次差为 1； 21JMP 0 0 ：无条件转移到指令 0，即无条件结束过程； 22INT 0 7 ：数据栈栈顶指针增加 7； 23LIT 0 45 ：取常量 45 放入数据栈栈顶； 24STO 0 3 ：将数据栈栈顶内容存入变量，其中相对地址为 3，层次差为 0； 25LIT 0 27 ：取常量 27 放入数据栈栈顶； 26STO 0 4 ：将数据栈栈顶内容存入变量，其中相对地址为 4，层次差为 0； 27CAL 0 12 ：调用过程（入口指令地址为 12，层次差为 0） ； 28LOD 0 3 ：取相对地址为 3，层次差为 0 的变量放到数据栈栈顶； 29LIT 0 0 ：取常量 0 放入数据栈栈顶； 30OPR 0 9 ：执行运算（9 代表执行比较运算）并将运算结果存入数据栈栈 顶； 31JPC 0 35 ：条件转移到指令地址 35（即结束循环） ，当数据栈栈顶的内容 为 0（假时） ，转移到指令 35，即结束循环。否则继续向下执行； 沈阳航空工业学院毕业设计论文 第 5 章 测试 -23- 32CAL 0 3 ：调用过程（入口指令地址为 3，层次差为 0） ； 33CAL 0 12 ：调用过程（入口指令地址为 12，层次差为 0） ； 34JMP 0 28 ：无条件转移到指令 28，即执行循环过程； 35LOD 0 4 ：取相对地址为 4，层次差为 0 的变量放到数据栈栈顶； 36STO 0 5 ：将数据栈栈顶内容存入变量，其中相对地址为 5，层次差为 0； 37LIT 0 45 ：取常量 45 放入数据栈栈顶； 38LIT 0 27 ：取常量 27 放入数据栈栈顶； 39OPR 0 4 ：执行运算（4 代表执行乘法运算）并将运算结果存入数据栈栈 顶； 40LOD 0 5 ：取相对地址为 5，层次差为 0 的变量放到数据栈栈顶； 41OPR 0 5 ：执行运算（5 代表执行除法运算）并将运算结果存入数据栈栈 顶； 42STO 0 6 ：将数据栈栈顶内容存入变量，其中相对地址为 6，层次差为 0； 43LOD 0 5 ：取相对地址为 5，层次差为 0 的变量放到数据栈栈顶； 44OUT 0 0 ：输出数据栈栈顶的内容（g 的值） ； 45LOD 0 6 ：取相对地址为 6，层次差为 0 的变量放到数据栈栈顶； 46OUT 0 0 ：输出数据栈栈顶的内容（m 的值） ； 47JMP 0 0 ：无条件转移到指令 0，即无条件结束程序； （2）对于错误输入的程序，系统的分析为： CONST a=45,b=27; VAR x, y, g, m * 5（漏了“,“或“;“） Procedure swap; Begin Temp: =x; * 11（标识符未说明） 沈阳航空工业学院毕业设计论文 第 5 章 测试 -24- x: =y; y: =temp * 11 end; Procedure mod; x: =x-x/y*y; Begin x: =a; y: =b; call mod; while x0 then * 18（应该为 do） begin call swap; call mod end; g =y; m: =a*b/g; * 13（应为赋值运算符:=） Write (g, m; * 22（漏右括号） END. 沈阳航空工业学院毕业设计论文 结 论 -25- 结 论 本系统的优点和特点： 1界面友好，操作简单。用户可根据菜单项的提示进行具体操作，并可获 得直观的结果显示。 2辅助功能齐全，用户可通过文件功能选项快速编辑源程序，并对用户的 调试步骤及结果加以保存防止了重要数据的丢失。 系统对语法分析的方法及形式定义明确，运用了最简单、最基本的语法分析器设计方案。 沈阳航空工业学院毕业设计论文 结束语 -26- 结 束 语 通过各个阶段的学习和设计，在老师的要求和指导下，可视化语法分析器设 计任务基本上完成。它的功能要求基本都得以实现，能够完成对用户所编辑的源 文件进行语法分析的要求。在编辑器模块中能实现对用户的源文件及运行结果的 保存调用等编辑，在词法分析及语法分析模块中能实现对源文件进行词法分析及 语法分析并给出直观显示。 没有量的积累，不会有质的飞跃。本次设计运用编译技术及 Delphi 环境得 以实现。从而也使我对这方面的知识经历了从认识、学习到运用、提高的一个过 程，在设计中遇到很多困难，通过老师指导和学生帮助，本次设计任务终于圆满 完成。 当然，由于自身程序设计水平有限，整个系统还不够完善，存在一些问题。 例如：系统运行不够安全，对源程序的输入格式有严格的要求，小小的输入错误 可能会导致程序错误运行又无法调试。 沈阳航空工业学院毕业设计论文 附 录 -27- 附 录 错误提示信息对照： 1: 常量说明中的“=“写成了“:=“ 2: 常量说明中的之后不是数字 3: 标识符的后继符号不是“=“ 4: CONST、VAR、PRCEDURE 的 后记符号不是标识符 5: 漏了“,“或“;“ 6: ;后继符号不正确 7: 应该为语句 8: 程序体内语句部分后的符号不 正确 9: 程序没有以“.“结尾 10: 语句之间缺少“;“ 11: 标识符未说明 12: 不可向常量或过程赋值 13: 应为赋值运算符:= 14: call 后应为标识符 15: 不可调用常量或变量 16: 应为 then 17: 应为“;“或 end 18: 应为 do 19: