Toyl语法分析系统的设计与实现
学生姓名：郭少芬 指导教师：谷 波
内容提要 本文对编译原理做了简要的介绍，包括编译原理在计算机界的历史地位和作用，以及词法分析、语法分析在编译原理中的主要作用。详细的介绍了编译原理涉及的设计过程，并主要对本实验的重点--词法分析、语法分析以及语法树的构造和实现做了详细的介绍，并对其他过程做了简要的概述。对词法分析、语法分析、语法树的构造的具体实现过程做介绍，并附有关键算法的设计以及关键算法。通过本论文的工作，使得读者可以完全理解一个完整的Toyl语言语法分析系统的设计与实现过程。
关键词 编译原理；词法分析；语法分析；文法 1 引言
1.1编译原理简介
自从二十世纪50年代中期诞生世界上第一个高级语言编译器—Fortran语言编译器以来，编译技术不断进步，它已经成为计算机科学中发展最迅速、最成熟的一个重要分支。编译技术集中体现了计算机科学发展的重要成果与精华。ACM图灵奖是授予在计算机技术领域做出突出贡献的科学家的最高奖励，自1966年设立以来，程序设计语言、编译理论与方法的方面的得奖成果约占总数的1/3。可见，程序语言及其编译的研究在计算机科学中始终处于非常重要的地位。
通过编译原理的学习，一方面掌握和理解编译系统的结构、工作流程以及编译程序各组成部分的设计原理和实现技术，获得分析、设计、实现和维护编译系统的初步能力；另一方面，通过学习编译的理论和方法，提高学生对程序设计语言、操作系统、计算机原理和体系结构等课程知识的综合理解。对于将来从事编译系统设计工作的学生来说，编译原理课程将为其打下坚实的能力和知识基础；对于从事其它工作的学生，也能够提高他们对计算机系统总体的认识。
如果我们考究一下历史，就会发现很多被称为程序设计大师的人都是编译领域的高手，写出第一个在微型机上运行的Basic语言的比尔盖茨，设计出Delphi的Borland的“世界上最厉害的程序员”，SUN的JAVA之父，贝尔实验室的C++之父。
编译程序完成从源程序到目标程序的翻译工作，是一个复杂的整体的过程。从概念上来讲，一个编译程序的整个工作过程是划分成阶段进行的，每个阶段将源程序的一种表示形式转换成另一种表示形式，各个阶段进行的操作在逻辑上是紧密连接在一起的。一般一个编译过程划分成词法分析、语法分析、语义分析、中间代码生成，代码优化和目标代码生成六个阶段,这是一种典型的划分方法。事实上，某些阶段可能组合在一起，这些阶段间的源程序的中间表示形式就没必要构造出来了。我
1
将分别介绍各阶段的任务。另外两个重要的工作：表格管理和出错处理与上述六个阶段都有联系。编译过程中源程序的各种信息被保留在种种不同的表格里，编译各阶段的工作都涉及到构造、查找或更新有关的表格，因此需要有表格管理的工作；如果编译过程中发现源程序有错误，编译程序应报告错误的性质和错误发生的地点，并且将错误所造成的影响限制在尽可能小的范围内，使得源程序的其余部分能继续被编译下去，有些编译程序还能自动校正错误，这些工作称之为出错处理。 图1表示了编译的各个阶段。在本毕业设计中主要做的是词法分析和语法分析。 下面，我们从源程序在不同阶段所被转换成的表示形式来介绍各个阶段的任务。
标处理 源 程 序 词法分析 语法分析 语义分析 中间代码生成 中间代码优化 目标代码生成 目标代码 错误处理 图1 编译器的功能分解图
1.2、编译原理中词法分析、语法分析的作用和应用
词法分析阶段是编译过程的第一个阶段。这个阶段的任务是从左到右逐个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个单词(也称单词符号或符号)。词法分析的一般过程是：(1)语言的句法描述；(2)根据描述产生正则表达式；(3)根据正则表达式NFA----->DFA；(4)根据DFA来构造程序。词法分析作为编译原理的第一步，是非常重要的，它是所有后边工作的基础，通过词法分析将作为一个字符串的程序中的各个单词分离出来，并将他们分类，便于识别。 语法分析是编译过程的一个逻辑阶段。语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短语，如“程序”，“语句”，“表达式”等等.语法分析程序判断源程序在结构上是否正确.源程序的结构由上下文无关文法描述。它将词法分析的结果作为输入，依据文法规则，检查源程序的语法错误，当发现错误时输出相关信息，并尽可能地根据需要检查；语法分析在发现错误时，将有关错误单词的位置、错误类别和错误性质等信息显示给用户。而在后续的语义分析中又会以语法分析的结果为输入，因此语法分析是编译过程的核心部分，它的主要任务是按照和程序语言的语法规则，从由词法分析输出的源程序符号串中识别出各类语法分析成分，同时进行语法检查，为语义
2
分析和代码生成做准备。 2. 系统分析
根据前面的设计思想进行分析，系统流程图如图2所示，按照系统开发的基本观点对此软件进行分解，从内容上可对此语法分析系统作如下划分
(1）程序输入：设计一个程序可以读入一个含待分析源程序的TXT文件，具备分析的基本条件 (2）词法分析: 将读入的程序中所有单词抽取出来，分类
(3）语法分析: 将读入的程序按固定的文法分析其语法成分，并检查正误
(4）生成语法树:设计一个程序，可以使系统自动生成输入程序按照规定文法的一棵语法树 。
输入待分析程序
图2 系统流程图
3系统设计
通过运用编译原理的相关理论，自己制定一个词法规则、语法规则，实现一个小软件，这个软件可以输入一个程序，然后对这个程序做词法分析、语法分析，最后画出相应的语法树。所有这些都用C++设计辅以MFC使之可视化。
考虑到本程序做的是一个语法分析器，所以参照平时使用的VC++，VB等编程环境的界面，设计将做一个大的窗口，窗口有分为两个小窗口，上一个窗口中实现输入程序功能，下一个窗口实现分析结果输出功能。在菜单中加入一些自己想实现的功能项。
在界面设计中，由于本科阶段一直学习的是C++，而且一直都是在黑屏上操作，想借此机会，深入学习一下这个语言在界面设计中的一些功能，所以选用MFC类库来做界面。 3.1词法分析设计
词法分析阶段是编译过程的第一个阶段。这个阶段的任务是从左到右逐个字符地读入源程序，
3
分析程序 文法规则 生成分析结果 输出分析结果 对构成源程序的字符流进行扫描和分解，从而识别出一个个单词(也称 单词符号或符号)。这里所谓的单词是指逻辑上紧密相连的一组字符，这些字符具有集体含义。比如标识符用于表示变量名,是由字母字符开头，后跟字母、数字字符的字符序列组成的一种单词。保留字(关键字或基本字)是一种单词，此外还有算符，界符等等。例如某源程序片断如下：
begin var x,y:integer; read(y);x:=10;end #
词法分析阶段将构成这段程序的字符组成了如下19个单词序列：
(2) 保留字 (var) (9) 保留字(read ) (16)分号 (；) (3) 标识符 (x) (10)左括号 (（ ) (17)分号 (；) (4) 逗号 (，) (5) 标识符(y)
(11)标识符(y) (18)保留字 (end) (12)右括号( ）) (19)界符 ( #)
(1) 保留字 (begin) (8) 分号 (；) (15)数字 (10)
(6) 冒号 (：) (13)标识符 (x) (7) 保留字(integer) (14)赋值号 (:=)
可以看出，五个字符即b，e，g，i和n构成了一个称为保留字的单词begin，两个字符即∶和=构成了表示赋值运算的符号∶=这些单词间的空格在词法分析阶段都被滤掉了。
我们知道, 标识符用于表示变量名,可以很方便的使用id1,NUM表示x标识符和10这个数字的内部形式，那么经过词法分析后上述程序片断中的赋值语句x:=10则表示为id1∶=NUM。 3.2语法分析设计
语法分析是编译过程的第二个阶段。语法分析的任务是在词法分析的基础上将单词序列分解成各类语法短语，如\程序\，\语句\，\表达式\等等。一般这种语法短语，也称语法单位可表示成语法树，比如上述程序段中的单词序列：id1∶=10经语法分析得知其是PASCAL语言的\赋值语句\，表示成如图3所示的语法树
Var x,y:integer;经语法分析得知其是PASCAL语言的“声明语句”语法树如图4
4
赋值语句 标识符 := 表达式 ID(x) NUM (10)
图3 语句\∶=10\语法树 表达式 V ar : integer 标识符
ID(x)
标识符
@ ID(y) 图4 语句 \语法树
声明语句 ; 表达式 ， 表达式 表达式 在上图4中，在非文本框中的内容是叶节点，在词法规则中是终极符，文本框中的为非叶子节点，在此法规则中为非终极符。
词法分析和语法分析本质上都是对源程序的结构进行分析。但词法分析的任务仅对源程序进行线性扫描即可完成，比如识别标识符，因为标识符的结构是字母打头的字母和数字串，这只要顺序扫描输入流，遇到既不是字母又不是数字字符时，将前面所发现的所有字母和数字组合在一起而构成单词标识符。但这种线性扫描则不能 用于识别递归定义的语法成分，比如就无法仅用线性扫描去匹配表达式中的括号。
语法分析的功能是进行层次分析，把源程序的单词序列组成语法短语(表示成语法树)。依据的是语法规则。Pascal语言的赋值语句的规则为： （1）<赋值语句>::=<标识符>“:=”<表达式> （2）<标识符>::=id （3）<表达式>::=n
单词序列id1 ∶= 10之所以能表示成上图3的语法树，依据的是赋值语句和表达式的定义规则。 Pascal语言的声明语句的规则为：
5