同济大学编译原理第五章语法分析自下而上分析

第五章语法分析——自下而上分析概述自下而上分析法就是从输入串开始，逐步进行“归约”，直至归约到文法的开始符号。从语法树的末端，步步向上“归约”，直到根结。自上而下分析法:开始符号S⇒输入串α（推导）自下而上分析法:输入串α⇒开始符号S（归约）**内容线索自下而上分析基本问题算符优先分析方法规范归约LR分析方法归约移进-归约法使用一个符号栈，把输入符号逐一移进栈，当栈顶形成某个产生式右部时，则将栈顶的这一部分替换（归约）为该产生式的左部符号。例.给定文法G：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→d输入串abbcde是否为句子？归约过程如下：abbcdebabcdeAabcdebAacdeAacdecAadedcAaeabbcdeeBcAaSBcAae例.给定文法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分析树:用树表示“移进-归约”过程bdbaceSABA符号栈的使用实现移进-归约分析的一个方便途径是用一个栈和一个输入缓冲区，用#表示栈底和输入的结束栈输入串#w#栈输入串#S#初始最终例.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#接受语法分析的操作移进下一输入符号移进栈顶,读头后移；归约检查栈顶若干个符号能否进行归约，若能，就以产生式左部替代该符号串，同时输出产生式编号；接收移进－归约的结局是栈内只剩下栈底符号和文法开始符号，读头也指向语句的结束符；出错发现了一个语法错,调用出错处理程序注:可归约的串在栈顶,不会在内部语法树的表示——穿线表方法:在移进-归约过程中自下而上构造句子的语法树移进符号a时，构造表示端末结a的数据结构，其地址与a同时进栈a0An.....符号儿子数左部非终结符儿子数指向子结点的指针指向子结点的指针符号栈符号结点地址用A→X1X2…Xn归约时，构造新结A的数据结构，其地址与A同时进栈接受时，语法树已经构成，S及根地址在栈中例.i*i+i的语法树EE...3...E1.E1.i0*0i0+0i0E1.3自下而上分析的基本问题X→·bβA→·B→·如何找出或确定可规约串？对找出的可规约串替换为哪一个非终结符号？内容线索自下而上分析基本问题算符优先分析方法规范归约LR分析方法算符优先分析方法算符优先分析法是自下而上进行句型归约的一种分析方法。定义终结符（算符）的优先关系，按终结符（算符）的优先关系控制自下而上语法分析过程（寻找“可归约串”和进行归约）。分析速度快，适于表达式的语法分析。优先关系任何两个可能相继出现的终结符a和b（它们之间可能插有一个非终结符）的优先关系：aba的优先级低于ba=ba的优先级等于baba的优先级高于b注：这三种关系不同于数学中的,=,关系。算符文法一个文法，如果它的任一产生式右部都不含两个相继（并列）的非终结符，即不含如下形式的产生式右部：…QR…,Q,R∈VN则称该文法为算符文法。算符优先关系设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++++算符优先文法如果一个算符文法G中的任何终结符对(a,b)至多满足下述关系之一ab,则称G为算符优先文法。a=b,ab例.给定文法G：E→E+E|E*E|(E)|i其中：VT={+,*,i,(,)}。G是算符文法G是算符优先文法吗？考察终结符对(+,*)（1）因为E→E+E，且E⇒E*E，所以+*（2）因为E→E*E，且E⇒E+E，所以+*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为算符优先文法（＃看作终结符号，作为句子括号）优先关系表的构造通过检查G的每个产生式的每个候选式，可找出所有满足a=b的终结符对。确定满足关系和的所有终结符对：a=b当且仅当G含有产生式P→…ab…或P→…aQb…ab当且仅当G含有产生式P→…aR…且R⇒b…或R⇒Qb…ab当且仅当G含有产生式P→…Rb…且R⇒…a或R⇒…aQ++++FIRSTVT(P)和LASTVT(P)设P∈VN，定义：FIRSTVT(P)={a│P⇒a…或P⇒Qa…,a∈VT,Q∈VN}LASTVT(P)={a│P⇒…a或P⇒…aQ,a∈VT,Q∈VN}++++优先关系表的构造有了这两个集合之后，就可以通过检查每个产生式的候选式确定满足关系和的所有终结符对。假定有个产生式的一个候选形为…aP…那么，对任何bFIRSTVT(P)，有ab。假定有个产生式的一个候选形为…Pb…那么，对任何aLASTVT(P)，有ab。FIRSTVT(P)和LASTVT(P)构造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)。FIRSTVT(P)的构造——数据结构二维布尔矩阵F[P,a]和符号栈STACK.T.a∈FIRSTVT(P)布尔矩阵F[P,a]=.F.aFIRSTVT(P)栈STACK:存放使FIRSTVT为真的符号对(P,a).FIRSTVT(P)的构造——算法把所有初值为真的数组元素F[P,a]的符号对(P,a)全都放在STACK之中。如果栈STACK不空，就将栈顶逐出，记此项为(Q,a)。对于每个形如P→Q…的产生式，若F[P,a]为假，则变其值为真，且将(P,a)推进STACK栈。上述过程必须一直重复，直至栈STACK拆空为止。例.G:S→a│^│(T)T→T,S│S求FIRSTVT(S),FIRSTVT(T)类似地可得:LASTVT(S)={a,^,)}LASTVT(T)={a,^,),,}FIRSTVT(S)={a,^,(}FIRSTVT(T)={a,^,(,,}SaS＾S(T,T(T＾TaM=STFFFFFFFFFFa^(),TTTTTTTFIRSTVT主程序:BEGINFOR每个非终结符P和终结符aDOF[P,a]:=FALSE;FOR每个形如P→a…或P→Qa…的产生式DOINSERT(P,a);WHILESTACK非空DOBEGIN把STACK的顶项(Q,a)弹出;FOR每条形如P→Q…的产生式DOINSERT(P,a);ENDOFWHILE;ENDPROCEDUREINSERT(P,a);IFNOTF[P,a]THENBEGINF[P,a]:=true;把(P,a)下推进STACK栈END;FOR每条产生式P→X1X2…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^(=),优先关系最左素短语—算符优先分析中的可归约串短语令G是一个文法，S是文法的开始符号，若αβδ是文法G的一个句型，如果有S⇒αAδ且A⇒β则称β是句型αβδ相对于非终结符A的短语。素短语是一个短语，它至少含有一个终结符且除它自身之外不含有任何更小的素短语。最左素短语处于句型最左边的那个素短语。*+例.设文法G（S）：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→d给出句型aAbcde的短语。由S⇒aAcBe⇒aAcde⇒aAbcdeS⇒aAcBe⇒aAbcBe⇒aAbcde短语：d,Ab,aAbcde句型语法树和句型的短语短语句型语法树中每棵子树（某个结点连同它的所有子孙组成的树）的所有叶子结点从左到右排列起来形成一个相对于子树根的短语。例.设文法G（S）：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→d给出句型aAbcde的短语。SaAcBeAbd句型aAbcde的语法树为：短语：d,Ab,aAbcde例.对文法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*PEEF+*TiFTFTP+ETP句型：T+F*P+i短语：素短语：最左素短语：,T+F*P+iT,F,P,F*P,,iT+F*PF*P,iF*P例.对文法G:(1)E→E+T│T(2)T→T*F│F(3)F→P↑F│P(4)P→(E)│i算符优先文法的最左素短语算符优先文法句型(括在两个＃之间)的一般形式为:＃N1a1N2a2…NnanNn+1＃其中:ai∈VT,Ni∈VN(可有可无）一个算符优先文法G的任何句型的最左素短语是满足下列条件的最左子串Njaj…NiaiNi+1aj-1ajaj=aj+1=…=ai-1=aiaiai+1例.句型#P*P+i#中，#*,*+，所以P*P是最左素短语最左素短语一个算符优先文法G的任何句型的最左素短语是满足下列条件的最左子串Njaj…NiaiNi+1aj-1ajaj=aj+1=…=ai-1=aiaiai+1＃N1a1…aj-1Njaj…NiaiNi+1ai+1…NnanNn+1＃=R例.对文法G:(1)E→E+T│T(2)T→T*F│F(3)F→P↑F│P(4)P→(E)│iLASTVTFIRSTVTM=ET+*()iFP↑FTFTFFFTTTTTFTTTFFFFTTTTM=ET+*()iFP↑FTFTFFFTFFFFFTTTTTTTTTTT+*↑()i+*↑(=)i句型：T+F*P+i最左素短语：F*P例.对文法G:(1)E→E+T│T(2)T→T*F│F(3)F→P↑F│P(4)P→(E)│i+*↑()i+*↑(=)i+*+算符优先分析算法1）将输入串依此逐个存入符号栈S中，直到符号栈顶元素Sk与下一个待输入的符号a有优先关系Ska为止；2）至此，最左素短语尾符号Sk已在符号栈S的栈顶，由此往前在栈中找最左素短语的头符号Sj+1，直到找到第一个为止