【正文】 導出e 注：對LL(1)文法進行語法分析時不會產(chǎn)生回溯。a，A174。S →… Aa…,a206。：判定是否為LL（1）文法首符號FIRST集：設G=（ VT ，VN，S，P）是上下文無關文法FIRST(a)={a| a →aβ,a206。如果能夠推導出，則該輸入串是給定文法的句子。 有窮自動機的狀態(tài)s和t不等價，則稱這兩個狀態(tài)是可區(qū)別的。NFA的確定化基本方法 基本方法:e邊合并 ,符號合并 (NFA轉(zhuǎn)化成的DFA不是唯一的) 【 例 】 NFA M如右圖所示，試將其確定化為DFA M39。）：DFA的表示（1）用轉(zhuǎn)換函數(shù)；（2）狀態(tài)轉(zhuǎn)換矩陣；（3）狀態(tài)轉(zhuǎn)換圖NFA與DFA的主要區(qū)別：允許有多個初始狀態(tài)。不可終止的：文法中那些不能從其推出終結(jié)符號串的非終結(jié)符。 句型i+i*i的語法樹有5棵子樹，短語和直接短語如下：直接短語：i1， i2 ， i3短語：i1，i2，i3，i1*i2，i1*i2+i3句柄：i1注意：i2+i3不是短語不是某棵子樹的結(jié)果：有害規(guī)則是指形為UU的產(chǎn)生式。句柄：一個句型的最左直接短語。 +β，則稱β是句型αβδ相對于非終結(jié)符A的短語。 a1|a2|…|an,那么如何確定用哪個產(chǎn)生式右部去替代A? ：自下而上分析法，是從輸入符號串開始，逐步進行歸約，直至歸約到文法的開始符號。如果一個文法存在某個句子對應兩棵不同的語法樹,或者說,若一個文法中存在某個句子,它有兩個不同的最左(最右)推導,則說這個文法是二義的. 如果產(chǎn)生上下文無關語言的每一個文法都是二義的，則說此語言是先天二義的。VT200。 a A,B 206。VN，b 206。 (VT200。a189。VN)*, a中至少有一個非終結(jié)符1型（上下文有關） ：189。：語言 L(G）是由文法G產(chǎn)生的所有句子所組成的集合。（VT，VN ,S, P ），其中： VT是一個非空有窮終結(jié)符號集合； VN是一個非空有窮的非終結(jié)符號集合， 且VT∩VN＝Φ； P是一個產(chǎn)生式的非空有窮集合（注意：產(chǎn)生式左部至少含有一個非終結(jié)符）； S206。 存儲區(qū)內(nèi)容：編譯方式翻譯和執(zhí)行分開，解釋方式翻譯和執(zhí)行同時并允許修改源程序，因此二者存儲組織不同。遍（PASS)：對輸入文件（源程序或其等價的中間語言程序）從頭到尾掃視，完成預定處理的過程。2. 前端和后端的概念，試問前端通常包括那些階段，后端包括那些階段？ 答：前端只依賴于源語言，與目標機無關。2） 語法分析：是在詞法分析基礎上將單詞序列分解成各類語法短語(比如程序、語句、表達式等），通過語法分析確定整個輸入串是否構(gòu)成一個語法上正確的程序。3） 語義分析：是審查源程序有無語義錯誤，為代碼生成階段收集類型信息。編譯程序的前端通常包括詞法分析程序、語法分析程序、語義分析程序、中間代碼生成程序及相關的表格管理程序和出錯處理程序。 一個多遍的編譯程序較之一遍的編譯程序可能少占內(nèi)存，邏輯結(jié)構(gòu)可能清晰些，但效率相對可能差點：結(jié)構(gòu)上的語法規(guī)則，語義上的語義規(guī)則。效率：解釋慢于編譯，很多語言兩種方式都有。 VN ，稱為開始符號，且S至少必須在某個產(chǎn)生式的左部出現(xiàn)一次 。5文法的類型：逐漸對產(chǎn)生式施加限制 四種類型：0型，1型，2型，3型0型：G=(VT,VN,S,P)，規(guī)則形式 ： b174。b189。,僅S e除外 規(guī)則形式 ： a A b 174。VN)*, ge185。 (VT200。VN （左線性） A174。{e}（最右）推導在推導的任何一步α222。：自上而下分析法,是從文法開始符號出發(fā),反復使用各種產(chǎn)生式,逐步進行推導，直至推導出輸入符號串。 過程：自下而上方法是從輸入符號串開始，以它作為語法樹的末端結(jié)點，自底向上地構(gòu)造語法樹，使語法樹的根結(jié)點正好是文法的開始符號。直接短語：若S222。（產(chǎn)生式的右部）：一棵語法樹中一個特有的結(jié)點連同它的全部后裔，連接這些后裔的邊以及這些結(jié)點的標記，稱為子樹。會引起文法二義性。第四章：詞法分析：從左至右逐個字符地對源程序進行掃描，產(chǎn)生一個個單詞序列，用以語法分析接口方式：（1）詞法分析工作可以組織成獨立的一遍,把字符流的源程序變?yōu)閱卧~序列，輸出在一個中間文件上，這個文件作為語法分析程序的輸入而繼續(xù)編譯過程。允許狀態(tài)在其輸出邊上有相同的符號(多值映射)?！窘獯稹浚?）用子集法將圖所示的NFA M確定化為表1。 ：r=s|txyN(t)N(s)eeeer=s*xyeeeeN(s)第五章：自頂向下語法分析方法求FIRST集，F(xiàn)OLLOW集LL（1）文法判定語法分析是編譯程序的核心部分：在詞法分析的基礎上，識別單詞符號序列是否是給定文法的正確句子（程序）。如果不能推導出，則該輸入串不是給定文法的句子。 VT, a ，β 206。 VT, A 206。β，滿足：Select(A174。(1)文法到LL(1)文法的等價變換:1. 提取左公因子2. 消除左遞歸（如果一個文法是左遞歸時，則不能采用自頂向下分析法。V* 直接左遞歸 ② A174。 V* 間接左遞歸(2)直接左遞歸的消除 （改為右遞歸）S174。b 形如： A → A a|β（a非e，β不以A打頭）改寫為： A →βA162。改寫為： A →b1 A162。 →a1 A162。E39。 → * F T39?；舅枷?：從左到右掃描源程序，直接根據(jù)：預測分析器構(gòu)成：預測分析程序，先進后出棧，預測分析表——與文法有關第七章:LR分析LR(0)分析表識別活前綴的DFA分析過程對輸入串的分析過程（已知文法的分析表）LR分析法：是一種規(guī)范規(guī)約過程LR(k)含義L ：從左到右掃描輸入符號R ：最右推導對應的最左歸約(反序完成最右推導)k ：超前讀入k個符號，以便確定歸約用的產(chǎn)生式LR(0)項目分類移進項目，形如A→a ? ab，a是終結(jié)符,a ,b 206。文法符號的屬性:單詞的含義，即與文法符號相關的一些信息。每個屬性與文法的一個終結(jié)符或非終結(jié)符相連。綜合屬性:若產(chǎn)生式左部的單非終結(jié)符A的屬性值由右部各非終結(jié)符的屬性值決定, 則A的屬性稱為綜合屬性。在計算時： 綜合屬性沿屬性語法樹向上傳遞；繼承屬性沿屬性語法樹向下傳遞。一般，快速編譯程序直接生成目標代碼。便于移植，便于修改，便于進行與機器無關的優(yōu)化。代碼區(qū)（code）靜態(tài)數(shù)據(jù)區(qū)（static data）：編譯時能確定所占用空間的數(shù)據(jù)。適用的分配對象：子程序的目標代碼段；全局數(shù)據(jù)目標（全局變量）靜態(tài)存儲分配的要求：不允許遞歸調(diào)用，不含有可變數(shù)組。 【例】在具有遞歸結(jié)構(gòu)的語言程序中，每當調(diào)用一個過程時，它所需的數(shù)據(jù)空間就分配在棧頂，每當過程工作結(jié)束時就釋放這部分空間。構(gòu)成臨時工作單元；局部變量；機器狀態(tài)信息；存取鏈；控制鏈；實參；返回地址第十一章：什么是代碼優(yōu)化所謂優(yōu)化，就是對代碼進行等價變換，使得變換后的代碼運行結(jié)果與變換前代碼運行結(jié)果相同，而運行速度加快或占用存儲空間減少。優(yōu)化分類：局部優(yōu)化，循