编译原理大作业

《编译原理大作业》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、可行性研究报告编译原理大作业论文学号：1083710614姓名：杨文华哈尔滨工业大学软件学院2010年12月-I-Abstract摘要语法分析是编译程序的核心部分，其任务是检查词法分析器输出的单词序列是否构成源语言中的句子，亦即是否符合源语言的语法规则。本文从自上而下和自下而上两种角度论述了几种语法分析方法的优劣和各自试用的文法。关键词　编译；语法分析；文法；-II-AbstractAbstractSyntax analysisis thecoreof thecompiler,the taskistocheck theoutputof thelexerc

2、onstitute thesourcelanguage word sequence inthe sentence,thatis, whether thesource languagesyntax rules. Fromthe topdown andbottom-up perspectiveof bothanalysismethods arediscussed theadvantagesanddisadvantages ofseveral syntaxand grammarof their trial.Keywords　Compile,grammatica

3、lanalysis,grammar不要删除行尾的分节符，此行不会被打印-II-第一章综述目录摘要IAbstractII第1章综述11.1语法分析概述11.2分析方法1第2章四种文法的比较22.1LL(1)22.2SLR(1)32.3LR(1)42.4LALR(1)42.5小结5参考文献6千万不要删除行尾的分节符，此行不会被打印。在目录上点右键“更新域”，然后“更新整个目录”。更新后，请在摘要和引言之间插入一个“回车符”-8-第3章小结第1章综述1.1语法分析概述语法分析的任务是检查词法分析器输出的单词序列是否构成源语言中的句子，亦即是否符合源语言的语法规

4、则。1.2分析方法进行语法分析主要有两种：自顶向下的分析方法和自底向上的分析方法。本文讨论基于以上两种分析方式的五种文法：LL(1)，LR(1)，SLR(1)，LALR(1)以及算符优先文法。这五种文法各有其特点与适用范围，很难确切的说孰优孰劣。-8-第3章小结第1章五种文法的比较1.1LL(1)文法1.1.1概述LL(1)语法分析属于自顶向下的语法分析。所谓自顶向下的语法分析，就是对给定的输入单词序列w，试图自顶向下的为其建立一棵语法分析树。或者说从文法德开始符号出发，试图寻找w的一种最左推导。这种分析过程实质上是一种试探过程，而且对文法的限制比较多，

5、可能会导致分析效率极低甚至失败。具体的有预测分析法和递归下降分析法。1.1.2对文法的限制但是无论哪种方法，在分析过程中都可能会遇到一些共同的问题：1二义性问题;2回溯问题;3左递归引起的无穷推导问题。所以说，自顶向下的语法分析方法并不能处理所有的文法，有时为了适应所选择的分析方法，常常需要对原始文法进行改造，包括如下3步：1消除二义性。这一步只能是人工手动的修改文法。2消除左递归。这一步可以由程序来处理。假设有n个语法变量，那么这一步的时间复杂度是O（）。3提取左公因子。这一步也主要有人工手动处理。经过这三步处理后的文法，便可以使用预测分析法或者递归下

6、降分析法来进行语法分析了。1.1.3处理过程在接下来的处理中，两种方法都需要进行三步预处理，即：1求出单个文法符号X和文法符号串α的FIRST集；2求FOLLOW集；3求LL（1）分析表。-8-第3章小结对于求单个文法符号X的时间复杂度，假设文法符号的个数为n，非终结符个数为m，由于循环的次数与嵌套的层数和计算的顺序有极大的关联，最坏情况要循环O（n）次，为方便计算，再根据实际情况假设每个产生式右部的文法符号个数为10，所以，求单个文法符号X的时间复杂度为O（10*n*m）=O(mn),而对于符号串α，假设它包含k个符号，则计算它的时间复杂度为O（mnk

7、），求出了FIRST集采能求FOLLOW集，易知求FOLLOW集的时间复杂度也为O（mn）。接下来，还需要求出LL（1）分析表，分析表是一个二维数组M[A,a],A是语法变量，a是输入符号或#。也可以在O（mn）的时间内求出，两种方法其实都用到了预测LL（1）分析表，只不过使用的方法不太一样。1.1.1预测分析法对于预测分析法，它采用表驱动的方式来实现，它具有一个输入缓冲区、一个分析栈、一张LL（1）分析表和一个输出流。输入缓冲区中包含待分析的串和结束符#。分析栈用来存放文法符号序列，栈底符号是#。初始时，栈中只有文法开始符号及其下的#。整个分析过程在于

8、从文法开始符号开始，试图构造输入缓冲区中待分析串的最左推导。假设某程序共有符号s