上下文無關(guān)課件

1、第四章文法與語法分析本章主要內(nèi)容(Chapter 4)4.1 語法分析程序概述4.2 上下文無關(guān)文法4.3 遞歸下降法自頂向下分析4.4 LL分析方法自頂向下分析4.5 LR方法自底向上分析4.6 LR分析分析器的生成器4.7 語法錯(cuò)誤處理4.1 語法分析程序概述1） 語法分析器的功能 根據(jù)文法規(guī)則，從源程序單詞符號(hào)串中識(shí)別出語法成分，并進(jìn)行語法檢查。 基本任務(wù)：識(shí)別符號(hào)串S是否為某語法成分4.1 語法分析程序概述2） 語法分析器的輸入語法分析器的輸入是語法分析器的輸出，即Token序列或者稱Token流。4.1 語法分析程序概述3） 語法錯(cuò)誤類別及關(guān)鍵性錯(cuò)誤a. 程序的開始單詞錯(cuò)，表達(dá)式的開

2、始單詞錯(cuò)，語句的開始單詞錯(cuò)，表達(dá)式的后繼單詞錯(cuò)，語句的后繼單詞錯(cuò)b. 標(biāo)識(shí)符和常量單詞錯(cuò)c. 括號(hào)類錯(cuò)誤d. 分隔符錯(cuò)（最關(guān)鍵性錯(cuò)誤）4.1 語法分析程序概述4） 語法錯(cuò)誤處理語法錯(cuò)誤糾正語法錯(cuò)誤信息輸出a. 插入b. 刪除c. 修改4.2 上下文無關(guān)文法當(dāng)我們表述一種語言時(shí)，無非是說明這種語言的句子，如果語言只含有有窮多個(gè)句子，則只需列出句子的有窮集就行了，但對(duì)于含有無窮句子的語言來講，存在著如何給出它的有窮表示的問題。1） 上下文無關(guān)文法的概念（談?wù)勈裁词俏姆ǎ┮宰匀徽Z言為例，人們無法列出全部句子，但是人們可以給出一些規(guī)則來說明句子的組成結(jié)構(gòu)，比如漢語句子可以描述為：由主語后接謂語構(gòu)成，構(gòu)

3、成謂語的是動(dòng)詞和直接賓語我們采用BNF來表示這種句子的構(gòu)成規(guī)則：句子=主語謂語主語=代詞名詞代詞=我你他名詞=王明大學(xué)生工人英語謂語=動(dòng)詞直接賓語動(dòng)詞=是學(xué)習(xí)直接賓語=代詞名詞 4.2 上下文無關(guān)文法1）上下文無關(guān)文法的概念（談?wù)勈裁词俏姆ǎ┯辛艘唤M規(guī)則以后，按照如下方式導(dǎo)出句子：開始去規(guī)則中找=左端的帶有句子的規(guī)則并把它由=右端的符號(hào)串代替，那么這個(gè)過程一種可能為在頁底所示：句子=主語謂語主語=代詞名詞代詞=我你他名詞=王明大學(xué)生工人英語謂語=動(dòng)詞直接賓語動(dòng)詞=是學(xué)習(xí)直接賓語=代詞名詞 句子 主語謂語 代詞謂語我謂語我動(dòng)詞直接賓語 我是直接賓語我是名詞我是大學(xué)生結(jié)論：文法是一組規(guī)則，用以定義

4、語言的語法結(jié)構(gòu)4.2 上下文無關(guān)文法1）上下文無關(guān)文法的概念（上下文無關(guān)文法數(shù)學(xué)定義） 上下文無關(guān)文法G定義為四元組(VN，VT，P，S )其中：VN為非終結(jié)符號(hào)(或語法實(shí)體，或變量)集；VT為終結(jié)符號(hào)集；P為產(chǎn)生式(也稱規(guī)則)的集合； 具有如下形式： AX1X2Xn，A為VN ，Xi為（VN VT） 。 S稱作識(shí)別符號(hào)或開始符號(hào)，它是一個(gè)非終結(jié)符，至少要在一條產(chǎn)生式中作為左部出現(xiàn)。VN和VT不含公共的元素，即VN VT = 4.2 上下文無關(guān)文法1）上下文無關(guān)文法的概念（舉例1）例1 文法G=（VN，VT，P，S）VN = S , VT = 0, 1 P=S0S1, S01 S為開始符號(hào)注：

5、 1.產(chǎn)生式左部相同時(shí)可以進(jìn)行合并：如：S, S， S 可以寫作S 例1中的P可以寫成如下形式：P= S0S1014.2 上下文無關(guān)文法1）上下文無關(guān)文法的概念（舉例2）例2 文法G=（VN，VT，P，S）VN =I，T，DVT =a,b,c,x,y,z,0,1,9P=IT IT ID， Tab|z|A|B|Z， D09， S=I2.習(xí)慣表示 大寫字母：非終結(jié)符小寫字母：終結(jié)符 開始符號(hào)和文法的名字寫在一起：如GS注： 4.2 上下文無關(guān)文法1）上下文無關(guān)文法的概念（簡寫的例子）例3GS： SaSb Aab |aAb |例4GS：S ABA Ax | yB z4.2 上下文無關(guān)文法1） 上下文

6、無關(guān)文法的概念（推導(dǎo)的定義）直接推導(dǎo)“”的定義: A是文法G的產(chǎn)生式， 則有A , 讀作A 直接推導(dǎo)到 也稱直接歸約到A 推導(dǎo)的定義(直接推導(dǎo)的定義)例5：G： S0S1， S01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S14.2 上下文無關(guān)文法1）上下文無關(guān)文法的概念（推導(dǎo)的定義） 推導(dǎo)的定義(多步推導(dǎo)的定義) 若存在v w0 w1 . wn=w,(n0) 則記為v =+ w，v推導(dǎo)出w，或w歸約到v 若有v =+ w，或v=w，則記為v =* w例6：G：S0S1， S01 0S1 00S11 00S11 000S111 000S111 0

7、0001111 S 0S1 00S11 000S111 00001111 S =+ 00001111 S =* S 00S11 =* 00S114.2 上下文無關(guān)文法 推導(dǎo)的定義(最左和最右推導(dǎo))最左（最右）推導(dǎo)：在推導(dǎo)的任何一步，其中、是句型，都是對(duì)中的最左（右）非終結(jié)符進(jìn)行替換最右推導(dǎo)被稱為規(guī)范推導(dǎo)。由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型。1）上下文無關(guān)文法的概念（推導(dǎo)的定義）4.2 上下文無關(guān)文法1）上下文無關(guān)文法的概念（句型、句子的定義） 句型、句子的定義句型有文法G，若S =* x，則稱x是文法G的句型。句子有文法G，若S =* x，且xVT*，則稱x是文法G的句子。例7：G： S0S1，

8、 S01 S 0S1 00S11 000S11100001111 G的句型S,0S1 ,00S11 ,000S111,00001111 G的句子00001111, 014.2 上下文無關(guān)文法1）上下文無關(guān)文法的概念（文法生成的語言）由文法G生成的語言記為L(G),它是文法G的一切句子的集合: L(G)=x|S =* x，其中S為文法的開始符號(hào)，且x VT* 文法生成的語言例8：G： S0S1， S01L(G)=0n1n|n14.2 上下文無關(guān)文法1）上下文無關(guān)文法的概念（文法的等價(jià)） 文法的等價(jià)若L（G1）=L（G2），則稱文法G1和G2是等價(jià)的。例9如文法G1A：A0R A01 RA1 與G

9、2S：S0S1 S01表達(dá)的語言是相同的，所以有G1與G2是等價(jià)的4.2 上下文無關(guān)文法2） 文法的類型（四種類型的定義）對(duì)產(chǎn)生式施加不同的限制，Chomsky將文法分為四種類型：0型文法：對(duì)任一產(chǎn)生式，都有(VNVT)+， (VNVT)*1型文法：對(duì)任一產(chǎn)生式，都有|， 僅僅 S除外2型文法：對(duì)任一產(chǎn)生式，都有VN ， (VNVT)*3型文法：任一產(chǎn)生式的形式都為AaB或Aa，其中AVN ，BVN ，aVT4.2 上下文無關(guān)文法1型文法（上下文有關(guān)文法）：產(chǎn)生式的形式為1A212，即只有A出現(xiàn)在1和2的上下文中時(shí)，才允許取代A。其識(shí)別系統(tǒng)是線性界限自動(dòng)機(jī)。 2型文法（上下文無關(guān)文法CFG）：

10、產(chǎn)生式的形式為A，取代A時(shí)與A的上下文無關(guān)。其識(shí)別系統(tǒng)是不確定的下推自動(dòng)機(jī)。 3型文法（正規(guī)文法RG）：產(chǎn)生的語言是有窮自動(dòng)機(jī)（FA）所接受的集合2） 文法的類型（四種文法產(chǎn)生式的形式）4.2 上下文無關(guān)文法0型文法1型文法2型文法3型文法四種文法之間的關(guān)系是：包含關(guān)系.（原因：將產(chǎn)生式做進(jìn)一步限制而定義的。）2） 文法的類型（四種類型文法包含關(guān)系）4.2 上下文無關(guān)文法例10：1型（上下文有關(guān)）文法 文法GS： SCDAbbA CaCABaaB CbCBBbbB ADaDC BDbDD AabD2） 文法的類型（1型文法舉例）4.2 上下文無關(guān)文法例11：2型（上下文無關(guān)）文法 文法GS：S

11、ABABS|0BSA|1例12：3型(正則（或正規(guī)）文法)文法 文法GS：S0A|1B|0 A0A|1B|0S B1B|1|02） 文法的類型（2型和3型文法舉例）4.2 上下文無關(guān)文法 a. 0型文法產(chǎn)生的語言稱為0型語言 b. 1型文法或上下文有關(guān)文法（ CSG ）產(chǎn)生的語言稱為1型語言或上下文有關(guān)語言（CSL） c. 2型文法或上下文無關(guān)文法（ CFG ）產(chǎn)生的語言稱為2型語言或上下文無關(guān)語言（ CF L ） d. 3型文法或正則（正規(guī)）文法（ RG ）產(chǎn)生的語言稱為3型語言正則（正規(guī)）語言（ RL ） 2） 文法的類型（四種類型文法產(chǎn)生的語言）4.2 上下文無關(guān)文法 0型文法（短語結(jié)構(gòu)

12、文法）的能力相當(dāng)于圖靈機(jī)，可以表征任何遞歸可枚舉集，而且任何0型語言都是遞歸可枚舉的 帶 a0 a1 a2 a3 a4 a5 a6 a7 a8 an-1 an 控制器磁頭任何能用圖靈機(jī)描述的計(jì)算都能機(jī)械實(shí)現(xiàn)，任何能在現(xiàn)代計(jì)算機(jī)上實(shí)現(xiàn)的計(jì)算都能用圖靈機(jī)描述2） 文法的類型（0型文法和圖靈機(jī)）4.2 上下文無關(guān)文法3） 正規(guī)語言、正規(guī)式與有限自動(dòng)機(jī)的表達(dá)能力 正規(guī)語言、正規(guī)式與有限自動(dòng)機(jī)FA的表達(dá)能力是相同的。即: a. 如果存在一個(gè)正規(guī)語言、其表達(dá)的語言為L（G），則一定存在表達(dá)能力相同的正規(guī)式和有限自動(dòng)機(jī)FA。 b. 如果存在一個(gè)正規(guī)式、其表達(dá)的語言為L（r），則一定存在表達(dá)能力相同的正規(guī)語言

13、和有限自動(dòng)機(jī)FA。 c. 如果存在一個(gè)有限自動(dòng)機(jī)、其表達(dá)的語言為L（M），則一定存在表達(dá)能力相同的正規(guī)語言和正規(guī)式。且L(G)=L(r)=L(M)且L(G)=L(r)=L(M)且L(G)=L(r)=L(M)4.2 上下文無關(guān)文法有窮自動(dòng)機(jī)NFA M 這樣構(gòu)造： = VT K= VN N, N為一個(gè)新狀態(tài),它不在VN中 A=S Z=N 對(duì)G中的形如 DtB的產(chǎn)生式,t為終結(jié)符或,有f(D,t)=B； 對(duì)G中形如Dt的產(chǎn)生式， t為終結(jié)符或,有f(D,t)=N; 對(duì)VT中的每一個(gè)a ,有f(N,a)=設(shè)G=（VN，VT，P，S）是正規(guī)文法，則存在一個(gè)有窮自動(dòng)機(jī) M=(K, , f, A, Z)，使

14、得L(M)=L(G)3） 正規(guī)語言、正規(guī)式與有限自動(dòng)機(jī)的表達(dá)能力(續(xù))4.2 上下文無關(guān)文法G 的構(gòu)造： VT = VN= K S = A 若 f(D,t)=B ，則DtB在P中 若 f(D,t)=B ，且B在Z中，則Dt在P中已知一有窮自動(dòng)機(jī)M= (K, , f, A, Z),存在有一個(gè)3型文法G = （VN，VT，P，S）,使得L(G)=L(M)3） 正規(guī)語言、正規(guī)式與有限自動(dòng)機(jī)的表達(dá)能力(續(xù))4.2 上下文無關(guān)文法對(duì)上的正規(guī)式r ,存在一個(gè)RG=(VN,VT,P,S)：L(G)=L(r) VT= ,S VN ，生成正規(guī)產(chǎn)生式 Sr (R 1) 對(duì)形如 Ar1r2的正規(guī)產(chǎn)生式：Ar1B B

15、r2 BVN (R 2)對(duì)形如Arr1的正規(guī)產(chǎn)生式： ArB Ar1 BrB Br1 BVN (R 3)對(duì)形如Ar1r2的正規(guī)產(chǎn)生式: Ar1 A r2 不斷應(yīng)用R做變換，直到每個(gè)產(chǎn)生式右端至多有一個(gè)VN3） 正規(guī)語言、正規(guī)式與有限自動(dòng)機(jī)的表達(dá)能力(續(xù))4.2 上下文無關(guān)文法4）上下文無關(guān)文法的語法樹 上下文無關(guān)文法產(chǎn)生式形式為：A ，它表示不管A的前后是 什么，都可以把A用替換。 語法樹-句型推導(dǎo)的直觀表示 上下文無關(guān)文法有足夠的能力描述程序設(shè)計(jì)語言的語法結(jié)構(gòu)， 所以我們在本章研究上下文無關(guān)文法。4.2 上下文無關(guān)文法4）上下文無關(guān)文法的語法樹（續(xù)）設(shè)G=( VN,VT,P,S)為一cfg，

16、若一棵樹滿足下列4個(gè)條件，則此樹稱作G的語法樹(推導(dǎo)樹)(派生樹）：1. 每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記，此標(biāo)記是V的一個(gè)符號(hào)2. 根的標(biāo)記是S3. 若一結(jié)點(diǎn)n至少有一個(gè)它自己除外的子孫，并且有標(biāo)記A，則肯定AVN4. 如果結(jié)點(diǎn)n有標(biāo)記A,其直接子孫結(jié)點(diǎn)從左到右的次序是n1，n2，nk，其標(biāo)記分別為A1，A2，Ak，那么AA1A2，Ak一定是P中的一個(gè)產(chǎn)生式語法樹的結(jié)果：從左到右讀出葉子的標(biāo)記而構(gòu)成的行謂之語法樹的結(jié)果。 語法樹的定義 4.2 上下文無關(guān)文法 語法樹的例子 4）上下文無關(guān)文法的語法樹（續(xù)） 例13: GS:SaASASbAASSSaAba句子aabbaa的語法樹（推導(dǎo)樹） S a A S

17、 S b A a a b a句子aabbaa推導(dǎo)過程：S aAS aSbAS aabAS aabbaS aabbaa4.2 上下文無關(guān)文法 語法樹的有關(guān)結(jié)論 給定文法G=(VN,VT,P,S)，對(duì)于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹(推導(dǎo)樹)。若G為上下文無關(guān)文法，對(duì)于，有S =* ，當(dāng)且僅當(dāng)文法G有以為結(jié)果的一棵語法樹(推導(dǎo)樹)。4）上下文無關(guān)文法的語法樹（續(xù)） S a A S S b A a a b a4.2 上下文無關(guān)文法推導(dǎo)過程中施用產(chǎn)生式的順序4）上下文無關(guān)文法的語法樹（續(xù)） 例14: GS:SaASASbAASSSaAbaSaASaAaaSbAaaSbbaaaabbaaSaASa

18、SbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa一棵語法樹表示了一個(gè)句型的種種可能的(但未必是所有的)不同推導(dǎo)過程，包括最左(最右)推導(dǎo)。最左（右）推導(dǎo)：4.2 上下文無關(guān)文法二義文法的定義5）二義文法二義文法的定義 a. 若一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語法樹，則稱這個(gè)文法是二義的 b. 或者，若一個(gè)文法存在某個(gè)句子有兩個(gè)不同的最左（右）推導(dǎo)，則稱這個(gè)文法是二義的 4.2 上下文無關(guān)文法5）二義文法（二義文法的例子）例15GE:E E + E | E * E | (E ) | E | idE E * E E E + E id * E E * E

19、 +E id * E + E id * E + E id * id + E id * id + E id * id + id id * id + id二義文法的例子EEE*+EEidididEEidE*+EEidid4.2 上下文無關(guān)文法5）二義文法（二義文法的相關(guān)結(jié)論）判定任給的一個(gè)上下文無關(guān)文法是否二義，或它是否產(chǎn)生一個(gè)先天二義的上下文無關(guān)語言，這兩個(gè)問題都是遞歸不可解的，但可以為無二義性尋找一組充分條件。二義文法的相關(guān)結(jié)論文法的二義性和語言的二義性是不同的概念可能有兩個(gè)不同的文法G和G，這兩個(gè)文法所產(chǎn)生的語言是相同的，但G為二義的，而G 是無二義的。4.2 上下文無關(guān)文法5）二義文法（二

20、義文法改造為無二義文法）GE: E i GE：E T|E+TE E+E T F|T*FE E*E F （E）|iE (E) 規(guī)定優(yōu)先順序和結(jié)合律二義文法改造為無二義文法 如果產(chǎn)生上下文無關(guān)語言的每一個(gè)文法都是二義的，則說此語言是先天二義的。對(duì)于一個(gè)程序設(shè)計(jì)語言來說，常常希望它的文法是無二義的，因?yàn)橄Ｍ麑?duì)它的每個(gè)語句的分析是唯一的。4.2 上下文無關(guān)文法6）文法分析算法1) 令S_Lambda=Aj|Aj ；確定可推導(dǎo)出空串的非終極符對(duì)每個(gè)產(chǎn)生式p:Ap X1Xn,若X1Xn S_Lambda,則Ap并入S_Lambda；重復(fù)第2）步，直到S_Lambda收斂，此時(shí)的S_Lambda即為可推導(dǎo)出

21、空串的非終極符集。問題：哪些非終極符可以推導(dǎo)出空串？A + 例16：文法GS：SAa|bB|c AAa|bB| BAB|b|c S_Lambda=A4.2 上下文無關(guān)文法6）文法分析算法（續(xù)）First()=a VT| *a (if * then else )First集注：表示符號(hào)串，可以為非終極符和終極符組成的任意串，即 （VN VT） *。例17：文法GS：SaA|Bb|c AAa|bB| |B BaB|b|c First(S)=a, c, b, First(A)=b,a,c,First(B)=a,b,c4.2 上下文無關(guān)文法6）文法分析算法（續(xù)）Follow(A)=a VT|S *Aa

22、 (if S*A then # else )注：A為非終極符，即A VN 。Follow集例18：文法GS：SaA|Bb|c AAa|bB| |B BaB|b|c Follow(A)=#,a, Follow(B)=b,#4.2 上下文無關(guān)文法6）文法分析算法（續(xù)）Predict(A )=First() ，當(dāng)First()不含時(shí)First()- Follow(A),當(dāng)First()包含時(shí)注：A 為產(chǎn)生式。Predict集例19：文法GS：SaA|Bb|c AAa|bB| |B BaB|b|c Predict(BaB)=a, 因?yàn)镕irst(aB)=a Predict(AAa)=#, b,a,c,

23、 因?yàn)镕irst(Aa )=b,a,c, Follow(A)=#,a4.2 上下文無關(guān)文法7）語法分析方法（概述）語法分析的含義識(shí)別一個(gè)符號(hào)串是否為某文法的句型，是語法樹的構(gòu)造過程。在語言的編譯實(shí)現(xiàn)中，把完成句型分析的程序稱為分析程序或識(shí)別程序。分析算法又稱識(shí)別算法。從左到右的分析算法：即總是從左到右地識(shí)別輸入符號(hào)串，首先識(shí)別符號(hào)串中的最左符號(hào)，進(jìn)而依次識(shí)別右邊的一個(gè)符號(hào)，直到分析結(jié)束。例20：文法G：S cAd A ab A a識(shí)別輸入串w=cabd是否為該文法的句子4.2 上下文無關(guān)文法7）語法分析方法（分類）自頂向下分析法：從文法的開始符號(hào)出發(fā)，反復(fù)使用文法的產(chǎn)生式，尋找與輸入符號(hào)串匹配

24、的推導(dǎo)。分析算法分類自底向上分析法：從輸入符號(hào)串開始，逐步進(jìn)行歸約，直至歸約到文法的開始符號(hào)。4.2 上下文無關(guān)文法自頂向下的分析方法語法樹的構(gòu)造過程例21：文法G：S cAd A ab A a識(shí)別輸入串w=cabd是否為該文法的句子S S S c A d c A d a b推導(dǎo)過程：S cAd cAd cabd 7）語法分析方法（自頂向下分析方法）要點(diǎn)：由根向下構(gòu)造語法樹構(gòu)造最左推導(dǎo)推導(dǎo)出的終結(jié)符是否與當(dāng)前輸入符匹配 S ABA aA | B b | bBaaab.S AB S AB aAB A aA aaAB A aA aaaAB A aA aaa B A aaab B b4.2 上下文無

25、關(guān)文法7）語法分析方法（自頂向下分析方法要點(diǎn)） S aaab A B a A b a A a4.2 上下文無關(guān)文法例22：文法G： S cAd A ab A a識(shí)別輸入串w=cabd是否該文法的句子自底向上的分析方法語法樹的構(gòu)造過程SAA c a b d c a b d c a b d 規(guī)約過程構(gòu)造的推導(dǎo)： cAd cabd S cAd7）語法分析方法（自底向上分析方法）4.2 上下文無關(guān)文法兩種方法反映了兩種語法樹的構(gòu)造過程自頂而下方法是從文法符號(hào)開始，將它做為語法樹的根，向下逐步建立語法樹，使語法樹的結(jié)果正好是輸入符號(hào)串。自底而上方法則是從輸入符號(hào)串開始，以它做為語法樹的結(jié)果，自底向上地構(gòu)

26、造語法樹。7）語法分析方法（可能遇到的問題）4.2 上下文無關(guān)文法自頂向下的分析方法可能遇到的問題若S cAd 后選擇(3)，則得到S cAd cad那將會(huì)？ w的第二個(gè)符號(hào)可以與葉子結(jié)點(diǎn)a得以匹配，但第三個(gè)符號(hào)卻不能與下一葉子結(jié)點(diǎn)d匹配？宣告分析失?。ㄆ湟馕吨?，識(shí)別程序不能為串cad構(gòu)造語法樹，即cad不是句子）-顯然是錯(cuò)誤的結(jié)論。導(dǎo)致失敗的原因是在分析中對(duì)A的選擇不是正確的。 S c A d a7）語法分析方法（續(xù)）4.2 上下文無關(guān)文法對(duì)串cabd的分析中，如果不是選擇ab用產(chǎn)生式(2),而是選擇a用產(chǎn)生式(3)將a歸約到了A，那么最終就達(dá)不到歸約到S的結(jié)果，因而也無從知道cabd是一個(gè)

27、句子。自底向上的分析方法可能遇到的問題c a b dc A b d a7）語法分析方法（可能遇到的問題）4.3 遞歸下降法自頂向下分析1）遞歸下降法分析原理遞歸下降法的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：簡單，易于實(shí)現(xiàn)，可自動(dòng)生成。缺點(diǎn)：1）頻繁調(diào)用子程序，降低分析速度。2）對(duì)文法限制較嚴(yán)格。遞歸下降法的原理對(duì)非終極符，按其產(chǎn)生式結(jié)構(gòu)產(chǎn)生相應(yīng)的語法子程序，對(duì)其中的終極符：產(chǎn)生匹配命令，對(duì)其中的非終極符，產(chǎn)生調(diào)用命令。子程序結(jié)構(gòu)與文法的產(chǎn)生式結(jié)構(gòu)幾乎是一致的，文法遞歸則子程序也遞歸，所以稱該方法為遞歸下降法。4.3 遞歸下降法自頂向下分析1）遞歸下降法分析原理(續(xù))遞歸下降法示例一例23：文法G： VN =Stm,Ex

28、p VT =while,do P=Stm while Exp do Stm S=Stm對(duì)應(yīng)語法分析程序可如下：begin Match(#while); Exp; Match(#do); Stm end4.3 遞歸下降法自頂向下分析1）遞歸下降法分析原理（續(xù)）遞歸下降法示例二例24：文法G： VN =Z，B VT =a,b,c P=Z aBa, B bB|c S= Z對(duì)應(yīng)語法分析程序可如下： procedure Z;begin Match(a) end procedure B;begin case token of b:begin Match(b);B end; c:begin Match(c)

29、; end; -:Error() end; begin ReadToken; Z end 4.3 遞歸下降法自頂向下分析1）遞歸下降法分析原理（續(xù)）遞歸下降法要考慮的主要問題1.當(dāng)一非終極符有多個(gè)產(chǎn)生式時(shí)，如何保證唯一地確定其中一個(gè)產(chǎn)生式？2.如果非終極符有空產(chǎn)生式（ A ），怎么辦？例25：文法G： S cAd A ab A a A 識(shí)別輸入串w=cabd是否該文法的句子4.3 遞歸下降法自頂向下分析1）遞歸下降法分析原理（續(xù)）解決辦法1.對(duì)文法進(jìn)行限制，使得對(duì)每一個(gè)輸入符，文法最多有一個(gè)產(chǎn)生式被選擇。此時(shí)每個(gè)非終極符全部產(chǎn)生式滿足條件：Predict(Ak) Predict(Aj) 2.對(duì)

30、于當(dāng)前輸入符a，選擇產(chǎn)生式A k的條件是：a Predict(Ak) 例26：文法G： S cAd A ab A a A 識(shí)別輸入串w=cabd是否該文法的句子例27：文法G： S cAd A ab A b A 識(shí)別輸入串w=cabd是否該文法的句子4.3 遞歸下降法自頂向下分析1）遞歸下降法分析原理（續(xù)）遞歸下降分析法的條件遞歸下降法對(duì)文法有一定要求，即，每個(gè)非終極符全部產(chǎn)生式滿足條件：Predict(Ak) Predict(Aj) 其中Ak與A j是A的任意兩條產(chǎn)生式實(shí)際程序設(shè)計(jì)語言中，文法不滿足上述條件的主要有兩種情形：1.某個(gè)非終極符A有如下產(chǎn)生式： A ，A 即有公共前綴。2.某個(gè)非

31、終極符A有如下產(chǎn)生式： A A，即有直接左遞歸。怎么辦？消除公共前綴，消除左遞歸。4.3 遞歸下降法自頂向下分析2）消除公共前綴消除公共前綴的步驟A ，A A （）A AA 4.3 遞歸下降法自頂向下分析2）消除公共前綴消除公共前綴例子例28：文法GStm： Stm id:=Exp Stm id(ExpL) ExpL Exp ExpL Exp,ExpL消除公共前綴后為： Stm id Stm Stm :=Exp Stm (ExpL) ExpL Exp ExpL ExpL ,ExpL ExpL 4.3 遞歸下降法自頂向下分析3）消除左遞歸消除直接左遞歸的步驟A A，非，不以P打頭A A，A A|

32、 4.3 遞歸下降法自頂向下分析2）消除左遞歸（續(xù)）消除直接左遞歸的例子例29 已知GE： E T*F | T/F | F T F | T*F | T/F 解：左遞歸改為右遞歸得： E T*F | T/F | F T FT T *FT | /FT | 4.3 遞歸下降法自頂向下分析2）消除左遞歸（續(xù)）1.把G的非終結(jié)符整理成某種順序A1，A2，An ，使得： A1 1|2|k A2 A1 r A3 A2u | A1v. . 2. For i:=1 to n do begin for j :=1 to i-1 do 把每個(gè)形如AiAjr的規(guī)則替換成 Ai (1|2|k) r 其中Aj 1|2|k

33、是當(dāng)前全部Aj 的規(guī)則 消除Ai規(guī)則中的直接左遞歸 end 3.化簡由2得到的文法即可。間接左遞歸直接左遞歸消除直接左遞歸消除一般左遞歸步驟4.4 LL分析方法自頂向下分析1）概述 LL（k）分析方法是自頂向下分析方法LL（k）是一類分析方法，其中的k表示向前看k個(gè)符號(hào)的意思。我們重點(diǎn)學(xué)習(xí)LL（1）分析方法。 LL（1）方法是遞歸下降法的區(qū)別1.遞歸下降法對(duì)每個(gè)非終極符產(chǎn)生子程序，而LL（1）方法產(chǎn)生LL分析表。2.遞歸下降法能判斷每個(gè)產(chǎn)生式的結(jié)束，而LL（1）方法不能。3.遞歸下降法不用符號(hào)棧，而LL（1）方法用符號(hào)棧。4.4 LL分析方法自頂向下分析2）LL（1）文法 LL（1）分析方法的

34、焦點(diǎn)問題在LL（1）分析方法中，每當(dāng)在符號(hào)棧的棧頂出現(xiàn)非終極符時(shí)，要決定用哪個(gè)產(chǎn)生式的右部進(jìn)行該非終極符的替換。 LL（1）文法對(duì)文法G，如果G中任意非終極符A，其任意兩個(gè)產(chǎn)生式都滿足如下條件：Predict(Ak) Predict(Aj) 則稱文法G為LL（1）文法。如果文法G中沒有空產(chǎn)生式，則要求G中任意非終極符A，其任意兩個(gè)產(chǎn)生式的右部都滿足條件：First(k) First(j) 4.4 LL分析方法自頂向下分析3）LL（1）分析表 LL（1）分析表構(gòu)造方法1.對(duì)文法G的每個(gè)產(chǎn)生式 執(zhí)行第二步和第三步；2.對(duì)每個(gè)終結(jié)符aFIRST()，把 加至A,a中；3.若 FIRST()，則對(duì)任何bFOLLOW(A)把 加至A,b中；4.把所有無定義的A,a標(biāo)上“出錯(cuò)標(biāo)志”。注：可以證明，一個(gè)文法G