編譯原理：第4章 語法分析(Syntax Analysis)-自上而下分析法

1、 課 程 內(nèi) 容第 1 章 編 譯 引 論第 2 章 形式語言與自動機(jī)基礎(chǔ)第 3 章 詞法分析 (Lexical Analysis)第 4 章 語法分析(Syntax Analysis) 自上而下分析法第 5 章 語法分析(Syntax Analysis) 自下而上分析法第 6 章 語義分析與中間代碼生成第 7 章 運(yùn) 行 環(huán) 境第 8 章 代碼優(yōu)化（optimization）4.1 語法分析綜述 4.2 不確定的自上而下分析法4.3 遞歸下降分析法與遞歸下降分析器4.4 LL(1)分析法與LL(1)分析器 第 4 章 語法分析(Syntax Analysis) 自上而下分析法Ch4 語法分析

2、4.1.1 語法分析程序的功能 4.1.2 語法分析方法 一. 自上而下分析 二. 自下而上分析 Ch4 語法分析 4.1 語法分析程序綜述 4.1 語法分析綜述Ch4 語法分析 4.1 語法分析程序綜述 4.1.1 語法分析程序的功能語法分析器 ( Analyzer )源程序 L2源程序L1 語法分析程序的功能 scanner 語法分析語義分析 中間代碼生成源程序 源程序L1取下一個(gè)單詞 分析樹 完成語法分析任務(wù)的程序稱為語法分析器，或語法分析程序。 語法分析程序的功能 按照源語言的語法規(guī)則，從詞法分析的結(jié)果中識別出相應(yīng)的語法范疇，同時(shí)進(jìn)行語法檢查。 給定文法G和字符串( VT*)，檢查、判

3、定 L(G)？即檢查、判定是否是文法G所能產(chǎn)生的合法的句子，同時(shí)報(bào)告和處理語法錯(cuò)誤。Ch4 語法分析 4.1 語法分析程序綜述 4.1.1 語法分析程序的功能 語法分析程序的構(gòu)造要素 源程序串 （L1形式）處理對象源語言的文法G分析依據(jù)識別出的語法范疇的表示分析結(jié)果 Ch4 語法分析 4.1 語法分析程序綜述 4.1.1 語法分析程序的功能4.1.1 語法分析程序的功能 4.1.2 語法分析方法 一. 自上而下分析 二. 自下而上分析 Ch4 語法分析 4.1 語法分析程序綜述 4.1 語法分析綜述 一 . 自上而下語法分析方法 給定文法G和源程序串r。從G的開始符號S出發(fā)，通過反復(fù)使用產(chǎn)生式

4、對句型中的非終結(jié)符進(jìn)行替換(推導(dǎo))，逐步推導(dǎo)出r 。 * 是一種產(chǎn)生的方法，面向目標(biāo)的方法。Ch4 語法分析 4.1 語法分析程序綜述 4.1.2 語法分析方法* 分析的主旨是選擇產(chǎn)生式的合適的侯選 式進(jìn)行推導(dǎo)，逐步使推導(dǎo)結(jié)果與r匹配。分析方式1(推導(dǎo))： S = aA 例4.1 設(shè)有文法G和輸入串 r G： S aA A BaA | B + | | * | , r: a*a+a= aBaA= a*aA= a*aBaA= a*a+aA= a*a+a= r L(G)Ch4 語法分析 4.1 語法分析程序綜述 4.1.2 語法分析方法分析樹的從左到右葉結(jié)點(diǎn)=r，則 rL(G)。Sa A B a A

5、 B a A *上下SrCh4 語法分析 4.1 語法分析程序綜述 4.1.2 語法分析方法S aA A BaA | B + | | * | ,r: a*a+a分析方式2(分析樹)：+r4.1.1 語法分析程序的功能 4.1.2 語法分析方法 一. 自上而下分析 二. 自下而上分析 Ch4 語法分析 4.1 語法分析程序綜述 4.1 語法分析綜述 二 . 自下而上語法分析方法 從給定的輸入串r開始，不斷尋找子串與文法G中某個(gè)產(chǎn)生式P的候選式進(jìn)行匹配，并用P的左部代替(歸約)之，逐步歸約到開始符號S。 * 是一種辨認(rèn)的方法，基于目標(biāo)的方法。* 分析的主旨是尋找合適的子串與P的侯選 式進(jìn)行匹配，直

6、到歸約到G的S為止 。Ch4 語法分析 4.1 語法分析程序綜述 4.1.2 語法分析方法 * 是一種產(chǎn)生的方法，面向目標(biāo)的方法。 一 . 自上而下語法分析方法 給定文法G和源程序串r。從G的開始符號S出發(fā)，通過反復(fù)使用產(chǎn)生式對句型中的非終結(jié)符進(jìn)行替換(推導(dǎo))，逐步推導(dǎo)出r 。Ch4 語法分析 4.1 語法分析程序綜述 4.1.2 語法分析方法* 分析的主旨是選擇產(chǎn)生式的合適的侯選 式進(jìn)行推導(dǎo)，逐步使推導(dǎo)結(jié)果與r匹配。 二 . 自下而上語法分析方法 從給定的輸入串r開始，不斷尋找子串與文法G中某個(gè)產(chǎn)生式P的候選式進(jìn)行匹配，并用P的左部代替(歸約)之，逐步歸約到S。 * 是一種辨認(rèn)的方法，基于目

7、標(biāo)的方法。* 分析的主旨是尋找合適的子串與P的侯選 式進(jìn)行匹配，直到歸約到G的S為止 。 Ch4 語法分析 4.1 語法分析程序綜述 4.1.2 語法分析方法例4.2 設(shè)有文法G和輸入串 r G： S aA A BaA| B + | - | * | , r: a*a+aa * a + a BAABAS上下rSCh4 語法分析 4.1 語法分析程序綜述 4.1.2 語法分析方法分析方式1(分析樹)：例4.2 設(shè)有文法G和輸入串 r G： S aA A BaA| B + | | * | , r: a*a+aa * a + a BAABAS分析方式2(推導(dǎo))：Ch4 語法分析 4.1 語法分析程序綜

8、述 4.1.2 語法分析方法S= aA=aBaA=aBaBaA=aBaBaA的形式，間接左遞歸文法會呈現(xiàn)A = A 的形式。+一. 消除文法的左遞歸 ch4 語法分析 4.2 不確定的自上而下分析法 4.2.2 不確定性原因與解決方法（1） 直接左遞歸的消除：假定關(guān)于非終結(jié)符P的規(guī)則為 PP | 、(VTVN)* 其中，不以P開頭。 ch4 語法分析 4.2 不確定的自上而下分析法 4.2.2 不確定性原因與解決方法分析 ：PP | L(G(P)= *不變個(gè)數(shù)可以無窮多個(gè),只能用 遞歸表示且不 能用左遞歸。P P|PP P（1） 直接左遞歸的消除：假定關(guān)于非終結(jié)符P的規(guī)則為 PP | 、(VT

9、VN)* 其中，不以P開頭。把P的規(guī)則改寫成如下 等價(jià)的非直接左遞歸形式 P P P P| ch4 語法分析 4.2 不確定的自上而下分析法 4.2.2 不確定性原因與解決方法例4.6 設(shè)有簡單表達(dá)式文法G(E): EE+E | E*E |（E）| i 對G(E)消除二義性后，得到文法G(E) ： EE+T | T TT*F | F F(E) | i 繼續(xù)消除文法G(E) 的左遞歸 ，得到文法G (E) E TE E +TE| T FT T *FT| F ( E) | i ch4 語法分析 4.2 不確定的自上而下分析法 4.2.2 不確定性原因與解決方法假定關(guān)于非終結(jié)符P的規(guī)則為 P P1|

10、 P2 | | Pn |1 |2| |n其中，每個(gè) i不等于，1 ,2 ,n 不以P開頭。則可以把P的規(guī)則改寫成如下等價(jià)的非直接左遞歸形式 P 1P|2P|nP P1P| 2P| nP| ch4 語法分析 4.2 不確定的自上而下分析法 4.2.2 不確定性原因與解決方法例4.7 設(shè)有文法G： II0 | Ia | Ib | a | b ch4 語法分析 4.2 不確定的自上而下分析法 4.2.2 不確定性原因與解決方法 I aI | bI I 0I | aI | bI | 對左遞歸文法G改寫后的文法G為（2） 間接左遞歸的消除： 有些文法表面上不具有左遞歸性，卻隱含著左遞歸。例如設(shè)有文法G(

11、A)： A Ba | a B Cb | b C Ac | c經(jīng)若干步推導(dǎo)替換，有： A = Ba = Cba = Acba B = Cb = Acb = Bacb C = Ac = Bac = Cbac ch4 語法分析 4.2 不確定的自上而下分析法 4.2.2 不確定性原因與解決方法 后面給出一個(gè)消除文法所有左遞歸性的算法，該算法對文法的要求是，文法不含回路（形如P =P的推導(dǎo)）且不含以為右部的產(chǎn)生式。 + 消除間接左遞歸的方法： (1) 把間接左遞歸文法改寫為直接左遞歸 文法； (2) 用消除直接左遞歸的方法改寫文法。 ch4 語法分析 4.2 不確定的自上而下分析法 4.2.2 不確定

12、性原因與解決方法思考題：任何一文法都等價(jià)于一個(gè)不含回路且不含以為右部的產(chǎn)生式的文法。 ch4 語法分析 4.2 不確定的自上而下分析法 4.2.2 不確定性原因與解決方法 算法4.1 ( 消除文法左遞歸 ) 給定文法G 對文法的所有非終結(jié)符按任一種順序排列， 例如A1，A2，An。消除A1中的直接左遞歸。 for ( i=1;i=n;i+ ) for ( j=1; j = i-1;j+ ) 把形如Ai Aj 的產(chǎn)生式改寫成 Ai 12k 其中Aj 12k 是關(guān)于Aj的全部規(guī)則； 消除Ai規(guī)則中的直接左遞歸； 簡化由所得的文法，即去掉多余的規(guī)則。 ch4 語法分析 4.2 不確定的自上而下分析法

13、 4.2.2 不確定性原因與解決方法 令文法G(A)的非終結(jié)符排序?yàn)镃，B， A。對于C ，不存在直接左遞歸，把C代入B ， B的規(guī)則變?yōu)?BAcbdAbc代換后的B不含直接左遞歸，將其代入A，A的規(guī)則變?yōu)椋?A AcbadAbacabBA存在直接左遞歸，消除A的直接左遞歸有 A dAbaA| caA|bBA A cbaA| ch4 語法分析 4.2 不確定的自上而下分析法 4.2.2 不確定性原因與解決方法G(A):A Ba | bB B Cb | c C Ac | dA文法G(A)改寫為 A dAbaA| caA|bBA A cbaA| B AcbdAbc C Ac | c ch4 語法分

14、析 4.2 不確定的自上而下分析法 4.2.2 不確定性原因與解決方法 刪除多余的規(guī)則，最后得到文法G(A)的無左遞歸的等價(jià)文法G(A) 為A dAbaA| caA|bBA A cbaA| B AcbdAbc 令文法G(A)的非終結(jié)符排序?yàn)锳，B，C。對于A，不存在直接左遞歸，對于B，候選式中不包含A，且不存在直接左遞歸。將A，B帶入C，代換后的C的規(guī)則變?yōu)椋?C BacbBcdA C CbaccacbBcdAC存在直接左遞歸，消除C的直接左遞歸有 C cacC| bBcC| dAC C bacC| ch4 語法分析 4.2 不確定的自上而下分析法 4.2.2 不確定性原因與解決方法G(A):

15、A Ba | bB B Cb | c C Ac | dA文法G(A)改寫為 A Ba | bB B Cb | c C cacC| bBcC| dAC C bacC| ch4 語法分析 4.2 不確定的自上而下分析法 4.2.2 不確定性原因與解決方法二. 消除回溯 P 1 | 2 | n 當(dāng)前r：ai 在一般自上而下分析中，對于一個(gè)VN進(jìn)行推導(dǎo)并試圖去匹配句子剩余符號時(shí)，若VN含有兩個(gè)或兩個(gè)以上的候選式，是依次一個(gè)一個(gè)地去試探，試圖找出一個(gè)合乎要求的 i 。先選 1 ，與當(dāng)前輸入a i匹配成功則替換，否則選 2，依此類推。 ch4 語法分析 4.2 不確定的自上而下分析法 4.2.2 不確定性

16、原因與解決方法 ch4 語法分析 4.2 不確定的自上而下分析法 4.2.2 不確定性原因與解決方法 定義4.4 設(shè)G是二型文法，則中的任意 V*的終結(jié)首符集FIRST()為 FIRST ( ) = a | = a ，aVT 若 =, 則FIRST() 。*不帶回溯的條件：(充分非必要) 如果對文法G的關(guān)于每一個(gè)非終結(jié)符A的產(chǎn)生式 ，設(shè)為： A 1 | 2 | n 如果它的每個(gè)候選式 i均不存在 i =的情況，而且FIRST( i)兩兩彼此互不相交。* ch4 語法分析 4.2 不確定的自上而下分析法 4.2.2 不確定性原因與解決方法如果對文法G的關(guān)于每一個(gè)非終結(jié)符A的產(chǎn)生式 ，設(shè)為： A

17、1 | 2 | n 滿足不帶回溯條件 則據(jù)當(dāng)前掃描單詞a，若a FIRST(i) ， 其中i是1 n 中之一，選取A i 進(jìn)行推導(dǎo)。 ch4 語法分析 4.2 不確定的自上而下分析法 4.2.2 不確定性原因與解決方法計(jì)算FIRST(X)(XV)的算法描述：為構(gòu)造FIRST(X)， 可反復(fù)應(yīng)用如下規(guī)則：1、若X是終結(jié)符,則FIRST(X)X;2、若X是非終結(jié)符，且XX1X2 Xk是一個(gè)產(chǎn)生式，則 FIRST(X1)中的所有終結(jié)符號加到FIRST(X)中； 若對于某個(gè)i，a FIRST(Xi)且X1X2 Xi1 ，則 將a加到FIRST(X)中； 若對于所有的j1，2，k， FIRST(Xj)，

18、則 將加到FIRST(X)中。 ch4 語法分析 4.2 不確定的自上而下分析法 4.2.2 不確定性原因與解決方法計(jì)算FIRST()( V*)的算法描述：設(shè)=X1X2 Xk (XiV)為構(gòu)造FIRST()， 可反復(fù)應(yīng)用如下規(guī)則：1、 FIRST(X1)中的所有終結(jié)符號加到FIRST()中；2、若對于某個(gè)i，a FIRST(Xi)且X1X2 Xi1 ， 則將a加到FIRST()中；3、若對于所有的j1，2，k， FIRST(Xj)， 則將加到FIRST()中。 ch4 語法分析 4.2 不確定的自上而下分析法 4.2.2 不確定性原因與解決方法計(jì)算FIRST(X)(XV)的算法描述：為構(gòu)造FI

19、RST(X)， 可反復(fù)應(yīng)用如下規(guī)則：1、若X是終結(jié)符,則FIRST(X)X;2、若X是非終結(jié)符，且XX1X2 Xk是一個(gè)產(chǎn)生式，則 FIRST(X1)中的所有終結(jié)符號加到FIRST(X)中； 若對于某個(gè)i，a FIRST(Xi)且X1X2 Xi1 ，則 將a加到FIRST(X)中； 若對于所有的j1，2，k， FIRST(Xj)，則 將加到FIRST(X)中。X的FIRST為其所有候選式的FIRST集合的并集。 ch4 語法分析 4.2 不確定的自上而下分析法 4.2.2 不確定性原因與解決方法 例4.8 設(shè)有文法G： S Ap | Bq A a | cA B b | dB 對S: FIRST

20、(Ap)=a,c FIRST(Bq)=b,d 且 FIRST(Ap) FIRST(Bq)=對A: FIRST(a)=a FIRST(cA)=c 且 FIRST(a) FIRST(cA)=對B: FIRST(b)=b FIRST(dB)=d 且 FIRST(b) FIRST(dB)= ch4 語法分析 4.2 不確定的自上而下分析法 4.2.2 不確定性原因與解決方法若給出r=cap ,則有： A p c A ar: capS Ap | Bq A a | cA B b | dBFIRST(Ap)=a,c FIRST(Bq)=b,dFIRST(a)=a FIRST(cA)=cFIRST(b)=b

21、FIRST(dB)=d Sr: capr: cap ch4 語法分析 4.2 不確定的自上而下分析法 4.2.2 不確定性原因與解決方法對非終結(jié)符A的多個(gè)候選式的FIRST( i)的相互兩個(gè)彼此交集，一般是因?yàn)?i中有公共左因子，可以通過提取左公因子來改造文法。(由BNF范式改EBNF范式)可以使用下面規(guī)則改寫文法為： A A A1 | 2 | n若有文法： A 1 | 2 | n(1 | 2 | n) ch4 語法分析 4.2 不確定的自上而下分析法 4.2.2 不確定性原因與解決方法若文法G為： A 11| 12 | 1n| 21 | 2 2| 2 m使用下面規(guī)則改寫文法G為G ： A1A

22、 |2A A 1|2|n A 1| 2| m1( 1| 2 |n )A2( 1 | 2| m )A4.1 語法分析綜述 4.2 不確定的自上而下分析法4.3 遞歸下降分析法與遞歸下降分析器4.4 LL(1)分析法與LL(1)分析器 第 4 章 語法分析(Syntax Analysis) 自上而下分析法Ch4 語法分析 ch4 語法分析 4.3 遞歸下降分析法和遞歸下降分析器 遞歸下降分析器( Recursive-Descent Parser ) 由一組遞歸過程組成，且每個(gè)過程對應(yīng)文法的一個(gè)VN 的分析程序。(將一個(gè)非終結(jié)符的文法規(guī)則看作識別非終結(jié)符的一個(gè)過程)。 遞歸下降分析器的基本構(gòu)造方法

23、對文法的每個(gè)非終結(jié)符號，都根據(jù)其產(chǎn)生式的各個(gè)候選式的結(jié)構(gòu)，為其編寫一個(gè)對應(yīng)的子程序（或函數(shù)），該子程序完成相應(yīng)的非終結(jié)符對應(yīng)的語法成份的識別和分析任務(wù)。 遞歸下降分析器對文法要求：LL(1)文法 ch4 語法分析 4.3 遞歸下降分析法和遞歸下降分析器 例4.9 設(shè)有文法G (E) ： E TE E +TE| T FT T *FT| F ( E)| i 文法G()的遞歸下降語法分析程序如下 ch4 語法分析 4.3 遞歸下降分析法和遞歸下降分析器 E ( ) F ( ) T; E; if ( c=i ) n+; else if ( c=( ) E( ) n+; E; if (c=) ) n+;

24、 if (c=+) else error；n+; T; E; else error； T ( ) T ( ) F; T; if (c=*) n+; F; T ; 其中: n 讀單詞指針；c 單詞指針指的的單詞；OK1NO1ETE E+TE|TFTT*FT |F( E) | iOK2NO2主程序 ch4 語法分析 4.3 遞歸下降分析法和遞歸下降分析器設(shè)有 r1=i+i*i #匹配i， pop FE T i+i*i #查看E Ti+i*i #stackpop T E匹配+,pop E,Push ETi+i*i #E T Fpop T,push T,FETEE+TE|TFT T *FT |F( E

25、) | iE Ti+i*i #分析完成格局 ch4 語法分析 4.3 遞歸下降分析法和遞歸下降分析器查看i+i*i #E TE T Fpop T,push T,F匹配i, pop Fi+i*i #E T 匹配*,pop T,Push T,Fi+i*i #E T F匹配i, pop Fi+i*i #E T pop T,E ETEE+TE |TFT T *FT |F( E) | i設(shè)有 r1=（+i # E T（+i #匹配（pop F,Push ) EPush T FE T F（+i # ch4 語法分析 4.3 遞歸下降分析法和遞歸下降分析器查看（+i #pop E,Push E TE T )

26、 EE T ）E TETEE+TE |TFT T *FT |F( E) | ierror分析完成格局 ch4 語法分析 4.3 遞歸下降分析法和遞歸下降分析器（ +i #查看（+i #E T ）E Tpop T,Push T FE T ) E T F（+i #ETEE+TE |TFT T *FT |F( E) | i ch4 語法分析 4.3 遞歸下降分析法和遞歸下降分析器 遞歸下降分析器設(shè)計(jì)工具 狀態(tài)圖(FA) 狀態(tài)圖構(gòu)造：為文法G的每個(gè)VN 1） 建立1個(gè)初態(tài)和1個(gè)終態(tài)(函數(shù)返回態(tài))； 2） 為每個(gè)產(chǎn)生式 A x1x2 xn 建立從初態(tài)到終 態(tài)的路徑，弧標(biāo)記為x1，x2， ，xn ； *

27、其中：xi(VTVN)例如，E TE E +TE |01+3E01T2E2T 1） 開始處于圖的初態(tài)，即分析器的進(jìn)入點(diǎn)； 2） 在某狀態(tài)S， 若 aVT 當(dāng)前輸入符號為a，分析器掃描指針+1，進(jìn)入t狀態(tài); 若 AVN 分析器進(jìn)入對A的分析，掃描指針不變，分析完A后進(jìn) 入到狀態(tài)t ; 若 直接進(jìn)入t狀態(tài)，掃描指針不變;StAStSta ch4 語法分析 4.3 遞歸下降分析法和遞歸下降分析器 如何利用狀態(tài)圖構(gòu)造遞歸下降分析器 ch4 語法分析 4.3 遞歸下降分析法和遞歸下降分析器通過狀態(tài)圖的化簡來化簡遞歸下降分析器 E的遞歸直接進(jìn)入E的FA的開始例如，E TE E +TE |01+3E01T2

28、E2T01+3T化簡01+32T ch4 語法分析 4.3 遞歸下降分析法和遞歸下降分析器E代入E ： 0T12+3TE TEE +TE |T FTT *FT|F （ E） | i0T1+23F4*5T代入 T ： 67 (9)8EiF：4.1 語法分析綜述 4.2 不確定的自上而下分析法4.3 遞歸下降分析法與遞歸下降分析器4.4 LL(1)分析法與LL(1)分析器 第 4 章 語法分析(Syntax Analysis) 自上而下分析法Ch4 語法分析4.4 LL(1)分析法與LL(1)分析器 4.4.1 LL(1)分析器的邏輯結(jié)構(gòu) 4.4.2 LL(1)分析器的構(gòu)造 4.4.3 關(guān)于LL(

29、1)文法 ch4 語法分析 4.4 LL(1)分析法與LL(1)分析器L L (1)掃描模式：自左向右分析模式：最左推導(dǎo)在分析中最多向前看1個(gè)輸入字符 ch4 語法分析 4.4 LL(1)分析法與LL(1)分析器 4.4.1 LL(1)分析器的結(jié)構(gòu)預(yù)測分析器顯式地維護(hù)一個(gè)狀態(tài)棧，而不是通過隱式的遞歸調(diào)用來做自上而下的語法分析。 ch4 語法分析 4.4 LL(1)分析法與LL(1)分析器 4.4.1 LL(1)分析器的結(jié)構(gòu)LL(1)分析器的邏輯結(jié)構(gòu) 總控程序LL(1)分析表分析棧組成輸入字符串r a1 a2 ai an #總控程序+ （分析表）X #分析棧輸出 ch4 語法分析 4.4 LL(

30、1)分析法與LL(1)分析器 4.4.1 LL(1)分析器的結(jié)構(gòu)(1) 分析棧 存放分析過程中的文法符號（已經(jīng)推導(dǎo)出的待處理的串）。 初始為：#S句子界符(棧底標(biāo)志)文法開始符號 ch4 語法分析 4.4 LL(1)分析法與 LL(1)分析器 4.4.1 LL(1)分析器的結(jié)構(gòu)(2) 分析表 a1 a2 an #A1A2 An文法的VT文法的VNM(A1,a1)M(A1,a2)M(A1,an)M(Ai,ai)文法的一條產(chǎn)生式規(guī)則(候選式唯一) 出錯(cuò)（空白）預(yù)測分析函數(shù) ch4 語法分析 4.4 LL(1)分析法與 LL(1)分析器 4.4.1 LL(1)分析器的結(jié)構(gòu)(3) 總控程序 (LL(1

31、)分析) 算法4.2 (1) 初始化工作： (2) 若當(dāng)前分析棧頂符號是文法的終結(jié)符號，則 對于： Xai“”，表示分析成功，停止分析過程； Xai“”，則將從分析棧頂退掉，p指向 下一個(gè)輸入字符； Xai，表示不匹配的出錯(cuò)情況。 # S a1 a2 an #p ch4 語法分析 4.4 LL(1)分析法與 LL(1)分析器 4.4.1 LL(1)分析器的結(jié)構(gòu)(3) 若N，則查分析表。此時(shí)對(X , ai)： 若(, ai)中為一個(gè)產(chǎn)生式規(guī)則，則將X從 棧中彈出并將此規(guī)則右部的符號序列按倒序推進(jìn) 棧(若產(chǎn)生式規(guī)則為，則僅將從棧中彈出) 。 若(, ai)中為空白，表示出錯(cuò)，可調(diào)用語法出錯(cuò)處理子

32、程序。 ch4 語法分析 4.4 LL(1)分析法與LL(1)分析器 4.4.1 LL(1)分析器的結(jié)構(gòu) 例4.10 設(shè)有文法G()： ETE E+ TE TFT T*FT F(E)id和文法的LL(1)分析表，對輸入串 id+id*id使用LL(1)分析器的分析過程。 ch4 語法分析 4.4 LL(1)分析法與LL(1)分析器 4.4.2 LL(1)分析器的構(gòu)造EETTF + * ( ) id #文法G(E)的LL(1)分析表ETE ETETFT TFTF (E) FidE+TEE ET*FT T TT返回返回2 ch4 語法分析 4.4 LL(1)分析法與LL(1)分析器 4.4.1 L

33、L(1)分析器的結(jié)構(gòu)步 驟 分析棧 余留輸入串 所用產(chǎn)生式1 # E id +id*id#2 # E T id +id*id#3 # E T F id +id*id# 4 # E Tid id +id*id# 5 # E T +id*id# T 6 # E +id*id# E+TE 7 # E T+ +id*id# p+ 8 # E T id*id# TFT 9 # E T F id*id# Fid 10 # E Tid id*id# p+ 11 # E T *id# T*FT 表下頁ETETFTFidp+ ch4 語法分析 4.4 LL(1)分析法與LL(1)分析器 4.4.1 LL(1)分

34、析器的結(jié)構(gòu)步 驟 分析棧 余留輸入串 所用產(chǎn)生式12 # E TF* *id# p+ 13 # E TF id# Fid 14 # E Tid id# p+ 15 # E T # T 16 # E # E 17 # # 分析成功 注意： (1) 整個(gè)分析過程是分析棧和待匹配串構(gòu)成的二元 式不斷變化的過程。 (2)不同的源語言僅是分析表不同，分析器結(jié)構(gòu)、總 控程序不變。表4.4 LL(1)分析法與LL(1)分析器 4.4.1 LL(1)分析器的邏輯結(jié)構(gòu) 4.4.2 LL(1)分析器的構(gòu)造 4.4.3 關(guān)于LL(1)文法 ch4 語法分析 4.4 LL(1)分析法與LL(1)分析器LL(1)分析器

35、構(gòu)造關(guān)鍵 分析表的構(gòu)造 ch4 語法分析 4.4 LL(1)分析法與LL(1)分析器 4.4.2 LL(1)分析器的構(gòu)造根據(jù)LL(1)分析過程，問題的關(guān)鍵是解決根據(jù)當(dāng)前要替換的文法的非終結(jié)符和下一步要匹配的終結(jié)符，選擇非終結(jié)符對應(yīng)的產(chǎn)生式規(guī)則的哪一個(gè)候選式。其就是預(yù)測函數(shù)。分析表的構(gòu)造關(guān)鍵 預(yù)測函數(shù)據(jù)FIRST集合的定義：對文法G，若G中產(chǎn)生式形如A 且沒有 =的情況，則產(chǎn)生LL(1)分析表的預(yù)測函數(shù)： ch4 語法分析 4.4 LL(1)分析法與LL(1)分析器 4.4.2 LL(1)分析器的構(gòu)造第一種情況：對文法規(guī)則 A 若aFIRST() ，那么要匹配輸入單詞a時(shí)，應(yīng)該使用候選式替換A。

36、所以有 (A，a) = A ch4 語法分析 4.4 LL(1)分析法與LL(1)分析器 4.4.2 LL(1)分析器的構(gòu)造由于(A，a)的 產(chǎn)生式中應(yīng)該只有唯一候選式,否則會產(chǎn)生回溯，所以任一終結(jié)符不應(yīng)同時(shí)屬于某一非終結(jié)符的兩個(gè)或兩個(gè)以上的候選式的FIRST集合,即任何非終結(jié)符的候選式的FIRST集合應(yīng)該兩兩互不相交. ch4 語法分析 4.4 LL(1)分析法與LL(1)分析器 4.4.2 LL(1)分析器的構(gòu)造 前例4.8 設(shè)有文法G： S Ap | Bq A a | cA B b | dB 對S: FIRST(Ap)=a,c FIRST(Bq)=b,d 且 FIRST(Ap) FIRS

37、T(Bq)=對A: FIRST(a)=a FIRST(cA)=c 且 FIRST(a) FIRST(cA)=對B : FIRST(b)=b FIRST(dB)=d 且 FIRST(b) FIRST(dB)= ch4 語法分析 4.4 LL(1)分析法與LL(1)分析器 4.4.2 LL(1)分析器的構(gòu)造SABBb BdB a b c d p q文法G的LL(1)分析表 若有FIRST()怎么辦？此時(shí)當(dāng)面臨a FIRST()時(shí)并不一定出錯(cuò)。 SBqSBqSApSApAaAcA S Ap | Bq A a | cA B b | dB對S：FIRST(Ap)=a,c 對A：FIRST(a)=a 對B

38、： FIRST(b)=b FIRST(Bq)=b,d FIRST(cA)=c FIRST(dB)=d ch4 語法分析 4.4 LL(1)分析法與LL(1)分析器 4.4.2 LL(1)分析器的構(gòu)造 定義4.5 設(shè)上下文無關(guān)文法G，S是文法的開始符號，對于文法G的任何非終結(jié)符AFOLLOW(A)a|S=Aa，aVT 若S=A，則令FOLLOW(A)。* FOLLOW(A)的含義是指，在文法G的句型中，能夠緊跟著A之后的一切終結(jié)符或“”。 ch4 語法分析 4.4 LL(1)分析法與LL(1)分析器 4.4.2 LL(1)分析器的構(gòu)造構(gòu)造FOLLOW集方法算法4.3 文法G中的每一個(gè)BN ，為構(gòu)

39、造FOLLOW(B)， 可反復(fù)應(yīng)用如下規(guī)則： 對文法的開始符號S，令FOLLOW(S) ； 若文法G中有形如AB的規(guī)則，且， 則將FIRST()中的一切非符號加入 FOLLOW(B)； 若G中有形如 A B 或 A B的規(guī)則，且 FIRST()，則FOLLOW(A)中的全部元素 屬于FOLLOW(B)。據(jù)算法4.3計(jì)算文法GS所有VN的FOLLOW集。# FOLLOW(S)；由規(guī)則SAB | bC ： FOLLOW(S) FOLLOW(B) ；FOLLOW(S) FOLLOW(A)；FOLLOW(S) FOLLOW(C)；FIRST(B) FOLLOW(A) FOLLOW(S)=#； FOLL

40、OW(B) =#；FOLLOW(A)=#，a； FOLLOW(C)# ch4 語法分析 4.4 LL(1)分析法與LL(1)分析器 4.4.2 LL(1)分析器的構(gòu)造 例4.11 設(shè)有文法GS為： SAB | bC A| b B| aD CAD| b DaS| c ch4 語法分析 4.4 LL(1)分析法與LL(1)分析器 4.4.2 LL(1)分析器的構(gòu)造規(guī)則A| b 對FOLLOW集合無影響；由規(guī)則B| aD得:：FOLLOW(B) FOLLOW(D) FOLLOW(S)=#； FOLLOW(B) =#；FOLLOW(A)=#，a； FOLLOW(C)# FOLLOW(D)#，由規(guī)則CA

41、D| b得:FOLLOW(C) FOLLOW(D)，F(xiàn)IRST(D) FOLLOW(A) ,FOLLOW(S)=#； FOLLOW(B) =#；FOLLOW(A) =#，a，c， FOLLOW(C)# FOLLOW(D)#，由規(guī)則DaS| c得:FOLLOW(D) FOLLOW(S)， 所有的FOLLOW集合無變化。SAB | bC A| bB| aDCAD| bDaS| cFOLLOW(S)=#； FOLLOW(B) =#；FOLLOW(A)=#，a； FOLLOW(C)# ch4 語法分析 4.4 LL(1)分析法與LL(1)分析器 4.4.2 LL(1)分析器的構(gòu)造FOLLOW(S)=#

42、； FOLLOW(B) =#；FOLLOW(A)=#，a，c； FOLLOW(C)# FOLLOW(D)#再對每個(gè)產(chǎn)生式查一遍，發(fā)現(xiàn)FOLLOW集合無變化，所以上面的即為最后求得的FOLLOW集合。SAB | bC A| bB| aDCAD| bDaS| c 2. 構(gòu)造FOLLOW集方法二關(guān)系圖法文法G中的每個(gè)終結(jié)符和“#”對應(yīng)圖中的一個(gè)結(jié)點(diǎn)，每個(gè)非終結(jié)符A對應(yīng)兩個(gè)結(jié)點(diǎn)FOLLOW(A)和FIRST(A)。 從開始符號S的FOLLOW(S)結(jié)點(diǎn)到”#”號的結(jié)點(diǎn)連一條箭弧。 如果文法中有產(chǎn)生式ABX,當(dāng)XVN時(shí)，則從FOLLOW(B)結(jié)點(diǎn)到FIRST(X)結(jié)點(diǎn)連一條弧，當(dāng)XVT時(shí)，則與X相連。

43、如果文法中有產(chǎn)生式A B,且=,則從FOLLOW(B)結(jié)點(diǎn)到FOLLOW(A) 結(jié)點(diǎn)連一條箭弧。 對每一FIRST(A)結(jié)點(diǎn)如果有產(chǎn)生式A X1X2 Xk,當(dāng)X1VT時(shí),則與X1相連;當(dāng)X1VN時(shí),從FIRST(A)到FIRST(X1)結(jié)點(diǎn)連一條箭弧,當(dāng)X1X2 Xi1 ，從FIRST(A)到FIRST(Xi)結(jié)點(diǎn)連一條箭弧。凡是從FOLLOW(A)結(jié)點(diǎn)有路徑可以到達(dá)的終結(jié)符或“#”號的結(jié)點(diǎn)，其所標(biāo)記的終結(jié)符或“#”號即為FOLLOW(A)的成員。 ch4 語法分析 4.4 LL(1)分析法與LL(1)分析器 4.4.2 LL(1)分析器的構(gòu)造* ch4 語法分析 4.4 LL(1)分析法與L

44、L(1)分析器 4.4.2 LL(1)分析器的構(gòu)造#caFOLLOW(B)FOLLOW(D)FOLLOW(C)FOLLOW(S)FIRST(B)FOLLOW(A)FIRST(D)SAB | bC A| bB| aDCAD| bDaS| cFOLLOW(S)=FOLLOW(B)=FOLLOW( D)=FOLLOW (C) =#；FOLLOW(A)=#，a，c； ch4 語法分析 4.4 LL(1)分析法與LL(1)分析器 4.4.2 LL(1)分析器的構(gòu)造自上而下語法分析的主旨是選擇產(chǎn)生式的合適的侯選式進(jìn)行推導(dǎo)，逐步使推導(dǎo)結(jié)果與r匹配。 LL(1)分析法用分析棧和輸入緩沖區(qū)記錄分析的過程，分析表

45、為根據(jù)當(dāng)前情況確定選擇那一個(gè)候選式的表格。所以分析表的構(gòu)造：（1）對文法G，若G中對非終結(jié)符A的產(chǎn)生式形如A|且 和均不推出，則可產(chǎn)生LL(1)分析表的A行為， 對 aFIRST() ，a列即(A，a) = A 對 bFIRST() ，b列即(A，b) = A ch4 語法分析 4.4 LL(1)分析法與LL(1)分析器 4.4.2 LL(1)分析器的構(gòu)造 設(shè)對文法G求出FIRST 和FOLLOW，則對=情況的文法確定惟一候選的方法： 對 A 1 | 2 當(dāng) 1 、 2不同時(shí)推出時(shí)，設(shè) 2 = *如果滿足 FIRST( 1)(FIRST( 2 )FOLLOW(A)=則惟一候選為： 若aFIRS

46、T( 1 )，則置 M(A, a)= A 1 ； 若bFIRST( 2)或bFOLLOW(A)，則置 M(A, b)= A 2 。 設(shè)S=Ab 由于對文法規(guī)則存在A2且FIRST(2)，當(dāng) 2 =，則A =。 故有S=Ab =b A自動獲得匹配* ch4 語法分析 4.4 LL(1)分析法與LL(1)分析器 4.4.2 LL(1)分析器的構(gòu)造 已知 FOLLOW(A)aS =Aa，aT 若有 bFOLLOW(A)則必有S=Ab(bT )這樣的句型。*分析 (A ,b) =A 2(這樣在自上而下分析的推導(dǎo) 中才可能從棧中退掉A。 ) ch4 語法分析 4.4 LL(1)分析法與LL(1)分析器

47、4.4.2 LL(1)分析器的構(gòu)造 算法4.4 LL(1)分析表構(gòu)造 輸入：文法G；G的FIRST和FOLLOW集合 輸出：文法G的LL(1)分析表 方法：for 文法G的每個(gè)產(chǎn)生式A1 |2 |m if aFIRST (i ) 置(A, a) = Ai ； if FIRST (i ) for 任何 bFOLLOW(A) 置(A, b) = Ai else 置所有無定義的(A, ai)為出錯(cuò) ch4 語法分析 4.4 LL(1)分析法與LL(1)分析器 4.4.2 LL(1)分析器的構(gòu)造 前例4.10 設(shè)有文法G(E)： ETE E+ TE TFT T*FT F (E) i對E： FIRST(

48、TE )= (，i 對T： FIRST( FT )= (，i 對F： FIRST(E)= ( FIRST( i )= i = ch4 語法分析 4.4 LL(1)分析法與LL(1)分析器 4.4.2 LL(1)分析器的構(gòu)造 對E ： FIRST(+ TE )=+ FIRST()= FOLLOW(E)= #, ) 滿足： +( #, ) ) = 對T ： FIRST(*FT)= * FIRST( )= FOLLOW(T)= #, ), + 滿足：* ( #, ), + ) = E TEE +TE|T FTT *FT|F （ E） | i ch4 語法分析 4.4 LL(1)分析法與LL(1)分析

49、器 4.4.2 LL(1)分析器的構(gòu)造EETTF + * ( ) i #文法G(E)的LL(1)分析表ETE ETETFT TFTF (E) FiE+TEE ET*FT T T TETE: FIRST(TE )=(，iE+TE|:FIRST(+TE)=+ FIRST()= FOLLOW(E)= #, ) TFT: FIRST( FT )=(，iT*FT|:FIRST(*FT)=* FIRST()= FOLLOW(T)= #, ),+ F(E) |i :FIRST(E)=( FIRST( i )=i設(shè)有 r1=（+i # E T（+i #匹配（pop F,Push ) EPush T FE T

50、F（+i # ch4 語法分析 4.3 遞歸下降分析法和遞歸下降分析器（+i #pop E,Push E TE T ) EE T ） E TETEE+TE |TFT T*FT |F( E) | ipop T,Push T FE T ) E T F（+i #error設(shè)有 r1=（+i # ch4 語法分析 4.3 遞歸下降分析法和遞歸下降分析器EETTF + * ( ) i #文法G(E)的LL(1)分析表ETE ETETFT TFTF (E) FiE+TEE ET*FT T T T # E # E T # E T F # E T ) E （ # E T ) E ch4 語法分析 4.4 LL

51、(1)分析法與LL(1)分析器 4.4.2 LL(1)分析器的構(gòu)造 例4.12 設(shè)有文法G(S) S iCtSSa SeS b對S： FIRST( iCtSS )= i FIRST( a )= a 對S: FIRST(eS )= e FIRST( )= FOLLOW(S)=#,eFIRST(eS ) (FIRST( ) FOLLOW(S) 對C： FIRST( b )= b ch4 語法分析 4.4 LL(1)分析法與LL(1)分析器 4.4.2 LL(1)分析器的構(gòu)造文法G(S)的LL(1)分析表 a b e i t # S Sa SiCtSS S SeS S S C Cb多重定義S iCt

52、SSa: FIRST( iCtSS )= i FIRST( a )= a SeS: FIRST(eS )=e FIRST()= FOLLOW(S)=#,e b: FIRST( b )= b 4.4 LL(1)分析法與LL(1)分析器 4.4.1 LL(1)分析器的邏輯結(jié)構(gòu) 4.4.2 LL(1)分析器的構(gòu)造 4.4.3 關(guān)于LL(1)文法 ch4 語法分析 4.4 LL(1)分析法與LL(1)分析器 ch4 語法分析 4.4 LL(1)分析法與LL(1)分析器 4.4.3 關(guān)于LL(1)文法 定義4.6 一部文法G，若它的LL(1)分析表不含多重定義入口，則稱它是一個(gè)LL(1)文法。由LL(1)文法產(chǎn)生的語言稱為LL(1)語言。L L (k)掃描模式：自左向右分析模式：最左推導(dǎo)在分析中最多向前看k個(gè)輸入字符 ch4 語法分析 4.4 LL(1)分析法與LL(1)分析器 4.4.3 關(guān)于LL(1)文法 關(guān)于LL(1)文法及LL(1)語言重要的性質(zhì) 任何LL(1)文法是無二義性的。 若一文法為左