自顶向下语法分析教学辅助系统设计.doc

1、蓝天工作室-为您提供最优秀的计算机毕业设计论文解决方案 客服QQ:599057179自顶向下语法分析教学辅助软件的开发目 录摘 要IABSTRACTII第1章 绪论11.1 开发背景11.2 开发目标11.3 开发平台2第2章 基本原理概述32.1 基本知识32.2 LL(1)文法的概念32.3 预测分析程序4第3章 软件设计与实现53.1 界面设计53.2 核心算法的实现73.2.1 FIRST集合求解算法实现73.2.2 FOLLOW集合求解算法实现83.2.3 SELECT集合求解算法实现93.2.4 LL(1)文法的判定实现93.2.5 语法正确性判断实现103.2.6 预测分析表构造

2、和分析过程实现103.3 相关类的介绍11第4章 系统的运行与测试124.1 界面的运行效果124.2 系统的测试14结 论17参考文献18蓝天工作室-为您提供最优秀的计算机毕业设计论文解决方案 客服QQ:599057179摘 要自顶而下语法分析是编译原理课程中的一个核心理论，由于理论的抽象性，常规的教学手段很难收到理想的教学效果，而教学辅助软件能以更形象化的方式把内容表达出来，因此教学辅助软件的开发十分必要。本论文以介绍该教学辅助软件的开发为核心，首先介绍开发背景、开发目标、开发平台及软件的基本功能；然后简单介绍软件开发中用到的基础理论，其中包括LL（1）文法等概念；接下来详细阐述软件的具体

3、开发过程，其中，FIRST集合、FOLLOW集合算法的实现是核心，这个实现的过程中用到了队列，在进行语法分析时用到了栈；最后对软件进行简单的测试，检查是否达到了预期目的。关键词 自顶向下语法分析，FIRST集合，FOLLOW集合，预测分析表ABSTRACTTop-down syntax analysis is a core theory in the Compiler Principle . Because this theory is abstract , conventional teaching means can not receive very good teaching resul

4、ts. But, teaching aid software can be a more figurative way to convey the content of expression.So development of a teaching aid software is very necessary.This paper mainly introduces the process of development. Firstly, it introduces the background, the objective, the platform and the basic functi

5、ons.Secondly, basic theory, such as LL(1) syntax analysis concepts ,etc, which is used in this paper is simply introduced.Thirdly, it elaborates specific process of the development, in which implementation of the algorithm of FIRST sets and FOLLOW sets is the core. Queue is used to it and in the pro

6、cess of syntax analysis stack is applied. Finally, it is a simple test,which can check the effect of the teaching aid software.Keywords Top-down syntax analysis,FIRST sets, FOLLOW sets, Predicting and Analyzing Table第 18 页第1章 绪论自顶而下的语法分析是编译原理课程中的一个重要内容，其教学辅助软件的开发对编译原理教学有着重要作用。本章介绍本软件的开发背景、开发目标，以及开发平

7、台。1.1 开发背景随着计算机的迅速普及，计算机软件的发展也正是方兴未艾，它已经渗透到社会的各个领域和各个行业，并率先应用于大学教学领域。考虑到让这些现代化教育资源的投资发挥应有的作用，大家都很重视计算机辅助教学的推广和应用。教师和学生都希望能得到高质量、使用方便的教学软件。而厂商也看到计算机教学辅助软件将会形成有潜力的市场，而积极投入了教学软件的开发和经营。教学辅助软件正是在这个大环境下逐渐有了一定的市场的，正因为它具有良好的图形界面，交互性更强，更容易被人们所接受，所以受到了教育界的普遍欢迎。在计算机专业课的学习过程中，由于所涉及的内容比较抽象，理解起来比较困难，教学辅助软件可以把抽象化的

8、概念用更加形象的方式表达出来，从而激发学生的学习兴趣，提高学习效率。1.2 开发目标自顶而下的语法分析是编译原理课程中一个十分重要的部分，同时它也是考试的重点和难点。因此，本着辅助教学的目的，软件总体上要有友好的界面，良好的交互性，较强的实用性。内容方面，LL（1）文法是一种能够进行确定、无回溯自顶而下语法分析的描述工具，软件要能够把整个LL（1）的分析过程清晰、准确、直观的展示出来。给定一个文法，首先应实现FIRST集合和FOLLOW集合的求解，实现预测分析表的构造，然后进行LL（1）文法确定性的判断，最后给定输入串，进行预测分析。1.3 开发平台在开发的过程中使用了Visual Studi

9、o 2005开发平台。Visual Studio 2005是.NET 2003的优化版和改进版，具有改进的可视化设计器。因为LL(1)分析器的核心内容是一些复杂算法的实现，选择这个平台可以方便界面设计，把精力集中于算法实现。另外Visual Studio 2005自带打包工具，在开发出来一个软件以后更加利于后期的管理，无需使用专门的打包软件，就可以进行打包。只要安装了Framework SDK V2.0就可以直接运行打过包的软件，使用起来方便、简单。随着C#2.0的问世，语言新增了几个重要的特性，例如ArrayList类、迭带器以及正则表达式，本设计中就用到了这些。第2章 基本原理概述本章介绍

10、自顶向下语法分析中的基本原理和概念，为后面的具体开发打下基础。2.1 基本知识在进行软件的设计过程中，需要了解以下基本的知识和概念。1、终结符号：是组成语言的基本符号，终结符号是一个语言的不可再分的基本符号，即单词符号，一般用英文小写字母表示。终结符号集通常用VT表示。2、非终结符号：一个非终结符号代表一个一定的语法概念，是一个类记号，它表示一定符号串的集合，通常用大写英文字母表示。非终结符号集通常用VN表示。3、开始符号：是一个特殊的非终结符号，是进行分析的入口。4、产生式：是定义语法范畴的一种书写规则。5、上下文无关文法：是文法的一种，用来定义语言的语法结构，所定义的语法范畴完全独立于这种

11、范畴可能出现的环境。表示为（VT, VN,S,P），其中VT代表终结符号集，VN代表非终结符号集，S代表开始符号，P代表产生式集合，一个产生式的形式是“A”，其中A是非终结符号，是由终结或非终结符号组成的字符串，即（VTVN）*。这些知识都是参考了而总结出来的。2.2 LL(1)文法的概念在自顶向下语法分析中，会出现回溯以及虚假匹配问题，并且由于文法的左递归性，会造成死循环。为避免以上问题，进行确定的、无回溯的自上而下分析，引入了LL(1)文法。它属于上下文无关文法的范畴，该文法满足以下特点：1、文法不含左递归；2、对于文法中每一个非终结符号A的各个产生式的侯选首符集两两不相交。即若A1|2|

12、n，则FIRST(i)FIRST(j)=；3、对于文法的每个非终结符号A,若它存在某个侯选首符集含（空字）,则FIRST (A)FOLLOW(A)=。2.3 预测分析程序预测分析表是一个MA,a形式的矩阵。其中A为非终结符，a是终结符或#，#不是文法符号，我们总是把它当成输入串的结束符。矩阵元素MA,a中也存放着一条关于A的产生式，指出当A面临输入符号a时应采用的侯选。MA,a中也可能存放一个“出错标志”，指出A根本不该面临输入符号a。预测分析过程的每一步，都是取出栈顶符号和当前输入符号，并查看预测分析表进行的。预测分析器结构如图2-1所示。第3章 软件设计与实现本章主要介绍软件的具体开发过程

13、，包括界面设计、核心算法的实现和相关类的介绍。3.1 界面设计按照软件的设计流程，首先进行界面的设计。作为教学辅助软件，界面应简明、小巧、实用，软件总体界面如图3-1所示。图3-1 系统总体界面1、界面中的“帮助说明”以电子书(CHM格式)的形式展现出，需要先设计一个CHM文档，以便作为模版使用,对提出的理论进行论证说明。System.Diagnostics.Process.Start(path);/打开帮助说明文档软件的输入界面，用一个TabePage控件来进行设计，分别是终结符和非终结符、文法规则、自顶而下的语法分析三个页面。2、在输入终结符和非终结符的页面中用到了两个Textbox的文本

14、框，分别用来显示终结符号和非终结符号，或者可以自行编辑，在打开文件的过程中需要用流来读取文件，它的实现方法如下。private void btnLoadSymbols_Click(object sender, EventArgs e)/打开文件的单击事件。tryusing (StreamReader sr=new StreamReader(ofiledlg.FileName)textboxEndall.AppendText(strTaskItem + rn);SymbolSet.getInstance().EndallSet.Add(strTaskItem) Sr.colse()在输入终结符号

15、和非终结符号的时候规定一个字符占一行，这样使格式更加清晰。3、在文法规则的页面上用了一个ListBox控件来显示文法，可以把编辑好的文法保存到一个文件中，保存操作的实现方法如下。private void btnSaveProducts_Click(object sender, EventArgs e) /存文件的单击事件。sfiledlg.Filter = (*.txt)|*.txt|*.*|*.*;sfiledlg.ShowDialog();if (sfiledlg.FileName != )using (StreamWriter sw = new StreamWriter(sfiledlg

16、.FileName)sw.Close();/实现保存文件操作4、运行页面的设计过程和上面的相同，最大的特点就是运用到了一个WebBrower的组件。它可以把网页模版和最后结果显示在到这个控件上，使得界面效果更加的美观。OutResult(ArrayFIRST,ArrayFOLLOW,ArraySellect,HashAnalysis) /输出结果3.2 核心算法的实现程序的核心是FIRST集合和FOLLOW集合的构造算法以及预测分析表的实现问题。3.2.1 FIRST集合求解算法实现1、若XVT，则FIRST(X)=X；2、若XVN，且有产生式Xa，aVT，则aFIRST(X)；3、若XVN，

17、且有产生式X，则FIRST(X)；4、若XVN， Y1，Y2，Yi都属于VN，且有产生式XY1Y2Yn，当Y1,Yi-1=(1in)时，则把 FIRST(Yi) 去掉后的部分（FIRST(Yi)中有的话）放入FIRST(X)中，记为FIRST(Yi)/FIRST(X)；当Y1,Yn*=时，则最终把放入FIRST(X)，即FIRST(X)。在实现的过程中最主要的是第四步的判定，前三步容易实现，不做介绍。在第四步的实现过程中，首先判断第一个字符是否为非终结符，设定一个布尔型扫描标志FLAG，赋初值TRUE，然后就要扫描后面的每一个字符了，可能会出现以下几种情况。1、Yi如果是非终结符号，并且能推出

18、空字符串，那么就把FIRST(Yi)/加入到FIRST(X)中。2、Yi如果是非终结符号，并且不能推出空字符，那么就把FIRST(Yi)直接加入到FIRST(X)中。并且停止对后面字符串的扫描工作。3、Yi如果是最后一个符号，那么不管它能否能推出空字符，直接把FIRST(Yi)加入到FIRST(X)中。在实现的过程中，为了记录FIRST(X)用到了哪些其他非终结符号的FIRST集，引入队列这种数据结构，同时设置一组布尔型变量记录FIRST集是否完成，也就是说是否还需要用到其它非终结符的FIRST集。把那些已经完成集合求解的非终结符号的FIRST集放入到没有完成集合求解的非终结符号的FIRST集

19、中去，没有完成FIRST集求解的非终结符号放入队列。FIRST集的实现用public ArrayList FIRSTSet()方法：X属于VT，则FIRST(X)=X 。if (SymbolSet.getInstance().IsInEndSet(product.LeftItem) lstFIRSTi.Add(product.LeftItem); 若XVN，且有产生式Xa，aVT，则aFIRST(X)。if(SymbolSet.getInstance().IsInEndSet(strFIRSTLetter) if(!Tools.IsInList(strFIRSTLetter,lstFIRSTi

20、) lstFIRSTi.Add(strFIRSTLetter) 若XVN，且有产生式X，则FIRST(X)。if(!Tools.IsInList(,lstFIRSTi)lstFIRSTi.Add();上面所说的第四步出现的情况较多，但基本实现过程和前三步类似，使用了5个if语句，不再详细列举代码。private bool CheckEmptySymbol(string strChar)/检测空字符public ArrayList FinishFIRST(ArrayList FIRSTList,Queue queueFIRST)./完成FIRST集的计算,把未求出FIRST集的非终结符求出pub

21、lic void outFIRST(ArrayList arylst) /输出FIRST集3.2.2 FOLLOW集合求解算法实现在求FOLLOW集时按照以下步骤来进行：1、X是开始符号，把#加入到FOLLOW(X)；2、AB是一个产生式，则把FIRST()/加到FOLLOW(B)；3、AB是一个产生式，或AB是一个产生式而=，则把FOLLOW(A)加入到FOLLOW(B)中。FOLLOW集合求解算法的实现和FIRST集的类似。在求某个非终结符FIRST集时先扫描产生式左部不同的产生式，然后扫描左部相同的产生式的每一个右部。而在求FOLLOW集的时候，则需要扫描每一个产生式，第一次扫描可以确定

22、哪些FIRST集或FOLLOW集属于所求的FOLLOW集，由于FIRST集已经求出，所以第一次扫描就可以把相应的FIRST集加入到FOLLOW集中，设置FOLLOW集完成标记位，设置队列，把未完成的非终结符送入队列，依次取出队列元素，把求出FOLLOW集的非终结符的FOLLOW集加入到相应的FOLLOW集中，把未求出的送回队列。主要的实现方法如下所示：public ArrayList FOLLOWSet(ArrayList aryFIRST)/得到FOLLOW集private ArrayList FOLLOWLetter(string strChar,ArrayListarylstFOLLOW

23、)/ 返回所有产生式右部指定的字符后边的字母public void outFOLLOW(ArrayList arylst)/输出FOLLOW集public String OutFIRSTFOLLOW(ArrayList irst,ArrayList FOLLOW)/输出FIRST集和FOLLOW集到网页表格3.2.3 SELECT集合求解算法实现1、若是终结符，那么SELLECT(A)=。2、若是，则SELECT(A)=FOLLOW(A)。3、若是非终结符那么 若*=，则SELECT(A)= FIRST()FOLLOW(A)。 若*=，SELECT(A)=FIRST()。主要的实现方法如下所示

24、：public ArrayList SelectSet(ArrayList aryFIRST, ArrayList aryFOLLOW) /得到SELECT集；public void outSellect(ArrayList arylst)/输出SELCET集3.2.4 LL(1)文法的判定实现当SELECT集求出来后就可以判断是不是一个文法是不是LL(1)文法了，扫描产生式左部相同的SELCET集是否含有相同元素，一旦发现相同元素返回FALSE，用public bool IsLL1(ArrayList select)来方来实现具体代码如下：if( i= listboxProducts.Ite

25、ms.Count-1)ListSelect.Add(arylistRight);/判断左部相同的产生式的SLECT集是否含有相同元素for(int i=0 ; i*），可以判断出来该文法确实是LL(1)文法。根据以上的判断说明本软件求出来的SELECT集解以及对LL(1)文法的判断是正确的。通过本软件运行而构造出来的预测分析表如图4-7所示。图4-7 预测分析表的构造根据构造预测分析表的算法的我们可以判断出所构造出来的预测分析表也是正确的，最后对预测分析过程进行测试，同时也判断所测试的字符串是否为该文法的句子，测试结果如图4-8所示。图4-8 预测分析过程根据预测分析程序的步骤，可以检验得出，

26、该预测分析是正确的，符合预测分析程序的总控程序的步骤。同时所检测的句子是该文法的句子。在通过多组产生式的验证后(不再一一列举)，可以得出本软件的运行结果是正确的，达到了预期目的。结 论本次设计初步实现了自顶向下语法分析的基本功能，其中包括判断一个文法是否是LL(1)文法，判断一个输入串是否是一个句子；同时，可以构造预测分析表，并进行预测分析。但同时也存在很多的不足,比如在输入文法的时候,如果一个非终结符号为T但是本系统会按一个终结符号T和一个非终结符号来看待,而且没有解决公共左因子的问题；同时因为时间原因以及受自己能力水平的限制,系统中有些异常并没有得到妥善的处理。在本次毕业设计中，同时也用到

27、了数据结构上的栈、队列，使自己的算法更加利于实现，查询数据的过程更加的快捷，在实现同样功能的基础上，减少了不少的代码。本人由于水平和能力有限,本系统有很多不足,但是自己已经尽力,感到在做设计的同时学到了很多东西,感到十分的高兴,由于算法的实现比较的困难，所以感到很具有挑战性,总的来说自己对本次设计还是比较满意的。参考文献1陈火旺、刘春林编著，编译原理，国防工业出版社，2000年1月2(英)John Sharp 著，周靖译，Visual C# 2005从入门到精通，清华大学出版社，2006年6月3蓝天工作室等著，数据库原理及应用教程， ，2012年3月4张敬和著，编译原理实用教程，清华大学出版社，2005年4月5严蔚敏著，数据结构，清华大学出版社，2002年3月