同濟(jì)大學(xué)編譯原理第四章語(yǔ)法分析——自上而下分析

1、第四章 語(yǔ)法分析 自上而下分析內(nèi)容線索n語(yǔ)法分析器的功能語(yǔ)法分析器的功能n自上而下分析方法概述自上而下分析方法概述nLL（1）分析方法）分析方法n遞歸下降分析程序遞歸下降分析程序n預(yù)測(cè)分析程序預(yù)測(cè)分析程序語(yǔ)法分析器n語(yǔ)法分析的任務(wù)語(yǔ)法分析的任務(wù) ：對(duì)任一給定對(duì)任一給定 w VT*，判斷，判斷 w L(G)?n 語(yǔ)法分析器：按照產(chǎn)生式規(guī)則，做識(shí)別語(yǔ)法分析器：按照產(chǎn)生式規(guī)則，做識(shí)別w的工作的工作詞法分析器詞法分析器語(yǔ)法分析器語(yǔ)法分析器編譯程序后續(xù)部分編譯程序后續(xù)部分符號(hào)表符號(hào)表源程序源程序單詞符號(hào)單詞符號(hào)取下一個(gè)取下一個(gè)單詞符號(hào)單詞符號(hào)語(yǔ)法分析樹語(yǔ)法分析樹語(yǔ)法分析器在編譯程序中的地位語(yǔ)法分析器在編

2、譯程序中的地位語(yǔ)法分析方法n自上而下分析自上而下分析 LL（1）分析法）分析法 遞歸下降分析法遞歸下降分析法 預(yù)測(cè)分析法預(yù)測(cè)分析法n自下而上分析自下而上分析 算符優(yōu)先分析法算符優(yōu)先分析法 LR分析法分析法從文法的開始符號(hào)出發(fā)，反從文法的開始符號(hào)出發(fā)，反復(fù)使用各種產(chǎn)生式，尋找與復(fù)使用各種產(chǎn)生式，尋找與輸入符號(hào)匹配的最左推導(dǎo)。輸入符號(hào)匹配的最左推導(dǎo)。從輸入符號(hào)串開始，逐步進(jìn)從輸入符號(hào)串開始，逐步進(jìn)行歸約（最右推導(dǎo)的逆過行歸約（最右推導(dǎo)的逆過程），直至歸約到文法的開程），直至歸約到文法的開始符號(hào)。始符號(hào)。內(nèi)容線索語(yǔ)法分析器的功能語(yǔ)法分析器的功能n自上而下分析方法概述自上而下分析方法概述nLL（1）分

3、析方法）分析方法n遞歸下降分析程序遞歸下降分析程序n預(yù)測(cè)分析程序預(yù)測(cè)分析程序自上而下分析n從文法的開始符號(hào)出發(fā)，向下推導(dǎo)，推出從文法的開始符號(hào)出發(fā)，向下推導(dǎo)，推出句子句子n對(duì)任何的輸入串對(duì)任何的輸入串(單詞符號(hào)單詞符號(hào))，試圖用一切可，試圖用一切可能的辦法能的辦法, 從文法的開始符號(hào)出發(fā)，自上而從文法的開始符號(hào)出發(fā)，自上而下地為輸入串建立一棵語(yǔ)法樹，即為輸入下地為輸入串建立一棵語(yǔ)法樹，即為輸入串尋找一個(gè)最左推導(dǎo)。串尋找一個(gè)最左推導(dǎo)。語(yǔ)法分析示例GS: Sid:=E EE+E EE*E E-E E (E) Eidid:=-id+id+id 是否為是否為GS的句子？的句子？S id:=E id:=

4、 -E id:= - E+E id:= - id+E id:= - id+E+E id:= - id+id+E id:= - id+id+id例例. 設(shè)文法設(shè)文法GS： SxAy，A*SxA y* *推導(dǎo)過程：推導(dǎo)過程： S xAy x*y(回溯回溯) x*y(成功成功)用用A*用用A* (成功成功) (回溯回溯)判定輸入串判定輸入串 x * y是否為它的句子是否為它的句子?x * y用用SxAy SxA ySxA y*例例GS: Sid:=E EE+E EE*E E-E E (E) Eidid:=-id+id+id 是否為是否為GS的句子？的句子？S id:=E id:= -E id:= -

5、 E+E id:= - E+E +E id:= - E+E +E+E 。帶回溯自上而下分析面臨的問題n虛假匹配虛假匹配問題問題n回溯回溯回溯會(huì)引起時(shí)間和空間的大量消耗回溯會(huì)引起時(shí)間和空間的大量消耗n文法的文法的左遞歸左遞歸問題問題一個(gè)文法是含有左遞歸的，如果存在非終結(jié)符一個(gè)文法是含有左遞歸的，如果存在非終結(jié)符P P P含有左遞歸的文法將使自上而下的分析過程陷入無(wú)限循環(huán)含有左遞歸的文法將使自上而下的分析過程陷入無(wú)限循環(huán)n報(bào)告分析不成功時(shí)，難于知道輸入串中出錯(cuò)的確切位置。報(bào)告分析不成功時(shí)，難于知道輸入串中出錯(cuò)的確切位置。實(shí)際上采用了一種實(shí)際上采用了一種窮盡一切可能的試探法窮盡一切可能的試探法，因此

6、效率很低，因此效率很低，代價(jià)很高代價(jià)很高+內(nèi)容線索n語(yǔ)法分析器的功能語(yǔ)法分析器的功能n自上而下分析方法概述自上而下分析方法概述LL（1）分析方法）分析方法n遞歸下降分析程序遞歸下降分析程序n預(yù)測(cè)分析程序預(yù)測(cè)分析程序nLL（1）分析中的錯(cuò)誤處理）分析中的錯(cuò)誤處理LL(1)分析法n從左從左(Left)到右掃描輸入串；構(gòu)造最左到右掃描輸入串；構(gòu)造最左(Leftmost)推導(dǎo)；分析時(shí)每步向前看一個(gè)推導(dǎo)；分析時(shí)每步向前看一個(gè)(1)字符。字符。n目的：構(gòu)造不帶回溯的自上而下分析算法目的：構(gòu)造不帶回溯的自上而下分析算法左遞歸的消除左遞歸的消除消除回溯，提左因子消除回溯，提左因子FIRST集合，集合，F(xiàn)OLL

7、OW集合集合LL(1)分析條件分析條件LL(1)分析方法分析方法左遞歸文法n一個(gè)文法含有下列形式的產(chǎn)生式時(shí)，一個(gè)文法含有下列形式的產(chǎn)生式時(shí)， a)直接遞歸直接遞歸 AA A VN, V* b)間接遞歸間接遞歸 AB B A A,B VN, ， V* 稱為稱為左遞歸文法左遞歸文法。n 如果一個(gè)如果一個(gè) 文法是左遞歸時(shí)，則不能采用自頂向下分析法。文法是左遞歸時(shí)，則不能采用自頂向下分析法。例例2. 文法文法 P1aP2 P1P2b P2P1c P2d是間接左遞歸是間接左遞歸例例1. 文法文法S Sa S b 是直接左遞歸是直接左遞歸 語(yǔ)言是：語(yǔ)言是：L ban | n0消除直接左遞歸P P（，不以不

8、以P開頭）開頭）P PP P 例例. 文法文法EE+TT TT*FF F(E)i ETEE TE TFT T *FT F(E)i n一般地一般地, 假定假定P關(guān)于的產(chǎn)生式是關(guān)于的產(chǎn)生式是 PP1P2 Pm 1 2 n 其中：其中：i，i不以不以P開頭，開頭， 則改寫為則改寫為: P 1 P 2 P .n P P 1 P 2 P m P 消除左遞歸的算法思想P2P1P3 P1P3d文法文法 P2P1b P3P2c P3P2c P1bc P3dbc文法文法 P1P3d P2P1b P2P1P3消除左遞歸算法（1） 排序排序: P1、P2、 、Pn（2） FOR i := 1 TO n DO BEG

9、IN FOR j:= 1 TO i -1 DO 把形如把形如PiPj的規(guī)則改寫為：的規(guī)則改寫為： Pi12 k 其中：其中： Pj 1 2 k 是關(guān)于是關(guān)于Pj 的所有規(guī)則的所有規(guī)則; 消除關(guān)于消除關(guān)于Pi 規(guī)則的直接左遞歸。規(guī)則的直接左遞歸。 END（3） 化簡(jiǎn)化簡(jiǎn): 刪除永不使用的產(chǎn)生式刪除永不使用的產(chǎn)生式算法示意P2P1P3 P1P3d文法文法 P2P1b P3P2c P3P2c P3dbc文法文法 P1P3d P2P1b P3db P2P1P3例例.文法文法GP3: P3P2c|c P2P1b|b P1P3a|a有推導(dǎo)：有推導(dǎo)：P3 P2c P1bc P3abc, 存在左遞歸。存在左遞

10、歸。按按P1(1)、P2(2)、P3(3)排序，執(zhí)行算法得：排序，執(zhí)行算法得：i=1，j從從1至至0，P1的產(chǎn)生式的產(chǎn)生式P1P3a|a無(wú)直接左遞歸，無(wú)需消除直接左遞無(wú)直接左遞歸，無(wú)需消除直接左遞歸。歸。i=2，j從從1至至1，P2的候選式含的候選式含P1，P1的產(chǎn)生式代入的產(chǎn)生式代入P2的產(chǎn)生式得：的產(chǎn)生式得：P2P3ab|ab|b，無(wú)直接左遞歸。，無(wú)直接左遞歸。i=3，j從從1至至2: j=1，P3的候選式不含的候選式不含P1，所以無(wú)需替換；，所以無(wú)需替換； j=2，P3的候選式含的候選式含P2，將，將P2P3ab|ab|b代入代入S的候選式得：的候選式得：P3P3abc|abc|bc|c

11、 再消除直接左遞歸得：再消除直接左遞歸得：P3abcP3| bcP3| cP3P3abcP3|消除無(wú)用產(chǎn)生式：消除無(wú)用產(chǎn)生式：P2P3ab|ab|b，P1P3a|a，得文法：得文法： P3abcP3| bcP3| cP3 P3abcP3|文法對(duì)應(yīng)的正規(guī)式：文法對(duì)應(yīng)的正規(guī)式：V1=(abc|bc|c)(abc)* 。例例.文法文法GS: S Qc|c QRb|b RSa|a有推導(dǎo)：有推導(dǎo)：S Qc Rbc Sabc, 存在左遞歸。存在左遞歸。按按R(1)、Q(2)、S(3)排序，執(zhí)行算法得：排序，執(zhí)行算法得：i=1，j從從1至至0，R的產(chǎn)生式的產(chǎn)生式RSa|a無(wú)直接左遞歸，無(wú)需消除直接左遞歸。無(wú)

12、直接左遞歸，無(wú)需消除直接左遞歸。i=2，j從從1至至1，Q的候選式含的候選式含R，R的產(chǎn)生式代入的產(chǎn)生式代入Q的產(chǎn)生式得：的產(chǎn)生式得：QSab|ab|b，無(wú)直接左遞歸。，無(wú)直接左遞歸。i=3，j從從1至至2: j=1，S的候選式不含的候選式不含R，所以無(wú)需替換；，所以無(wú)需替換； j=2，S的候選式含的候選式含Q，將，將QSab|ab|b代入代入S的候選式得：的候選式得：SSabc|abc|bc|c 再消除直接左遞歸得：再消除直接左遞歸得：SabcS| bcS| cSSabcS|消除無(wú)用產(chǎn)生式：消除無(wú)用產(chǎn)生式：QSab|ab|b，RSa|a，得文法：得文法： SabcS| bcS| cS Sab

13、cS|文法對(duì)應(yīng)的正規(guī)式：文法對(duì)應(yīng)的正規(guī)式：V1=(abc|bc|c)(abc)* 。例例. 文法文法GS: S Qc|c QRb|b RSa|a解：解： 1）排序：）排序：S(1)、Q(2)、R(3) 2）代入得：）代入得： S Q cc Q R bb R Rbcabca | ca | a 消除直接左遞歸：消除直接左遞歸： S Q cc Q R bb R bcaR caR | aR R bcaR 消除隱含的左遞歸算法與非終極符排序方法無(wú)關(guān)消除隱含的左遞歸算法與非終極符排序方法無(wú)關(guān)回溯問題例如，有產(chǎn)生式：例如，有產(chǎn)生式：語(yǔ)句語(yǔ)句 if 條件條件 then 語(yǔ)句語(yǔ)句 else 語(yǔ)句語(yǔ)句 | whi

14、le 條件條件 do 語(yǔ)句語(yǔ)句 | begin 語(yǔ)句表語(yǔ)句表 end 若要尋找一個(gè)語(yǔ)句，那么關(guān)鍵字若要尋找一個(gè)語(yǔ)句，那么關(guān)鍵字 if，while，begin就提示某個(gè)替換式是唯一的替換式。就提示某個(gè)替換式是唯一的替換式。無(wú)回溯！無(wú)回溯！回溯問題例如，有產(chǎn)生式：例如，有產(chǎn)生式：語(yǔ)句語(yǔ)句 if 條件條件 then 語(yǔ)句語(yǔ)句 else 語(yǔ)句語(yǔ)句 | if 條件條件 then 語(yǔ)句語(yǔ)句 | while 條件條件 do 語(yǔ)句語(yǔ)句 | begin 語(yǔ)句表語(yǔ)句表 end 產(chǎn)生回溯！產(chǎn)生回溯！回溯原因若當(dāng)前符號(hào)若當(dāng)前符號(hào) = a，下一步要展開，下一步要展開A ，而而 A 1|2|n ，怎樣選擇怎樣選擇i？（1

15、）以）以a為頭的為頭的i如果只有一個(gè)，則替換唯一；如果只有一個(gè)，則替換唯一；（2）若以）若以a為頭有多個(gè)為頭有多個(gè)i的，則替換不唯一，可的，則替換不唯一，可能需要回溯，這是文法的問題，應(yīng)該變換文法。能需要回溯，這是文法的問題，應(yīng)該變換文法。無(wú)回溯n對(duì)任何非終結(jié)符號(hào)對(duì)任何非終結(jié)符號(hào)A，用它匹配輸入串時(shí)能夠根，用它匹配輸入串時(shí)能夠根據(jù)當(dāng)前輸入，準(zhǔn)確地指派一個(gè)候選式據(jù)當(dāng)前輸入，準(zhǔn)確地指派一個(gè)候選式若匹配成功，則不虛假；若匹配成功，則不虛假；若匹配不成功，則其它的候選式也不會(huì)成功。若匹配不成功，則其它的候選式也不會(huì)成功。n 即當(dāng)即當(dāng)A執(zhí)行匹配時(shí)，執(zhí)行匹配時(shí)， A12 n 若若A面臨的第一個(gè)輸入符號(hào)為面

16、臨的第一個(gè)輸入符號(hào)為a，則應(yīng)該準(zhǔn)確地指派，則應(yīng)該準(zhǔn)確地指派某一個(gè)某一個(gè)i，其成敗完全代表，其成敗完全代表A，無(wú)需進(jìn)行試探和回溯。，無(wú)需進(jìn)行試探和回溯。文法的要求（1）不含左遞歸）不含左遞歸（2）對(duì)每個(gè)非終結(jié)符的候選式，其任何推導(dǎo)的頭符號(hào)（終）對(duì)每個(gè)非終結(jié)符的候選式，其任何推導(dǎo)的頭符號(hào)（終結(jié)符）集合兩兩不相交。結(jié)符）集合兩兩不相交。n以上條件（以上條件（2）可表示為：對(duì)文法的任一非終結(jié)符號(hào)）可表示為：對(duì)文法的任一非終結(jié)符號(hào)A，若，若 A12 n 則應(yīng)有則應(yīng)有 FIRST(i)FIRST(j) = ，i jn符號(hào)串符號(hào)串的的終結(jié)首符集終結(jié)首符集FIRST () 定義為：定義為：FIRST() =

17、a a , aVT 特別地，若特別地，若 ，則規(guī)定，則規(guī)定FIRST ()。*回溯解決方法n提取公共左因子，將文法改造成任何非終結(jié)符的所有候選提取公共左因子，將文法改造成任何非終結(jié)符的所有候選首符集兩兩不相交。首符集兩兩不相交。A 12 n 1 2 m （其中（其中1 、 2 、 、 m不以不以開頭）開頭）A A 1 2 mA 12 n例例. 文法文法G：SaSb|aS| 解：提?。航猓禾崛。篠 aS( b|) S引入新符：引入新符：S aSA|A b|例例. 對(duì)文法對(duì)文法G2： A ad A Bc B aA B bB解：先替換為：解：先替換為：A adA aAcA bBcB aAB bB再提

18、取再提取A a（Ac|d)A bBcB aAB bB引入新符引入新符A aAA bBcA Ac|d B aAB bB一般地，經(jīng)過反復(fù)提取左因子可把每一個(gè)非終一般地，經(jīng)過反復(fù)提取左因子可把每一個(gè)非終結(jié)符的所有候選首符集變成兩兩不相交。結(jié)符的所有候選首符集變成兩兩不相交。LL（1）分析條件n若文法已經(jīng)消除了左遞歸，且對(duì)每個(gè)非終結(jié)符滿若文法已經(jīng)消除了左遞歸，且對(duì)每個(gè)非終結(jié)符滿足足FIRST(i)FIRST(j) = 是否就解決了是否就解決了虛假匹配虛假匹配和和回溯回溯的問題？的問題？n對(duì)某個(gè)輸入符號(hào)對(duì)某個(gè)輸入符號(hào)a，及待匹配的非終結(jié)符，及待匹配的非終結(jié)符A（A12 n）a屬于某個(gè)候選式的屬于某個(gè)候選

19、式的FIRST集合集合a不屬于任何候選式的不屬于任何候選式的FIRST集合，即對(duì)任意集合，即對(duì)任意i，a FIRST (i) S aA abAS abS abd這是因?yàn)檫@是因?yàn)锳有產(chǎn)生式有產(chǎn)生式A,而從開始符號(hào)而從開始符號(hào)S可以得出可以得出 S Ad *示例例例. G(S):S aA|d輸入符號(hào)串輸入符號(hào)串a(chǎn)bd是否為句子？是否為句子？ A bAS|d| SaAbASdFIRST(S)=a, dFIRST(A) =b, d，S aA abAS abdS 。FOLLOWn設(shè)設(shè)S是文法是文法G的開始符號(hào)，對(duì)的開始符號(hào)，對(duì)G的任何非終結(jié)符的任何非終結(jié)符A，定義定義A的后繼終結(jié)符號(hào)集的后繼終結(jié)符號(hào)集為

20、：為：FOLLOW（A） aS Aa , aVT n特別地特別地,若若S A，則規(guī)定，則規(guī)定FOLLOW(A)。FOLLOW(A)是所有句型中出現(xiàn)在緊接是所有句型中出現(xiàn)在緊接A之后的終結(jié)之后的終結(jié)符或符或“”。*結(jié)論n當(dāng)非終結(jié)符當(dāng)非終結(jié)符A面臨輸入符號(hào)面臨輸入符號(hào)a，且，且a FIRST(i) (對(duì)任意對(duì)任意i)時(shí)，如果時(shí)，如果A的某個(gè)候選首符集包含的某個(gè)候選首符集包含（即（即FIRST（A），那么，當(dāng)），那么，當(dāng)aFOLLOW（A）時(shí)，就允許）時(shí)，就允許A自動(dòng)自動(dòng)匹配（即選用匹配（即選用A工作），否則，認(rèn)為工作），否則，認(rèn)為a的出現(xiàn)是一種語(yǔ)的出現(xiàn)是一種語(yǔ)法錯(cuò)誤。法錯(cuò)誤。n要正確進(jìn)行不帶回溯的

21、語(yǔ)法分析，文法應(yīng)滿足的第三個(gè)條要正確進(jìn)行不帶回溯的語(yǔ)法分析，文法應(yīng)滿足的第三個(gè)條件可表示為：若件可表示為：若A的候選首符集中包含的候選首符集中包含，則，則 FIRST (A) FOLLOW (A) = LL（1）文法n如果文法如果文法G滿足以下條件：滿足以下條件：（1）文法消除了左遞歸；文法消除了左遞歸；（2）文法中每個(gè)非終結(jié)符）文法中每個(gè)非終結(jié)符A的各個(gè)產(chǎn)生式的候選首符集兩兩的各個(gè)產(chǎn)生式的候選首符集兩兩不相交，即不相交，即 若若 A12 n ， 則則 FIRST(i)FIRST(j) = ，（，（i j）；）；（3）對(duì)文法中的每個(gè)非終結(jié)符）對(duì)文法中的每個(gè)非終結(jié)符A，若它存在某個(gè)候選首符集，若

22、它存在某個(gè)候選首符集中包含中包含，則，則FIRST(A) FOLLOW(A) = ，則稱該文法則稱該文法G為為L(zhǎng)L(1)文法文法。LL（1）分析方法n對(duì)一個(gè)對(duì)一個(gè)LL（1）文法，可以對(duì)某個(gè)輸入串進(jìn)行有效的無(wú)回）文法，可以對(duì)某個(gè)輸入串進(jìn)行有效的無(wú)回溯的自上而下分析。溯的自上而下分析。n設(shè)面臨的輸入符號(hào)為設(shè)面臨的輸入符號(hào)為a，要用非終結(jié)符，要用非終結(jié)符A進(jìn)行匹配，且進(jìn)行匹配，且A12 n ，則可如下分析，則可如下分析: （1）若）若aFIRST (i) ，則指派，則指派i執(zhí)行匹配任務(wù)；執(zhí)行匹配任務(wù)； （2）否則）否則 1）若）若FIRST(A)，且，且aFOLLOW (A)，則讓，則讓A 與與自動(dòng)匹配；自動(dòng)匹配； 2）否則，）否則，a的出現(xiàn)是一種語(yǔ)法錯(cuò)誤。的出現(xiàn)是一種語(yǔ)法錯(cuò)誤。對(duì)于文法對(duì)于文法G的每個(gè)文法符號(hào)的每個(gè)文法符號(hào)XVTVN，構(gòu)造，構(gòu)造FIRST（X）的）的方法是：方法是：（1）若）若XVT，則，則FIRST（X）=X；（2）若）若X VN，且有產(chǎn)生式，且有產(chǎn)生式Xa, aVT，則把，則把a(bǔ)加入到加入到FIRST（X）中，若有中，若有X