編譯原理教案-文庫吧在線文庫

　　

【正文】 部分編譯程序或整個編譯程序的有效工具。 現在，有些編譯程序是通過“移植”得到的。 討論□ 示教□ 指導254。運算符可采用一符一種的分法，但也可以把具有一定共性的算符（如所有關系符）視為一種。詞法分析的工作（單詞符號的識別）可以直接在這個緩沖區中進行。這里就需要用到超前搜索。若輸入字符Y，則讀進Y，并轉換到狀態3。3. GETCHAR 子程序過程，把下一個輸入字符讀到CHAR中，把搜索指示器前移一字節位置。6. LETTER和DIGIT布爾函數過程，它們分別CHAR中的字符是否為字母和數字，從爾給出真值TRUE或假值FALSE。 上的正規式，它們所表示的正規集分別記為L（U）和L（V），那么，（U V）、（U|V）和（U）*也都是正規式，它們所表示的正規集分別為L（U）200。意味著：當現行狀態為s，輸入字符a時，將轉換到下一狀態s39。若 M的初態結同時又是終態結， 則空字ε可為M所識別（或接受）。（2） 對每一個FA M，都存在一個右線性正規文法GR或左線性正規文法GL，使得L（M）＝L（GR）＝L（GL） 正規式與有限自動機的等價性 我們可以證明：（1） 對任何FA M，都存在一個正規式r，使得L（r）＝L（M）。一個產生式的 形式是 A174。”也用“：：＝”表示：這種表示方法也稱巴科斯范式。 討論課□ 實驗課□ 練習課254。一個上下文無關文法如何定義一個語言呢?其中心思想是，從文法的開始符號出發，反復連續使用產生式，對非終結符施行替換和展開。(E+E)。(i+i)。其中，He，me，book，gave，a等，稱為終結符號；句子、主語、謂語、動詞、代詞等，稱為非終結符號；這個文法最終是要定義句子的語法結構，所以句子在這里稱為開始符號；間接賓語冠詞名詞這種書寫形式稱為產生式。例如，“算術表達式”這個非終結符乃代表一定算術式組成的類。隨著推導的展開，當某個非終結符被它的某個候選式所替換時，這個非終結符的相應結就產生出下一代新結，候選式中自左至右的每個符號對應一個新結，并用這些符號標記其相應的新結。 形式語言鳥瞰 前面喬姆斯基把文法分成四種類型，即0型，1型，2型，和3型。： 若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}定義：對文法進行變換，使變換后的文法滿足某種要求并于原文法等價，這種變換成為文法的等價變換。若存在產生式P 222。Pα引入新的非終結符P’消除文法中的左遞歸，得： P 222。+g；也就是，對于P不存在永不終結的回路。 模型□ 實物□ 掛圖□ 音像□ 其他□討論、思考題、作業：P81：1，2，4教學內容第三章 語法分析——自上而下分析 語法分析器的功能 語法分析器：是這樣的一個程序，它將按文法的產生式，識別輸入符號串是否為一個句子。 左遞歸的消除 假定關于非終結符P的規則為 :P P|αβ 其中，每個 都不以P開頭，那么我們可以把P的規則改寫成如下的非直接左遞歸形式：p βp39。VT}特別是，若a222。例如，假定關于A 的規則是 A174。判斷某給定文法是否為LL(1)文法其條件為： （1）文法不含左遞歸。 預測分析程序 用高級語言的遞歸過程描述遞歸下降分析器只有當具有實現這種過程的編譯系統剛才有實際意義。(2)非終結符A處于棧頂，面臨的輸入符號為a，但分析表M中的MIA，a]為空。例如，如果分號作為語句的結束符(C語言中就是這樣的)，那么作為語句開頭的關鍵字就可能不在產生表達式的非終結符的FOLIDW集中。 討論課□ 實驗課254。 規范歸約簡述 規范規約是關于α的一個最右推導的逆過程。特別是，如果有A222。因為，句柄的“最左性”和符號棧的棧頂兩者是相關的。所謂算符優先分析就是定義算符之間(確切地說，終結符之間)的某種優先關系，借助于這種優先關系尋找“可歸約串”和進行歸約。…ab…或P174。+…a或R 222。b的終結符對。+…a或P222。b。FIRSTVT(Q)，且有產生式P174。 a IF Xi為非終結符而Xi+1為終結符THEN FOR LASTVT(Xi)中的每個a DO 置 a 優先函數 如果優先函數存在，那么，從優先表構造優先函數的一個簡單方法是：(1)對于每個終結符a(包括)令其對應兩個符號fa和ga，畫一張以所有符號f(a)和g(a)為結點的方向圖，如果a如果沒有矛盾，則f和g就是所要的優先函數。因而，可能會掩蓋輸入串的某些錯誤。GOTO[s，X]規定了狀態s面對文法符號X(終結符或非終結符)時下一狀態是什么。執行歸約動作意味著b(=Xm－r＋1…Xm)已呈現于棧頂而且是一個相對于A的句柄。(so，)為分析開始前預先放在棧里的初始狀態和句子括號。 構成識別一個文法活前綴的DFA的項目集（狀態）的全體稱為這個文法的LR(0)項目集規范族 為了使接受狀態易于識別，我們總是把文法G 進行拓廣。 是G 的拓廣文法。 SLR分析表的構造 SLR是LR(0)的一種改進，它在歸約時除了考慮歷史情況之外還考慮了一點現實。 Follow(A), b 207。α?，那么在狀態k時，只要面臨 輸入符號a 206。這就是LR(1)的方法。這是一條定理。 語法分析器的自動生成工具YACC YACC是一個編譯程序的編譯程序，借助它可以構造編譯程序。 模型□ 實物□ 掛圖□ 音像□ 其他□討論、思考題、作業：P217：1，4，7，9教學內容第四章 語法制導翻譯和中間代碼產生 屬性文法和語法制導翻譯屬性文法是在上下文無關文法的基礎上為每個文法符號（終結符或非終結符）配備若干個相關的“值”（稱為屬性）。因此，通常使用自底向上的方法在每一個結點處使用語義規則計算綜合屬性的值。這里要掌握依賴圖的畫法。 在自底向上的分析法中。表達式E的后綴形式可以如下定義：(1) 如果E是一個變量或常量，則E的后綴式是E自身。 三地址代碼三地址代碼可以看成是抽象語法樹或DAG的一種線性表示。相對地址是指對靜態數據區基址或活動記錄中局部數據區基址的一個偏移量。過程enter(name，type，offset)用來把名字name填入到符號表中，并給出此名字的類型type及在過程數據區中的相對地址offset。我們也可以按過程被說明的順序對過程編號，并把這一編號填入表頭。id：T的語義動作是將域名id的有關信息填入此記錄的符號表中。課本P179給出了把簡單算術表達式及賦值語句翻譯為三地址代碼的翻譯模式。： i*w + (base – low*w)其中：i*w 是隨數組下標變量而變化的部分 （base – low*w）是在數組中不變化的常數記為C對于多維數組中二維的情況尤其應注意：若二維數組A按行存放，則可用如下公式計算A[i1,i2]的相對地址： base + (( i1 – low1)*n2 + i1 – low2) *w其中，lowlow2分別為ii2的下界；n2是i2可取值得個數。對于非終結符號Elist引進綜合屬性arry，用來紀錄指向符號表中相應數組名字表項的指針。一般說來，把這些信息保存在相應的域名的符號表表項之中。也就是說域名info將可以在t所指向的符號表中查找。p 是一個指向某個記錄的指針，這個記錄有一個類型為算術型的域名info。一個Elist可以產生一個k 維數組引用A[i1,i2,…ik]的前m維下標，并將生成計算下面式子的三地址代碼。要生成數組的引用代碼，其主要問題是把常數C和變數V 的計算與數組引用的文法聯系起來。在相關的語義動作中，調用過程emit將生成的三地址語句發送到輸出文件中，我們可以重新解釋lookup操作，若采用最近嵌套作用域規則查找非局部名字，如Pascal語言中的那樣，此時前面的翻譯模式仍是可用的。、類型及域寬等。參數newtable指向過程name的符號表。另一過程partition是在quicksort中被說明，因此它的符號表有指針指向quicksort的符號表。 過程中的說明語句 在C、Pascal及FORTRAN等語言的語法中，允許在一個過程中的所有說明語句作為一個組來處理，把它們安排在一個數據區中。語句可以帶有符號標號，而且存在各種控制流語句。例如 abc+* 所代表的表達式是 a*(b+c)。X1X2…Xn其每個語義規則中的每個屬性或者是綜合屬性，或者是Xj(1=j=n)的一個繼承屬性且這個繼承屬性僅依賴于： （1）產生式Xj的左邊符號X1,X2,…Xj1的屬性 （2）A的繼承屬性。. 如果與產生式A174。 如果在一棵語法樹中一個結點的屬性b依賴于屬性c，那么這個結點處計算b的屬性規則必須在確定c的語義規則之后使用。簡單的說，綜合屬性用于“自下而上”傳遞信息，而繼承屬性用于“自上而下”傳遞信息。 練習課254。E+E | E*E |(E)| i (5．11) 采用附加條件之后，發生沖突的表元素就只留下了一種操作；在上面的規則中，我們是認為“*”的優先級大于“+”，若現在規則發生變化，認為“+” 的優先級大于“*”，那么對它的實現根本不需修改文法，只要處理沖突時改變一下就行。對于同一個文法，LALR分析表和SLR分析表永遠具有相同數目的狀態。因為可能沒有一個規范句型含有前綴βAa。α產生式歸約；3）若當前輸入符a 206。一般而言，對于任何形如I={X174。 的活前綴識別自動機中的每個狀態（項目集）不存在下述情況：（1）既含移進項目又含規約項目；（2）或者含有多個規約項目，則稱G是一個LR(0)文法。S，而這個S39。我們將把“歷史”和“展望”材料綜合地抽象成某些“狀態” LR（0）項目集族和 LR（0）分析表的構造 字的前綴是指字的任意首部。它的任何一步只需按棧頂狀態s和現行輸人符號a執行ACTION[s，a]所規定的動作。(2)歸約 指用某一產生式A174。 LR分析法 LR分析器的核心部分是一張分析表。b，則f(a)g(b)；若ab，就畫一條從gb到fa的箭弧。N是指那樣一個產生式的左部符號，此產生式的右部和S[j＋1]…S[k]構成如下一一對應關系：自左至右，終結符對終結符，非終結符對非終結符，而且對應的終結符相同。其算法如下： FOR 每一條產生式P174。按定義，我們可用下面兩條規則來構造集合FIRSTVT(P):(1)若有產生式P174。和+a…或P222。b, a+b…或R 222。 算符優先分析文法及其優先表構造 一個文法，如果它的任何產生式的右部都不含兩個相繼（并列）的非終結符，即不含如下形式的產生式右部： …QR… 則我們稱該文法為算符文法。 算符優先分析法 現在，我們來討論一種簡單直觀、廣為使用的自下而上分析法，叫做算符優先分析法。 符號棧的使用與語法樹的表示 在形式語言中，最右推導常被稱為規范推導。如果文法G是無二義的，那么規范推導的逆過程必是規范規約。 其他□教學資源（請打√）：多媒體254。這種方法減少在錯誤恢復期間必須考慮的非終結符數。我們可以從以下幾個方面考慮同步符號集的選擇。 可以證明，一個文法G的預測分析表M不含多重定義入口，當且僅當該文法為LL(1)的。FIRST(aj) = f（i185。*…Aa…,a206。如果非終結符A的所有候選首符集兩兩不相交，即A的任何兩個不同的候選ai和aj FIRST(ai)199。 消除回溯、提左因子 我們首先來看一下在不得回溯的情況下對于文法有什么要求。自上而下分析過程恰好與此相反，它從文法的開始符號出發，反復使用各種產生式，尋找“匹配”于輸入串的推導。 練習課254。（2）每個非終結符P必須有用處。 Pδ,則稱該文法含有間接左遞歸。例：文法[S]: S →iEtS|iEtSeS|a E →b提取左因子該文法變為： G[S]: S →iEtSS’|a S’ →eS|ε E →b、消除左遞歸定義：若文法中存在推導：P 222。任何0型語言都是遞歸可枚舉的，反之，遞歸可枚舉集必定是一個0型語言。 語法樹這就是說，一棵語法樹表示了一個句型種種可能的(但未必是所有的)不同推導過程，包括最左(最右)推導。 語法分析樹與二義性 前面我們提到過可以用一張圖表示一個句型的推導，這種表示稱為語法分析樹，或簡稱為語法樹。句子主語謂語形容詞名詞動詞賓語形容詞名詞 hegavemeabook非終結符號(也稱語法變量)用來代表語法范疇?！竷H推導一步的意思。(E+E)。與前面一樣，我們用‘222。 模型□ 實物□ 掛圖□ 音像□ 其他□討論、思考題、作業：P36：6，8，11教學內容 上下文無關文法 箭頭‘’讀為“定義為”，直豎‘|’讀為“或”，它們是元語言符號。有些能用于自動產生掃描器(如LEX)，有些可用于自動產生語法分析器(如YACC)，有些甚至可用來自動產生整個的編譯程序。產生式是用來定義語法范疇的。 詞法分析器的自動產生 教學目的：使用狀態轉換圖構造詞法分析程序；上機實踐LEX的實現。