東北大學(xué)秦皇島分校編譯原理課件第六章.ppt

第6章 自底向上優(yōu)先分析法,自底向上分析法的基本思想及主要方法,自底向上分析法也稱移進(jìn)-歸約法。 自底向上分析法的基本思想是：從待輸入的符號(hào)串開始，利用文法的規(guī)則步步向上歸約，試圖歸約到文法的識(shí)別符號(hào)。 從語(yǔ)法樹的角度來(lái)看：自底向上分析的過程是以輸入符號(hào)串作為末端結(jié)點(diǎn)符號(hào)串，向著根結(jié)點(diǎn)的方向往上構(gòu)造語(yǔ)法樹，使識(shí)別符號(hào)正好是該語(yǔ)法樹的根結(jié)點(diǎn)。 自底向上分析法的關(guān)鍵在于：如何在每一步歸約當(dāng)中，找到當(dāng)前句型的句柄，并判斷句柄是否唯一。 主要的分析方法有：簡(jiǎn)單優(yōu)先分析法、算符優(yōu)先分析法、LR類分析法。,自底向上分析法中面臨的問題及解決方法,采用自底向上分析法分析的每一步中，會(huì)遇到兩個(gè)基本問題： （1）如何找出進(jìn)行直接歸約的簡(jiǎn)單短語(yǔ)？ （2）找出的簡(jiǎn)單短語(yǔ)應(yīng)直接歸約到哪一個(gè)非終結(jié)符號(hào)？ 解決方法：由于分析過程是從左往右掃描源程序，所以遇到的第一個(gè)簡(jiǎn)單短語(yǔ)正好是句柄，因此，第一個(gè)問題變?yōu)椋喝绾握业骄浔?。?duì)于如何找到句柄，找到句柄后應(yīng)歸約到哪一個(gè)非終結(jié)符號(hào)這兩個(gè)問題，不同的自底向上分析法有不同的解決方法。 簡(jiǎn)單短語(yǔ)：只經(jīng)過一次推導(dǎo)得到的短語(yǔ)叫簡(jiǎn)單短語(yǔ)； 句柄： 句型的最左簡(jiǎn)單短語(yǔ)。,自底向上分析法的基本實(shí)現(xiàn)方法,自底向上分析的基本實(shí)現(xiàn)方法是：移進(jìn)-歸約法。 引入“#”作為棧底標(biāo)志符號(hào)。 在整個(gè)分析過程中，共有4類動(dòng)作： （1）移入：讀入下一個(gè)輸入符號(hào)并把它下推進(jìn)棧。 （2）歸約：當(dāng)棧頂?shù)模ú糠郑┓?hào)串形成一個(gè)句柄時(shí)，對(duì)此句柄進(jìn)行歸約，把形成句柄的符號(hào)串替換為相應(yīng)的非終結(jié)符號(hào)。 （3）接受：當(dāng)識(shí)別程序發(fā)現(xiàn)棧頂除了棧底標(biāo)志符號(hào)#外僅有識(shí)別符號(hào)，而輸入也以達(dá)到右端標(biāo)志符號(hào)#時(shí)，便識(shí)別出輸入符號(hào)串是一個(gè)句子，執(zhí)行接受動(dòng)作并結(jié)束本次識(shí)別。 （4）報(bào)錯(cuò)：發(fā)現(xiàn)輸入符號(hào)串不是句子而無(wú)法繼續(xù)識(shí)別。,自底向上優(yōu)先分析法的基本思想,常見的自底向上的分析算法： （1）優(yōu)先分析法 （2）LR類分析法 優(yōu)先分析法分為： （1）簡(jiǎn)單優(yōu)先分析法：采用規(guī)范歸約，考慮所有文法符號(hào)（包括終結(jié)符號(hào)、非終結(jié)符號(hào)）之間的優(yōu)先關(guān)系。 （2）算符優(yōu)先分析法：不是規(guī)范歸約，只考慮算符（即終結(jié)符號(hào)）之間的優(yōu)先關(guān)系。 自底向上優(yōu)先分析法的基本思想： 利用文法符號(hào)中相鄰符號(hào)之間的優(yōu)先關(guān)系找出句柄。,簡(jiǎn)單優(yōu)先分析法及簡(jiǎn)單優(yōu)先文法,簡(jiǎn)單優(yōu)先分析法按照文法符號(hào)（終結(jié)符號(hào)和非終結(jié)符號(hào)）的優(yōu)先關(guān)系確定句柄。 如何確定任意兩個(gè)文法符號(hào)之間的優(yōu)先關(guān)系？ 如何構(gòu)造優(yōu)先關(guān)系表,補(bǔ)充內(nèi)容,FIRST關(guān)系：U FIRST S存在規(guī)則 US（注：S可以是終結(jié)符號(hào)，也可以是非終結(jié)符號(hào)。） FIRST關(guān)系的傳遞閉包： FIRST+= FIRST FIRST2 FIRST3 LAST關(guān)系： U LAST S存在規(guī)則 US（注：S可以是終結(jié)符號(hào)，也可以是非終結(jié)符號(hào)。） LAST關(guān)系的傳遞閉包： LAST += LAST LAST 2 LAST 3 ,例：求文法G的FIRST關(guān)系和LAST關(guān)系,GA：AAf|B BDdc|De Ce DBf, AAf AB BDdc BDe Ce DBf, A FIRST A A FIRST B B FIRST D B FIRST D C FIRST e D FIRST B,FIRST=（A，A），（A，B），（B，D），（C，e），（D，B）, A LAST f A LAST B B LAST c B LAST e C LAST e D LAST f,LAST=（A，f），（A，B），（B，c） ，（B，e） ，（C，e），（D，f）,FIRST=（A，A），（A，B），（B，D），（C，e），（D，B） FIRST2=（A，A），（A，B），（A，D），（B，B），（D，D） FIRST3=（A，A），（A，B），（A，D），（B，D），（D，B） FIRST4= FIRST2 FIRST+= FIRST FIRST2 FIRST3 = (A，A)，(A，B)，(A，D)，(B，D)， (C，e)，(D，B) ，(D，D),LAST=(A，f)，(A，B)，(B，c) ，(B，e) ，(C，e)，(D，f) LAST+=(A，f)，(A，B)，(A，c) ，(A，e) ，(B，c) ，(B，e) ，(C，e)，(D，f),優(yōu)先關(guān)系的形式定義： （1）相等關(guān)系 X=Y：當(dāng)且僅當(dāng)G中存在規(guī)則 AXY （2）小于關(guān)系X Y） （3）大于關(guān)系XY：當(dāng)且僅當(dāng)G中存在規(guī)則 ABD，且 B LAST+ X （即B=X）和 D FIRST* Y（即D= Y）。在此限定S為終結(jié)符號(hào)。 簡(jiǎn)單優(yōu)先文法滿足條件： （1）在文法符號(hào)集V中，任意兩個(gè)符號(hào)之間最多只有一種優(yōu)先關(guān)系成立。 （2）在文法中任意兩個(gè)產(chǎn)生式?jīng)]有相同的右部。 由簡(jiǎn)單優(yōu)先文法的定義可知，簡(jiǎn)單優(yōu)先文法是無(wú)二義性的。,+,+,*,構(gòu)造優(yōu)先關(guān)系,構(gòu)造相等關(guān)系“=”很簡(jiǎn)單，只需要順次考察文法的各規(guī)則即可。如：例6.2（1）。 構(gòu)造大于和小于關(guān)系，可以使用如下兩個(gè)公式：,其中，（FIRST*）為FIRST的自反傳遞閉包； （LAST+）T為L(zhǎng)AST+的逆關(guān)系。,例：構(gòu)造文法GZ的簡(jiǎn)單優(yōu)先關(guān)系表,GS：SbAb， A（B|a， BAa）,首先構(gòu)造相等（=）關(guān)系。根據(jù)文法規(guī)則： = = （b，M）, （M，b） ,（，L ），（A，a） ,（a，） ,構(gòu)造小于（）關(guān)系： FIRST= （S，b）,（A，（ ）,（A，a）,（B，A） FIRST+= （S，b） ,（A，（ ） ,（A，a） ,（B，A） ,（B，（） ,（B，a） =（=）（ FIRST+）= （b，（ ）,（b，a）,（，A）,（，（）,（，a） ,構(gòu)造大于（）關(guān)系： LAST=（S，b）,（A，B）,（A，a）,（B，） LAST+=（S，b）,（A，B）,（A，a）,（A，）,（B，） （LAST+）T=（b，S）,（B，A）,（a，A）,（），B）,（），A） = （LAST+）T（=）（FIRST *） = （B，b）,（B，a）,（a，b）,（a，a）,（ ），b）,（ ），a）,文法GZ的優(yōu)先關(guān)系矩陣,課堂練習(xí)： 利用公式求出例6.2的三個(gè)優(yōu)先關(guān)系，并給出其優(yōu)先關(guān)系矩陣。,簡(jiǎn)單優(yōu)先分析法算法,根據(jù)給定的簡(jiǎn)單優(yōu)先文法構(gòu)造出相應(yīng)的簡(jiǎn)單優(yōu)先關(guān)系表，并將文法的產(chǎn)生式保存，設(shè)置符號(hào)棧S，再根據(jù)如下算符步驟進(jìn)行分析： （1）將輸入符號(hào)串a(chǎn)1a2an#依次逐個(gè)存入符號(hào)棧S中，直到遇到棧頂符號(hào)ai的優(yōu)先性下一個(gè)待輸入符號(hào)aj時(shí)為止。 （2）棧頂當(dāng)前符號(hào)ai尾句柄尾，由此向左在棧中找句柄的頭符號(hào)ak，即找到ak-1 ak，為止。 （3）由句柄akai在文法的產(chǎn)生式中查找右部尾akai的產(chǎn)生式，若找到則用相應(yīng)左部代替句柄，若找不到則出錯(cuò)。 （4）重復(fù)上述三個(gè)步驟直到規(guī)約完輸入符號(hào)串，棧中只剩文法的開始符號(hào)或出錯(cuò)為止。,算符優(yōu)先分析法,算符優(yōu)先分析法常用于高級(jí)語(yǔ)言的表達(dá)式的語(yǔ)法分析。 算符優(yōu)先關(guān)系的形式定義： （1）相等關(guān)系 a=b：當(dāng)且僅當(dāng)G中存在 Aab 或 AaBb 的規(guī)則。 （2）小于關(guān)系a b 或 B= Cb （3）大于關(guān)系a b：當(dāng)且僅當(dāng)G中存在規(guī)則 ABb，且 B=a 或 B=aC 算符優(yōu)先分析法的基本思想：根據(jù)算符（廣義為終結(jié)符號(hào)）之間的優(yōu)先關(guān)系來(lái)決定如何歸約。,+,+,+,+,算符文法及其性質(zhì),算符文法的形式定義： 設(shè)有一文法G，如果G中沒有形如ABC的規(guī)則，其中B和C為非終結(jié)符，則稱G為算符文法，也稱OG文法。 算符文法的性質(zhì)： （1）在算符文法中任何句型都不包含兩個(gè)相鄰的非終結(jié)符。 （2）如果Ab（或bA）出現(xiàn)在算符文法的句型中，其中AVN，bVT，則中任何含b的短語(yǔ)必含有A。,算符優(yōu)先文法及其性質(zhì),算符優(yōu)先文法的形式定義： 設(shè)有一不含產(chǎn)生式的算符文法G，如果對(duì)任意兩個(gè)終結(jié)符對(duì)a,b之間至多只有=、三種關(guān)系中的一種成立，則稱G是一個(gè)算符優(yōu)先文法。也稱為OPG文法。 算符優(yōu)先文法的性質(zhì)： 如果aNb或ab出現(xiàn)在句型r中，則a和b之間有且僅有一種優(yōu)先關(guān)系即： （1） 若a b 則 在r中必有含a而不含b的短語(yǔ)存在 （3）若a = b 則 在r中含有a的短語(yǔ)必含有b，反之亦然。,算符優(yōu)先關(guān)系表的構(gòu)造,由定義直接構(gòu)造 （1）FIRSTVT集合：FIRSTVT（B）=b|B=b或B=Cb （2）LASTVT集合： LASTVT（B）=a|B=a或B=aC 由關(guān)系圖法構(gòu)造 （1）FIRST關(guān)系：A FIRST B 當(dāng)且僅當(dāng)存在形如 AB 的產(chǎn)生式。 （2）LAST關(guān)系： A LAST B 當(dāng)且僅當(dāng)存在形如 A B 的產(chǎn)生式。 （3）FIRSTTERM關(guān)系：B FIRSTTERM b 當(dāng)且僅當(dāng)存在形如 Bb 或 BCb的產(chǎn)生式。 （4）LASTTERM關(guān)系：B FIRSTTERM a 當(dāng)且僅當(dāng)存在形如 Ba 或 BaC的產(chǎn)生式。 （5）FOLLOWEDB關(guān)系：X FOLLOWEDB Y 當(dāng)且僅當(dāng)存在形如 AXY 的產(chǎn)生式（X、Y中必須是一個(gè)為終結(jié)符，另一個(gè)為非終結(jié)符）。 用公式法構(gòu)造 （1） =（LAST*）（LASTTERM）T（=）,+,+,+,+,編譯方法中對(duì)公式的證明： 注意：此處相等關(guān)系的符號(hào)為“”，與教材采用的符號(hào)不同。規(guī)則中連接左部與右部的符號(hào)也不同，為EBNF中的形式。,例：用公式構(gòu)造文法GE的算符優(yōu)先關(guān)系表,課堂練習(xí)：求該文法的優(yōu)先關(guān)系“”,用程序構(gòu)造算符優(yōu)先關(guān)系的方法和步驟,教材6.3.3,算符優(yōu)先分析法與最左素短語(yǔ),引入最左素短語(yǔ)的目的： 解決在算符優(yōu)先分析過程中如何尋找句柄的問題。 最左素短語(yǔ)的形式定義： 設(shè)有文法GS，其句型的素短語(yǔ)是一個(gè)短語(yǔ)，該短語(yǔ)至少包含一個(gè)終結(jié)符，并且除自身外不包含其他素短語(yǔ)，最左邊的素短語(yǔ)稱最左素短語(yǔ)。由句型的語(yǔ)法圖我們可以直接找出所有的素短語(yǔ)和最左素短語(yǔ)。 算符優(yōu)先分析法的關(guān)鍵問題是尋找最左素短語(yǔ)。 算符優(yōu)先分析法的局限性：算符優(yōu)先分析法去掉了單個(gè)非終結(jié)符之間的歸約，使得其在分析過程中很難完全避免把錯(cuò)誤的句子得到正確的歸約。,算符優(yōu)先分析法算法,算符優(yōu)先分析法的算法用到一個(gè)符號(hào)棧S和一個(gè)存放輸入符號(hào)串的數(shù)組R，算法中的Q為一工作單元，用于存放待比較的終結(jié)符號(hào)： （1）將輸入符串R1R2RK依次逐個(gè)存入符號(hào)棧S中，直至符號(hào)棧頂元素Sj與下一個(gè)待輸入的符號(hào)Rk有關(guān)系Sj Rk為止； （2）最左素短語(yǔ)尾Sj已在符號(hào)棧S的棧頂，由此往前（左）在棧中找最左素短語(yǔ)的頭