编译原理第三版_第五章_自下而上语法分析

第5章语法分析－自下而上分析本章要点自下而上分析方法概述算符优先分析方法LR分析方法语法分析器的自动生成5.1自下而上语法分析概述语法分析的任务:按文法的产生式分析输入串(单词串)是否是句子。语法分析的方法:自上而下分析法:开始符号S=输入串α(推导)自下而上分析法:输入串α=开始符号S(归约)**1、归约与分析树(1)移进-归约法:使用符号栈,把输入符号逐一移进栈,栈顶出现某个产生式右部时归约为左部。例：给定文法G：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→d输入串abbcde是否为句子？归约过程如下：步骤：动作：1.进aa2.进bba3.归(2)4.进b5.归(3)6.进c7.进d8.归(4)10.归(1)9.进eAabAaAacAadcAaBcAaeBcAaS(2)分析树:用树表示“移进-归约”过程AbAAbbBdSaAcBeAbdb这是一个自下而上地构造树的过程，故称为自下而上语法分析。关键何时归约：一旦栈顶出现可归约串，就立即进行归约。（最左归约、规范归约）找到构成产生式右部的符号串（即可归约串）。2、规范归约简述定义短语:对于文法G（S），设αβδ是一个句型,若有S=αAδ且A=β，则称β是句型αβδ关于非终结符A的短语。*+例：设文法G（S）：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→d给出句型aAbcde的短语。由S=aAcBe=aAcde=aAbcde,因为S=aAcdeA=Ab所以Ab是短语;*直接短语:特别地,若A=β,则称β是句型αβδ关于产生式A→β的直接短语。句柄:句型的最左直接短语称为句柄。由S=aAcBe=aAbcBe=aAbcde,因为S=aAbcBe,B=d所以d是短语；aAbcde本身也是短语。Ab,d都是直接短语。Ab是句柄。*例：设文法G（S）：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→d给出句型aAbcde的短语、直接短语、句柄。*句型语法树和句型的短语、直接短语、句柄（1）短语：句型语法树中每棵子树（某个结点连同它的所有子孙组成的树）的所有叶子结点从左到右排列起来形成一个相对于子树根的短语。（2）直接短语：只有父子两代的子树形成的短语。（3）句柄：语法树中最左那棵只有父子两代的子树形成的短语。例1：对文法G（S）：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→d句型aAbcde的语法树为：SaAcBeAbdAb是短语，d是短语,aAbcde是短语Ab,d是直接短语，Ab是句柄，例2：G（E）:E→E+T│E-T│TT→T*F│T/F│FF→i│(E)试找出句型(T+i)*i-F的所有短语、直接短语和句柄EE-TTFT*FF(E)E+TTFii解:短语(T+i)*i-F(T+i)*i(T+i)T+iTi(左)i(右)F举例：用语法树寻找短语、直接短语、句柄直接短语TiF句柄T设α是文法G的一个句子,若序列αn,αn-1,…,α0，满足：(1)αn=α；(2)α0=S；(3)对任意i,0i≤n,αi-1是从αi将句柄替换成相应产生左部符号而得到的；则称该序列是一个规范归约。规范归约句子abbcde的规范归约过程如下:－－“剪枝”SaAcBeAbdbSaAcBeaAcBeaAcBESSSAbdd规范归约是最右推导的逆过程；最右推导又称为规范推导。规范归约归约规则abbcde(2)A→baAbcde(3)A→AbaAcde(4)B→daAcBe(1)S→aAcBeS例:对文法G（S）(1)S→aAcBe(2)A→b(3)A→Ab(4)B→d3、符号栈的使用与语法树的表示(1)符号栈的使用例：G:E→E+E│E*E│(E)│i，给出i1*i2+i3的移进归约过程步骤栈输入串动作0#i1*i2+i3#预备1#i1*i2+i3#移进2#E*i2+i3#归约E→i3#E*i2+i3#移进4#E*i2+i3#移进5#E*E+i3#归约E→i6#E+i3#归约E→E*E7#E+i3#移进8#E+i3#移进9#E+E#归约E→i10#E#归约E→E+E11#E#成功(2)语法树的表示穿线表方法:在移进-归约过程中自下而上构造句子的语法树•移进符号a时,构造表示端末结的数据结构,其地址与a同时进栈•用A→X1X2…Xn归约时,构造新结A的数据结构,其地址与A同时进栈•接受时,语法树已经构成,S及根地址在栈中a0An.....符号儿子数左部非终结符儿子数指向子结点的指针指向子结点的指针符号栈[例]i*i+i的语法树符号结点地址EE...3...E1.E1.i0*0i0+0i0E1.35.2算符优先分析法1、基本思想•简单优先分析法：按一定原则找出所有符号即终结符和非终结的优先关系、确定句柄进行归约分析。它是一种规范归约，但效率低，使用价值不大。•算符优先分析法：规定终结符(算符)的优先关系，按终结符(算符)的优先关系控制自下而上语法分析过程（寻找“可归约串”和进行归约）。它不是规范归约，但分析速度快，适于表达式的语法分析。2、优先关系•用下面方法表示任何两个可能相继出现的终结符a和b（它们之间可能插有一个非终结符）的优先关系，这些关系有三种：aba的优先级低于ba=ba的优先级等于baba的优先级高于b•这三种关系不同于数学中的,=,关系，ab不一定有ba等。3、算符优先文法和优先关系表的构造•算符优先分析法只适用于算符优先文法。（1）算符文法:一个文法，如果它的任一产生式右部都不含两个相继（并列）的非终结符，即不含如下形式产生式右部：如…QR…,Q,R∈VN，则称该文法为算符文法。G[E]:E→E＋E|E*E|(E)|iG[E]:E→EAE|(E)|iA→＋|*例×√3、算符优先文法和优先关系表的构造（2）算符优先关系:设G为算符文法且不含ε-产生式，a,b∈VT,算符间的优先关系定义为：a=b当且仅当G含有产生式P→…ab…或P→…aQb…ab当且仅当G含有产生式P→…aR…且R=b…或R=Qb…ab当且仅当G含有产生式P→…Rb…且R=…a或R=…aQ(3)算符优先文法:如果一个算符文法G中的任何终结符对(a,b)至多满足以上关系之一,则称G为算符优先文法。++++例：文法G:(1)E→E+T│T(2)T→T*F│F(3)F→P↑F│P(4)P→(E)│i算符优先关系为：由(4):P→(E)∴(=)由(1)(2):E→E+T,T=T*F∴+*由(2)(3):T→T*F,F=P↑F∴*↑由(1):E→E+T,E=E+T∴++由(3):F→P↑F,F=P↑F∴↑↑由(4):P→(E),E=E+T∴(+,+)...∴G为算符优先文法（优先关系表如表5.1所示,P90）＃看作终结符号G[E]:E→E＋E|E*E|(E)|i×(4)优先表的构造设P∈VN，定义：•FIRSTVT(P)={a│P=a…或P=Qa…,a∈VT,Q∈VN}•LASTVT(P)={a│P=…a或P=…aQ,a∈VT,Q∈VN}若已构造FIRSTVT(P)和LASTVT(P)，则可通过以下检查确定终结符对的优先关系：•若产生式有候选形如…aP…,则任b∈FIRSTVT(P),ab…•若产生式有候选形如…Pb…,则任a∈LASTVT(P),ab++++FIRSTVT(P)构造•规则1:若P→a…或P→Qa…,则a∈FIRSTVT(P);•规则2:若a∈FIRSTVT(Q),且P→Q…,则a∈FIRSTVT(P)。LASTVT(P)构造•规则1:若P→…a或P→…aQ,则a∈LASTVT(P);•规则2:若a∈LASTVT(Q),且P→…Q,则a∈LASTVT(P)。例：对文法G:(1)E→E+T│T(2)T→T*F│F(3)F→P↑F│P(4)P→(E)│iFIRSTVT(P)={(,i}FIRSTVT(F)={↑}+FIRSTVT(P)={↑,(,i}FIRSTVT(T)={*,↑,(,i}FIRSTVT(E)={+}+FIRSTVT(T)={+,*.↑,(,i}LASTVT(P)={),i}LASTVT(F)={↑}+LASTVT(P)={↑,),i}LASTVT(T)={*}+LASTVT(F)={*,↑,),i}LASTVT(E)={+}+LASTVT(T)={+,*,↑,),i}进而可写出优先关系FIRSTVT（P）的构造算法•数据结构:二维布尔矩阵M[P,a]和符号栈STACK.T.a∈FIRSTVT(P)布尔矩阵M[P,a]=.F.a∈FIRSTVT(P)栈STACK:存放使FIRSTVT为真的偶对(P,a).•算法:主程序+过程INSERT(P,a)PROCEDUREINSERT(P,a);IFNOTM[P,a]THENBEGINM[P,a]:=true;把(P,a)下推进STACK栈END;主程序:BEGINFOR每个非终结符P和终结符aDOM[P,a]:=FALSE;FOR每个形如P→a…或P→Qa…的产生式DOINSERT(P,a);WHILESTACK非空DOBEGIN把STACK的顶项(Q,a)弹出;FOR每条形如P→Q…的产生式DOINSERT(P,a);ENDOFWHILE;END结果:在二维数组F中,FIRSTVT(P)={a│M[P,a]=.T.}例:G:S→a│^│(T)T→T,S│S求FIRSTVT(S),FIRSTVT(T)类似地可得:LASTVT(S)={a,^,)}LASTVT(T)={a,^,),,}结果M=TTTFFTTTFTFIRSTVT(S)={a,^,(}FIRSTVT(T)={a,^,(,,}解:a＾(),初始M=SFFFFFTFFFFFa＾(),M=STTTFFTFTFFFSaS＾S(T,TT(TT＾TTa•优先关系表构造算法FOR每条产生式PX1X2…XnDOFORi:=1TOn-1DOBEGINIFXi和Xi+1均为终结符THEN置Xi=Xi+1IFi=n-2且Xi和Xi+2均为终结符但Xi+1为非终结符THEN置Xi=Xi+2;IFXi为终结符而Xi+1为非终结符THENFORFIRSTVT(Xi+1)中的每个aDO置Xia；IFXi为非终结符而Xi+1为终结符THENFORLASTVT(Xi)中的每个aDO置aXi+1END[例]G:S→a│^│(T)T→T,S│SFIRSTVT(S)={a,^,(}FIRSTVT(T)={a,^,(,,}LASTVT(S)={a,^,)}LASTVT(T)={a,^,),,}a^(),a^(=),优先关系4、算符优先分析算法的设计(1)最左素短语—算符优先分析中的可归约串•素短语:是一个短语,它至少含有一个终结符且除它自身之外不含有任何更小的素短语。•最左素短语：处于句型最左边的那个素短语。例1：对文法G:(1)E→E+T│T(2)T→T*F│F(3)F→P↑F│P(4)P→(E)│i求句型P*P+i的最左素短语解:句型的语法树为:EE+TTT*FFPPFPi句型的短语:P,P*P,i,P*P+i素短语:P*P,i最左素短语:P*P(2)定理:•算符优先文法句型(括在两个＃之间)的一般形式为:＃N1a1N2a2…NnanNn+1＃其中:ai∈VT,Ni∈VN(可有可无）•一个算符优先文法G的任何句型的最左素短语是满足下列条件的最左子串Njaj…NiaiNi+1aj-1ajaj=aj+1,=…=ai-1=aiaiai+1例:句型#P*P+i#中,#.*,*.+,所以P*P是最左素短语(3)算符优先分析算法：•用符号栈S实现最左素短语的查找,栈底放#。•用任意名字如N代替归约的非终结符。•算法大意：1）将输入串依此逐个存入符号栈S中，直到符号栈顶元素Sk与下一个待输入的符号a有优先关系Sk.a为止；2）至此，最左素短语尾符号Sk已在符号栈S的栈顶，由此往前再栈中找最左素短语的头符号Sj+1,直