编译原理大作业(哈工大)

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

1、编译原理大作业论文学号：1093710411姓名：周国栋哈尔滨工业大学软件学院2012年1月不要删除行尾的分节符，此行不会被打印千万不要删除行尾的分节符，此行不会被打印。在目录上点右键“更新域”，然后“更新整个目录”。更新后，请在摘要和引言之间插入一个“回车符”第1章综述1.1语法分析概述语法分析是编译过程的一个逻辑阶段。语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短语1.2分析方法语法分析主要有两种：自顶向下的分析方法和自底向上的分析方法。不论是哪一种方法，语法分析器都是自左向右地扫面输入字符串，每次读取一个符号。本文讨论基于以上两种分析方式的五种文法：LL(1)

2、，LR(1)，SLR(1)，LALR(1)以及算符优先文法。最有效的自顶向下和自底向上分析方法只能处理文法的一些子类。对文法的要求比较高，然而这些文法的子类就足以描述程序设计语言中的大部分语言结构。第1章五种文法的比较1.1LL(1)文法1.1.1概述LL(1)语法分析属于自顶向下的语法分析。所谓自顶向下的语法分析，就是对给定的输入单词序列w，试图自根向叶为其建立一棵语法分析树。或者说从文法开始符号出发，寻求所给的输入符号串的一个最左推导。1.1.2存在的问题但是无论哪种方法，在分析过程中都可能会遇到一些共同的问题：1二义性问题;2回溯问题;3左递归引起的无穷推导问题。所以说，自

3、顶向下的语法分析方法并不能处理所有的文法，有时为了适应所选择的分析方法，常常需要对原始文法进行改造，包括如下3步：1消除二义性。这一步只能是人工手动的修改文法。2消除左递归。这一步可以由程序来处理。假设有n个语法变量，那么这一步的时间复杂度是O（）。3提取左公因子。这一步也主要有人工手动处理。经过这三步处理后的文法，便可以使用预测分析法或者递归下降分析法来进行语法分析了。1.1.3处理过程在接下来的处理中，两种方法都需要进行三步预处理，即：1求出单个文法符号X和文法符号串α的FIRST集；2求FOLLOW集；3求LL（1）分析表。所以改造后的文法LL（1）有一些特殊的性质。它不是

4、二义性的，也不含左递归。可以证明，G是LL(1)文法，当且仅当G的任何两个不同的产生式A→α

5、β满足下面条件：1、不存在这样的终结符α，使得α和β导出的串都以a开始2、α和β中至多有一个能导出空串3、如果β→ε，那么α不能导出以FOLLOW(A)中的终结符开始的任何串。对于求单个文法符号X的时间复杂度，假设文法符号的个数为n，非终结符个数为m，由于循环的次数与嵌套的层数和计算的顺序有极大的关联，最坏情况要循环O（n）次，为方便计算，再根据实际情况假设每个产生式右部的文法符号个数为10，所以，求单个文法符号X的时间复杂度为O（10*n*m）=O(mn),而对于符号串α，假设它包含k

6、个符号，则计算它的时间复杂度为O（mnk），求出了FIRST集采能求FOLLOW集，易知求FOLLOW集的时间复杂度也为O（mn）。构造预测分析表的方法：输入：文法G输出：分析表M。方法：1、对于文法中的每个产生式A→α，执行第二步和第三步2、对FIRST(α)中的每个终结符α，将A→α加入到M[A,a]中3、若ε在FIRST(α)中，则对FOLLOW(A)的每个终结符b，将A→α加[]入到M[A,b]中，若ε在FIRST(α)中，且﹟在FOLLOW(A)中，则将A→α加入到M[A,﹟]中4、将M中每个没定义的表项均置为error分析表是一个二维数组M[A,a],A是语法变量，a

7、是输入符号或#。也可以在O（mn）的时间内求出，两种方法其实都用到了预测LL（1）分析表，只不过使用的方法不太一样。1.1.1预测分析法对于预测分析法，它采用表驱动的方式来实现，它具有一个输入缓冲区、一个分析栈、一张LL（1）分析表和一个输出流。输入缓冲区中包含待分析的串和结束符#。分析栈用来存放文法符号序列，栈底符号是#。初始时，栈中只有文法开始符号及其下的#。整个分析过程在于从文法开始符号开始，试图构造输入缓冲区中待分析串的最左推导。假设某程序共有符号s个，整个控制程序的时间复杂度为O（s）。使用预测分析的主要困难在于为源语言编写一个能构造出预测语法分析器的文法。虽然消除左递

8、归和提取左因子都非常简单，但它们使得结果文法很难阅读而且不易翻译。1.1.1递归下降分析法而对于递归下降分析法，是指根据各个候选式的结构，为文法的每个语法变量编写一个处理子程序，用来识别该语法变量所代表的语法成分。设有产生式AàX1X2X3…Xk…Xn，则与A对应的处理子程序遇到的Xk是终结符时直接进行匹配，而遇到Xk是语法变量时就调用与Xk对应的处理子程序。由于产生式中的语法变量可能是递归定义的，所以这种实现方法要求处理子程序可以递归调用。另外，这种分析方法也是寻求输入串的一个