自下而上语法分析概述简单优先分析算符优先分析6.1自下而上语法分析概述6.1自下而上语法分析概述例6.1文法G[S]：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→d6.1自下而上语法分析概述简单优先分析法：按照文法符号（包括终结符和非终结符）的优先关系确定句柄，这种归约实际上是一种规范归约。简单优先分析方法，准确、规范，但分析效率低，实际实用价值不大。6.2自底向上优先分析方法概述6.3算符优先分析方法6.3.2算符优先文法性质1：在算符文法中，任何句型都不包含两个相邻的非终结符。证明：设是文法G的一个句型，则有假设Sω0ω1…ωn-1ωn=，当n=1时，即S=ω0ω1=，S,S→是G的一条产生式，所以结论成立。假设n>1，ωn-1满足性质1.由于ωn-1ωn,假设ωn-1=αAδ,A→β.则α的尾符号和δ的首符号都不可能是非终结符。ωn-1ωn=αβδ=,而A→β是算法文法G的一条产生式，所以β不含两个相邻的非终结符，这样也不含两个相邻的非终结符。证毕。性质2：如果Ab或（bA）出现在算符文法的句型中，其中A∈VN，b∈VT，则中任何含b的短语必含A.证明：反证法。由已知条件=αbAβ,假如存在,b和A不同时归约，则必有，存在相邻的非终结符的句型，与性质1矛盾。证毕。优先关系定义【定义6.3】算符优先文法（OperatorPrecedenceGrammar），OPG文法。设G是不含产生式的算符文法，a,bVT,a,b至多有，<·，·>三种关系中的一种成立，则称G是一个算符优先文法。注意：允许b·>c,c·>b;不允许b·>c,b<·c,bc中任两个同时存在。bc不一定cb。例1中：“（”“）”，“）”≠“（”.6.3.3算符优先关系表的构造关系图法构造FIRSTVT例2(拓广)文法G¢[E¢]：(0)E¢→#E#(1)E→E+T(2)E→T(3)T→T*F(4)T→F(5)F→PF|P(6)P→(E)(7)P→i关系图法构造LASTVT例2(拓广)文法G¢[E¢]：(0)E¢→#E#(1)E→E+T(2)E→T(3)T→T*F(4)T→F(5)F→PF|P(6)P→(E)(7)P→iFIRSTVT(E’)={#}FIRSTVT(E)={+,*,,(,i}FIRSTVT(T)={*,,(,i}FIRSTVT(F)={,(,i}FIRSTVT(P)={(,i}LASTVT(E’)={#}LASTVT(E)={+,*,,),i}LASTVT(T)={*,,),i}LASTVT(F)={,),i}LASTVT(P)={),i}为解决在算符优先分析过程中如何寻找可归约串，引进最左素短语的概念定义:文法G[S]的句型的素短语是一个短语，它至少包含一个终结符，且除自身外不再包含其他素短语。处于句型最左边的素短语为最左素短语文法G[S]SαAδ且A则称是句型αδ相对于非终结符A的短语算符优先分析的可归约串是句型的最左素短语文法G[E]：(1)E→E+T(2)E→T(3)T→T*F(4)T→F(5)F→PF|P(6)P→(E)(7)P→i6.3.4算符优先分析算法若有句型NiaiNi+1ai+1...NjajNj+1,当aiNi+1ai+1...Njaj属于句柄，则Ni,Nj+1也在句柄中，这是因为算符文法的任何句型中均无两个相邻的非终结符，且终结符和非终结符相邻时，含终结符的句柄必含有非终结符.(6.3.2中的性质2)【算法】算符优先分析法“#”放入符号栈S；设a为S最上部终结符或#；repeatread下一符号b/*b当前输入符*/if(ab)or(ab)then/*a,b<>#*/begin把b推入栈中；/*移进*/endifa·bthen/*归约*//*可归约串的右端*/repeat从栈中弹出符号until栈顶终结符号最近弹出的终结符号/*可归约串的左端*/elseerroruntila=b=#栈优先关系输入动作6.3.5优先函数算法：从优先关系构造优先函数1.aVT{#},建立两个符号fa和ga；2.a，bVT，若ab，或a=b,则从fa至gb画一条弧；若ab，或a=b,则从gb至fa画一条弧；3.图中每个结点能达到的结点（包括自身）数就是该结点的函数值；4.对构造的优先函数，若不满足优先关系的条件，则说明不存在优先函数。gid优先函数的缺陷6.3.6算符优先分析法的局限性