编译原理及实现技术 教学课件 作者 刘磊 第05章 语法分析-自底向上分析方法.ppt

《编译原理及实现技术 教学课件 作者 刘磊 第05章 语法分析-自底向上分析方法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章自底向上分析方法主要内容自底向上分析的基本思想简单优先分析方法LR类分析方法基本思想从待分析的符号串开始，自左向右进行扫描，自下而上进行分析，通过反复查找当前句型的句柄，并使用产生式规则将找到的句柄归约为相应产生式的左部非终极符，直到将输入串归约为文法的开始符。(移入-归约分析)两种分析方法简单优先和LR类分析方法自底向上语法分析方法介绍例：SaAcBe[1]Ab[2]AAb[3]Bd[4]输入流：abbcde。规范推导过程为：逆过程:(符号栈，输入流)(-,abbcde)(a,bbcde)(ab,bcde)(aA,bcde)(aAb,cde)(a

2、A,cde)(aAc,de)(aAcd,e)(aAcB,e)(aAcBe,-)(S,-)SaAcBe[1]aAcd[4]e[1]aAb[3]cd[4]e[1]ab[2]b[3]cd[4]e[1]简单优先分析一种shift-reduce分析方法根据文法符号的优先关系确定句柄文法符号的优先关系的确定简单优先分析中的三种关系XY：当且仅当存在一个产生式A→…XY…X⊲Y：当且仅当存在一个产生式A→…XB…并有B+Y…。X⊳Y：当且仅当存在一个产生式A→…BC…并有B+…X，C*Y…。文法G为简单优先文法如果满足：对于任意两个语法符号X和Y，至多成立一

3、种优先关系；任意两个产生式都具有不同的右部。文法优先关系的确定FIRST(W)={S

4、W+S…，S(VNVT)}LAST(W)={S

5、W+…S，S(VNVT)}若有U…SiSj…:则有SiSj;若有U…SiW…:任SjFIRST(W),有Si⊲Sj若有U…VW…:任SiLAST(V),Sj(FIRST(W){W})则有Si⊳Sj输入流的开始和结束标志‘＃’，文法的开始符为Z，SFIRST(Z),有#⊲S，;且＃⊲ZSLAST(Z)，有S⊳#，;且Z⊳＃优先关系矩阵一个文法的全部优先关系可以用矩阵来表示，称作优先关系矩阵。例：ZbMbM

6、aM(LLMa)#)a(bLMZ#)a(bLMZ)aL)bM(aa(bLMZFIRSTLAST⊲⊲⊳⊳⊳⊲⊲⊲⊳⊳⊳⊳⊳⊲⊲定理：设X1…XiXi+1…Xj…Xn是一个句型，若有Xi⊲Xi+1Xi+2…Xj-1Xj⊳Xj+1则Xi+1Xi+2…Xj-1Xj一定是该句型的简单短语。结论：⊲用来确定句柄的头；用来确定句柄的内部；⊳用来确定句柄的结束。简单优先分析算法要点找第一个使Sj⊳Sj+1的Sj从Sj开始往前(左)找第一个使Si-1⊲Si的Si用SiSi+1…Sj去查产生式的右部，并用相应的左部符号代替句柄SiSi+1…Sj(归约)。重复上述过程，

7、直至输入符结束。如果归约出文法的开始符号则成功。否则失败。简单优先分析实例符号栈关系输入流#⊲b(aa)b##b⊲(aa)b##b(⊲aa)b##b(a⊳a)b##b(Ma)b##b(Ma)b##b(Ma)⊳b##b(L⊳b##bMb##bMb⊳##Z⊳#规范句型：用最右推导导出的句型(也称右句型）。规范前缀：若存在规范句型，且是终极符串或空串，则称为规范前缀。规范活前缀：若规范前缀不含句柄或含一个句柄并且具有形式=(是句柄)，则称规范前缀为规范活前缀(简称活前缀）。归约规范活前缀：若活前缀是含句柄的活前缀，即有=，且是句柄，则称活

8、前缀为归约规范活前缀（简称归约活前缀）。LR类分析方法活前缀的描述性定义：形成可归前缀之前，包括可归前缀在内所有规范句型的前缀都称为活前缀。活前缀为一个或若干规范句型的前缀。在规范归约过程中的任何时刻已分析过的部分，即在分析栈（符号栈）中的符号串均为规范句型的活前缀，表明输入串的已被分析过的部分是该文法某规范句型的一个正确部分。派生定理开始符产生式的右部是归约活前缀。如果A是归约活前缀，且A→是产生式，则也是归约活前缀。任何归约活前缀，都可按上述方式被派生。设文法开始符的产生式是：S→1

9、2

10、…

11、nRPSG={1,…,n}{

12、ARPSG,

13、A→P}识别规约活前缀的LRSM的构造例有文法G[S]:S→aAc[1]A→Abb[2]A→b[3]可归前缀集：aAcaAbbabLR(0)项目：若A→是产生式，则称A→为LR(0)项目(简称项目），也写作[p]形式。项目集的投影：假设IS是LR(0)项目集，则称下面IS(X)为IS关于X的投影集：IS(X)={A→X

14、A→XIS,X(VTVN)}.项目集的闭包：假设IS是LR(0)项目集，则称下面CLOSURE(IS)为IS的闭包集：CLOSURE(IS)=IS{A→

15、Y→A