第五章自底向上优先分析法

《第五章自底向上优先分析法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章自底向上优先分析法自底向上语法分析概述简单优先分析算符优先分析自下而上语法分析概述向下而上分析：该类分析方法是从输入符号串开始，查找句柄，并使用规则把它归约成相应的非终结符号。任何自底向上分析的关键，就是要找出这种句柄。自下而上语法分析试图将一个字符串反向归约至开始符号。自下而上语法分析比自上而下语法分析更有效率，对语法的限制更少。自下而上语法分析概述自下而上语法分析的策略：移进-归约分析；移进就是将一个终结符推进栈归约就是将0个或多个符号从栈中弹出，根据产生式将一个非终结符压入栈移进-归约过程是自顶向下最右推导的逆过程（规范归

2、约）自下而上分析一般过程例：文法G：S→cAdA→aA→ab识别输入串w=cabd是否该文法的句子AAa!!!ScAbd???cabdcabdSAAcabdcabdcabd归约过程形成的推导：ScAdcabd文法G[S]：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→dabbcde步骤符号栈输入符号串动作1）#abbcde#移进2）#abbcde#移进A3）#abbcde#归约(A→b)4）#aAbcde#移进A5）#aAbcde#归约(A→Ab)6）#aAcde#移进7）#aAcde#移进B8）#aAcde#归约

3、(B→d)9）#aAcBe#移进11）#S#接受S10）#aAcBe#归约(S→aAcBe)分析符号串abbcde是否G[S]的句子对输入串abbcde#的移进-规约分析过程SaAcBeaAcdeaAbcdeabbcde上述每一步都是归约当前句型的句柄。且句柄出现在符号栈栈顶，不会在栈中间，上述分析过程并未真正解决句柄的识别问题。例如，对于上面的例子，分析进行到第（5）步，当时栈内符号串为aAb。根据该符号串，我们有规则A→Ab和规则A→b。那么，符号串Ab和b都是某条规则的右部，故都有可能被判别是句型的句柄。假如我们选择b作

4、为句柄，并把b归约为A，那么，最终就达不到归约到S的目的。因而，我们也就无从得知输入串abbcde是一个句子了。文法G[S]：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→dabbcde步骤符号栈输入符号串动作1）#abbcde#移进2）#abbcde#移进A3）#abbcde#归约(A→b)4）#aAbcde#移进A5）#aAbcde#归约(A→Ab)6）#aAcde#移进7）#aAcde#移进B8）#aAcde#归约(B→d)9）#aAcBe#移进11）#S#接受S10）#aAcBe#归约(S→aAcBe)分析符号串a

5、bbcde是否G[S]的句子对输入串abbcde#的移进-规约分析过程SaAcBeaAcdeaAbcdeabbcde算法应考虑的问题在自底向上分析中，如何寻找确定一个句型的句柄是构造一个自左向右扫描，自底向上分析方法必须要解决的一个问题。在每一步中如何选择子串进行归约？短语、直接短语、句柄的定义：文法G[S]，SαAδ且Aβ则称β是句型αβδ相对于非终结符A的短语。若有Aβ则称β是句型αβδ相对于该规则A→β的直接短语。一个句型的最左直接短语称为该句型的句柄。短语、直接短语、句柄简单优先分析法是按照文法符号（终结符和非终结符

6、）的优先关系确定句柄的，因此我们首先介绍任意两个文法符号之间的优先关系是怎样确定的，及如何构造优先关系表。简单优先分析法按照文法符号（包括终结符和非终结符）的优先关系确定句柄。首先定义优先关系的表示：X≖Y表示X和Y的优先关系相等。X⋗Y表示X的优先性比Y的优先性大。X⋖Y表示X的优先性比Y的优先性小。这样我们就可以对已知文法对它的任意两个文法符号X,Y按其在句型中可能会出现的相邻关系来确定它们的优先关系。（注意‘≖’、‘⋗’、‘⋖’和数学中的‘=’‘>’、‘<’不同）i+i-ii-i+i优先关系优先关系X≖Y文法G中存在产生式A→

7、···XY···X⋖Y文法G中存在产生式A→···XB···，且BY···X⋗Y文法G中存在产生式A→···BD···，且B···X,DY···如何确定两个文法符号之间的优先关系？文法G[S]：S→bAbA→(B

8、aB→Aa）根据上面≖、⋗、⋖关系的定义，由文法的产生式可求得文法符号之间的优先关系如下：（1）求≖关系：由S→bAb,A→(B,B→Aa)可得：b≖A,A≖b,(≖B,A≖a,a≖)优先关系（2）求⋖关系：由S→bAb,且A(B，Aa)可得：b⋖(，b⋖a由A→（B且B（B···，Ba···；BA···，可得：（⋖（,

9、（⋖a,（⋖AS→bAbA→(B

10、aB→Aa）X⋖Y文法G中存在产生式A→···XB···，且BY···（3）求⋗关系：由S→bAb且A···),A···B,Aa可得：)⋗b,a⋗b,B⋗b由B→Aa）且A···），