- 編譯執(zhí)行和解釋執(zhí)行的區(qū)別
把計算機高級語言編寫的程序（源程序）翻譯成該計算機的匯編語言或機器語言書寫的程序（目標程序）的計算機程序稱為編譯器或編譯程序。
解釋程序是和編譯器類似的一種語言翻譯程序，與編譯器的不同之處在于它以源程序為輸入，在執(zhí)行過程中不產(chǎn)生目標程序，而是邊解釋邊執(zhí)行。邊解釋邊執(zhí)行工作效率低，可能需要重復(fù)翻譯和執(zhí)行語句，經(jīng)常用于執(zhí)行命令語言和交互式會話語言。 - 詞法分析程序
詞法分析程序是逐個讀入源程序的字符并按照構(gòu)詞規(guī)則切分成一系列單詞(token)。
- 正則表達式
用特定的運算符及運算對象按規(guī)則構(gòu)造的表達式，每個正則表達式匹配一個字符串集合。 -
確定性有窮自動機
image.png - 非確定性有窮自動機
有窮自動機在一個狀態(tài)上，對于某個輸入符號，存在不止一種轉(zhuǎn)換，稱該有窮自動機為不確定性有窮自動機。 -
正則表達式是一種描述單詞的工具，可以根據(jù)正規(guī)式構(gòu)造等價的DFA，而DFA描述單詞被識別的過程，可以根據(jù)DFA構(gòu)造詞法分析程序。
image.png
- 語法分析程序
語法分析程序以詞法分析程序輸出的單詞序列作為輸入，分析源程序的語法結(jié)構(gòu)，并可以確定單詞序列中違反語法結(jié)構(gòu)規(guī)則的錯誤。語法分析的結(jié)果一般表示為分析樹或語法樹。
在保證語義信息不丟失的情況下，去掉語法分析樹的冗余節(jié)點形成抽象語法樹。多個終結(jié)符都可提到根節(jié)點上。
-
上下文無關(guān)文法又稱為2型文法，是語法結(jié)構(gòu)描述的標準方式
image.png - 推導(dǎo)和規(guī)約
推導(dǎo)：從開始符號S開始，逐步用產(chǎn)生式右部替換左部
規(guī)約：從表達式開始，逐步用產(chǎn)生式左部替換右部 -
句子和句型
句子是句型，開始符號S是句型，由終結(jié)符構(gòu)成的字符串是句子
image.png - 最左推導(dǎo)和最右推導(dǎo)
最左推導(dǎo)：每一次直接推導(dǎo)都是用字符串中最左邊的非終結(jié)符對應(yīng)的產(chǎn)生式規(guī)則進行推導(dǎo)
同理有最右推導(dǎo)，最右推導(dǎo)也稱規(guī)范推導(dǎo)，由最右推導(dǎo)所得的句型稱為規(guī)范句型 - 自上而下的語法分析程序
已知文法G[S], 對任意輸入串w, 若從文法的開始符號S出發(fā)，能為w構(gòu)造一個最左推導(dǎo)，則w是一個合法的句子，否則w有語法錯誤。該算法自上而下的為w的分析結(jié)果建立一棵語法樹。- 遞歸下降分析
該方法執(zhí)行一組遞歸函數(shù)判斷輸入的單詞序列是否符合語法規(guī)則。為每個產(chǎn)生式規(guī)則撰寫一個函數(shù)，終結(jié)符匹配，非終結(jié)符調(diào)用其所在產(chǎn)生式對應(yīng)的函數(shù)。 - LL(1)分析：只走一條唯一可能成功的道路
L：從左向右處理輸入
L：為輸入串找出一個最左推導(dǎo)
1：使用輸入單詞序列中的一個單詞預(yù)測分析
構(gòu)造LL(1)分析表的步驟：
1)求First集合
2)求Follow集合
3)構(gòu)造LL(1)分析表
M[N,T]表示當前分析棧的棧頂符號為N, 而當前詞法分析的輸入單詞為T時，查看LL(1)分析表應(yīng)該按照哪個產(chǎn)生式進行推導(dǎo)。
- 遞歸下降分析
- 自下而上的語法分析
從輸入單詞序列開始，自左至右逐步進行規(guī)約，試圖將其規(guī)約為文法的開始符號。從左到右規(guī)約對應(yīng)的逆過程為最右推導(dǎo)（規(guī)范推導(dǎo)），故稱之為規(guī)范規(guī)約。
自下而上的語法分析工作的每一步，都是從當前串中選擇一個子串，將它規(guī)約到某個非終結(jié)符。
句柄：最左邊的可規(guī)約的子串
活前綴：包含句柄以及句柄之前的所有前綴
可歸前綴：包含句柄的前綴，也就是最長活前綴
LR(k)分析是一種有效的自下而上的語法分析技術(shù)，它能適用于大部分上下文無關(guān)文法的分析。
L：自左向右分析輸入單詞序列
R：分析過程都是構(gòu)造最右推導(dǎo)的逆過程（規(guī)范規(guī)約）
k：在當前分析動作時向右看的單詞個數(shù)- LR(0)：只要當前可規(guī)約就規(guī)約，不看后面的字符
- SLR(1): 僅在發(fā)生沖突時才向右看一個符號，從而確定該采取什么動作
- LR(1): 在LR(0)項目中放置一個向右搜索符號 [A->a., b]
- 語義分析程序
語義分析是在語法分析程序確定出語法短語后，審查有無語義錯誤，并為代碼生成階段收集符號屬性信息。如形參和實參不匹配，類型檢查，數(shù)組下標是否為整數(shù)等。
程序設(shè)計語言的語義分為靜態(tài)語義和動態(tài)語義：
靜態(tài)語義：在編譯階段能夠檢查的語義
動態(tài)語義：在目標程序運行階段能夠檢查的語義
- 語義分析的任務(wù)
計算各類語法成分的語義信息（屬性信息），一般將收集的語義信息存放到相應(yīng)的信息表中。在編譯程序中符號表是用來存放源程序中標識符相關(guān)屬性信息的一種信息表 - 屬性文法的作用
根據(jù)已求得的各產(chǎn)生式的語義規(guī)則，計算任意句子推導(dǎo)過程中各文法符號(終結(jié)符或非終結(jié)符)對應(yīng)的屬性值，根據(jù)屬性值進行相關(guān)語義分析。
