第4章(2)語(yǔ)法分析遞歸預(yù)測(cè)分析

1、4.2.4 遞歸下降分析法 遞歸下降分析法是確定的自上而下分析法，這種分析法要求文法是LL(1)文法。 4.2.4 遞歸下降分析法基本思想 對(duì)文法中的每個(gè)非終結(jié)符編寫(xiě)一個(gè)函數(shù) (或子程序), 每個(gè)函數(shù)（或子程序）的功能是識(shí)別由該非終結(jié)符所表示的語(yǔ)法成分。由于描述語(yǔ)言的文法常常是遞歸定義的，因此相應(yīng)的這組函數(shù)（或子程序）必然以相互遞歸的方式進(jìn)行調(diào)用，所以將此種分析法稱為遞歸下降分析法。 4.2.4 遞歸下降分析法構(gòu)造遞歸下降分析程序的方法: 為每個(gè)非終結(jié)符編制一個(gè)遞歸下降分析函數(shù)，每個(gè)函數(shù)名是相應(yīng)的非終結(jié)符，函數(shù)體則是根據(jù)規(guī)則右部符號(hào)串的結(jié)構(gòu)和順序編寫(xiě)。A12niVTiVN 12n=4.2.4

2、遞歸下降分析法(1) 當(dāng)遇到終結(jié)符a時(shí)，則編寫(xiě)語(yǔ)句 if (當(dāng)前讀來(lái)的輸入符號(hào)=a) 讀下一個(gè)輸入符號(hào)； (2) 當(dāng)遇到非終結(jié)符A時(shí)，則編寫(xiě)語(yǔ)句調(diào) 用 A( )； (4) 當(dāng)某個(gè)非終結(jié)符的規(guī)則有多個(gè)候選式 時(shí)，按LL(1)文法的條件能唯一地選 擇一個(gè)候選式進(jìn)行推導(dǎo)。 (3) 當(dāng)遇到規(guī)則A 時(shí)，則編寫(xiě)語(yǔ)句 4.2.4 遞歸下降分析法if (當(dāng)前讀來(lái)的輸入符號(hào)FOLLOW(A) error( )；E E + T | TT T * F | FF (E) | id 例 設(shè)有文法GE：試構(gòu)造一個(gè)識(shí)別該文法句子的遞歸下降分析程序。 4.2.4 遞歸下降分析法分析 首先消去文法左遞歸，得到文法 GEE TE

3、E +TE | T FTT *FT | F (E) | idEE + T |TTT * F |FF(E) | id 4.2.4 遞歸下降分析法 無(wú)左遞歸的文法不一定是LL(1)文法，根據(jù)LL(1)文法的判斷條件，對(duì)非終結(jié)符 E, T, F有： E TEE +TE | T FTT *FT | F (E) | id4.2.4 遞歸下降分析法ETEETE T FTF (E) (TE ) ETE T FT +ETE FT + TE +ETE (FT ) SELECT(E +TE)SELECT(E ) =FIRST(+TE)FOLLOW(E) = + ), $ = SELECT(T *FT)SELECT

4、(T ) =FIRST(*FT)FOLLOW(T) = * ), $, + = 4.2.4 遞歸下降分析法 SELECT(Fid )SELECT(F(E) = FIRST(id)FIRST(E)=id(=所以文法GE是LL(1)文法。 4.2.4 遞歸下降分析法分析程序中定義兩個(gè)函數(shù)：(1) 函數(shù) Scaner( ) 功能: 讀進(jìn)源程序的下一個(gè)單詞符號(hào) 并將它放在全程變量sym。(2) 函數(shù) error( ) 功能: 出錯(cuò)處理程序。 4.2.4 遞歸下降分析法 對(duì)文法GE可寫(xiě)出相應(yīng)的遞歸下降分析程序如下： E TEE +TE | T FTT *FT | F (E) | idmain( ) Sc

5、aner ( ); E ( ); if (sym= =$) printf (“success”); else printf (“fail”); 4.2.4 遞歸下降分析法E ( ) T( ); E( ); E( ) if (sym = =+) Scaner( ); T ( ) ; E ( ); else if (sym!=)&(sym!=$) error( ); 4.2.4 遞歸下降分析法E TEE +TE | T FT T *FT | F (E) | idT ( ) F ( ) ; T ( ); E TEE +TE | T FT T *FT | F (E) | idT ( ) if (sym

6、 = =*) Scaner( ); F ( ) ; T ( ); else if (sym follow(T) error( ); 4.2.4 遞歸下降分析法F ( ) if (sym= = id) Scaner ( ); else if (sym= = () Scaner( ) ; E ( ); if (sym = = ) ) Scaner ( ); else error ( ); else error ( ); E TE E +TE | T FT T *FT | F (E) | id4.2.4 遞歸下降分析法4.2.4 遞歸下降分析法main( ) Scaner ( ); E ( ); i

7、f (sym= =$) printf (“success”); else printf (“fail”); id + id $E ( ) T( ); E ( ); T ( ) F ( ) ; T ( ); 見(jiàn)F見(jiàn)E見(jiàn)T返回下一頁(yè)F ( ) if (sym= = id) Scaner ( ); else if (sym= = () Scaner( ) ; E ( ); if (sym = = ) ) Scaner ( ); else error ( ); else error ( ); 4.2.4 遞歸下降分析法返回T4.2.4 遞歸下降分析法T ( ) if (sym = =*) Scaner

8、( ); F ( ) ; T ( ); else if (sym follow(T) error( ); follow(T)=+, ), $ 返回T4.2.4 遞歸下降分析法E ( ) if (sym = =+) Scaner( ); T ( ) ; E ( ); else if (sym!=)&(sym!=$) error( ); 返回E見(jiàn)T返回E 對(duì)這個(gè)例子，若采用擴(kuò)充的BNF表示法改寫(xiě)文法，得到GE：E T +T T F *F F (E) | id4.2.4 遞歸下降分析法EE + T |TTT * F |FF(E) | id 該文法是LL(1)文法，其遞歸下降分析程序中主函數(shù)和函數(shù)F(

9、 )同上，對(duì)函數(shù)E( )和函數(shù)T( )用while語(yǔ)句描述如下： 4.2.4 遞歸下降分析法E ( ) T ( ); while ( sym = =+) Scanner ( ); T ( ); T ( ) F ( ); while ( sym = =*) Scanner ( ); F ( ); E T +T T F *F F (E) | id4.2.4 遞歸下降分析法缺點(diǎn): 對(duì)文法要求高，必須是LL(1)文 法，同時(shí)由于遞歸調(diào)用較多，影 響分析器的效率。 優(yōu)點(diǎn): 遞歸下降分析法簡(jiǎn)單、直觀，易 于構(gòu)造分析程序。 4.2.4 遞歸下降分析法4.2.5 預(yù)測(cè)分析法與預(yù)測(cè)分析表的構(gòu)造 預(yù)測(cè)分析法(LL

10、(1)分析法)是確定的自上而下分析的另一種方法，采用這種方法進(jìn)行語(yǔ)法分析要求描述語(yǔ)言的文法是LL(1)文法。 預(yù)測(cè)分析器的邏輯結(jié)構(gòu)預(yù)測(cè)分析表總控程序 a1 a2 ai an $T j 輸入串 X $輸出4.2.5 預(yù)測(cè)分析法與預(yù)測(cè)分析表的構(gòu)造分析棧 輸入緩沖區(qū)Tj中存放待分析的輸入符號(hào)串，它以右界符 $ 或#作為結(jié)束。 分析棧SK中存放替換當(dāng)前非終結(jié)符的某規(guī)則右部符號(hào)串，句子左界符$或#存入棧底。 預(yù)測(cè)分析表是一個(gè)二維形式的矩陣，其中矩陣的行為文法非終結(jié)符，矩陣的列為文法終結(jié)符或$或# 。4.2.5 預(yù)測(cè)分析法與預(yù)測(cè)分析表的構(gòu)造見(jiàn)表 預(yù)測(cè)分析器的總控程序在任何時(shí)候都是根據(jù)棧頂符號(hào)和當(dāng)前輸入符號(hào)

11、a來(lái)決定分析器的動(dòng)作。$和文法開(kāi)始符號(hào)進(jìn)S棧第一個(gè)輸入符號(hào)讀進(jìn)aS棧頂符號(hào)上托出去放 X中 XVT?X=a ?Y將下一個(gè)輸入符號(hào)讀入aY出錯(cuò)NNX=$ ?X=a ?YSTOPYN查MX,a=Xy1y2yn ?N將y1y2yn逆序放入S棧中，若右部符號(hào)串為，則不進(jìn)S棧Y出錯(cuò)N 預(yù)測(cè)分析器的總控程序?qū)τ诓煌腖L(1)文法都是相同的，而預(yù)測(cè)分析表對(duì)于不同的LL(1)文法是不相同的。 構(gòu)造預(yù)測(cè)分析表的方法：輸入: 文法G輸出: 預(yù)測(cè)分析表M 4.2.5 預(yù)測(cè)分析法與預(yù)測(cè)分析表的構(gòu)造方法：4.2.5 預(yù)測(cè)分析法與預(yù)測(cè)分析表的構(gòu)造 1.計(jì)算文法G的每一非終結(jié)符的FIRST集 和FOLLOW集。 2.對(duì)文

12、法的每個(gè)規(guī)則A, 若aFIRST(), 則置MA, a= A 。 3.若FIRST(), 則對(duì)任bFOLLOW(A), 則置MA, b= A 。 4.把分析表中每個(gè)未定義的元素標(biāo)上出 錯(cuò)標(biāo)志error（表中用空白格表示）4.2.5 預(yù)測(cè)分析法與預(yù)測(cè)分析表的構(gòu)造例 設(shè)有文法GE： 試構(gòu)造該文法的預(yù)測(cè)分析表。 E TEE +TE | T FTT *FT | F (E) | id4.2.5 預(yù)測(cè)分析法與預(yù)測(cè)分析表的構(gòu)造 E E T T F (, id ), $ (, id +, ), $ (, id +, ), $, * +, ), $ *, +, ), $ FIRSTFOLLOWE TEE +TE

13、 | T FTT *FT | F (E) | id id + * ( ) $ E E T T F對(duì)規(guī)則E TEFIRST(TE) = (, id ETEETE FIRST(+TE) = + E +TE FOLLOW(E)= ), $ EETFTTFTTTTT*FTFidF(E)E TEE +TE | T FTT *FT | F (E) | id對(duì)規(guī)則E +TE 對(duì)規(guī)則E 句子 id+id*id $ 的分析過(guò)程 分析棧 輸入串$ E id+id*id $ $ ET id+id*id $ ETF id+id*id $ETid id+id*id $ ET +id*id $ E +id*id $ ET

14、+ +id*id $ ET id*id $ $ 見(jiàn)表4.2.5 預(yù)測(cè)分析法與預(yù)測(cè)分析表的構(gòu)造例 設(shè)有文法GSSa | (T)TT, S | S1.消去文法左遞歸,改寫(xiě)文法GS為GS 2.計(jì)算文法GS每個(gè)非終結(jié)符的FIRST集 和FOLLOW集 。3.判斷文法GS 是否LL(1)文法。 4.試構(gòu)造文法GS 的預(yù)測(cè)分析表。 5.給出輸入串(a)$ 的分析過(guò)程。 4.2.5 預(yù)測(cè)分析法與預(yù)測(cè)分析表的構(gòu)造 分析 引進(jìn)新的非終結(jié),改寫(xiě)文法,得到文法GS:S a | (T)T STT,ST| 根據(jù)FIRST集和FOLLOW集的定義,求出文法每個(gè)非終結(jié)符的FIRST集和FOLLOW集： Sa | (T)TT

15、, S | S4.2.5 預(yù)測(cè)分析法與預(yù)測(cè)分析表的構(gòu)造 FIRST FOLLOW S T T a, , ( ) FIRST(S)= FIRST(a)FIRST()FIRST(T) = a, , ( S a | (T)T STT,ST | FOLLOW(S) = $, , ,) , , ) a, , ( $, , , ) 4.2.5 預(yù)測(cè)分析法與預(yù)測(cè)分析表的構(gòu)造 無(wú)左遞歸的文法不一定是LL(1)文法，根據(jù)LL(1)文法的判斷條件，對(duì)非終結(jié)符S和T有： SELECT(Sa)SELECT(S)= FIRST(a)FIRST()=a=SELECT(Sa)SELECT(S(T)= FIRST(a)FIR

16、ST(T)=a ( =SELECT(S)SELECT(S(T)= FIRST()FIRST(T)= ( =SELECT(T,ST)SELECT(T)= FIRST(,ST)FOLLOW(T)=, ) =所以文法GS是LL(1)文法。S a | (T)T STT,ST | 4.2.5 預(yù)測(cè)分析法與預(yù)測(cè)分析表的構(gòu)造 FIRST(a)=a FIRST()= FIRST(T)=( 對(duì)規(guī)則Sa 對(duì)規(guī)則S 對(duì)規(guī)則S(T) a ( ) , $ SaS S (T)TST TST TSTTT,ST對(duì)規(guī)則T ST FIRST(ST)= a, , ( 對(duì)規(guī)則T FOLLOW(T)= ) 對(duì)規(guī)則T ,ST FIRST(,ST)= , STT分析符號(hào)串(a)$的過(guò)程如下表 :分析棧 輸入串$ S (a) $ )T( (a) $ )T a) $ $ )TS a) $ )Ta a) $ )T )