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