浙大軟院資料-浙大編譯原理提綱

編譯原理（復習）考試情況：一、開卷考試二、題型：1、判斷題：20分，10題2、選擇題：15分，10題3、問答題（包括簡答題），65分，分值分布不均勻的。三、考試范圍：以課件內(nèi)容為主。主要復習內(nèi)容：一、介紹（對應第一章）1.什么是編譯程序：將一種語言翻譯為另一種語言的計算機程序。2、編譯程序的基本結構，每個部分的簡單介紹。詞法分析（自動生成，LEX的應用）（對應第三章）1、詞法分析程序： 自動生成。 給出一組關于單詞的正規(guī)式描述，生成表驅動的詞法分析器。正規(guī)表達式→有限狀態(tài)自動機→生成表驅動的詞法分析程序輸入緩沖區(qū)2、正規(guī)表達式：正規(guī)表達式的操作：鏈接，乘方Xn=X·X·X·····X閉包*：L*=L0UL1UL2UL3U·····,L0={ε}正則閉包+：L+=L1UL2UL3U·····選擇操作：|3、有限自動機：識別由正規(guī)表達式描述的單詞DFA,NFA正規(guī)表達式→ NFA→DFA（確定化，最小化）利用lex自動生成掃描程序lex的源程序：文件一般格式：{定義}%%{規(guī)則}%%{用戶程序}定義段：可選，包括一些定義，C代碼要放在%{和%}之間。規(guī)則段：具有如下的形式，動作是一個C語言的語句，或由{及}括起來的一串C語言程序段。正則表達式動作用戶程序段：在規(guī)則段中要用到的一些函數(shù)或子程序等。 語法分析(對應第四章) 上下文無關文法與分析1、基本概念與定義： 左部→右部 上下文無關文法G是一個四元組G=（VN，VT，P，S） VN：非終結符集合 VT：終結符集合 P：A→α的集合，A∈VN，α∈（VN∪VT）* S：開始符號推導、由文法定義的語言與分析樹（抽象語法樹）最右推導，最左推導 3、文法的二義性：若一個句子有二棵以上的分析樹，則該文法稱為二義文法（或歧義文法）二義性的消除4、消除左遞歸和提取左因子：對文法做的修改 消除左遞歸：A→Aα┃β A→βA’ A’→αA’┃ε自頂向下的分析遞歸下降的分析算法FIRST集與FOLLOW集的計算LL（1）分析LL（1）文法定義，LL（1）的含義 LL（1）的分析算法（步驟）構造LL（1）分析表滿足什么條件，該文法是LL（1）文法。6、LL（1）文法的構造，如何把一非LL（1）文法轉換為LL（1）文法提取左公因子法、消除左遞歸。（消除二義性）7、錯誤恢復技術LR分析（自底向上的分析）1、什么是LR分析？LR（1）的含義，什么是句柄。自下而上的分析過程：移進、歸約、接受、出錯。LR分析算法LR（0）文法、SLR（1）文法、LR（1）文法、LALR（1）文法的定義。（LR狀態(tài)機和LR分析表。）滿足什么條件，該文法是LR（1）文法等。如何利用二義文法LALR（1）分析器的自動生成工具：YACC的使用YACC如何利用歧義文法，沖突的消除等等。自底向上的錯誤校正語法制導下的翻譯（對應第五章）語法制導定義，繼承屬性，綜合屬性SDD，屬性計算，依賴圖，S屬性定義，L屬性定義，語法制導翻譯的應用SDT，實現(xiàn)L屬性的SDD中間代碼生成（對應第六章）語法樹的變化中間代碼的形式（三地址碼，四元組，三元組）類型和聲明表達式的翻譯，數(shù)組元素的翻譯，類型檢查，控制流語句的翻譯，避免多余的goto,布兒表達式和跳轉語句的翻譯，地址的回填，switch語句的餓翻譯，過程調(diào)用的翻譯運行環(huán)境