编译原理,课件第6章 自底向上优先分析法

第6章自底向上优先分析法自底向上优先分析法简单优先分析法算符优先分析法算符优先文法的定义算符优先关系表的构造算符优先分析算法算符优先分析法的局限性自底向上分析法自底向上分析法，也称移进-规约分析法。思想：对输入符号串自左向右进行扫描，并将输入符逐个移入一个栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄或可规约串（该句柄对应某产生式的右部）时，就用产生式左部的非终结符代替之；这称为一步规约。自底向上分析的移进-规约过程是自顶向下的最右推导的逆过程。将输入分成两部分：未消化的和半消化的总控程序outputInput#未消化的半消化的分析表产生式表例子G[S]：S-aAcBeA-bA-AbB-dabbcde的最右推导为：SaAcBeaAcdeaAbcdeabbcde输入串abbcde例子（续）G[S]：S-aAcBeA-bA-AbB-dabbcde的移进-规约过程为：SaAcBeaAcdeaAbcdeabbcde输入串abbcde文法G[S]：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→dabbcde步骤符号栈输入符号串动作1）#abbcde#移进2）#abbcde#移进A3）#abbcde#归约(A→b)4）#aAbcde#移进A5）#aAbcde#归约(A→Ab)6）#aAcde#移进7）#aAcde#移进B8）#aAcde#归约(B→d)9）#aAcBe#移进11）#S#接受S10）#aAcBe#归约符号串abbcde是否是G[S]的句子对输入串abbcde#的移进-规约分析过程SaAcBeaAcdeaAbcdeabbcde自底向上的移进-规约过程也是自底向上构造语法树的过程，每步规约都是构造一棵子树；输入串结束时刚好构造出整个语法树。规约过程总是对出现在栈顶的句柄进行。如何确定句柄呢？自底向上优先分析法优先分析法分为：简单优先分析法和算符优先分析法。简单优先分析法：按一定的原则求出该文法所有符号（终结符和非终结符）之间的优先关系，按照这种关系确定规约过程中的句柄；是规范规约。算符优先分析法：只规定算符（终结符）之间的优先关系；不是规范规约。适用于表达式的规约。简单优先分析优先关系：X=Y表示X和Y的优先关系相等；XY表示X的优先性比Y的优先性大；XY表示X的优先性比Y的优先性小；优先关系定义：X=Y当且仅当G中存在产生式规则A…XY...XY当且仅当G中存在产生式规则A…XB...，且BY...XY当且仅当G中存在产生式规则A…BD...，且B...X和DY...*例子G[S]：S-bAbA-(B|aB-Aa)(1)=关系：b=A,A=b,(=B,A=a,a=)(2)关系b(,ba;((,(a,(A(3)关系)b,ab,Bb;)a,aa,Ba;以上关系也可从语法树中得到！简单优先文法满足以下条件的文法：(1)在文法符号集V中，任意两个符号之间最多只有一种优先关系成立；(2)在文法中任意两个产生式没有相同的右部。简单优先分析法根据已知优先文法构造相应优先关系矩阵，设置符号栈S；算法如下：(1)将输入符号串a1a2…an#依次存入符号栈S，直到栈顶符号ai的优先性下一输入符号aj时为止。(2)栈顶当前符号ai为句柄末尾符，由此向下在栈中找句柄的头符号ak，即找到ak-1ak为止。(3)由句柄ak…ai在文法产生式中查找右部为ak…ai的产生式，若找到则用相应左部代替句柄；若找不到则出错。(4)重复上述步骤直到规约完输入符号串。算符优先分析法算符优先分析自下而上分析算法：模型（移进-归约）算符优先分析不是规范归约适用于算术表达式的语法分析分析程序模型总控程序算符优先关系表产生式输入串##输出对输入串i+i*i#的规约过程步骤栈当前符号剩余输入移进或规约1#i+i*i#移进2#i+i*i#规约33#E+i*i#移进4#E+i*i#移进5#E+i*i#规约36#E+E*i#移进7#E+E*i#移进8#E+E*i#规约39#E+E*E#规约210#E+E#规约111#E#接受G[E]：E→E+E|E*E|iReview优先关系：X=Y表示X和Y的优先关系相等；XY表示X的优先性比Y的优先性大；XY表示X的优先性比Y的优先性小；注意：优先关系是有序的；若ab,不一定有ba；a=b，不一定有b=a。如何确定算符优先关系？事先人为规定算符的优先顺序：直观算符优先分析法按规则计算算符之间的优先关系：算符优先文法直观算符优先分析法人为确定：（优先级及结合性质）（1）i的优先级最高（2）优先级次于i，右结合（3）*和/优先级次之，左结合（4）+和-优先级最低，左结合（5）括号‘(’,‘)’的优先级大于括号外的运算符，小于括号内的运算符，内括号的优先性大于外括号（6）#的优先性低于与其相邻的算符文法G[E]：E→E+E|E-E|E*E|E/E|EE|(E)|i+-*/()i#+-*/(=)i#=算符优先关系表算符优先文法的定义•定义：如果不含空产生式的上下文无关文法G中没有形如A…BC…的产生式，其中B，C∈VN则称G为算符文法（OG）。例1G[E]：E→E+E|E-E|E*E|E/E|EE|(E)|i例2G’[E]:E→E+T|TT→T*F|FF→PF|PP→(E)|i算符优先文法的性质性质1：在算符文法中任何句型都不包含两个相邻的非终结符。（证明用归纳法，对推导步长进行归纳。）性质2：如Ab或bA出现在算符文法的句型中，其中A∈VN，b∈VT，则中任何含b的短语必含有A。性质2的证明用反证法，设存在含b的短语不包含A。若Sγ=bAβ，则存在B2b且=12，因而有，S1BAβ，与性质1矛盾。***算符优先关系在OG中定义（算符优先关系）：a=bG中有形如：A…ab…或A…aBb...的产生式。abG中有形如:A…aB…的产生式,而Bb…或BCb…abG中有形如:A…Bb…的产生式,而B…a或B…aC规定：若Sa…或SCa…则#a若S…a或S…aC则a#在OG文法G中，若任意两个终结符间至多有一种算符优先关系存在，则称G为算符优先文法(OPG)。注意：优先关系的有序性。允许bc,cb；不允许bc,bc,b=c中任两个同时存在；b=c不一定c=b；如例7.1中：“（”=“）”，“）”“（”。结论:算符优先文法是无二义的。算符优先关系表的构造首先定义如下两个集合：FIRSTVT(B)=｛b｜Bb…或BCb…｝LASTVT(B)=｛a｜B…a或B…aC｝按如下算法计算出给定文法中任何两个终结符对(a,b)之间的优先关系：1)‘=‘关系–直接看产生式的右部，若出现了A→…ab…或A→…aBb,则a=b2)’‘关系–求出每个非终结符B的FIRSTVT(B)–若A→…aB…,则b∈FIRSTVT(B),则ab3)’’关系–求出每个非终结符B的LASTVT(B)–若A→…Bb…,则a∈LASTVT(B),则ab计算算符优先关系例文法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}Forward(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→i3)‘’关系找形如：A→…Bb…的产生式E#:则LASTVT(E)#E+:则LASTVT(E)+T*:则LASTVT(T)*P:则LASTVT(P)E):则LASTVT(E))2）‘’关系找形如A→…aB…的产生式#E：则#FIRSTVT(E)+T:则+FIRSTVT(T)*F:则*FIRSTVT(F)F:则FIRSTVT(F)(E:则(FIRSTVT(E)1)‘=’关系由产生式(0)和(6),得#=#，(=)表达式文法G’[E’]的算符优先关表+*()i#+*(=)i#=FIRSTVT和LASTVT的其它计算方法基于规则进行计算的方法：需要建立布尔数组F[A,a]和栈；关系图法计算FIRSTVT和LASTVT；Skip基于规则的计算方法有以下规则：(a)若有产生式A→a…或A→Ba…，则a∈FIRSTVT(A)，其中A、B为非终结符，a为终结符；(b)若a∈FIRSTVT(B)且有产生式A→B…，则有a∈FIRSTVT(A)。基于规则的计算方法（续）建立布尔数组F[A,a]和栈STACK；F[A,a]的值为真当且仅当a∈FIRSTVT(A)。首先按规则(a)对数组元素F[A,a]赋初值，并将初值为真的符号对(A,a)放入栈中。当栈STACK不空时，将栈顶弹出，记为(B,a)，使用规则(b)，若F[A,a]为假则令其为真，并将(A,a)压入栈；直到栈空为止。类似的，可计算LASTVT(A)。+*i（）#E’ETFP布尔数组的值111111111111111文法G简单关系图法例文法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)FIRSTVT(T)FIRSTVT(F)FIRSTVT(P)+(*iFOR每个产生式AX1X2…XnDOFORi:=1TOn-1DOBEGINIFXi和Xi+1均为终结符THEN置Xi=Xi+1；IFi=n-2ANDXi和Xi+2均为终结符,Xi+1为非终结符THEN置Xi=Xi+2；IFXi为终结符而Xi+1为非终结符THENFORFIRSTVT(Xi+1)中的每个bDO置Xib；IFXi为非终结符而Xi+1为终结符THENFORLASTVT(Xi)中的每个aDO置aXi+1；END算符优先关表的构造算法Skip关系图法构造优先关系表定义设文法G为上下文无关文法，在V上定义以下关系：AFIRSTB当且仅当存在形如A→B…的产生式ALASTB当且仅当存在形如A→…B的产生式BFIRSTTERMb当且仅当存在形如B→b…，或者B→Cb…的产生式BLASTTERMa当且仅当存在形如B→…a，或者B→…aC的产生式XFOLLOWEDBYY当且仅当存在形如A→…XY…的产生式，X、Y中一为终结符，一为非终结符AFIRST*B当且仅当A=B或存在形如A→X1…，X1→X2…，…，Xn-1→Xn…，Xn→B…的产生式序列ALAST*B当且仅当B=A或存在形如A→…X1，X1→…X2，…，Xn-1→…Xn，Xn→…B的产生式序列Bb…或BCb…等价于BFIRST*PPFIRSTTERMb因此，当文法中有形如A→…aB…的产生式存在时，则a，b之间的关系可写成：ab等价于aFOLLOWEDBYBBFIRST*PPFIRSTTERMb构造关系图•关系图的每个结点为文法符号；•凡有终结符在前非终结符在后相邻关系的则由终结符结点到非终结符结点画一箭弧；•对有FIRSTTERM关系的非终结符和终结符对，则从非终结符结点到终结符结点画一箭弧；•对非终结符对之间存在FIRST关系的，从左边的非终结符结点到右边的非终结符结点画一箭弧；•对每