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

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