简单优先分析方法

《简单优先分析方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、简单优先分析方法一种shift-reduce分析方法根据文法符号的优先关系确定句柄文法符号的优先关系的确定简单优先分析中的三种关系XY：当且仅当存在一个产生式A→…XY…X⊳Y：当且仅当存在一个产生式A→…XB…并有B+Y…。X⊲Y：当且仅当存在一个产生式A→…BC…并有B+…X，C*Y…。文法G为简单优先文法如果满足：对于任意两个语法符号X和Y，至多成立一种优先关系；任意两个产生式都具有不同的右部。文法优先关系的确定FIRST(W)={S

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

3、W+…S，S(VNVT)}若有U…SiSj…:则有SiSj;若有

4、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aM(LLMa)#)a(bLMZ#)a(bLMZ)aL)bM(aa(bLMZFIRSTLAST⊳⊳⊲⊲⊲⊳⊳⊳⊲⊲⊲⊲⊲⊳⊳简单优先分析算法要点找第一个使Sj⊲Sj+1的Sj从Sj开始往前(左)找第一个使Si-1⊳Si的Si用SiSi+1…Sj去查产生式的右部，并用相应的左部符号代替句

5、柄SiSi+1…Sj(归约)。重复上述过程，直至输入符结束。如果归约出文法的开始符号则成功。否则失败。简单优先分析实例符号栈关系输入流#⊳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⊲#二义性文法的处理任何语法分析方法都拒绝二义性，会引起分析动作的不确定。解决二义性的方法：改变文法，消除二义性。增加额外的规则利用二义性简化语法分析例条件语句定义：[i]SifEthenSelseS[j]SifEthenS表达式文法：EE+EEE*EEidE(E)第四章

6、总结上下文无关文法(CFG)：(VN,VT,S,P)语法分析树：二义性文法，句柄文法分析算法：三个集合的定义及求法语法分析作用：目的是判定输入串是否为文法所接受的语言语法分析方法自顶向下分析：思想：从文法开始符出发，适当选择产生式，力图推导出输入串。关键问题：产生式的选择主要方法：递归下降法LL(1)分析方法等价变换:消除公共前缀，消除左递归分析条件：分析方法：分析过程：自底向上分析：思想：从输入串出发，从左到右进行归约，直至归约出文法的开始符。关键问题：何时归约、归约产生式的选择主要分析方法－LR分析方法：LR(0)SLR(1)LR(1)LALR(1)简单优先分析方法：优先关系

7、矩阵LR分析方法比较：LRSM的构造（展望符的计算）：判断分析条件：构造分析表：分析过程：LR分析方法的比较状态数：LR(0)=SLR(1)=LALR(1)

8、sYY→;sY

9、有文法如下：G1：SAa

10、bAc

11、dc

12、b

13、daAdG2：SAa

14、bAc

15、Bc

16、bBaAdBd证明G1是LALR(1)文法但不是SLR(1)文法，并构造LALR(1)分析表；G2是LR(1)文法但不是LALR(1)文法并构造LR(1)分析表。判断文法是否是简单优先文法(判断是否有多重定义)SA/AAaAASA/