這是之前學習編譯原理過程中做下的筆記。
因能力有限，在很多地方都了解不到位，特别是對于詞法分析與文法分析的過程感覺特别晦澀。
分享這個筆記也是為了自己做個總結，算是一個小的提綱吧，都沒怎麼深入解析編譯的過程。
等以後領悟更多了再作補充吧。
希望各路人士能多加指點，謝謝。
詞法分析
作用：将輸入轉換為一個一個的token，而其用一串整數來表示。
協作：隻有當解析器需要的時候才會請求詞法分析器，繼續掃描輸入流，在這個過程中将不斷生成符号表。
實作：在通常的程式設計語言中，相對于不确定的有限自動機(NFA)，确定的有限自動機(DFA)中不會有過多的記号使得狀态數達到指數級。是以可以為每個NFA構造等價的DFA，而且最關鍵的是有限自動機的狀态數，而在沒有不确定狀态的情況下，就要求DFA将每個不确定的狀态轉換成從起始到終結狀态間的路徑，而這可能會導緻增加DFA的狀态數。而在多數情況下，設計NFA要簡單些，如可通過正規表達式建構，步驟是先分解正規表達式為簡單的子表達式，并構造相應的NFA，再通過正則的運算符組合他們。
文法分析
部分概念解析
移進-歸約(shift-reduce)解析器
其中有包括待解析短語的輸入流+存放終結符以及之前歸約産生的非終結符的堆棧。
移進操作等于将符号從輸入移動到堆棧中；
歸約操作則結合已完成的序列和最後移進的終結符形成堆棧中的非終結符；
算符文法
文法中的任一産生式規則右邊不存在“空”或者兩個連續出現的非終結符；
錯誤恢複
目前棧頂的終結符和輸入的下一個符号之間沒有任何優先關系：隻允許移進下一個輸入的字元，提前為優先表中的空白項指定恢複過程。
沒有任何産生式的右句型可以比對目前的句柄：從合法規則中選擇近似的值，再報告差異錯誤；
LR分析
LR分析器一直追蹤着句柄的活字首，并使用自動機來識别這些活字首，其中的一些工作呗goto部分模拟了，是以不需要掃描堆棧中的每個輸入字元來判斷目前的狀态，因為狀态始終都是在棧頂。
類型檢查
類型檢測
包括表達式，語句，函數；
第一次是關于操作數運算符的适用性；
第二次是檢查需要确定使用的變量的定義；
類型等價
名稱等價
結構等價：構造函數
類型轉換
當強制轉換類型時，隻是在那個局部轉換，原來的類型保持不變；
符号表
内容：名稱，類型，位置，作用域，其他屬性
嵌套的詞法作用域
每個作用域單獨一張表：堆棧/清單/樹/hash
單個全局表： 使用清單時需要額外的符号位來表示作用域；樹的話新符号都是在葉子端，删除也要周遊；hash存根節點；
當存放記錄項（對象）時，要通路記錄項（對象）的不同字段（屬性），如R.a和R.b可以通過包含a，b定義的符号表來通路；也可以将其看做R.a和R.b來通路；
運作時環境管理
活動記錄：參數空間，簿記(bookkeeping)資訊包括傳回位址，局部變量空間，局部臨時變量空間；
含有局部過程的環境：
通路變量的定義相對于目前的過程是局部的，是以要檢視嵌套過程的活動記錄來決定；
這可以通過通路鍊來解決；
首先計算出聲明和引用的兩個詞法嵌套層之間的差異d；
再沿着d的通路鍊到達正确的活動記錄；
通過偏移量來通路變量。
優化
而在搜尋通路鍊的時候，由于是虛拟的頁面環境，可能會因為頁面交換而變得十分緩慢，為了可以不搜尋，可以使用display。
display是活動記錄的全局指針數組，d[i]指向嵌套深度為i的代碼塊中最近的活動；
是以要通路非局部變量X，隻要最靠近X嵌套聲明的深度為i，則d[i]指向包含X的活動記錄，再根據相對位址就可以通路X了。
中間代碼生成
進階表示
抽象文法樹
有向非循環圖：公共子表達式由單個節點構成
P-代碼：用于基于堆棧的虛拟機
低級表示
三位址代碼
實作：四元組表示法
代碼生成：對于非終結符E，分别用不同屬性儲存E的值的名稱，和對應計算的三位址語句序列；
數組：一維:(base-low * w)+i * w;(w是每個元素的寬度)；二維：base+((i1 - low1) * n2 + i2 - low2) * w；
布爾類型：為解決兩階段生成代碼問題，引入truelist, falselist和相應creatlist(i), mergelist(list1,list2), backpatch(list,target)函數；
case：當分支數量較少時可使用線性查找/二分查找；多則使用轉移表，若分支值不緊密聚集，空間成本會更高；
函數調用
目标代碼生成
影響因素
輸入的比對程度，即中間代碼與目标代碼的映射程度；
目标代碼的結構：絕對代碼，可重定位，彙編；
指令集的選擇：CISC, RISC；
寄存器配置設定：資料+位址；
求值次序：使用寄存器的數目；
基本塊：程式的第一個語句；轉移目标；緊跟在轉移語句之後的語句；
寄存器配置設定
無向寄存器沖突圖；
圖着色；
k可着色圖：選取邊數少于k的節點t，将t壓棧并從圖中删除它和它的所有鄰接邊，重複直至所有節點删除；
k不可着色圖：
必須選擇節點溢出到記憶體，需要時再載入配置設定；
如何選取：沖突最大的；定義和使用很少的；盡量不在循環體内的；
使用動态規劃生成；
代碼優化
如果你需要轉載，請标注我的名字“AnnsShadoW”和本文位址：http://www.cnblogs.com/annsshadow/p/4986928.html，謝謝~