论文

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

（1）<声明语句>::=Var <表达式>“:” “integer”“;” （2）<表达式>::=<标识符><表达式> （3）<表达式>::=“,”<表达式> （4）<标识符>:: =id

（5）<表达式>::=@（空操作）

单词序列Var x,y:integer;之所以能表示成如上图4的语法树，依据的是赋值语句和表达式的定义规则。 4. 系统实现

4.1开发工具的选用及介绍

MFC的主要优点是可以用物件导向的方法来使用Windows API，以及应用程式开发的便捷。 MFC将很多应用程序开发中常用的功能自动化，并且提供了文档框架检视结构和活动文档这样的便于自订的应用程序框架。同时，在Visual C++内部也内建了很多对MFC的例如类这样的支援以减少软件开发的时间，使用类可以生成从hello world这样的简单程序到活动文档服务器这样的复杂程序。MFC的消息响应机制也避免了使用性能较低的庞大虚拟函数式表。

MFC,微软基础类(Microsoft Foundation Classes),实际上是微软提供的,用于在C++环境下编写应用程序的一个框架和引擎,VC++是Windows下开发人员使用的专业C++ SDK(SDK, Standard Software Develop Kit,专业软件开发平台),MFC就是挂在它之上的一个辅助软件开发包,MFC作为与VC++血肉相连的部分，MFC同BC++集成的VCL一样是一个非外挂式的软件包,只不过MFC类是微软为VC++专配的。

MFC是对Windows API的封装，大大简化了我们的工作；学VC主要就是要学MFC，大约有100多个类，但常用的也就二三十个。应该像背4级单词一样将这些常用类搞懂；当然不需要死记，通过看帮助、看例子、动手练习就可学会它们；而且，并非每个类内部的所有函数都要学会，要日积月累。如果真的想成为高手，做个笔记本把自己认为重要的类、函数记下来，随时学习，也是很好的突击方法。 4.2本实验实现

在我的毕业设计中，具体实现的是一个Toyl语言语法分析系统的设计与实现，主要的工作有：设计一个词法规则，规定什么样的单词是可接受的即正确的，并将这些正确的单词归类，然后设计一个文法规则，分析输入的程序是否符合所规定文法的规则，如不符合做错误处理。实现步骤如下： 4.2.1词法分析

设计词法规则：确定有如下的单词集和相应的Token表示：

（1）标示符（x,.....） (ID ,\ （2）正整数（10,...） (NUM ,\ （3）加号（+） (ADD ,\ （4）分号（;） (SEMI ,\ （5）冒号（:） (COLON ,\ （6）赋值号（:=） (ASS ,\ （7）小于号（<） (LT ,\ （8）小于等于号（<=） (LE ,\

6

（9）保留字（begin） (保留字 ,\

自动机如下：

L D D L other D other //（标示符和保留字） //（正整数） ?+? //（加号）

?*? //（乘号） ?:? =

?;? //（分号）

?(? //（左括号） ?)? //（右括号） ?#? //# '\\0'

//（结束）

图 5 根据词法规则做出的自动机

注释： 表示结束， 表示中间状态 表示起始状态。自动机以外的情况为出错状态。识别正误单词并进行分类的算法实现如下： While(程序没结束) {

接收下一个字符；

While(如果是空格或tab键或换行键） 接收下一个字符； While (1) {

If(是单词) 退出； Else if(是数字) 退出； Else if（是+号） 退出； Else if（是-号） 退出； Else if（是；号） 退出；

//（赋值号）

7

Else if（是：号） 退出； Else if（是:=号） 退出； Else if（是<号） 退出； Else if（是<=号） 退出； Else if（是保留字） 退出； } }

4.2.2语法分析

设计文法规则：

（1）prog------>begin SL end # （16）P1------>@ （2）SL------>S S1 （17）P------>( E ) （3）S1------>S S1 （18）P------>ID （4）S1------>@ （19）P------>NUM （5）S------>ID := E ; （20）addop------>+ （6）S------>read ( IL ) ; （21）addop------>-

（7）S------>write ( EL ) ; （22）S------>if N then S ELSE （8）IL------>ID I1 （23）N------>ID < NUM （9）I1------>, ID I1 （24）ELSE------>else S （10）I1------>@ （25）ELSE------>@ （11）EL------>E E1 （26）S------>var M : integer ; （12）E1------>, E E1 （27）M------>ID Q （13）E1------>@ （28）Q------>, M （14）E------>P P1 （29）Q------>@ （15）P1------>addop P P1

（30）S------>@

手工分析得到该文法非终极符的First和Follow集如表1

8

表1 First和Follow集

First Follow prog begin # SL id,read,write,if,other end S id,read,write,if,other id,read,if,other,end S1 id,read,write,if,other end E (,id,n id,read,if,other,end,; IL id, ) EL (,id,n ) I1 , ), , E1 , ) , P (,id,n +，-，），； P1 +，- ),; addop +，- (,id,n ELSE else id,read,write,if,other

同时可得该文法的Predict集表，如表2所示

表2 文法的Predict集表 Predict(P) Predict集 First(begin SL end) begin First(S S1) id read write if Var First(S S1) id read write if Var (First(@)-@)uFollow(S1) end First(id:=E;) id First(read(IL);) read First(write(EL);) write First(id I1) id First(, id I1) , (First(@)-@)uFollow(I1) ) First(E E1;) id n ( First(,E E1;) , (First(@)-@)uFollow(E1) ) First(P P1;) id n ( First(addop P P1;) (First(@)-@)uFollow(P1) , ; ) First((E)) ( First(id) id First(num) n First(+) +

9

First(-) First(if N then S ELSE) First(ID < NUM) First(else S) (First(@)-@)uFollow(ELSE) First(var M : integer ;) First(ID Q) First(, M) (First(@)-@)uFollow(Q) (First(@)-@)uFollow(S) - if id else id read write if Var Var id , : id,read,if,other,end

同时可得LL分析表，如表3所示

表3 LL分析表 prog SL S S1 E IL EL I1 E1 P P1 addop ELSE id num := 2 5 5 14 8 11 18 25 14 11 19 , 9 12 ; 11 + - ( 14 11 17 ) begin end read 10 13 16 1 4 2 6 3 25 write 2 7 3 25 # if other else 2 22 3 25 2 23 3 25 24 16 16 15 15 20 21

输入程序于文法进行匹配的算法，实现如下：

注释：st2是从符号栈中弹出来的一个符号，可能是终极符也可能是非终极符； Match为整型数，若接收的Token与st2匹配则置为1；

此函数只是一个大概思想，需要不断重复调用，从第一个文法prog开始，到完全匹配或出错处理为止。

if(st2等于Token的seman或者st2等于Token的classs) {match赋值为1;} //此时st2为终极符； Else if //即为st2为非终极符； {

if(st2等于分析表第一列上的某个非终极符) {

10

比较一下此时的Token的seman或classs是否与该终极符对应的该行上的某一个 非终极符相等，若有一个且只有一个相等，取出该行该列的数，赋值给 index， 则将该数对应的第index文法放进符号栈；

}

Else 为出错； }

Else 否则出错；

4.2.3画出一颗语法树

画一棵语法树的具体算法实现： While(输入的待分析程序没有结束) {

接收进一个token;

从符号栈中弹出一个符号赋值给st2；

弹出当前st2的层数，以及他的父节点有几个子节点和它是第几个子节点； 弹出父节点的坐标；

根据上述信息计算出st2点的坐标， 并将st2 和他的父节点连接起来； 接收下一个token； }

在这个实现中主要用到9个堆栈，五个是第一次画树时使用的，剩下四个栈是在窗口重绘时使用的。 例：输入下列程序： begin

var x,y:integer; read(y); end #

画出的树如下图6所示

11

prog : M ; integer ； S S1 Var ： ID Q read ( IL ) ; @ , I D I1 M @ ID Q @ S S1 Begin SL end # 图6 语句“begin var x,y:integer;read(y);end” 语法树

4.3界面设计与重点代码的设计

（1）首先将覆盖在主框架上的CEditView分为两个视类，使得在第一个类中输入程序，第二个

视中输出分析结果

BOOL CMainFrame::OnCreateClient(LPCREATESTRUCT lpcs, CCreateContext* pContext) {

// TODO: Add your specialized code here and/or call the base class //创建一个静态分栏窗口，分为二行一列

if(m_wndSplitter1.CreateStatic(this,2,1)==NULL)

return FALSE;

// 将CCuteFTPView连接到0行0列窗格上

m_wndSplitter1.CreateView(0,0,RUNTIME_CLASS(CCompileView),CSize(100,100), pContext);

m_wndSplitter1.CreateView(1,0,RUNTIME_CLASS(CView2),CSize(100,100), pContext);

12

}

// 将CView4连接到0行1列 return TRUE;

//return CFrameWnd::OnCreateClient(lpcs, pContext);

图7 运行出来的界面

如图7中，上边一个文本框为第一个view,其中输入要分析的源程序，下边的文本框为第二个view，在其中输出分析结果。

（2）点击各个菜单项即可运行相应功能并能做出相应结果

例如输入一段程序后，点击词法分析的各个键的结果

图9 词法分析的功能键

（3）点击语法分析的各个键的结果

图10 语法分析各个功能键

4.4 实现环境 （1）软件环境 Windows XP Visual studio C++6.0 （2）硬件环境

Pentium III 450以上的CPU处理器，64MB以上的内存，200MB的自由硬盘空间、CD-ROM

驱动器、能支持24位真彩色的显示卡。

13

5 结束语

本程序基本实现的功能有：输入一个程序，按照规定的文法可以进行词法与语法分析并构造出一棵语法树，可以在分析的同时检查出一些错误，如果是一些严重的错误，程序就直接结束。 下面再谈一下需要继续改进的地方

（1）系统的设计有些欠妥当，因为文法已经写进程序中，只能分析固定文法的程序。解决办法：编一个程序，输入一个文法，然后用程序将这一文法的first 集和follow集识别出来，自动生成一个分析表，然后再与输入的待分析程序进行比较、匹配。

（2）因为整个系统的设计是一边学MFC一边做的，所以数据结构方面感觉安排的不是很好 致在最后做语法分析那一块，用了需要申请很大的内存，空间效率和时间效率都有待提高！解决办法：可以用MFC自带自带的堆栈结构等尽量解决这一问题。 致谢

首先衷心感谢我的导师谷波老师，本论文是在他的精心指导下完成的。在我的学习和实习 的过程中，谷老师给与我很大的帮助，他严谨的治学态度，广博的专业知识，对工作认真负责的精神，和蔼可亲的为人给我留下了深刻的印象，并深深地影响着我，这将使我在今后的工作和学习中受用无穷。在此，我想谷老师表示衷心的感谢。另外我还特别要感谢我的同学们，感谢你们在平时的学习和生活中的热心帮助。我还要感谢我的家人，是他们对我的无私支持，使我安心完成学业。感谢所有在我学习期间给予我帮助的所有老师、同学和朋友们！ 参考文献

[1] HAlshawi and D Carter. Training and Scaling P reference Functions for Disambiguation.

Computational Linguistics, 1996,20 (4),635-638

[2] R Bod. Data-Oriented Parsing (DOP). Proceedings COLING'92, Nantes, France. 1992

[3] T L Booth and R A Thompson. Applying Probability Measures to Abstract Languages. IEEE Transactions on Computers, C-22(5),442-450

[4] E Brill. Automatic Grammar Induction and Parsing Free Text, A Transformation-Based Approach. In

Proceedings of the 21st Annual Meeting of the Association for Computational Linguistics.1993 [5] K Church. A Stochastic Parts Program and Noun Phrase Parser for Unrestricted Text. Second

Conference on Applied Natural Language Processing, ACL,1988

[6] M Collin. Head-Driven Statistical Models for Natural Language Parsing. Ph, D. Thesis, the

University of Pennsylvania, 1999 A P Dumpster, N M Laird and D B Rubin. Maximum Likelihood

from Incomplete Data via the EM Algorithm. Journal of the Royal Statistical Society,1977

[7] J Goodman. Parsing Algorithms and Metrics. In Proceedings of the Fourth International Workshop on

Parsing Technologics,1997

[8] J Goodman. Parsing Inside-Out. h. D .Thesis, Harvard University,1998

[9] F Jelinek, JD Lafferty and R L Mercer. Basic Methods of Probabilistic Context Free Grammars.

14

NATOASI Series, 1992,F75,345-360

[10] M A Jones and J M Eisner. Anrobahilisci, n-a., A its application. In Proceedings of National

Conference on Artificial Intelligence( AAAI-92).San Jose,1992,32 2-328 [11] Joshua T. Goodman. Parsing Inside-Out. Ph. D. thesis, Harvard University,1998

[12] 朱胜火，周明，刘听，黄昌宁.一种有效的概率上下文无关文法分析算法.软件学报，1998;9(8),592-597 [13] 王挺，史晓东，陈火旺，杨谊.一种用未分析语料训练文法的方法.软件学报，1998,9(l）；36-42 [14] 周强，黄昌宁.基于局部优化的汉语句法分析方法学报，1999,10(l）；4-6

Design and Implementation of the system on Toyl Language grammar

Analysis

Abstract：In this paper, a more comprehensive overview to the status of the compiler and the role of the principle has done, including the status and role in the history of the computer industry, as well as the main role it in computer systems. A detailed introduction about the design process which is involved in compile ，and about the main focus of the experiment---lexical analysis, syntax analysis and syntax tree structure and the achievement , and a brief overview on other processes has done . The concrete realization of the lexical analysis, syntax analysis, and syntax tree structure are introduced with the design of key algorithms and key algorithm. Through the work of this thesis, the reader can fully understand a complete analysis to the system of Toyl language grammar Design and Implementation of the process.

Keywords：Compilation Principle; lexical analysis; syntax analysis; LL analysis; grammar

15

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