編譯原理教案(編輯修改稿)

　

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