編譯器的語法分析

『壹』 編譯原理

編譯原理是計算機專業的一門重要專業課，旨在介紹編譯程序構造的一般原理和基本方法。內容包括語言和文法、詞法分析、語法分析、語法制導翻譯、中間代碼生成、存儲管理、代碼優化和目標代碼生成。 編譯原理是計算機專業設置的一門重要的專業課程。編譯原理課程是計算機相關專業學生的必修課程和高等學校培養計算機專業人才的基礎及核心課程，同時也是計算機專業課程中最難及最挑戰學習能力的課程之一。編譯原理課程內容主要是原理性質，高度抽象[1]。

中文名
編譯原理[1]
外文名
Compilers: Principles, Techniques, and Tools[1]
領域
計算機專業的一門重要專業課[1]
快速
導航
編譯器

編譯原理課程

編譯技術的發展

編譯的基本流程

編譯過程概述
基本概念
編譯原理即是對高級程序語言進行翻譯的一門科學技術, 我們都知道計算機程序由程序語言編寫而成, 在早期計算機程序語言發展較為緩慢, 因為計算機存儲的數據和執行的程序都是由0、1代碼組合而成的, 那麼在早期程序員編寫計算機程序時必須十分了解計算機的底層指令代碼通過將這些微程序指令組合排列從而完成一個特定功能的程序, 這就對程序員的要求非常高了。人們一直在研究如何如何高效的開發計算機程序, 使編程的門檻降低。[2]
編譯器
C語言編譯器是一種現代化的設備, 其需要藉助計算機編譯程序, C語言編譯器的設計是一項專業性比較強的工作, 設計人員需要考慮計算機程序繁瑣的設計流程, 還要考慮計算機用戶的需求。計算機的種類在不斷增加, 所以, 在對C語言編譯器進行設計時, 一定要增加其適用性。C語言具有較強的處理能力, 其屬於結構化語言, 而且在計算機系統維護中應用比較多, C語言具有高效率的優點, 在其不同類型的計算機中應用比較多。[3]
C語言編譯器前端設計
編譯過程一般是在計算機系統中實現的, 是將源代碼轉化為計算機通用語言的過程。編譯器中包含入口點的地址、名稱以及機器代碼。編譯器是計算機程序中應用比較多的工具, 在對編譯器進行前端設計時, 一定要充分考慮影響因素, 還要對詞法、語法、語義進行分析。[3]
1 詞法分析[3]
詞法分析是編譯器前端設計的基礎階段, 在這一階段, 編譯器會根據設定的語法規則, 對源程序進行標記, 在標記的過程中, 每一處記號都代表著一類單詞, 在做記號的過程中, 主要有標識符、關鍵字、特殊符號等類型, 編譯器中包含詞法分析器、輸入源程序、輸出識別記號符, 利用這些功能可以將字型大小轉化為熟悉的單詞。[3]
2 語法分析[3]
語法分析是指利用設定的語法規則, 對記號中的結構進行標識, 這包括句子、短語等方式, 在標識的過程中, 可以形成特殊的結構語法樹。語法分析對編譯器功能的發揮有著重要影響, 在設計的過程中, 一定要保證標識的准確性。[3]
3 語義分析[3]
語義分析也需要藉助語法規則, 在對語法單元的靜態語義進行檢查時, 要保證語法規則設定的准確性。在對詞法或者語法進行轉化時, 一定要保證語法結構設置的合法性。在對語法、詞法進行檢查時, 語法結構設定不合理, 則會出現編譯錯誤的問題。前端設計對精確性要求比較好, 設計人員能夠要做好校對工作, 這會影響到編譯的准確性, 如果前端設計存在失誤, 則會影響C語言編譯的效果。[3]

『貳』 3-8解碼器的工作原理

3-8解碼器的功能就是把輸入的3位2進制數翻譯成10進制的輸出。

簡單介紹：

3-8解碼器的輸入是3個腳,輸出是8個腳。用高低電平來表示輸入和輸出。

1、輸入是二進制。3隻腳也就是3位二進制數。輸入可以3位二進制數。3位二進制最大是111 也就是8。

2、輸出是8個腳，表示10進制。是根據輸入的二進制數來輸出。如果輸入是101 那麼就是第5隻腳高電平，表示二進制數是5。

3、3-8線解碼器是一種全解碼器（二進制解碼器）。全解碼器的輸入是3位二進制代碼，3位二進制代碼共有8種組合，故輸出是與這8種組合一一對應的8個輸出信號。

(2)編譯器的語法分析擴展閱讀：

解碼器工作方法：

1、首先編譯器進行語法分析，也就是要把那些字元串分離出來。

2、然後進行語義分析，就是把各個由語法分析分析出的語法單元的意義搞清楚。

3、最後生成的是目標文件，也稱為obj文件。

4、再經過鏈接器的鏈接就可以生成最後的EXE文件了。

有些時候需要把多個文件產生的目標文件進行鏈接，產生最後的代碼。這一過程稱為交叉鏈接。

『叄』 編譯器筆記10-語法分析-FIRST集和FOLLOW集的計算

FIRST(X)：可以從X推導出的所有串首終結符，如果 X=>*ε，那麼ε∈FIRST(X)。

不斷應用下列規則，直到沒有新的終結符或ε可以被加入到任何FIRST集合中為止

FOLLOW(A)：可能在某個句型中緊跟在A後邊的終結符a的集合

如果A是某個句型的的最右符號，則將結束符「$」添加到FOLLOW(A) 中。

不斷應用下列規則，直到沒有新的終結符可以被加入到任何FOLLOW

注意說明：

『肆』 編譯器筆記14-語法分析-SLR分析

當在狀態2時輸入符號為 * 時候，可以採取移入操作也可以採取歸約操作。那到底選用哪一個操作呢？歸根結底還是一個如何識別句柄的問題。如果棧頂的T為句柄的話就使用歸約操作，否則的話就不能使用歸約操作。由此可見LR(0)的信息已經不能幫助我們確定是否進行歸約。

事實上LR(0)分析在構造時，向前查看了零個符號，也就是沒有向前查看符號，即沒有考慮文法符號的上下環境。

上圖例子中狀態2在下一個符號是*時，如果把棧頂的T歸約成E。由上圖可知 * 不在FOLLOW(E)中，所以即便歸約成E，E後也不可能跟 * ，所以不應該歸約，T不是句柄。由此可見FOLLOW集可以幫助判斷在哪些情況下不能進行歸約，這也是SLR分析法的基本思想。

解決LR(0)文法的移入歸約沖突，其實就是加強對文法的約束以避免沖突，其實分析方法中並沒因此做出任何改變。

如果給定文法的SLR分析表中不存在有沖突的動作，那麼該文法成為SLR文法。

由上圖可知當狀態2遇到等號時遇到了移入歸約沖突。某些情況下僅利用FOLLOW集的信息去化解沖突是不夠的。為了消解這種沖突需要使用更強大的 LR(1)分析法 。

『伍』 編譯器的功能是什麼

1、編譯器就是將「一種語言（通常為高級語言）」翻譯為「另一種語言（通常為低級語言）」的程序。一個現代編譯器的主要工作流程：源代碼 (source code) → 預處理器 (preprocessor) → 編譯器 (compiler) → 目標代碼 (object code) → 鏈接器(Linker) → 可執行程序 (executables)。
2、工作方法：
1）、首先編譯器進行語法分析，也就是要把那些字元串分離出來。
2）、然後進行語義分析，就是把各個由語法分析分析出的語法單元的意義搞清楚。
3）、最後生成的是目標文件，也稱為obj文件。
4）、再經過鏈接器的鏈接就可以生成最後的EXE文件了。
5）、有些時候需要把多個文件產生的目標文件進行鏈接，產生最後的代碼。這一過程稱為交叉鏈接。

『陸』 編譯器的組成及各部分的功能及作用

1. 詞法分析 詞法分析器根據詞法規則識別出源程序中的各個記號（token），每個記號代表一類單詞（lexeme）。源程序中常見的記號可以歸為幾大類：關鍵字、標識符、字面量和特殊符號。詞法分析器的輸入是源程序，輸出是識別的記號流。詞法分析器的任務是把源文件的字元流轉換成記號流。本質上它查看連續的字元然後把它們識別為「單詞」。 2. 語法分析 語法分析器根據語法規則識別出記號流中的結構（短語、句子），並構造一棵能夠正確反映該結構的語法樹。 3. 語義分析 語義分析器根據語義規則對語法樹中的語法單元進行靜態語義檢查，如果類型檢查和轉換等，其目的在於保證語法正確的結構在語義上也是合法的。 4. 中間代碼生成 中間代碼生成器根據語義分析器的輸出生成中間代碼。中間代碼可以有若干種形式，它們的共同特徵是與具體機器無關。最常用的一種中間代碼是三地址碼，它的一種實現方式是四元式。三地址碼的優點是便於閱讀、便於優化。 5. 中間代碼優化 優化是編譯器的一個重要組成部分，由於編譯器將源程序翻譯成中間代碼的工作是機械的、按固定模式進行的，因此，生成的中間代碼往往在時間和空間上有很大浪費。當需要生成高效目標代碼時，就必須進行優化。 6. 目標代碼生成 目標代碼生成是編譯器的最後一個階段。在生成目標代碼時要考慮以下幾個問題：計算機的系統結構、指令系統、寄存器的分配以及內存的組織等。編譯器生成的目標程序代碼可以有多種形式：匯編語言、可重定位二進制代碼、內存形式。 7 符號表管理 符號表的作用是記錄源程序中符號的必要信息，並加以合理組織，從而在編譯器的各個階段能對它們進行快速、准確的查找和操作。符號表中的某些內容甚至要保留到程序的運行階段。 8 出錯處理用戶編寫的源程序中往往會有一些錯誤，可分為靜態錯誤和動態錯誤兩類。所謂動態錯誤，是指源程序中的邏輯錯誤，它們發生在程序運行的時候，也被稱作動態語義錯誤，如變數取值為零時作為除數，數組元素引用時下標出界等。靜態錯誤又可分為語法錯誤和靜態語義錯誤。語法錯誤是指有關語言結構上的錯誤，如單詞拼寫錯、表達式中缺少操作數、begin和end不匹配等。靜態語義錯誤是指分析源程序時可以發現的語言意義上的錯誤，如加法的兩個操作數中一個是整型變數名，而另一個是數組名等。

『柒』 把編譯的過程劃分為詞法分析和語法分析的原因

將編譯器的工作過程劃分為詞法分析，語義分析，中間代碼生成，代碼優化和目標代碼生成時，語法分析階段的輸入是( 記號流 )若程序中的括弧不配對，則會在( 語法分析 )階段檢查出錯誤。

『捌』 語法分析器可以發現語法錯誤

可以。語法分析器通常是作為編譯器或解釋器的組件出現的，它的作用是進行語法檢查、並構建由輸入的單片語成的數據結構。語法分析器可以發現語法錯誤，語法分析器使用一個獨立的詞法分析器從輸入字元流中分離出一個個的「單詞」，並將單詞流作為其輸。語法是語言學的一個分支，研究按確定用法來運用的"詞類"、"詞"的曲折變化或表示相互關系的其他手段以及詞在句中的功能和關系。

『玖』 一般設計編譯器要將詞法分析和語法分析分開的原因是什麼

1. 簡單性——詞法分析技術不如語法分析技術技術復雜，分開之後詞法分析過程更簡單。(這里還有一些意思差不多的話)

2. 效率——詞法分析佔用的時間是整個編譯時間的一大部分，所以將它們分開有利於優化詞法分析，而提高編譯效率

3. 可移植性——詞法分析通常平台相關，語法分析器可以是平台無關的。分開了對移植有利。

（引自《程序設計語言概念》(第9版) Sebesta著）

『拾』 編譯器筆記13-語法分析-LR分析法概述

可以用LR分析法分析的文法可以稱為LR分析法。LR文法（ Knuth ，1963）是最大的、可以構造出相應移入- 歸約語法分析器的文法類。

LR(k)分析，需要向前查看k個輸入符號的LR分析，k=0 和 k=1 這兩種情況具有實踐意義，當省略(k)時，表示k=1。而在LR(k)這樣的名稱中，k代表的是分析時所需前瞻符號（lookahead symbol）的數量，也就是除了當前處理到的輸入符號之外，還得再向右引用幾個符號之意；省略 （k）時即視為LR(1)，而非LR(0)。

作為對比這里列出LL(1)文法的含義：

問：自底向上分析的關鍵問題是什麼？
答：如何正確地識別句柄，句柄是逐步形成的，用「狀態」表示句柄識別的進展程度。例如在 自底向上分析概述 中所提及到句柄識別錯誤的例子，通過狀態跟下一個輸入符號就可以判斷出應該做出哪一個動作，而狀態相當於一種記憶功能記錄當前句柄識別到什麼程度。

與移入分析器不同的是LR分析器多了一個與符號棧平行的狀態棧。

之後的分析過程與上圖類似，直至到如下狀態，分析成功。可見分析時進行什麼動作是由棧狀態棧棧頂的狀態和下一個輸入符號決定。

輸入：串w和LR語法分析表，該表描述了文法G的ACTION函數和GOTO函數。
輸出：如果w在L(G)中，則輸出w的自底向上語法分析過程中的歸約步驟；否則給出一個錯誤指示。
方法：初始時，語法分析器棧中的內容為初始狀態s0 ，輸入緩沖區中的內容為w$。然後，語法分析器執行下面的程序：

先了解LR(0)項目和增廣文法這兩個概念

右部某位置標有圓點的產生式稱為相應文法的一個LR(0)項目（簡稱為項目）：A → α1·α2

文法開始符號S表示的是語言中的最大成分。如下圖當b出現時可以將它移入到分析棧中。b移進棧後我們期待歸約出B。當歸約出B時我們還期待再歸約一個B。

如果G是一個以S為開始符號的文法，則G的增廣文法G'就是在G中加上新開始符號S'和產生式S'→S而得到的文法

引入這個新的開始產生式的目的是使得文法開始符號僅出現在一個產生式的左邊，從而使得分析器只有一個接受狀態。

項目可以分為以下幾類：

上圖中S'對應的第一個項目稱為初始項目，而S'對應的最後一個項目稱之為接收項目在此狀態下文法的開始符號已經被歸約出來，因此可以接收了故稱為接收項目。紅色方框中的項目則被稱為歸約項目。

項目集閉包(Closure of Item Sets)

可以把等價的項目組成一個項目集(I)，稱為項目集閉包，每個項目集閉包對應著自動機的一個狀態。

先了解CLOSURE和GOTO這兩個函數

項目集I的閉包的數學定義：

返回項目集I對應於文法符號X的後繼項目集閉包

規范LR(0)項集族(Canonical LR(0) Collection)

說明： 該自動機的初始狀態就是文法的初始項目的項目集閉包，其終止狀態集合只有一個狀態就是文法的接收項目的項目集閉包。

如果LR(0)分析表中沒有語法分析動作沖突，那麼給定的文法就稱為LR(0)。不是所有CFG都能用LR(0)方法進行分析，也就是說，CFG不總是LR(0)文法。

為了解決移進/歸約沖突和歸約/歸約沖突需要使用到 SLR分析法 和 LR(1)分析法 。

問: 為什麼沒有移進/移進沖突？
答: 首先只有在移進狀態和待約狀態下的項目才會有使用到移進操作。在0狀態時所有項目都是移進狀態根據LL文法顯然不會產生移進/移進操作，因為每個產生式左部的SELECT集是沒有交集的。而在其他具有待約狀態項目的狀態中，所有集合都是等價的。假若在某狀態下輸入終結符y時發生移進/移進沖突，即存在兩個這樣的項目A0→α0·yβ0，A1→α1·yβ1，但顯然這兩個項目是不等價的顯然與同一狀態下所有項目等價相矛盾，因此這種移進/移進沖突是不存在的。假若在某狀態下輸入非終結符X時發生移進/移進沖突，即存在兩個這樣的項目A0→α0·Xβ0，A1→α1·Xβ1，而A0與A1在同一狀態下是等價的則兩項目要麼是A0→α0·Xβ0與X→.Xβ1(原項目A1變為X，α1變為ε)要麼是A1→α1·Xβ1與X→.Xβ0(原項目A0變為X，α0變為ε)。顯然X→Xβ0|Xβ1（左遞歸）是不符合LL文法的因此這種情況也是不可能出現。

綜上移進/移進沖突在LR分析下是不存在的。