《編譯原理》復習緒論主要內容：翻譯、編譯、目標語言和源語言這幾個概念的理解。編譯的總體過程：詞法分析，語法分析、語義分析與中間代碼的生成、代碼優化、目標代碼的生成，以及伴隨著整個過程的表格管理與出錯處理。思考：編譯過程主要包括五個階段，每個階段的主要任務是什么？編譯程序是否都需要實現這五個階段？（不需要，只有詞法分析、語法分析、語義分析和目標代碼生成是必要的，而中間代碼生成和代碼優化并不是必須的。）編譯方式與解釋方式有什么異同？編譯方式和解釋方式都對源程序進行了翻譯，只是前者相當于實際生活中的筆譯，而后者相當于口譯。雖然有些解釋程序對源程序進行了某些形式上的轉換，但最終并沒有生成目標代碼。因此兩者的根本區別在于是否生成目標代碼，而不是是否進行了翻譯。文法和語言主要內容：與文法相關的概念：字母表，符號及符號串、閉包和正閉包，連接，空集，產生式，推導，直接推導，歸約，句子，句型，句柄，，語法樹，語言，最左推導，最右推導（規范推導），文法的遞歸等。文法的定義：文法是一個四元組：（終結符號集，非終結符號集，開始符號、產生式集）。用文法來描述語言及通過文法能分析該文法所描述的語言。二義性的概念、能通過畫語法樹來分析一個文法描述的語言是否具有二義性。Chomsky對文法和所對應語言的分類。特別是上下文無關文法的定義和正規文法的定義。能判斷一個語言的文法是哪一類文法。思考：已知文法G1=({A,B,C},{a,b,c},P,A)，其中P由以下產生式組成：A→abcA→aBbcBb→bBBc→CbccbC→CbaC→aaBaC→aa此文法所表示的語言是什么？此文法所描述的語言是{anbncn|n>0}。構造描述語言L(G[S])={(n)n|n≥0}的文法。過程：（1）找出該語言的一些典型的句子。（2）分析句子的特點。（3）湊規則。（4）寫文法。（5）驗證。最后構造的文法是G[S]:S→(S)|ε構造描述某種子語言，比如十進制帶符號的整常數、C語言的標識符等的文法。設有文法G[S]:S→a|ε|(T)T→T,S|S給出句子(a,(a,a))的最左、最右推導。已知文法G[E]:E→T|E+T|E-TT→F|T*F|T/FF→(E)|i該文法的開始符號（識別符號）是什么？給出該文法的終結符號集合VT和非終結符號集合VN。找出句型T+T*F+i的所有短語、直接短語和句柄。消除該文法的直接左遞歸。判別一個文法是否有二義性？可以采用什么方法消除二義性？在語法分析中，是否必須消除二義性文法？詞法分析主要內容：詞法分析程序的任務。單詞的類別和單詞的輸出形式。程序語言中單詞符號的分類：比如關鍵字、標識符、常數、運算符、界符。正規集與正規式,正規式的遞歸定義。DFA是一個五元組：（狀態、字母表、唯一初態、映射關系、終態集）。DFA的表示形式：轉換矩陣、狀態轉換圖。狀態轉換圖的相關概念：狀態（結點）、初態、終態、接受（識別）。非確定有限自動機（NFA）的定義及NFA與DFA的區別。NFA到DFA的轉換：子集構造法（Subset）。DFA的化簡。由正規表達式構造確定的有窮自動機的步驟。由狀態轉換圖編寫詞法分析程序的步驟。1）畫出狀態轉換圖。2）將狀態轉換圖看作是通常的程序框圖，按如下方法寫出相應的詞法分析程序：對于狀態圖中的每一個狀態（代表一個非終結符）構造一段代碼，代碼的功能為從輸入串中讀一個字符；判明讀入的字符與由此狀態出發的哪條弧上的標記相匹配，便轉至相匹配的那條弧所指向的狀態；均不匹配時便失敗（不能正常出口）。具體構造程序時，對于不含回路的分叉結點，對應一個switch語句或一組if…then…else語句；含回路的結點，對應一個while和if語句構成的程序段；終態結點對應一個形如return(code,value)的語句，意為返回調用者。思考：如何求一個狀態子集的ε閉包？DFA和NFA的區別是什么？3、為正規式(a|b)*a(a|b)(a|b)構造DFA。4、設計一個DFA，其輸入字母表是{0,1}，接受以0開始以1結尾的所有序列。5、給出一個文法，寫出對應的詞法分析程序。第四章語法分析主要內容：語法分析器的功能。自上而下分析法自上而下分析法：從文法開始符號出發，自上而下地為輸入串建立一棵語法樹，或者說為輸入串尋找一個最左推導。自上而下分析面臨的問題：左遞歸（直接左遞歸和間接左遞歸）和回溯，如何解決？遞歸下降分析程序的設計思路。LL（1）分析法的基本思路。首字符集FIRST（A）及后跟字符集FOLLOW（A）的定義求某一文法中各文法符號的首字符集和后跟字符集LL（1）分析的條件：沿某一文法規則進行推導時，可能出現的下一個終結符是唯一的。在實際問題分析中要先求出各個文法符號的FIRST集及FOLLOW集，根據它們之間是否相交來判定是否滿足條件。預測分析程序的設計思路。預測分析表的構造方法。自下而上分析法自下而上分析法就是從輸入串開始，逐步進行“歸約”，直至歸約到文法的開始符號，從輸入串的語法樹上直觀地看就是沿著語法樹的底部向上分析歸約，最終能到達根結點的就認為當前的輸入串能被接受。大部分現代的編譯器都采用LR分析作為語法分析的方式。因此本章的學習重點是學習如何構造LR分析表。基本概念：移進、歸約、直接短語、句柄、規范歸約、規范推導、活前綴、項目集、項目集規范族等。語法分析棧的四個基本動作：移進，歸約，接受，出錯處理，各表示什么意義，具體如何完成。LR分析法的關鍵在于如何確定可歸約串？進一步如何識別可歸約串？由LR（0）的分析的實例理解LR分析的基本過程（即LR總控程序所完成的功能）。理解LR分析表中狀態、action、goto的含義。LR（0）項目集族和LR（0）分析表的構造方法。構造識別活前綴的DFA。SLR（1）是基于LR（0）進行優化而形成：通過向前看一個輸入字符來擴展LR分析的語法范圍。SLR（1）主要是為了解決什么問題？SLR（1）分析表的構造。思考：消除下列文法的左遞歸G[A]:A→Ba|Aa|cB→Bb|Ab|d設文法G[E]:E→T+E|T-E|TT→F*T|F/T|FF→(E)|i該文法能否直接應用自上而下分析技術來實現其識別程序？說明理由。設法為該文法構造LL(1)分析表，寫出構造過程。給出某個文法，求每一個非終結符號的FIRST集合FOLLOW集合。給出一個LR分析表，寫出對某個輸入串的“移進—歸約”的分析過程。LR(0)和SLR(1)分析表的主要區別。有文法G[S]：S→a|b|(T)T→T,S|S（1）試寫出產生式T→T,S的所有LR(0)項目。（2）構造CLOSURE({S→(.T)}),并寫出它的后繼項目集。已知文法G[A]：A→(A)|a構造該文法的以LR(0)項目集為狀態的識別活前綴的DFA。構造該文法的LR(0)分析表，該文法是LR(0)文法嗎？構造該文法的SLR(1)分析表，該文法是SLR(1)文法嗎？8、已知算術表達式文法G[E]:E→E+E|E*E|(E)|i（1）該文法是二義性文法嗎？說明理由。（2）若要對其進行語法分析，你準備如何進行處理？（3）若采用LR分析，試構造該文法的LR分析表。它是LR(0)文法嗎？它是SLR(1)文法嗎？若不是，如何解決？（提示：在不修該文法的情況下，考慮引入運算符的優先級和結合律來解決“移進—歸約”沖突。主要側重理解二義性文法的應用。）第五章語法制導翻譯和中間代碼的表示主要內容：語法制導翻譯的概念。屬性文法的相關基本概念：屬性，語義規則，綜合屬性，繼承屬性，屬性文法。屬性文法處理的一般過程：對單詞符號串進行語法分析，構造語法分析樹（注釋分析樹），然后構造屬性依賴圖，最后根據需要遍歷語法樹并在語法樹的各結點處按語義規則進行屬性的計算或其他處理。中間代碼的形式：逆波蘭式、三元式、四元式。思考：為什么要使用中間代碼形式？簡單臺式計算器的語法制導定義如下：L→En{Print(E.val)}E→E（1）+T{E.val:=E（1）.val+T.val}E→T{E.val:=T.val}T→T（1）*F{T.val:=T（1）.val′F.val}T→F