【文章內(nèi)容簡(jiǎn)介】 導(dǎo)的步步展開之間的完全一致性。但是，一個(gè)句型是否只對(duì)應(yīng)唯一的一棵語(yǔ)法樹呢?也就是，它是否只有唯一的一個(gè)最左(最右)推導(dǎo)呢?不盡然。 形式語(yǔ)言鳥瞰 前面喬姆斯基把文法分成四種類型，即0型，1型，2型，和3型。0型強(qiáng)于1型，1型強(qiáng)于2型，2型強(qiáng)于3型。這幾類文法的差別在于對(duì)產(chǎn)生式施加不同的限制。 0型文法：也稱短語(yǔ)文法，其能力相當(dāng)于圖靈機(jī)。任何0型語(yǔ)言都是遞歸可枚舉的，反之，遞歸可枚舉集必定是一個(gè)0型語(yǔ)言。 1型文法：也稱上下文有關(guān)文法，對(duì)非終結(jié)符進(jìn)行替換時(shí)務(wù)必聯(lián)系上下文，并且一般不允許替換成空串。 2型文法：也稱上下文無(wú)關(guān)文法 3型文法：也稱右線性文法，這類文法等價(jià)于正規(guī)式，所以也稱正規(guī)文法。只有下面兩種形式的產(chǎn)生式：A→Ba 或A→a。： 若L(G1)=L(G2),則稱文法G1和G2是等價(jià)的例如：下列兩個(gè)文法是等價(jià)的G1[A]: A 0R A 01 R A1G2[A]：S 0S1 S 01因?yàn)長(zhǎng)(G1)=L(G2)={0n1n|n ≥1}定義：對(duì)文法進(jìn)行變換，使變換后的文法滿足某種要求并于原文法等價(jià)，這種變換成為文法的等價(jià)變換。、增廣文法定義：設(shè)文法G[S]={VN,VT,P,S}，構(gòu)造文法G’[S’]=(VN∪{S’},VT,P’,S’),其中，P’={A α|A α ∈P}∪{S’ S},顯然L(G)= L(G’)，稱G’為文法G的增廣文法。例：[Z]:Z →abZA|a A→b經(jīng)等價(jià)變換后可得到增廣文法G[A‘]: Z’ →Z Z →abZA|a A→b、提取左因子定義：若文法中有產(chǎn)生式P→δβ1|δβ2|…|δβn,則稱該文發(fā)含有左因子δ。其中P ∈VN ，β1，β2… βn ∈ (VN∪ VT)*。例：文法[S]: S →iEtS|iEtSeS|a E →b提取左因子該文法變?yōu)椋? G[S]: S →iEtSS’|a S’ →eS|ε E →b、消除左遞歸定義：若文法中存在推導(dǎo)：P 222。+ Pα,則稱該文法含有左遞歸。若存在產(chǎn)生式P 222。 Pα,則稱該文法含有直接左遞歸。若存在產(chǎn)生式P 222。 P1α，P1 222。P2β, ……,Pn1 222。Pnγ，Pn 222。 Pδ,則稱該文法含有間接左遞歸。其中P,P1, …,Pn ∈ VN, α, β, γ,δ ∈ (VN∪ VT)*。直接左遞歸的消除方法：假設(shè)非終結(jié)符P存在產(chǎn)生式P 222。Pα|β刪除左遞歸產(chǎn)生式P 222。Pα引入新的非終結(jié)符P’消除文法中的左遞歸，得： P 222。βP’ P’ 222。αP’|ε間接左遞歸的消除方法：將間接左遞歸轉(zhuǎn)化為直接左遞歸；消除直接左遞歸；化簡(jiǎn)文法，刪除含有從起始符號(hào)無(wú)法到達(dá)的非終結(jié)符的產(chǎn)生式最后，作為描述程序語(yǔ)言的上下文無(wú)關(guān)文法，我們對(duì)它有幾點(diǎn)限制。 （1）文法中不含任何下面形式的產(chǎn)生式： P→P因?yàn)檫@種產(chǎn)生式除了產(chǎn)生二義性外沒(méi)有任何用處。（2）每個(gè)非終結(jié)符P必須有用處。這一方面意味著，必須存在含P的句型；也就是，從開始符號(hào)出發(fā)，存在推導(dǎo) S222。*aPb. 另一方面意味著，必須存在終結(jié)符串g206。VT*,使得P222。+g；也就是，對(duì)于P不存在永不終結(jié)的回路。 我們以后所討論的文法均假定滿足上述兩條件。授課題目（教學(xué)章、節(jié)或主題）：第三章 語(yǔ)法分析——自上而下分析課時(shí)安排12授課時(shí)間 第4周 第36節(jié) 第6周 第16節(jié) 第7周 第12節(jié) 教學(xué)目的、要求（分掌握、熟悉、了解三個(gè)層次）：了解確定的自頂向下分析思想熟悉某些非LL（1）文法到LL（1）文法的等價(jià)變換掌握LL（1）文法的判別、確定的自頂向下分析方法教學(xué)重點(diǎn)和難點(diǎn)：語(yǔ)法分析器的功能、確定的自頂向下分析思想、LL（1）文法的判別、某些非LL（1）文法到LL（1）文法的等價(jià)變換、不確定的自頂向下分析思想、確定的自頂向下分析方法授課類型（請(qǐng)打√）：理論課254。 討論課□ 實(shí)驗(yàn)課254。 練習(xí)課254。 其他□教學(xué)方式（請(qǐng)打√）：講授254。 討論□ 示教□ 指導(dǎo)254。 其他□教學(xué)資源（請(qǐng)打√）：多媒體254。 模型□ 實(shí)物□ 掛圖□ 音像□ 其他□討論、思考題、作業(yè)：P81：1，2，4教學(xué)內(nèi)容第三章 語(yǔ)法分析——自上而下分析 語(yǔ)法分析器的功能 語(yǔ)法分析器：是這樣的一個(gè)程序，它將按文法的產(chǎn)生式，識(shí)別輸入符號(hào)串是否為一個(gè)句子。輸入串是指由單詞符號(hào)（文法的終結(jié)符）組成的有限序列。語(yǔ)法分析的方法：可大致分為兩類，一類是自下而上分析法，另一類是自上而下分析法。所謂自下而上分析法就是從輸入串開始，逐步進(jìn)行“歸約”，直至歸約到文法的開始符號(hào)。自上而下分析過(guò)程恰好與此相反，它從文法的開始符號(hào)出發(fā)，反復(fù)使用各種產(chǎn)生式，尋找“匹配”于輸入串的推導(dǎo)。 自上而下分析面臨的問(wèn)題 本節(jié)主要是通過(guò)例子使我們認(rèn)識(shí)到，作自上而下分析所遇到的主要困難是語(yǔ)法的左遞歸性使分析陷入無(wú)限循環(huán)；回溯的不確定性，要求我們將已經(jīng)完成工作推倒重來(lái)，為解決這些問(wèn)題我們要消除左遞歸和消除回溯。 LL(1)分析法 自上而下分析方法不允許文法含有任何左遞歸。為構(gòu)造不帶回溯的自上而下分析算法，首先要消除文法的左遞歸性，并找出克服回溯的充分必要條件。 左遞歸的消除 假定關(guān)于非終結(jié)符P的規(guī)則為 :P P|αβ 其中，每個(gè) 都不以P開頭，那么我們可以把P的規(guī)則改寫成如下的非直接左遞歸形式：p βp39。p39。 αp39。|ε(ε 為空字)這種形式和原來(lái)的形式是等價(jià)的，也就是說(shuō)，從P推出的符號(hào)串是相同的。 消除回溯、提左因子 我們首先來(lái)看一下在不得回溯的情況下對(duì)于文法有什么要求。前面已經(jīng)說(shuō)過(guò)，欲實(shí)行自上而下的分析，文法不得含左遞歸。令G是一個(gè)不含左遞歸的文法，對(duì)G 的所有的非終結(jié)符號(hào)的每個(gè)候選a定義它的終結(jié)首符集FIRST(a)為： FIRST(a)={a|a222。*a…,a206。VT}特別是，若a222。*ε，則規(guī)定ε206。FIRST(a)。換句話說(shuō)FIRST(a)是a的所有可能推導(dǎo)的開頭終結(jié)符或可能的ε。如果非終結(jié)符A的所有候選首符集兩兩不相交，即A的任何兩個(gè)不同的候選ai和aj FIRST(ai)199。FIRST(aj) = f那么，當(dāng)要求A匹配輸入串時(shí)，A 就能根據(jù)它所面臨的第一個(gè)輸入符號(hào)a，準(zhǔn)確地指派某個(gè)候選前去執(zhí)行任務(wù)。這個(gè)候選就是那個(gè)終結(jié)首符集含a的a。如何把一個(gè)文法改造成任何終結(jié)首符集的所有候選首符集兩兩不相交呢？其辦法是提取公共左因子。例如，假定關(guān)于A 的規(guī)則是 A174。db1|db2|…|dbn|g1|g2|… |gm （其中每個(gè)g不以d開頭）那么，可以把這些規(guī)則改寫成：A174。dA’|g1|g2|… |gmA’174。|b1|b2|…|bn LL(1)分析條件 假定S是文法G的開始符號(hào)，對(duì)于任何非終結(jié)符A我們定義： FOLLOW(A) = { a | S222。*…Aa…,a206。VT}特別是，若S222。*…A， 則規(guī)定206。FOLLOW(A). 也就是說(shuō)，F(xiàn)OLLOW(A)是所有句型中出現(xiàn)在緊接A之后的終結(jié)符或者‘’。判斷某給定文法是否為L(zhǎng)L(1)文法其條件為： （1）文法不含左遞歸。 （2）對(duì)于文法中每個(gè)非終結(jié)符A的各個(gè)產(chǎn)生式的候選首符集兩兩不相交。即，若 A174。a1 | a2 |…| an 則： FIRST(ai)199。FIRST(aj) = f（i185。j ） (3) 對(duì)文法中每一個(gè)終結(jié)符A，若它存在某個(gè)候選首符集包含ε，則 FIRST(A) 199。FLLOW(A)= f一個(gè)文法若滿足以上條件，則稱該文法G為L(zhǎng)L(1)文法 遞歸下降分析程序構(gòu)造 在不含左遞歸和每個(gè)非終結(jié)符的所有候選終結(jié)首符集都兩兩不相交的條件下，可能（僅是可能）構(gòu)造一個(gè)不帶回溯的自上而下分析程序. 文法如下：E TE’ E’ +TE’/εT FT’ T’ *FT’/εF （E）/i 當(dāng)一個(gè)文法滿足LL(1)條件時(shí)，我們就可以為它構(gòu)造一個(gè)不帶回溯的自上而下分析程序，這個(gè)分析程序是由一組遞歸過(guò)程組成的，每個(gè)過(guò)程對(duì)應(yīng)文法的一個(gè)非終結(jié)符。這樣的一個(gè)分析程序稱為遞歸下降分析器。 預(yù)測(cè)分析程序 用高級(jí)語(yǔ)言的遞歸過(guò)程描述遞歸下降分析器只有當(dāng)具有實(shí)現(xiàn)這種過(guò)程的編譯系統(tǒng)剛才有實(shí)際意義。實(shí)現(xiàn)LL(1)分析的另一種有效方法是使用一張分析表和一個(gè)棧進(jìn)行聯(lián)合控制。我們現(xiàn)在要介紹的預(yù)測(cè)分析程序就是屬于這種類型的LL(1)分析器 預(yù)測(cè)分析程序工作過(guò)程 預(yù)測(cè)分析程序的總控程序在任何時(shí)候都是按STACK棧頂符號(hào)X和當(dāng)前的輸入符號(hào)a行事的。 預(yù)測(cè)分析表的構(gòu)造 為了構(gòu)造預(yù)測(cè)分析表M，我們需要先構(gòu)造與文法G有關(guān)的集合FIRST和FOLLOW. 消除左遞歸和提取左因子將有助于獲得無(wú)多重定義的分析表M。 可以證明，一個(gè)文法G的預(yù)測(cè)分析表M不含多重定義入口，當(dāng)且僅當(dāng)該文法為L(zhǎng)L(1)的。 LL(1)分析中的錯(cuò)誤處理 我們以預(yù)測(cè)分析為例。在預(yù)測(cè)分析過(guò)程中，出現(xiàn)了下列兩種情況，則說(shuō)明遇到了語(yǔ)法錯(cuò)誤。(1)棧頂?shù)慕K結(jié)符與當(dāng)前的輸入符號(hào)不匹配。(2)非終結(jié)符A處于棧頂，面臨的輸入符號(hào)為a，但分析表M中的MIA，a]為空。發(fā)現(xiàn)錯(cuò)誤后，要盡快地從錯(cuò)誤中恢復(fù)過(guò)來(lái)，使分析能繼續(xù)進(jìn)行下去?；镜淖龇ň褪翘^(guò)輸入串中的一些符號(hào)直至遇到“同步符號(hào)”為止。這種做法的效果有賴于同步符號(hào)集的選擇。我們可以從以下幾個(gè)方面考慮同步符號(hào)集的選擇。(1)把FOLLOW(A)中的所有符號(hào)放人非終結(jié)符A的同步符號(hào)集。如果我們跳讀一些輸入符號(hào)直到出現(xiàn)FOLLOW(A)中的符號(hào)，把A從棧中彈出，這樣就可能使分析繼續(xù)下去。(2)對(duì)于非終結(jié)符A來(lái)說(shuō)，只用FOLLOW(A)作為它的同步符號(hào)集是不夠的。例如，如果分號(hào)作為語(yǔ)句的結(jié)束符(C語(yǔ)言中就是這樣的)，那么作為語(yǔ)句開頭的關(guān)鍵字就可能不在產(chǎn)生表達(dá)式的非終結(jié)符的FOLIDW集中。這樣，在一個(gè)賦值語(yǔ)句后少一個(gè)分號(hào)就可能導(dǎo)致作為下一語(yǔ)句開頭的關(guān)鍵字被跳過(guò)。(3)如果把FIRST(A)中的符號(hào)加入非終結(jié)符A的同步符號(hào)集，那么，當(dāng)FIRST(A)中的一個(gè)符號(hào)在輸人中出現(xiàn)時(shí)，可以根據(jù)A恢復(fù)語(yǔ)法分析。(4)如果一個(gè)非終結(jié)符產(chǎn)生空串，那么，推導(dǎo)6的產(chǎn)生式可以作為缺省的情況，這樣做可以推遲某些錯(cuò)誤檢查，但不能導(dǎo)致放棄一個(gè)錯(cuò)誤。這種方法減少在錯(cuò)誤恢復(fù)期間必須考慮的非終結(jié)符數(shù)。(5)如果不能匹配棧頂?shù)慕K結(jié)符號(hào)，一種簡(jiǎn)單的想法是彈出棧頂?shù)倪@個(gè)終結(jié)符號(hào)，并發(fā)出一條信息，說(shuō)明已經(jīng)插入這個(gè)終結(jié)符，繼續(xù)進(jìn)行語(yǔ)法分析。結(jié)果，這種方法使一個(gè)單詞符號(hào)的同步符號(hào)集包含所有其它單詞符號(hào)。授課題目（教學(xué)章、節(jié)或主題）：第三章 語(yǔ)法分析——自下而上分析課時(shí)安排16授課時(shí)間 第7周 第34節(jié)第8周 第14節(jié) 第9周 第14節(jié)第10周 第14節(jié)第11周 第12節(jié)教學(xué)目的、要求（分掌握、熟悉、了解三個(gè)層次）：熟悉自下而上分析思想了解算符優(yōu)先分析法掌握LR分析法教學(xué)重點(diǎn)和難點(diǎn)：自下而上分析思想、算符優(yōu)先分析法、LR分析法授課類型（請(qǐng)打√）：理論課254。 討論課□ 實(shí)驗(yàn)課254。 練習(xí)課254。 其他□教學(xué)方式（請(qǐng)打√）：講授254。 討論□ 示教□ 指導(dǎo)254。 其他□教學(xué)資源（請(qǐng)打√）：多媒體254。 模型□ 實(shí)物□ 掛圖□ 音像□ 其他□討論、思考題、作業(yè)：P133：1，2，3，5教學(xué)內(nèi)容第三章 語(yǔ)法分析程序自下而上分析所謂自下而上分析法就是從輸入串開始，逐步進(jìn)行“歸約”，直至歸約到文法的開始符號(hào)；或者說(shuō)從語(yǔ)法樹的末端開始，步步向上“歸約”，直到根結(jié)。 自下而上分析基本問(wèn)題 我們首先討論自下而上分析法的基本思想和基本概念 歸約 “移進(jìn)歸約”：用一個(gè)寄存符號(hào)的先進(jìn)后出棧，把輸入符號(hào)一個(gè)一個(gè)地移進(jìn)到棧里，當(dāng)棧頂形成某個(gè)產(chǎn)生式的一個(gè)候選式時(shí)，即把棧頂?shù)倪@一部分替換（歸約為）該產(chǎn)生式的左部符號(hào)。我們可用句柄來(lái)刻畫移進(jìn)—?dú)w約過(guò)程的“可歸約串”。 規(guī)范歸約簡(jiǎn)述 規(guī)范規(guī)約是關(guān)于α的一個(gè)最右推導(dǎo)的逆過(guò)程。因此，規(guī)范規(guī)約也稱最左規(guī)約。最右推導(dǎo)常被稱為規(guī)范推導(dǎo)。由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型。如果文法G是無(wú)二義的，那么規(guī)范推導(dǎo)的逆過(guò)程必是規(guī)范規(guī)約。 句柄：令G是一個(gè)文法，S是文法的開始符號(hào)，假定αβδ是文法G的一個(gè)句型，如果有S222。*αAδ且A222。＋β則稱β是句型αβδ相對(duì)于非終結(jié)符A的短語(yǔ)。特別是，如果有A222。β則稱β是句型αβδ相對(duì)于規(guī)則A174。b的直接短語(yǔ)。一個(gè)句型的最左直接短語(yǔ)稱為該句型的句柄。 符號(hào)棧的使用與語(yǔ)法樹的表示 在形式語(yǔ)言中，最右推導(dǎo)常被稱為規(guī)范推導(dǎo)。由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型。如果文法G是無(wú)二義的，那么，規(guī)范推導(dǎo)(最右推導(dǎo))的逆過(guò)程必是規(guī)范歸約(最左歸約)。請(qǐng)注意句柄的“最左”特征，這一點(diǎn)對(duì)于移進(jìn)—?dú)w約來(lái)說(shuō)是重要的。因?yàn)椋浔摹白钭笮浴焙头?hào)棧的棧頂兩者是相關(guān)的。對(duì)于規(guī)范句型來(lái)說(shuō)，句柄的后面不會(huì)出現(xiàn)非終結(jié)符I號(hào)(即，句柄的后面只能出現(xiàn)終結(jié)符)?；谶@一點(diǎn)，我們可用句柄來(lái)刻畫移進(jìn)—?dú)w約過(guò)程的“可歸約串”。因此，規(guī)范歸約的實(shí)質(zhì)是，在移進(jìn)過(guò)程中，當(dāng)發(fā)現(xiàn)棧頂呈現(xiàn)句柄時(shí)就用