编译原理——编译程序构造实践教程 教学课件 作者 张幸儿 戴新宇 501编译程序构造与实践教程第五章.ppt

《编译原理——编译程序构造实践教程 教学课件 作者 张幸儿 戴新宇 501编译程序构造与实践教程第五章.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第五章语法分析——自底向上分析技术5.1自底向上分析技术概况5.1.1讨论前提1.基本思想从语法分析树的角度，自底向上分析过程将以输入符号串为语法分析树的末端结点符号串，试图向着根结点方向往上构造语法分析树，使识别符号正是根结点。按自底向上分析技术，句型分析的过程是一个不断（直接）归约的过程。分析（识别）技术、识别算法、识别程序识别程序功能：进行句型分析(识别)讨论的前提处理对象（输入）是符号串(中间表示形式)基础文法是压缩了的上下文无关文法分析过程是从左到右逐个符号地进行规范分析自底向上句型分析的基础文法是压缩了的上下文无关文法，其中，压缩了的文法是这样的文法，其中每

2、个重写规则都用于句子的生成中，即，每个重写规则U::=u满足下列两个条件：(1)Z=>*U(U出现在句型中)，(2)u=>+t,tVT+(u能推导到终结符号串)。3.输入和输出输入：词法分析程序的输出(属性字序列)输出：识别出是句子时，输出语法分析树或其他内部中间表示；出错时报错。4.要解决的基本问题自底向上分析技术要解决的基本问题：在每一分析步的当前句型中，·找出要被(直接)归约的(简单)短语u·确定(直接)归约到哪个非终结符号U作为分析技术，重要的是如何自动、机械地解决上述基本问题。为什么自底向上分析技术可行？对于上下文无关文法的任一句子，都存在规范分析。5.

3、1.2基本实现方法1.基本思想分析过程中，当分析栈顶部分形成可以(直接)归约的(简单)短语时进行(直接)归约，当还未形成时便移入，因此称为移入-归约法。分析动作4个：移入归约成功报错2.基本实现工具：分析栈3.例G[E]：E∷=E+E

4、E*E

5、(E)

6、i输入符号串：i+i*iE=>E+E=>E+E*E=>E+E*i=>E+i*i=>i+i*i使用移入-归约法的分析过程如下。移入-归约法分析过程：步骤栈输入其余部分动作规则（1）#i+i*i#移入（2）#i+i*i#归约E::=i（3）#E+i*i#移入（4）#E+i*i#移入（5）#E+i*i#归约E::=i（6）#E+

7、E*i#移入（7）#E+E*i#移入（8）#E+E*i#归约E::=i（9）#E+E*E#归约E::=E*E（10）#E+E#归约E::=E+E（11）#E#成功所以，输入符号串i+i*i是该文法的句子。4.是规范分析吗？为什么？5.移入-归约法解决了自底向上分析技术的2个基本问题？·找出要被(直接)归约的(简单)短语u·确定归约到哪个非终结符号U答案：不！移入-归约法是自底向上分析技术？答案：不！6.自底向上分析技术分类LR分析技术（归约句柄，即最左简单短语）优先分析技术：算符优先分析技术(归约最左质短语)简单优先分析技术（归约句柄）5.2LR(1)分析技术5.2.1

8、LR(1)分析技术与LR(1)文法1.LR(1)分析技术的基本思想概况LR(k)分析技术设想：从左向右地扫描输入符号串中的符号，且向前看确定个数（k个）的符号，一点不回溯地识别给定的符号串（严格地从左到右地进行分析）。“LR(k)”的含义是：可以以k为界从左到右地翻译。LR(1)，即k=1，句型分析时向前看1个符号。讨论前提：输入(讨论对象)是符号串以压缩了的上下文无关文法为基础文法从左到右的规范分析基本实现方法：移入-归约法基本实现工具：分析栈(2)一个文法是LR(k)文法，条件是：在句型的识别过程中,任一句柄由其左部的符号串及其右部的k个符号所唯一地确定。LR(k)

9、文法的另一种说法是：应用LR(k)分析技术进行句型识别过程中，每一步的分析动作由可能句柄左部的符号串及其右部向前看的k个符号所唯一地确定。LR(k)文法是无二义性的文法,LR(1)文法当然也是。一个语言能由LR(k)文法生成，就能由LR(1)文法生成，因此只需关心LR(1)文法。(3)基于LR分析技术的识别程序称为LR识别程序。LR识别程序示意图如下图所示。可见LR识别程序由驱动程序与LR分析表两部分组成。分析栈(Sm,Xm)...(S2,X2)(S1,X1)(S0,#)分析栈状态S对应于LR(1)项集（LR(1)项组成的集合）。设p号规则：Up::=Xp1…XpjXp

10、j+1…XpnpLR(1)项：[p,j;α]（足标表示法）[Up→Xp1…Xpj.Xpj+1…Xpnp;α]（圆点表示法）历史信息向前看信息栈顶分析栈中元素结构：状态S符号X例G［E］：1：E∷=E+T2：E∷=T3：T∷=T*F4：T∷=F5：F∷=(E)6：F∷=iLR(0)项E.E+TEE.+TEE+.TEE+T.T.T*FTT.*FTT*.FTT*F.LR(1)项：a.[1，0；+][1，0；#][3，3；*][5，1；+]b.[E.E+T;+][E.E+T;#][TT*F.;*][F(.E);+]LR项指