《第6章 自底向上优先分析(4学时).ppt》由会员分享，可在线阅读，更多相关《第6章 自底向上优先分析(4学时).ppt（28页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第6 6章章 自底向上优先分析法自底向上优先分析法自底向上优先分析概述自底向上优先分析概述简单优先分析简单优先分析算符优先分析算符优先分析预备知识预备知识n自底向上分析方法，也称自底向上分析方法，也称移进移进-归约归约分析法。分析法。n实现思想：实现思想：对输入符号串自左向右进行扫描，并对输入符号串自左向右进行扫描，并将输入符逐个将输入符逐个移入一个栈中移入一个栈中，边移入边分析，边移入边分析，一旦栈顶符号串形一旦栈顶符号串形成某个句型的句柄时成某个句型的句柄时，就用就用该产生式的该产生式的左部左部非终结非终结符符代替代替相应右部的文法符号串，这称为相应右部的文法符号串，这称为归约归约。重复
2、这一过程，直到栈中只剩文法的开始符号时，重复这一过程，直到栈中只剩文法的开始符号时，则分析成功，也就确认输入串是文法的句子。则分析成功，也就确认输入串是文法的句子。例例1 文法文法GSGS：(1)S aAcBe(1)S aAcBe(2)A b(2)A b(3)A Ab(3)A Ab(4)B d(4)B d分析分析 abbcdeabbcdea b b c de步骤步骤符号栈符号栈输入符号串输入符号串动作动作 1）#abbcde#移进移进 2）#a bbcde#移进移进A 3）#ab bcde#归约归约(Ab)4）#aA bcde#移进移进A 5）#aAb cde#归约归约(AAb)6）#aA c
3、de#移进移进 7）#aAc de#移进移进B 8）#aAcd e#归约归约(Bd)9）#aAcB e#移进移进11）#S#接受接受S10）#aAcBe#归约归约(SaAcBe)对输入串对输入串#abbcde#abbcde#的移进的移进-归约分析过程：归约分析过程：自底向上分析法自底向上分析法n自底向上分析的自底向上分析的策略策略：移进：移进-归约分析。归约分析。移进移进就是将一个终结符推进符号栈就是将一个终结符推进符号栈归约归约就是将就是将0 0个或多个符号从栈中弹出，根据产生个或多个符号从栈中弹出，根据产生式将一个非终结符压入符号栈式将一个非终结符压入符号栈n移进移进-归约过程是规范推导（
4、最右推导）的逆过程，所归约过程是规范推导（最右推导）的逆过程，所以它是以它是规范归约规范归约。n自底向上分析的自底向上分析的关键关键：在分析过程中如何确定在分析过程中如何确定“句柄句柄”。即：确定何时可以归约栈顶的符号串。即：确定何时可以归约栈顶的符号串。6.1 6.1 自底向上优先分析法概述自底向上优先分析法概述优先分析法分类：优先分析法分类：n简单优先分析法简单优先分析法先按照一定原则，求出文法先按照一定原则，求出文法所有符号所有符号（VT和和VN）之间的之间的优先关系；再按照这种关系确定归约过程中的句柄。优先关系；再按照这种关系确定归约过程中的句柄。优点：规范归约，分析准确、规范优点：规
5、范归约，分析准确、规范缺点：分析效率低，实用价值不大缺点：分析效率低，实用价值不大n算符优先分析法算符优先分析法先按照一定原则，求出文法所有先按照一定原则，求出文法所有VT之间的优先关系；归约之间的优先关系；归约时，只要遇到句柄就归约。时，只要遇到句柄就归约。优点：分析速度快，特别适于表达式的分析优点：分析速度快，特别适于表达式的分析缺点：不是规范归约缺点：不是规范归约6.2 6.2 简单优先分析法简单优先分析法n主要思想：主要思想：先按照一定原则，求出文法所有符号（先按照一定原则，求出文法所有符号（VT和和VN）之间的之间的优先关系；再按照优先关系确定归约过程中的句柄。优先关系；再按照优先关
6、系确定归约过程中的句柄。n实现步骤：实现步骤：1.拓广文法拓广文法 S#S#2.构造优先关系表构造优先关系表3.判断是否为判断是否为简单优先文法简单优先文法4.根据优先关系表根据优先关系表分析句子分析句子下一节X YX Y ：X X与与Y Y优先关系相等优先关系相等文法文法G G中存在产生式中存在产生式A A.XY.XY.X YX Y ：X X的优先性比的优先性比Y Y小小文法文法G G中存在产生式中存在产生式A A.XB.XB.，且且B Y.B Y.X YX Y ：X X的优先性比的优先性比Y Y大大文法文法G G中存在产生式中存在产生式A A.BD.BD.，且且B .XB .X，D Y.D
7、 Y.注：其中注：其中 X,YX,Y(V(VT T V VN N)不等价于不等价于 Y XY X不等价于不等价于 Y XY X不等价于不等价于 Y XY X优先关系优先关系构造优先关系表（优先关系矩阵）构造优先关系表（优先关系矩阵）例例2 2 拓广后的文法拓广后的文法G G：(0)S(0)S#S#S#/特殊：特殊：#，#右相邻符号，左相邻符号右相邻符号，左相邻符号#(1)S bAb(1)S bAb(2)A (B(2)A (B(3)A a(3)A a(4)B Aa)(4)B Aa)求各符号之间的优先关系，并求该文法的优先关系矩阵。求各符号之间的优先关系，并求该文法的优先关系矩阵。解题步骤：解题步
8、骤：1 1）求各种优先关系）求各种优先关系求求 关系关系在产生式右部找相邻的符号在产生式右部找相邻的符号V1V2V1V2，则则 V1 V2V1 V2求求 关系关系在产生式右部找在产生式右部找V VT TV VN N形式，则形式，则 V VT T a a，其中其中V VN N a a在产生式右部找在产生式右部找V VN1N1V VN2N2形式，则形式，则 V VN1 N1 a a，其中其中V VN2N2 a a求求 关系关系在产生式右部找在产生式右部找V VN NV VT T形式，则形式，则 b Vb VT T，其中其中V VN N b b在产生式右部找在产生式右部找V VN1N1V VN2N2
9、形式，则形式，则 b Vb VN1N1，其中其中V VN1N1 b b2 2）根据优先关系，构造优先关系矩阵）根据优先关系，构造优先关系矩阵构造优先关系表（优先关系矩阵）构造优先关系表（优先关系矩阵）例例2 2 拓广后的文法拓广后的文法G G：(0)S(0)S#S#S#(1)S bAb(1)S bAb(2)A (B(2)A (B(3)A a(3)A a(4)B Aa)(4)B Aa)1 1）求各种优先关系）求各种优先关系 求求 关系关系#，b Ab A，A bA b，(B B，A aA a，a )a )求求 关系关系#S S，#b b，b ab a，b (b (，(A(A，(a(a，(求求 关
10、系关系S#S#，b#b#，a ba b，B bB b，)b b，a aa a，B aB a，)a a构造优先关系表（优先关系矩阵）构造优先关系表（优先关系矩阵）例例2 2 拓广后的文法拓广后的文法G G：(0)S(0)S#S#S#(1)S bAb(1)S bAb(2)A (B(2)A (B(3)A a(3)A a(4)B Aa)(4)B Aa)2 2）根据优先关系，构造优先关系矩阵）根据优先关系，构造优先关系矩阵优先关系：优先关系：#=#=#，b=Ab=A，A=bA=b，(=(=B B，A=aA=a，a=)a=)#S S，#b b，baba，b(b(，(A(A，(a(a，(#S#，b#b#，a
11、bab，BbBb，)b b，aaaa，BaBa，)a a返回简单优先文法的定义简单优先文法的定义满足以下条件的文法是简单优先文法满足以下条件的文法是简单优先文法（1 1）在文法符号集）在文法符号集V V中，任意两个符号之间最多只有一中，任意两个符号之间最多只有一种优先关系。种优先关系。（2 2）在文法中，任意两个产生式没有相同的右部。）在文法中，任意两个产生式没有相同的右部。（3 3）不含空产生式。）不含空产生式。采用简单优先分析时，必须是简单优先文法。采用简单优先分析时，必须是简单优先文法。返回简单优先分析法简单优先分析法构造相应优先关系矩阵，并将文法的产生式保存，设构造相应优先关系矩阵，并
12、将文法的产生式保存，设置符号栈置符号栈S S，算法步骤如下：算法步骤如下：1.1.将输入符号串将输入符号串a1a2a3.an#依次逐个存入符号栈依次逐个存入符号栈S S中，中，直到遇到直到遇到栈顶符号栈顶符号ai 下一个待输入符号下一个待输入符号aj 时为止。时为止。2.2.栈顶当前符号栈顶当前符号ai为句柄尾，由此向左在栈中找句柄的为句柄尾，由此向左在栈中找句柄的头符号头符号ak，即找到即找到ak-1 ak为止。为止。3.3.找到句柄找到句柄akai，在文法的产生式中查找右部为在文法的产生式中查找右部为ak.ai的产生式，若找到则用相应左部代替句柄，若找不到的产生式，若找到则用相应左部代替句
13、柄，若找不到则为出错，这时可断定输入串不是该文法的句子。则为出错，这时可断定输入串不是该文法的句子。4.4.重复上述三步，直到归约完所有输入符号串为止。重复上述三步，直到归约完所有输入符号串为止。（此时栈中只剩文法的开始符号）（此时栈中只剩文法的开始符号）例例2 2 文法文法GSGS：(1)S bAb(1)S bAb(2)A (B(2)A (B(3)A a(3)A a(3)B Aa)(3)B Aa)分析输入串分析输入串#b(aa)b#b(aa)b#步骤步骤符号栈符号栈S待输入符号串待输入符号串动作动作 1）#b(aa)b#b,移进移进 2）#b (aa)b#b(,移进移进 3）#b(aa)b#
14、(a,归约归约Aa 5）#b(A a)b#A=a,移进移进 6）#b(Aa )b#a=),移进移进 7）#b(Aa)b#)b,归约归约BAa)8）#b(B b#Bb,归约归约A(B 9）#bA b#A=b,移进移进10）#bAb#b#,归约归约SbAb11）#S#接受接受返回6.3 6.3 算符优先分析法算符优先分析法n主要思想：主要思想：对文法按照一定规则，求出对文法按照一定规则，求出V VT T之间的优先关系；再之间的优先关系；再按照这种优先关系来确定句柄。按照这种优先关系来确定句柄。n实现步骤：实现步骤：1.1.拓广文法拓广文法 S S#S#S#2.2.构造算符优先关系表构造算符优先关系
15、表3.3.判断是否为判断是否为算符优先文法算符优先文法（OPGOPG文法）文法）4.4.根据优先关系表根据优先关系表分析句子分析句子n优先函数优先函数为节约存储空间，用为节约存储空间，用“优先函数优先函数”代替代替“优先关系表优先关系表”i i的优先级最高的优先级最高 优先级次于优先级次于i i，右结合右结合*和和/优先级次之，左结合优先级次之，左结合+和和-优先级最低，左结合优先级最低，左结合括号的优先级大于括号外的运算符，小于括号内的运算符括号的优先级大于括号外的运算符，小于括号内的运算符内括号的优先性大于外括号内括号的优先性大于外括号#的优先性低于与其相邻的算符的优先性低于与其相邻的算符
16、例例3 3 文法文法GE：EE+E|E-EEE*E|E/EEE EE(E)Ei算符优先关系表：算符优先关系表：直观法确定算符优先关系直观法确定算符优先关系算符文法算符文法的定义的定义n算符文法算符文法：上下文无关文法：上下文无关文法G G中中没有没有形如形如 A ABCBC的产生式，其中的产生式，其中B,CVB,CVN N，则称，则称 G G为算符文法（为算符文法（OGOG，Operator GrammerOperator Grammer）。）。n性质性质1 1：在算符文法中任何句型都不包含两个相邻的：在算符文法中任何句型都不包含两个相邻的非终结符。非终结符。n性质性质2 2：如：如 Ab A
17、b 或或 bA bA 出现在算符文法的句型出现在算符文法的句型 中，中，其中其中 AVAVN N,bV,bVT T,则则 中任何含中任何含 b b 的短语必含的短语必含有有 A A。（但含（但含A A的短语未必含的短语未必含b b。）。）算符算符优先关系优先关系的定义的定义设设GSGS是一个不含是一个不含产生式产生式的算符文法的算符文法G G中中na ba b ：当且仅当文法中含有形如当且仅当文法中含有形如 A Aabab或或A A a aB Bb b的产生式的产生式na ba b ：当且仅当文法中含有形如当且仅当文法中含有形如 A AaBaB的产生式，且的产生式，且 B bB b 或或 B
18、B CbCb na ba b:当且仅当文法中含有形如当且仅当文法中含有形如 A ABbBb的产生式，且的产生式，且 B B a a 或或 B B aCaC 定义法定义法 构造算符优先关系表构造算符优先关系表（1 1）定义）定义 FirstVT FirstVT 和和 LastVTLastVTFirstVT(B)=b|B bFirstVT(B)=b|B b 或或 B CbB Cb LastVT(B)=a|B LastVT(B)=a|B a a 或或 B B aC aC（2 2）求优先关系）求优先关系（3 3）构造优先关系表）构造优先关系表算符优先关系表算符优先关系表的构造的构造定义法定义法关系图法
19、（自学）关系图法（自学）例例4 4 文法文法GEGE(0)E(0)E#E#E#(1)(1)EE+T EE+T(2)(2)ET ET(3)(3)TT*F TT*F(4)(4)TF TF(5)(5)FP FPF F(6)F(6)FP P(7)P(7)P(E)(E)(8)Pi(8)Pi构造算符优先构造算符优先关系表。关系表。构造优先分析表的步骤：构造优先分析表的步骤：1 1）计算每个）计算每个V VN N的的FirstVFirstVT T集和集和LastVLastVT T集集2 2）求优先关系）求优先关系 求求=关系关系 求求 关系：找关系：找aBaB，aFirstVT(B)a 关系：找关系：找Bc
20、Bc，LastVT(B)cLastVT(B)c3 3）构造优先关系表）构造优先关系表返回n设有一不含设有一不含产生式的算符文法产生式的算符文法G G，如果对任意两个如果对任意两个终结符终结符a a和和b b之间至多只有之间至多只有 、三种关系的三种关系的一种成立，则称一种成立，则称 G G是一个算符优先文法（是一个算符优先文法（OPG,OPG,Operator Precedence GrammarOperator Precedence Grammar）。）。不含空产生式不含空产生式任何产生式右部不包含两个相邻的非终结符任何产生式右部不包含两个相邻的非终结符任何两个终结符之间优先关系唯一任何两个
21、终结符之间优先关系唯一n算符优先文法是无二义的。算符优先文法是无二义的。算符优先文法算符优先文法的定义的定义返回算符优先分析算符优先分析举例举例:利用例利用例4 4的算符优先分的算符优先分析表分析句子析表分析句子#i+i#i+i#n归约过程中，只考虑终结符之间的优先关系来归约过程中，只考虑终结符之间的优先关系来确定句柄，而与非终结符无关。这样去掉了单确定句柄，而与非终结符无关。这样去掉了单个非终结符的归约，所以用算符优先分析法的个非终结符的归约，所以用算符优先分析法的规约过程规约过程不是规范归约不是规范归约。n为解决在算符优先分析过程中如何寻找句柄，为解决在算符优先分析过程中如何寻找句柄，引进
22、引进最左素短语最左素短语的概念的概念算符优先分析算符优先分析最左素短语最左素短语n素短语素短语设有文法设有文法GSGS，其句型的素短语是一个短语，它其句型的素短语是一个短语，它至少至少包含一个终结符包含一个终结符，且除自身外，且除自身外不再包含其他素短语不再包含其他素短语。n最左素短语：最左素短语：句型最左边的素短语。句型最左边的素短语。文法文法GEGE：(1)EE+T(1)EE+T(2)ET(2)ET(3)TT*F(3)TT*F(4)TF(4)TF(5)FP(5)FP F F(6)(6)FFP P(6)P(6)P(E)(E)(7)Pi(7)Pi求句型求句型#T+T*F+i#T+T*F+i#的
23、素短语。的素短语。EET+ETF*FTTi短语：短语：T+T*F+iT+T*F+iT+T*FT+T*FT TT*FT*Fi i算符优先分析的局限性算符优先分析的局限性 简单优先分析简单优先分析：是规范归约，关键是寻找当前句型的：是规范归约，关键是寻找当前句型的句柄句柄，符号栈顶一旦形成句柄就归约。，符号栈顶一旦形成句柄就归约。算符优先分析算符优先分析：不是规范归约，关键是寻找当前句型：不是规范归约，关键是寻找当前句型的的最左素短语最左素短语，符号栈顶一旦形成最左素短语就归约。，符号栈顶一旦形成最左素短语就归约。因此，算符优先分析可能出现因此，算符优先分析可能出现“错误的句子得到正确的错误的句子
24、得到正确的归约归约”；并且；并且一般语言的文法很难满足算符优先文法的一般语言的文法很难满足算符优先文法的条件。条件。结论：算符优先分析法只适用于结论：算符优先分析法只适用于表达式的语法分析表达式的语法分析。返回优先函数优先函数n优点优点：优先函数比优先矩阵节省空间：优先函数比优先矩阵节省空间优先矩阵占用内存空间：优先矩阵占用内存空间：(n+1)n+1)2 2 优先函数占用内存空间：优先函数占用内存空间：2(2(n+1)n+1)n缺点缺点：当发生错误时不能准确指出出错位置：当发生错误时不能准确指出出错位置n优先函数的优先函数的构造方法构造方法：由定义直接构造由定义直接构造用关系图构造优先函数（自
25、学）用关系图构造优先函数（自学）优先函数的定义优先函数的定义n定义两个函数定义两个函数f,g f,g，满足如下条件：满足如下条件：当当a ba b，则令则令f(a)=g(b)f(a)=g(b)当当a ba b，则令则令f(a)g(b)f(a)g(b)f(a)g(b)n由定义构造优先函数由定义构造优先函数a)a)对每个终结符对每个终结符a a，令令f(a)=g(a)=1f(a)=g(a)=1b)b)若若a ba b，而而f(a)f(a)g(b)g(b)则令则令f(a)=f(a)=g(b)+1g(b)+1c)c)若若a ba b，而而f(a)f(a)g(b)g(b)则令则令g(b)=f(a)+1g(b)=f(a)+1d)d)若若a ba b，而而f(a)f(a)g(b)g(b)则令则令 min(f(a),g(b)=max(f(a),g(b)in(f(a),g(b)=max(f(a),g(b)e)e)重复重复b-db-d，直到过程收敛直到过程收敛（重复过程中，若有一（重复过程中，若有一个值个值大于大于2 2n n，表明该文法表明该文法不存在不存在算符优先函数）算符优先函数）求例求例4 4优先关系表优先关系表所对应的优先函数所对应的优先函数课堂练习：课堂练习：P121 P121 例题例题1 1P122 1P122 1，3 3，4 4