编译原理第06章 自底向上优先分析法.ppt

《编译原理第06章 自底向上优先分析法.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、编译原理之优先分析法华东交通大学软件学院万仲保第06章自底向上优先分析法自底向上优先分析概述简单优先分析法算符优先分析法自底向上分析方法概述自底向上分析方法，也称移进-归约分析法。实现思想是对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄时，就用该产生式的左部非终结符代替相应右部的文法符号串，这称为一步归约。重复这一过程直到归约到栈中只剩文法的开始符号时则为分析成功，也就确认输入串是文法的句子。示例abbcde步骤符号栈输入符号串动作1）#abbcde#移进2）#abbcde#移进A3）#abbcd

2、e#归约(A→b)4）#aAbcde#移进A5）#aAbcde#归约(A→Ab)6）#aAcde#移进7）#aAcde#移进B8）#aAcde#归约(B→d)9）#aAcBe#移进11）#S#接受S10）#aAcBe#归约(S→aAcBe)分析符号串abbcde是否G[S]的句子对输入串abbcde#的移进-规约分析过程SaAcBeaAcdeaAbcdeabbcde最右推导：示例文法G[S]：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→d简单优先分析法按照文法符号（包括终结符和非终结符）的优先关系确定句柄。定义优先关系简单优先文法优先

3、关系矩阵：表示文法符号之间关系的矩阵。算法示例优先关系X≖Y：表示X、Y的优先关系相同，当且仅当文法G中存在产生式A→...XY…；X⋖Y：表示X的优先性比Y的要低，当且仅当文法G中存在产生式A→...XB...，且BY...X⋗Y：表示X的优先性比Y的要高，当且仅当文法G中存在产生式A→...BD...，且B...X，DY优先关系的定义简单优先文法的定义满足以下条件的文法是简单优先文法：（1）在文法符号集V中，任意两个符号之间最多只有一种优先关系成立；（2）在文法中任意两个产生式没有相同的右部。简单优先分析法——算法根据已知优先文法构造相应优先关系矩阵，并将文

4、法的产生式保存，设置符号栈S，算法步骤如下：将输入符号串a1a2a3...an#依次逐个存入符号栈S中，直到遇到栈顶符号ai的优先性.>下一个待输入符号aj时为止。栈顶当前符号ai为句柄尾，由此向左在栈中找句柄的头符号ak，即找到ak-1⋖ak为止。由句柄ak...ai在文法的产生式中查找右部为ak...ai的产生式，若找到则用相应左部代替句柄，若找不到则为出错，这时可断定输入串不是该文法的句子。重复上述三步，直到归约完输入符号串，栈中只剩文法的开始符号为止。简单优先文法分析示例文法G[S]：(1)S→bAb(2)A→(B

5、a(3)B→Aa)1、确定文法符号之间

6、的关系2、求出文法的简单优先关系矩阵3、对输入串进行分析（输入串b(aa)b#）确定文法符号之间的关系1.求≖关系：由(1)：b≖AA≖b由(2)：(≖B由(3)：A≖aa≖)2.求⋖关系：由(1)(2)：b⋖(b⋖a由(2)(3)：(⋖A(⋖((⋖a3.求⋗关系：由(1)：B⋗ba⋗b)⋗b由(3)：B⋗aa⋗a)⋗a求出文法的简单优先关系矩阵“#”用来表示语句括号，其优先关系低于所有与其有相邻关系的文法符号。对输入串进行分析（输入串b(aa)b#）步骤符号栈输入符号串动作1）#b(aa)b##⋖b,移进2）#b(aa)b#b⋖(,移进3）#b(aa)b#(⋖

7、a,移进4）#b(aa)b#a.>a,归约A→a5）#b(Aa)b#A.=a,移进6）#b(Aa)b#a.=),移进7）#b(Aa)b#).>b,归约B→Aa)8）#b(Bb#B.>b,归约A→(B9）#bAb#A.=b,移进10）#bAb#b.>#,归约S→bAb11）#S#接受文法G[S]：(1)S→bAb(2)A→(B

8、a(3)B→Aa)算符优先分析法某些文法具有“算符”特性表达式运算符（优先级、结合性）；人为地规定其算符的优先顺序，即给出优先级别和同一级别的结合性；只考虑算符之间的优先关系来确定句柄。定义算符文法算符优先关系算法优先文法最左素短语算

9、符优先关系表的构造算符优先分析法概述算符优先文法的性质算符优先分析算法优先函数算符优先分析法的局限性算符文法的定义如果不含空产生式的上下文无关文法G中没有形如U…BC…的产生式，其中B，C∈VN，则称G为算符文法（OperaterGrammar，OG）。性质1：在算符文法中任何句型都不包含两个相邻的非终结符。（归纳法）2：如Vx或xV出现在算符文法的句型中，其中V∈VN,x∈VT,则中任何含x的短语必含有V。（反证法）用归纳法设是句型，即S⇒*S=ω0⇒ω1⇒...⇒ωn-1⇒ωn=推导长度为n，归纳起点n=1时，S=ω0⇒ω1=，即S⇒，必存在

10、产生式S→，而由算符文