简单优先简单优先分析法是一种从分析法是一种从左左到右到右扫描扫描、最、最左左归归约约分析法；它属于自底向上分析方法。分析法；它属于自底向上分析方法。 该方法利用该方法利用文法符号文法符号之间的之间的优先关系优先关系来确定待归来确定待归约的句柄约的句柄 ，即可确定当前句型的，即可确定当前句型的句柄句柄。5.5 5.5 简单优先分析法简单优先分析法 利用一个利用一个分析表分析表，登记，登记选择选择句柄产生式句柄产生式的知识；的知识； 利用一个利用一个分析栈分析栈，记录分析过程；，记录分析过程；【分析算法分析算法】依次读取依次读取单词，单词，并进行如下操作：并进行如下操作： 当栈顶出现当栈顶出现句柄句柄时，时，规约规约之，否则之，否则移进移进。 5.5.1. 5.5.1. 简单优先分析法基本概念简单优先分析法基本概念 简单优先分析法的基本要点有三：简单优先分析法的基本要点有三：1. 1. 什么是简单优先分析法？什么是简单优先分析法？ 2. 2. 简单优先分析过程示例简单优先分析过程示例 符号串：符号串： = abbeae #SaAeBSbbaG(S): G(S): S SaAeB|baAeB|b A ASb|eSb|e B BaAaAAe 句柄产生式句柄产生式 操操 作作 剩余串剩余串 w w 分析栈分析栈 移进移进,NEXT,NEXT a e # a e # e e# a# a 移进移进,NEXT,NEXT e # e # a a# a A# a A 移进移进,NEXT,NEXT # # e e# a A e# a A e 归约归约 A - e A - e # # # aAeaAe a a 归约归约 B - B - aAaA # # # aAeaAe a a A - A - SbSb S - b S - b 归约归约 e a e # e a e # b b# a# a 移进移进,NEXT ,NEXT b b e a e # b b e a e # a a# # 归约归约 a e # a e # e e # a S # a S 移进移进,NEXT,NEXT e a e # e a e # b b# a # a 移进移进,NEXT,NEXT b e a e # b e a e # b b# # A A A A a a a a b b e e e e句句柄柄( (接上页接上页) ) 利用利用分析栈分析栈记录行分析过程：记录行分析过程：【注】【注】何时栈顶出现何时栈顶出现句柄？句柄？怎样求当前怎样求当前句柄产生式句柄产生式 ？设设 待分析的符号串待分析的符号串: abbeaeabbeae# # S# S b b# # aAeaAe # # B# B句句柄柄 S - S - aAeBaAeB 归约归约# # # # S S OKOK同时归约者为相等关系，记作同时归约者为相等关系，记作 ；3. 3. 文法符号之间的优先关系文法符号之间的优先关系归约过程中如何确认归约过程中如何确认句柄句柄？ 是否是句柄是否是句柄，还要看其，还要看其所在符号串中的所在符号串中的位置位置。语语法法树树从语法树上，找出优先关系（指相临符号之间）如下： S S b b，a a A A，A A e e，e e B B 如：如：左后归约者为小于关系，记作左后归约者为小于关系，记作 ； 如：如：aab,b,aae,e,ee ； 如：如：b bb,b,b bee 当把优先关系纳入待分析的符号串时，有如下关系： # a # a b e a e a # # # a # a S b e a e a #e # # a # a A A e a e a # # # a A # a A e e a A # # # # a B # # 结论：一个句型的句柄，位于第一次（自左至右）结论：一个句型的句柄，位于第一次（自左至右）出现在出现在 之间的符号串！之间的符号串！ 从文法中获取优先关系从文法中获取优先关系! ! 设设si si ，sjsj是两个文法符号是两个文法符号; ; 如：如：a Aa A，A eA e，e Be B，S bS b； si si sjsj ，当且仅当有当且仅当有U Usi si sjsj ； 优先关系的定义优先关系的定义 G(S): G(S): S SaAeB|baAeB|b A ASb|eSb|e B BaAaA sisi + +如：如：aeae，aSaS，aaaa，abab，eaesisjsj ，当且仅当有当且仅当有 U UVsjVsj ，且且 V V sisi； = + +如：如：bbbb，BbBb，AbAb，ebeb。 (3)头符号集合和尾符号集合头符号集合和尾符号集合 设设 AVAVN N， si si ，sjsj是两个文法符号是两个文法符号; ;则则: : FIRSTVT(A)=si| A si,FIRSTVT(A)=si| A si, = + +LASTVT(A) = LASTVT(A) = sj|Asj|A sjsj 。 = + +【例例5.125.12】G(S): G(S): S SaAeB|baAeB|b，A ASb|eSb|e，B BaAaA S A B a b e S A B a e S A BFIRSTVT a , b S,e,a,b aLASTVT B,b,A,e b , e A , b , e 头符号集合头符号集合尾符号集合尾符号集合优先矩阵优先矩阵表项表项=空空表示两个表示两个符号不可符号不可能相临。能相临。 + +简单优先分析器的基本组成：简单优先分析器的基本组成：优先优先分析法要求文法应是分析法要求文法应是简单优先简单优先文法文法。优先矩阵优先矩阵分析表分析表 优先分析优先分析控制器控制器 分析中只分析中只查看当前符号查看当前符号就可确认就可确认句柄句柄；5.5.2 5.5.2 简单优先分析器设计简单优先分析器设计1.1.简单优先简单优先文法文法及其判定及其判定 文法产生式没有相同的右部；文法产生式没有相同的右部； 如如A A ，B B ， 满足下述特点的文法称为满足下述特点的文法称为简单优先简单优先文法文法。例例5.12 5.12 文法，就是文法，就是简单优先简单优先文法，文法，请看：请看：文法符号之间至多有一种优先关系！文法符号之间至多有一种优先关系！ 【算法算法】 si si sjsj ， 当且仅当有当且仅当有U Usi si sjsj ； si si si sjsj ， 当且仅当有当且仅当有U UVsjVsj，且，且siLASTVT(VsiLASTVT(V) )。 2. 2. 简单优先分析矩阵分析表构造简单优先分析矩阵分析表构造设设 W,VVW,VVN N,si,si，sjsj是两个文法符号是两个文法符号; ; 简单优先分简单优先分析表析表是优先分析是优先分析法的知识表法的知识表, ,是是文文法法的一种机内表的一种机内表示形式：示形式：终结符终结符 + +非终结符非终结符+ +# # a a Z Z #优先关系优先关系符号符号终终结结符符+ +非非终终结结符符+ +# #3. 3. 简单优先控制程序简单优先控制程序设计设计开始开始PUSH(#)PUSH(#)NEXT(w)NEXT(w)查优先分析表查优先分析表R(Xk,wR(Xk,w)=?)=? 空空? ?n nerrerr(#S#) 结束结束PUSH WPUSH WPOP(sjPOP(sj) )，POP(sj-1)POP(sj-1)，POP(siPOP(si) )；PUSH(A)PUSH(A)。从从sj（栈顶符）开始，往栈内栈顶符）开始，往栈内查找，找到第一个使查找，找到第一个使si-1? ?y yn n只考虑算符（终结符）之间的优先关系只考虑算符（终结符）之间的优先关系 （1 1）算符文法）算符文法 设有一文法设有一文法G G，如果如果G G中没有形如中没有形如A AQRQR的产生式，其中的产生式，其中Q Q和和R R为非终结符，则称该文法为非终结符，则称该文法为算符文法（为算符文法（OGOG文法）。文法）。 5.5.3 5.5.3 算符优先分析算符优先分析(2)头符号集合和尾符号集合头符号集合和尾符号集合 设设 aVaVT T，P,RVP,RVN N， 则则: : FIRSTVT(P)=a| P a FIRSTVT(P)=a| P a 或或 P RaP Ra, = + +LASTVT(P) =a| P a LASTVT(P) =a| P a 或或 P P aR R 。 = + + = + + = + +设设a,bVa,bVT T，P,Q,RVP,Q,RVN N， a b a b ， 当且仅当有当且仅当有 P Pabab 或或 P PaQbaQb ； (3) 算符优先关系定义算符优先关系定义算符优先关系定义算符优先关系定义 ab a + + ab ab ， 当且仅当有当且仅当有 P PRbRb ，且，且R a R a 或或 R R aQaQ； = + +(4)算符优先文法算符优先文法 如果算符文法如果算符文法G G中的任何一对终结符中的任何一对终结符a a和和b b之间，仅满之间，仅满足上述一种关系，则足上述一种关系，则G G就是一个算符优先文法（就是一个算符优先文法（OPGOPG）。）。 = + + = + +习题：【习题习题5.135.13】已知下述文法：已知下述文法：G(E): E - T | E + T | E - T G(E): E - T | E + T | E - T T - F | T * F | T / F T - F | T * F | T / F F - i | ( E )F - i | ( E ) (1)试构造上述文法的简单优先矩阵。上述文法是简单优先文法吗？ (2)试构造上述文法的算符优先矩阵。【习题习题5.145.14】P133_3,4P133_3,4谢谢收看！谢谢收看！