編譯原理知識點參考

1、第三章3.1 對于詞法分析器的要求1詞法詞法分析的任務：從左至右逐個字符地對源程序進行掃描，產生一個個單詞符號。詞法分析器(Lexical Analyzer) 又稱掃描器(Scanner)：執(zhí)行詞法分析的程序。2程序語言的單詞符號：關鍵字、標識符、常數、運算符、界符。3輸出的單詞符號的表示形式:(單詞種別，單詞自身的值)Eg：while (i>=j) i-;輸出單詞符號：< while, - >< (, - >< id, 指向i的符號表項的指針 >< >=, - >< id, 指向j的符號表項的指針 >< ), -

2、>< id, 指向i的符號表項的指針 >< -, - >< ;, - >4詞法分析器作為一個獨立子程序：結構簡潔、清晰和條理化，有利于集中考慮詞法分析一些枝節(jié)問題。5詞法分析器3.2 詞法分析器的設計1詞法分析器2輸入、預處理：輸入串放在輸入緩沖區(qū)中。預處理子程序：剔除無用的空白、跳格、回車和換行等編輯性字符;區(qū)分標號區(qū)、捻接續(xù)行和給出句末符等掃描緩沖區(qū)（指向開始位置，向前搜索確定終點）3單詞符號的識別、超前搜索：(1)基本字識別Eg：DO99K=1，10 DO 99 K = 1，10 IF(5.EQ.M)GOTO55 IF (5.EQ.M) GOTO

3、 55DO99K=1.10IF(5)=55需要超前搜索才能確定哪些是基本字(2)標識符(3)常數(4)算符和界符4狀態(tài)轉換圖(有限方向圖)<1>結點代表狀態(tài)<2>狀態(tài)之間用箭弧連結，箭弧上的標記(字符)代表射出結狀態(tài)下可能出現的輸入字符或字符類。<3>一個狀態(tài)轉換圖可用于識別(或接受)一定的字符串。5語法分析的狀態(tài)轉換圖6狀態(tài)轉換圖的實現思想：每個狀態(tài)結對應一小段程序。7狀態(tài)轉換圖實現(了解)1)ch 字符變量、存放最新讀入的源程序字符2)strToken 字符數組，存放構成單詞符號的字符串3)GetChar 子程序過程，把下一個字符讀入到 ch 中4)Ge

4、tBC 子程序過程，跳過空白符，直至 ch 中讀入一非空白符5)Concat 子程序，把ch中的字符連接到 strToken6)IsLetter和 IsDisgital 布爾函數，判斷ch中字符是否為字母和數字7) Reserve 整型函數，對于 strToken 中的字符串查找保留字表，若它是保留字則給出它的編碼，否則回送08) Retract 子程序，把搜索指針回調一個字符位置9)InsertId 整型函數，將strToken中的標識符插入符號表，返回符號表指針10)InsertConst 整型函數過程，將strToken中的常數插入常數表，返回常數表指針。8一個詞法分析器的例子(多看看、

5、了解吧)：int code, value;strToken := “ ”;/*置strToken為空串*/GetChar(); GetBC();if (IsLetter()beginwhile (IsLetter() or IsDigit()beginConcat(); GetChar(); endRetract();code := Reserve();if (code = 0)beginvalue := InsertId(strToken);return ($ID, value);endelsereturn (code, -);endelse if (IsDigit()beginwhile

6、(IsDigit()beginConcat( ); GetChar( );endRetract();value := InsertConst(strToken);return($INT, value);endelse if (ch =) return ($ASSIGN, -);else if (ch =+) return ($PLUS, -);else if (ch =*)beginGetChar();if (ch =*) return ($POWER, -);Retract(); return ($STAR, -);endelse if (ch =;) return ($SEMICOLON,

7、 -);else if (ch =() return ($LPAR, -);else if (ch =) return ($RPAR, -);else ProcError( );/* 錯誤處理*/3.3正規(guī)表達式和有限自動機1. 正規(guī)集與正規(guī)式a. 正規(guī)式與正規(guī)集的遞歸定義（見課本P46，47）b. 若兩個正規(guī)式所表示得正規(guī)集相同，則二者等價。2. 確定有限自動機（DFA）a. 確定有限自動機的定義。（課本P47）b. DFA可以表示為狀態(tài)轉換圖。假定DFA M含有m個狀態(tài)和n個輸入字符，那么，這個圖含有m個狀態(tài)結點，每個結點頂多含有n條箭弧射出，且每條箭弧用上的不同的輸入字符來作標記。c.

8、DFA M所識別的字的全體記為L(M)。d. 對于S*中的任何字a，若存在一條從初態(tài)到某一終態(tài)的道路，且這條路上所有弧上的標記符連接成的字等于a，則稱a為DFA M所識別(接收)3. 非確定有限自動機（NFA）a. 非確定有限自動機的定義。（課本P49）b. NFA 和DFA的區(qū)別： （1） 弧上的標記可以是S*中的一個字，而不一定是單個字符； （2 ）同一個字可能出現在同狀態(tài)射出的多條弧上。c. DFA是NFA的特例。d.替換規(guī)則（課本P50圖3.7）4. NFA向DFA的變換 課本P51例3.3，課后習題7，12(1)5. 確定有限自動機的化簡。具體步驟課本P56,57頁課后習題12（b）

9、考試的時候注意題目要求，如果沒有明確要求將DFA簡化，可不寫6. 正規(guī)文法與有限自動機得等價性，正規(guī)式與有限自動機的等價性。P51 P53 記住結論就可以，證明過程可以不看。第四章知識點總結：1，定義： 語法分析：在詞法分析分析出符號串單詞后，分析判定程序是否符合語法規(guī)則，在整個架構中起到承上啟下作用。（圖見第四張ppt第二頁） 自上而下語法分析：從文法的開始符號出發(fā)，向下推導，把句子推出。上下文無關文法的定義： 一個上下文無關文法G是一個四元式 G=(VT，VN，S，P)，其中VT：終結符集合(非空)VN：非終結符集合(非空)，且VT Ç VN=ÆS：文法的開始符號，S&

10、#206;VNP：產生式集合(有限)，每個產生式形式為開始符S至少必須在某個產生式的左部出現一次。2，自上而下語法分析基本思想： 它從文法的開始符號出發(fā)，反復使用各種產生式，尋找"匹配"的推導（簡單說就是看見類似的往上湊，發(fā)現后面錯誤了就回溯到出錯前的一步進行推導）3，消除左遞歸：（1） 假設文法中有這樣的規(guī)則：則判定該文法含有直接左遞歸，要消除它的辦法是：將式子右邊所有P打頭的候選式提取出來，把他們修改成P，P規(guī)則右邊候選式格式變?yōu)镻，并且添加空候選式。即，然后在原來P規(guī)則右邊每個終結符后添加P，即。（2） 間接左遞歸：如上述文法中S經過3步推到最終會得到Sabc的式子，

11、形成左遞歸，但是這個左遞歸并沒有直接顯示在某一個規(guī)則中，稱為間接左遞歸。要消除間接左遞歸就要求該文法：（1）沒有直接左遞歸；（2）不存在回路。消除一個文法所有左遞歸的算法在書上70頁。4，消除回溯（1）消除回溯關鍵在于保證：對文法每一個非終結符，都能在面對輸入符號時準確指派他的一個候選式去匹配輸入串，既不存在模棱兩可的選擇。（2）First集定義：對任意一個非終結符G，它的所有候選式的第一個終結符或空符號的集合。（3）消除回溯：如果消除后扔存在會導致回溯的候選式存在，就再進行一次提取，直到不存在回溯的候選式存在。5,ll（1）文法（1） follow集定義：緊跟在非終結符A后面的終結符首位或空

12、的集合，叫做A的follow集。（2） LL（1）文法分析條件：1，文法不含任何形式左遞歸，不含回溯；2，文法中每一個非終結符A對應的任意兩個個候選式，不妨設為j1與j2其首個終結符各不相同，即first（j1）first（j2）；3，文法中如果有非終結符假設為A其follow中含有空，則他的first集與follow集不能有交集即，first（A）follow（A）=。6，遞歸下降分析程序構造（自學）因為這部分內容重要性較低，稍微看看就好，ppt第四章56-75頁。7，預測分析程序（1） 對于first集的求法：對于任意一個非終結符A求他的first集時：1，對其候選式首字符進行一次掃描，把

13、其中的終結符或空加入集合；2，尋找剩下的非終結符的first集（即對非終結符進行第一步）加入集合。（2） 對于follow集求法：對于任意一個非終結符A求它的follow集時：1，若其在某一個候選式如AB或Ab中出現，則把其后面的終結符，或者非終結符的first集加入follow集中（若A后表達式可形成空，也歸入步驟2）；2，若其在形如E->A中出現則把follow（E）整個加入follow（A）中。（3） 預測分析表構造：在求出first集及follow集后，要構造預測分析表，其步驟為：ps：在手動運算中出錯標志可放空白為示。預測分析程序主控程序思想：見書上76-77頁。 第五章1.

14、小題· 歸約的基本思想（ppt第4張）· 自下而上語法分析器的四個動作（ppt第21張）· 關于可歸約串o 規(guī)范歸約：句柄（無求法）o 算符優(yōu)先文法：最左素短語o LR分析法：句柄（通過活前綴來求句柄）· 移進歸約過程存在的問題（ppt第27張）· 關于優(yōu)先函數o 優(yōu)先函數存在性不確定：不是所有的文法都存在優(yōu)先函數o 優(yōu)先函數唯一性不確定：存在優(yōu)先函數則必定不唯一· 關于LR分析法o LR的含義（ppt第83張）o LR的優(yōu)缺點（ppt第84張）o LR文法不是二義的，二義文法肯定不會是LR的。o 規(guī)范歸約的過程中棧內永遠不會出現句柄

15、之后的符號o 識別活前綴的本質就是識別句柄· 二義性和各種分析法的關系o 每個SLR(1)文法都是無二義的。但也存在許多無二義文法不是SLR(1)的.o LR文法不是二義的，二義文法肯定不會是LR的。· 關于LALR文法o 如果文法G是LALR(1)文法，則G可采用LALR(1)分析法。o 如果文法G是LALR(1)文法，則G是無二義性的。o 如果文法G是LALR(1)文法，則G一定是LR(1)。 · 關于小題部分，上述只是列出了考試概率比較大的幾個關鍵問題，并不能保證100%的概率，如果要保險一點的話請看第5章ppt的旁白部分。2. 大題· 關于規(guī)范歸

16、約o 求短語，直接短語，句柄o 寫出移進-歸約過程（ppt第25張）（第7章也會用）o 構造某輸入串的語法樹（ppt第26張）· 關于算符優(yōu)先o 判斷是否為算符優(yōu)先文法（課本133頁3題）o 求短語，素短語，最左素短語（ppt第59張）o 求FIRSTVT，LASTVT（ppt第52張）o 構造算符優(yōu)先表（ppt第52張）o 構造優(yōu)先函數（ppt第78張）o 應用算符優(yōu)先文法分析輸入串（ppt第67張）· 關于LR（0）o 求活前綴（ppt第101張）o 構造識別LR（0）活前綴的DFA（課本134頁5題（1）（2）§ 求文法的所有LR（0）項目§ 構造

17、文法的項目集規(guī)范族（包括GO函數和DFA兩種方法）o 判斷文法是否為LR（0）文法o 通過LR（0）的DFA構造LR（0）分析表（ppt123張）o 應用LR（0）分析法分析輸入串（ppt第126張）· 關于SLR（1）o 判斷文法是否SLR（1）文法（課本134頁5題（3）o 通過LR（0）和FOLLOW集構造SLR（1）分析表（ppt136張）o 通過SLR（1）分析法分析輸入串· 關于LR（1）o 構造識別LR（1）的DFA（ppt152張）o 判斷文法是否為LR（1）文法（課本134頁5題（4）o 通過LR（1）文法的DFA構造LR（1）分析表（ppt第154張）o

18、 應用LR（1）分析法分析輸入串（ppt第155張）· 關于LALR（1）o 通過LR（1）的DFA構造LALR（1）的DFA（ppt第163張）o 判斷文法是否為LALR（1）（課本134頁5題（4）o 通過LALR（1）的DFA構造LALR分析表（ppt第165張）o 應用LALR（1）分析法輸入串第六章屬性文法與語法制導翻譯屬性文法o 綜合屬性與繼承屬性定義 P136 o VT只有綜合屬性o 綜合屬性的值還可以依賴于自己o 樹 o 語法樹&帶注釋的語法樹(語法樹結點有值的計算)o 依賴圖(通過依賴圖看值是否可計算，是否為良定義的文法) § 虛擬屬性 P140o 樹遍歷的屬性計算方法 P143 § 能理解自上而下，從左向右§ 能判斷幾次掃描可完成o 抽象語法樹 P144 § 操作符和關鍵字不做為葉節(jié)點§ 與DAG的區(qū)別(DAG可以合并重復子樹)o s屬性文法 o 僅含有綜合屬性(因此自下而上)o 在LR分析基礎上，加上語義規(guī)則；在具體實現