编译原理 - 陈火旺版 - 第五章

1编译方法中国人民大学信息学院陈文萍2第五章语法分析——自下而上分析5.1自下而上分析基本问题5.2算符优先分析5.3LR分析法5.4语法分析器的自动产生工具YACC35.1自下而上分析基本问题自下而上语法分析试图将一个字符串反向归约至开始符号比自上而下语法分析更有效率，对语法的限制更少移进－归约过程移进：将一个终结符推进栈归约：当栈顶形成某个产生式的候选式时，把这些符号从栈中弹出，把产生式的左部符号压入栈4文法G[S]：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→dbbcdeA3）#abbcde#归约(A→b)A5）#aAbcde#归约(A→Ab)B8）#aAcde#归约(B→d)S10）#aAcBe#归约(S→aAcBe)分析符号串abbcde是否G[S]的句子步骤符号栈输入符号串动作1）#abbcde#移进2）#abbcde#移进4）#aAbcde#移进6）#aAcde#移进7）#aAcde#移进9）#aAcBe#移进11）#S#接受对输入串abbcde#的移进-规约分析过程SaAcBeaAcdeaAbcdeabbcdea5规范归约短语、直接短语、句柄的定义：文法G[S]，SαAδ且Aβ则称β是句型αβδ相对于非终结符A的短语。若有Aβ则称β是句型αβδ相对于该规则A→β的直接短语。一个句型的最左直接短语称为该句型的句柄。规范归约:设α是文法G的一个句子，称序列αn,αn-1,…,α0是α的一个规范规约，如果此序列满足：αn＝αα0为文法的开始符，即αn＝S对任何i,0i=n,αi-1是从αi经把句柄替换为相应产生式的左部符号而得到的自顶向下最右推导的逆过程规范推导：最右推导规范句型：规范推导所得的句型*6规范归约例句型归约规则abbcde(2)A→baAbcde(3)A→AbaAcde(4)B→daAcBe(1)S→aAcBeS从语法树角度看句柄：最左子树端末结的自左至右排列，这棵子树只有而且必须有父子两代SaAcBeAbbSaAcBeAbSddaAcBed7规约TintT+int|移进T+|int移进int|*int+int移进int*|int+int移进|int*int+intE|规约ET+ET+E|规约ETT+T|移进T|+int规约Tint*Tint*T|+int规约Tintint*int|+int文法G[E]：ET+E|TTint*T|int|(E)ETE+int*intTintT8移进－归约过程(1)+int*intint|int*int+int文法G[E]：ET+E|TTint*T|int|(E)9移进－归约过程(2)+int*intintint|*int+int|int*int+int文法G[E]：ET+E|TTint*T|int|(E)10移进－归约过程(3)+int*intintint|*int+intint*|int+int|int*int+int文法G[E]：ET+E|TTint*T|int|(E)11移进－归约过程(4)+int*intintint|*int+intint*|int+int|int*int+intint*int|+int文法G[E]：ET+E|TTint*T|int|(E)12移进－归约过程(5)+int*intintTint|*int+intint*|int+int|int*int+intint*T|+intint*int|+int文法G[E]：ET+E|TTint*T|int|(E)13移进－归约过程(6)T+int*intintTint|*int+intint*|int+int|int*int+intT|+intint*T|+intint*int|+int文法G[E]：ET+E|TTint*T|int|(E)14移进－归约过程(7)T+int*intintTT+|intint|*int+intint*|int+int|int*int+intT|+intint*T|+intint*int|+int文法G[E]：ET+E|TTint*T|int|(E)15移进－归约过程(8)T+int*intintTT+int|T+|intint|*int+intint*|int+int|int*int+intT|+intint*T|+intint*int|+int文法G[E]：ET+E|TTint*T|int|(E)16移进－归约过程(9)T+int*intTintTT+int|T+|intint|*int+intint*|int+int|int*int+intT+T|T|+intint*T|+intint*int|+int文法G[E]：ET+E|TTint*T|int|(E)17移进－归约过程(10)TE+int*intTintTT+int|T+|intint|*int+intint*|int+int|int*int+intT+E|T+T|T|+intint*T|+intint*int|+int文法G[E]：ET+E|TTint*T|int|(E)18移进－归约过程(11)ETE+int*intTintTT+int|T+|intint|*int+intint*|int+int|int*int+intE|T+E|T+T|T|+intint*T|+intint*int|+int文法G[E]：ET+E|TTint*T|int|(E)195.2算符优先分析定义算符之间（确切的说，终结符之间）的某种优先关系，借助这种优先关系寻找“可归约串”进行归约。任何两个可能相继出现的终结符a和b的优先关系：ab:a的优先性低于ba=b:a的优先性等于bab:a的优先性高于b20算符优先文法算符文法：如果不含空产生式的上下文无关文法G中没有形如U…QR…的产生式，其中Q,R∈VN，则称G为算符文法。算符优先文法：G为不含空产生式的算符文法，对于任何一对终结符a、b，我们说a=b当且仅当G中有形如P…ab…或P…aQb...的产生式。ab当且仅当G中有形如P…aR…的产生式,而Rb….或RQb…ab当且仅当G中有形如.P…Rb…的产生式,而R….a或R…aQ如果一个G中的任何终结符对(a,b)至多满足上述三种关系之一，则G为一个算符优先文法。21算符优先表的构造首先引入两个概念FIRSTVT(P)={a|Pa…或PQa...}对于非终结符P，其往下推导所可能出现的首个算符LASTVT(P)={a|P…a或P...aQ}对于非终结符P，其往下推导所可能出现的最后一个算符22算符优先表的构造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)23算符优先表的构造优先关系1)‘=‘关系：直接看产生式的右部，若出现了A→…ab…或A→…aBb，则a=b2)’‘关系：求出每个非终结符B的FIRSTVT(B)若A→…aB…,则b∈FIRSTVT(B)，ab3)’’关系：求出每个非终结符B的LASTVT(B)若A→…Bb…,则a∈LASTVT(B)，ab24文法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}+*()i#+*(=)i#=1)‘=’关系由产生式(0)和(6),得#=#，（=）2）‘’关系找形如：A→…aB…的产生式#E：则#FIRSTVT(E)+T:则+FIRSTVT(T)*F:则*FIRSTVT(F)F:则FIRSTVT(F)(E:则(FIRSTVT(E)3)‘’关系找形如：A→…Bb…的产生式E#,则LASTVT(E)#E+,则LASTVT(E)+T*,则LASTVT(T)*P,则LASTVT(P)E),则LASTVT(E))25算符优先分析算法归约过程中，只考虑终结符之间的优先关系来确定可归约串，而与非终结符无关不存在单个非终结符组成的可归约串，用算符优先分析法的归约过程与规范归约是不同的为解决在算符优先分析过程中如何寻找可归约串，引进最左素短语的概念26算符优先分析算法算符文法的任一句型有如下形式：#N1a1N2a2......NnanNn+1#,对于算符优先文法，如果aNb(或ab)出现在句型r中若ab，则在r中必含有b而不含a的短语存在若ab，则在r中必含有a而不含b的短语存在若a=b，则在r中含有a的短语必含有b，反之亦然句型的素短语是一个短语，它至少包含一个终结符，且除自身外不再包含更小的素短语。处于句型最左边的素短语为最左素短语定理：一个算符优先文法G的任何句型的最左素短语是满足下列条件的最左子串Njai…NiajNj+1aj-1aj，ai=ai＋1=...=aj-1=aj，ajai+127算符优先分析算法文法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→i句型#T+T*F+i#其短语有：T+T*F+iT+T*FTT*FiEET++ETF*FTTi最左素短语为：T*F28算符优先分析算法K:=1;S[k]:=‘#’;Repeata：＝下一个输入符号；IFS[k]∈VTTHENj:=kELSEj:=k-1;WHILES[j]aDOBEGINREPEATQ:=S[j];IFS[j-1]∈VTTHENj:=j-1ELSEj:=j-2UNTILS[j]Q;把s[j+1]…s[k]归约为某个N;k:=k+1;S[k]:=N;ENDOFWHILE;IFS[j]aORS[j]=aTHENBEGINk:=k+1;S[k]:=aENDELSEERROR/*调用出错诊察程序*/UNTILa=‘#’29优先函数优先函数比优先表节省空间优先函数的构造，优先函数f和g，对于终结符若θ1θ2，f(θ1)g(θ2)若θ1=θ2，f(θ1)=g(θ2)若θ1θ2，f(θ1)g(θ2)由优先表构造优先函数以每个终结符a的fa,ga为结点的有向图,若a=b,则画一条从fa到gb的弧若a=b,则画一条从gb到fa的弧f(a),g(a)为从出发所能到达的结点数,包括自身检查f(a)和g(a),是否有矛盾,若有,则不存在优先函数30算符优先文法的错误处理错误种类栈顶的终结符与下一个输入符之间没有优先关系栈顶出现了素短语,但没有一个产生式的右部为此素短语错误处理改变,插入,删除符号给出错误信息31LR分析法能力强大部分上下文无关文法都能用LR分析识别效率高，准确发现输入串错误难点手工编写LR分析器工作量大现实有LR分析器的生成器，如YACC32LR分析法LR含义L：从左到右扫描输入串，R：构造最右推导LR分析特征栈顶状态为S,当前输入符号是a时做什么---?四种技术LR(0)SLR规范LRLALR33LR分析器LR分析器模型分析程序outputInput#S1