編譯原理結構示意圖

⑴ 編譯原理-文法定義

文法定義公式如下:

Chomsky 文法分類將文法分為四種，0型文法( PSG )、1型文法( CSG )、2型文法( CFG )和3型文法( RG )。

又被稱為無限制文法(Unrestricted Grammar), 或者短語結構文法（Phrase Structure Grammar）
定義: 對於產生式 α→β ， α 至少包含一個非終結符。

為什麼要叫無限制文法，明明它要求產生式的左部必須包含一個非終結符。

又被稱為上下文有關文法(Context-Sensitive Grammar)
定義：對於產生式 α→β , |α| <= |β| , 僅僅 S→ε 除外

為什麼叫做上下文有關文法？

一般情況下，這種產生式的形式為 α1Aα2→α1βα2

又被稱為上下文無關文法(Context-Free Grammar)
定義：對任一產生式 α→β ，都有 α∈VN，β∈(VN∪VT)*

為什麼叫上下文無關文法？

又被稱為正則文法（Regular Grammar，RG），分為右線性（Right Linear）文法和左線性（Left Linear）文法。

定義: 對任一產生式 α→β ，都有 α∈VN，β最多兩個字元元素，如果有二個字元必須是（終結符+非終結符）的格式，如果是一個字元，那麼必須是終結符。

根據產生式右部非終結符位置不同，分為右線性文法和左線性文法。

可以看出，不同文法就是對產生式進行逐層的限制，所以各個文法是包含關系，即0型文法包含1型文法；1型文法又包含2型文法；2型文法最後包含3型文法。

⑵ 編譯原理筆記17：自下而上語法分析（4）LR(0)、SLR(1) 分析表的構造

（移進項目就是納凱態指圓點右邊是終結符的項目，規約項目指的就是圓點在右部最右端的項目）

LR(0) 文法可以直接通過識別活前綴的 DFA 來構造 LR 分析表

假定 C = {I ₀ , I ₁ , ... , I _n } （aka. LR(0) 項目規范族、DFA 狀態集）

首先為文法產生式進行編號，拓廣文法的產生式要標記為 0（這里就是後面分析表中 rj 的產生式編號 j 的由來）

然後令每個項目集 I _k 的下標 k 作為分析器洞源的狀態（行首），包含 S' → .S 的集合下標為分析器的初態（也就是 DFA 的初態孫型，一般都是 0 ）。

下面用一個例子來說明 ACTION、GOTO 子表的構造：

SLR(1) 為解決沖突提出了一個簡單的方法：通過識別活前綴的 DFA 和【簡單向前看一個終結符】構造 SLR(1) 分析表。

如果我們的識別活前綴的 DFA 中存在移進-規約沖突、規約-規約沖突，都可以嘗試使用這個方法來解決沖突。（這里說【嘗試】，當然是因為 SLR 也只能解決一部分問題，並不是萬能的靈丹妙葯。。）

這里，我們拿前面那個 LR(0) 解決不了的文法來舉例

該文法不是 LR(0) 文法，但是是 SLR(1) 文法。

觀察上圖 DFA 中的狀態2，想像當我們的自動機正處於這個狀態：次棧頂已經規約為 T 了，棧頂也是當前的狀態 2 ，而當前剩餘輸入為 *。

如果這個自動機不會【往前多看一步】的話，那麼對處於這個狀態的自動機來說，看起來狀態 2 中的移進項目和規約項目都是可選的。這就是移進-規約沖突。

想要解決這個沖突，就輪到【往前多看一步】上場了——把當前剩餘輸入考慮進來，輔助進行項目的選擇：

對其他的沖突也使用同樣的方法進行判斷。

這種沖突性動作的解決辦法叫做 SLR(1) 解決辦法

准備工作部分，與 LR(0) 分析表的構造差不多：同樣使用每個項目集的狀態編號作為分析器的狀態編號，也就同樣用作行下標；同樣使用拓廣文法產生式作為 0 號產生式。

填表也和 LR(0) 類似，唯一的不同體現在對規約項的處理方法上：如果當前狀態有項目 A → α.aβ 和 A → α. ，而次棧頂此時是 α 且讀寫頭讀到的是 a，那麼當且僅當 a∈FOLLOW(A) 時，我們才會用 A → α 對 α 進行規約。

如果構造出來的表的每個入口都不含多重定義（也就是如上圖中表格那樣的，每個格子裡面最多隻有一個動作），那麼該表就是該文法的 SLR(1) 表，這個文法就是 SLR(1) 文法。使用 SLR(1) 表的分析器叫做一個 SLR(1) 分析器。

任意的二義文法都不能構造出 SLR(1) 分析表

例：懸空 else

例：

這里的 L 可以理解為左值，R 可以理解為右值

經過計算可以確定其 DFA 如下圖所示。

在 狀態4 中，由於 "=" 同時存在於 FOLLOW(L) 與 FOLLOW(R) 中，因此該狀態內存在移進-規約沖突，故該文法不是 SLR(1) 文法。

這樣的非二義文法可以通過增加向前看終結符的個數來解決沖突（比如LL(2)、LR(2)）但這會讓問題更加復雜，故一般不採用。而二義文法無論向前看多少個終結符都無法解決二義性。

⑶ 編譯原理

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

⑷ 編譯原理

編譯原理)：利用編譯程序從源語言編寫的源程序產生目標程序的過程； 用編譯程序產生目標程序的動作。 編譯就是把高級語言變成計算機可以識別的2進制語言，計算機只認識1和0，編譯程序把人們熟悉的語言換成2進制的。

編譯程序把一個源程序翻譯成目標程序的工作過程分為五個階段：詞法分析；語法分析；語義檢查和中間代碼生成

(4)編譯原理結構示意圖擴展閱讀：

編譯程序的語法分析器以單詞符號作為輸入，分析單詞符號串是否形成符合語法規則的語法單位，如表達式、賦值、循環等，最後看是否構成一個符合要求的程序，按該語言使用的語法規則分析檢查每條語句是否有正確的邏輯結構，程序是最終的一個語法單位。

編譯程序的語法規則可用上下文無關文法來刻畫。語法分析的方法分為兩種：自上而下分析法和自下而上分析法。自上而下就是從文法的開始符號出發，向下推導，推出句子。

而自下而上分析法採用的是移進歸約法，基本思想是：用一個寄存符號的先進後出棧，把輸入符號一個一個地移進棧里，當棧頂形成某個產生式的一個候選式時，即把棧頂的這一部分歸約成該產生式的左鄰符號。

⑸ 編譯原理中LR（1） 那個向前搜索符怎麼求的 跪求高手解答 復制粘貼或者答非所問的別來

1、首先第一步就是項目[S』-> . S,]，自動生成搜索符]，自動生成搜索符]，自動生成搜索符，從項目[A->α.Bβ,?]生成項目[B->…,first(β)]。

⑹ 編譯原理筆記9：語法分析樹、語法樹、二義性的消除

語法分析樹和語法樹不是一種東西 。習慣上，我們把前者叫做「具體語法樹」，其能夠體現推導的過程；後者叫做「抽象語法樹」，其不體現過程，只關心最後的結果。

語法分析樹是語言推導過程的圖形化表示方法。這種表示方法反映了語言的實質以及語言的推導過程。

定義：對於 CFG G 的句型，分析樹被定義為具有下述性質的一棵樹：

推導，有最左推導和最右推導，這兩種推導方式在推導過程中的分析樹可能不同，但因最終得到的句子是相同的，所以最終的分析樹是一樣的。

分析樹能反映句型的推導過程，也能反映句型的結構。然而實際上，我們往往不關心推導的過程，而只關心推導的結果。因此，我們要對 分析樹 進行改造，得到 語法樹 。語法樹中全是終結符，沒有非終結符。而且語法樹中沒有括弧

定義：

說白了，語法樹這玩意，就一句話： 葉子全是操作數，內部全是操作符 ，樹里沒有非終結符也不能有括弧。

語法樹要表達的東西，是操作符（運算）作用於操作數（運算對象）

舉倆例子吧：

【例】： -(id+id) 的語法樹：

【例】：-id+id 的語法樹：

顯然，我們從上面這兩個語法樹中，直接就能觀察出來它們的運算順序。

【例】：句型 if C then s1 else s2

二義性問題：一個句子可能對應多於一棵語法樹。

【例】： 設文法 G： E → E+E | E*E | (E) | -E | id

則，句子 id+id*id、id+id+id 可能的分析樹有：

在該例中，雖然 id+id+id 的 「+」 的結合性無論左右都不會影響結果。但萬一，萬一「+」的含義變成了「減法」，那麼左結合和右結合就會引起很大的問題了。

我們在這里講的「二義性」的「義」並非語義——我們現在在學習的內容是「語法分析器」，尚未到需要研究語言背後含義的階段。

我們現在講的「二義性」指的是一個句子對應多種分析樹。

二義性的體現，是文法對同一句子有不止一棵分析樹。這種問題由【句子產生過程中的某些推導有多於一種選擇】引起。懸空 else 問題就可以很好地體現這種【超過一種選擇】帶來的二義性問題，示例如下。

看下面這么個例子。。

（其實，我感覺這個其實比較像是「說話大喘氣」帶來的理解歧義問題。。。）上面的產生式中並沒體現出來該咋算分一塊，所以兩種完全不同的句子結構都是合法的。

二義性問題是有救的，大概有以下這三種辦法：

這些辦法的核心，其實都是將優先順序和結合性說明白。

核心：把優先順序和結合性說明白

既然要說明白，那就不能讓一個非終結符可以直接在當次推導中能推出會帶來優先順序和結合性歧義的東西。（對分析樹的一個內部節點，不會有出現在其下面的分支是相同的非終結符的情況。如果有得選，那就有得歧義了。沒得選才能確定地一路走到黑）

改寫為非二義文法的二義文法大概有下面這幾個特點：

改寫的關鍵步驟：

【例】改寫下面的二義文法為非二義文法。圖右側是要達成的優先順序和結合性

改寫的核心其實就兩句話：

所以能夠得到非終結符與運算的對應關系（因為不同的運算有不同的優先順序，我們想要引入多個優先順序就要引入多個新的非終結符。這樣每個非終結符就可以負責一個優先順序的運算符號，也就是說新的非終結符是與運算有關系的了。因此這里搞出來了「對應關系」四個字）如下：

優先順序由低到高分別是 +、 、-，而距離開始符號越近，優先順序越低。因此在這里的排序也可以+ -順序。每個符號對應一層的非終結符。根據所需要的結合性，則可確定是左遞歸還是右遞歸，以確定新的產生式長什麼樣子

【例】：規定優先順序和結合性，寫出改寫的非二義文法

我們已經掌握了一種叫做【改寫】的工具，能讓我們消除二義性。接下來我們就要用這個工具來嘗試搞搞懸空 else 問題！

懸空 else 問題出現的原因是 then 數量多於 else，讓 else 有多個可以結合的 then。在二義文法中，由於選哪兩個 then、else 配對都可以，故會引起出現二義的情況。在這里，我們規定 else 右結合，即與左邊最靠近的 then 結合。

為改寫此文法，可以將 S 分為完全匹配（MS）和不完全匹配（UMS）兩類。在 MS 中體現 then、else 個數相等即匹配且右結合；在UMS 中 then、else 不匹配，體現 else 右結合。

【例】：用改寫後的文法寫一個條件語句

經過檢查，無法再根據文法寫出其他分析樹，故已經消除了二義性

雖然二義文法會導致二義性，但是其並非一無是處。其有兩個顯著的優點：

在 Yacc 中，我們可以直接指定優先順序、結合性而無需自己重寫文法。

left 表示左結合，right 表示右結合。越往下的算符優先順序越高。

嗯就這么簡單。。。

我們其實可以把語言本身定義成沒有優先順序和結合性的。。然後所有的優先、結合都交由括弧進行控制，哪個先算就加括弧。把一個過程的結束用明確的標志標記出來。

比如在 Ada 中：

在 Pascal 中，給表達式加括弧：

⑺ 編譯原理

C語言編譯過程詳解
C語言的編譯鏈接過程是要把我們編寫的一個C程序(源代碼)轉換成可以在硬體上運行的程序(可執行代碼)，需要進行編譯和鏈接。編譯就是把文本形式源代碼翻譯為機器語言形式的目標文件的過程。鏈接是把目標文件、操作系統的啟動代碼和用到的庫文件進行組織形成最終生成可執行代碼的過程。過程圖解如下：

從圖上可以看到，整個代碼的編譯過程分為編譯和鏈接兩個過程，編譯對應圖中的大括弧括起的部分，其餘則為鏈接過程。
一、編譯過程
編譯過程又可以分成兩個階段：編譯和匯編。
1、編譯
編譯是讀取源程序(字元流)，對之進行詞法和語法的分析，將高級語言指令轉換為功能等效的匯編代碼，源文件的編譯過程包含兩個主要階段：
第一個階段是預處理階段，在正式的編譯階段之前進行。預處理階段將根據已放置在文件中的預處理指令來修改源文件的內容。如#include指令就是一個預處理指令，它把頭文件的內容添加到.cpp文件中。這個在編譯之前修改源文件的方式提供了很大的靈活性，以適應不同的計算機和操作系統環境的限制。一個環境需要的代碼跟另一個環境所需的代碼可能有所不同，因為可用的硬體或操作系統是不同的。在許多情況下，可以把用於不同環境的代碼放在同一個文件中，再在預處理階段修改代碼，使之適應當前的環境。
主要是以下幾方面的處理：
(1)宏定義指令，如 #define a b。
對於這種偽指令，預編譯所要做的是將程序中的所有a用b替換，但作為字元串常量的 a則不被替換。還有 #undef，則將取消對某個宏的定義，使以後該串的出現不再被替換。
(2)條件編譯指令，如#ifdef，#ifndef，#else，#elif，#endif等。
這些偽指令的引入使得程序員可以通過定義不同的宏來決定編譯程序對哪些代碼進行處理。預編譯程序將根據有關的文件，將那些不必要的代碼過濾掉
(3) 頭文件包含指令，如#include "FileName"或者#include <FileName>等。
在頭文件中一般用偽指令#define定義了大量的宏(最常見的是字元常量)，同時包含有各種外部符號的聲明。採用頭文件的目的主要是為了使某些定義可以供多個不同的C源程序使用。因為在需要用到這些定義的C源程序中，只需加上一條#include語句即可，而不必再在此文件中將這些定義重復一遍。預編譯程序將把頭文件中的定義統統都加入到它所產生的輸出文件中，以供編譯程序對之進行處理。包含到C源程序中的頭文件可以是系統提供的，這些頭文件一般被放在/usr/include目錄下。在程序中#include它們要使用尖括弧(<>)。另外開發人員也可以定義自己的頭文件，這些文件一般與C源程序放在同一目錄下，此時在#include中要用雙引號("")。
(4)特殊符號，預編譯程序可以識別一些特殊的符號。
例如在源程序中出現的LINE標識將被解釋為當前行號(十進制數)，FILE則被解釋為當前被編譯的C源程序的名稱。預編譯程序對於在源程序中出現的這些串將用合適的值進行替換。
預編譯程序所完成的基本上是對源程序的「替代」工作。經過此種替代，生成一個沒有宏定義、沒有條件編譯指令、沒有特殊符號的輸出文件。這個文件的含義同沒有經過預處理的源文件是相同的，但內容有所不同。下一步，此輸出文件將作為編譯程序的輸出而被翻譯成為機器指令。
第二個階段編譯、優化階段。經過預編譯得到的輸出文件中，只有常量；如數字、字元串、變數的定義，以及C語言的關鍵字，如main,if,else,for,while,{,}, +,-,*,\等等。
編譯程序所要作得工作就是通過詞法分析和語法分析，在確認所有的指令都符合語法規則之後，將其翻譯成等價的中間代碼表示或匯編代碼。
優化處理是編譯系統中一項比較艱深的技術。它涉及到的問題不僅同編譯技術本身有關，而且同機器的硬體環境也有很大的關系。優化一部分是對中間代碼的優化。這種優化不依賴於具體的計算機。另一種優化則主要針對目標代碼的生成而進行的。
對於前一種優化，主要的工作是刪除公共表達式、循環優化(代碼外提、強度削弱、變換循環控制條件、已知量的合並等)、復寫傳播，以及無用賦值的刪除，等等。
後一種類型的優化同機器的硬體結構密切相關，最主要的是考慮是如何充分利用機器的各個硬體寄存器存放的有關變數的值，以減少對於內存的訪問次數。另外，如何根據機器硬體執行指令的特點(如流水線、RISC、CISC、VLIW等)而對指令進行一些調整使目標代碼比較短，執行的效率比較高，也是一個重要的研究課題。
2、匯編
匯編實際上指把匯編語言代碼翻譯成目標機器指令的過程。對於被翻譯系統處理的每一個C語言源程序，都將最終經過這一處理而得到相應的目標文件。目標文件中所存放的也就是與源程序等效的目標的機器語言代碼。目標文件由段組成。通常一個目標文件中至少有兩個段：
代碼段：該段中所包含的主要是程序的指令。該段一般是可讀和可執行的，但一般卻不可寫。
數據段：主要存放程序中要用到的各種全局變數或靜態的數據。一般數據段都是可讀，可寫，可執行的。
UNIX環境下主要有三種類型的目標文件：
(1)可重定位文件
其中包含有適合於其它目標文件鏈接來創建一個可執行的或者共享的目標文件的代碼和數據。
(2)共享的目標文件
這種文件存放了適合於在兩種上下文里鏈接的代碼和數據。
第一種是鏈接程序可把它與其它可重定位文件及共享的目標文件一起處理來創建另一個 目標文件；
第二種是動態鏈接程序將它與另一個可執行文件及其它的共享目標文件結合到一起，創建一個進程映象。
(3)可執行文件
它包含了一個可以被操作系統創建一個進程來執行之的文件。匯編程序生成的實際上是第一種類型的目標文件。對於後兩種還需要其他的一些處理方能得到，這個就是鏈接程序的工作了。
二、鏈接過程
由匯編程序生成的目標文件並不能立即就被執行，其中可能還有許多沒有解決的問題。
例如，某個源文件中的函數可能引用了另一個源文件中定義的某個符號(如變數或者函數調用等)；在程序中可能調用了某個庫文件中的函數，等等。所有的這些問題，都需要經鏈接程序的處理方能得以解決。
鏈接程序的主要工作就是將有關的目標文件彼此相連接，也即將在一個文件中引用的符號同該符號在另外一個文件中的定義連接起來，使得所有的這些目標文件成為一個能夠被操作系統裝入執行的統一整體。
根據開發人員指定的同庫函數的鏈接方式的不同，鏈接處理可分為兩種：
(1)靜態鏈接
在這種鏈接方式下，函數的代碼將從其所在地靜態鏈接庫中被拷貝到最終的可執行程序中。這樣該程序在被執行時這些代碼將被裝入到該進程的虛擬地址空間中。靜態鏈接庫實際上是一個目標文件的集合，其中的每個文件含有庫中的一個或者一組相關函數的代碼。
(2) 動態鏈接
在此種方式下，函數的代碼被放到稱作是動態鏈接庫或共享對象的某個目標文件中。鏈接程序此時所作的只是在最終的可執行程序中記錄下共享對象的名字以及其它少量的登記信息。在此可執行文件被執行時，動態鏈接庫的全部內容將被映射到運行時相應進程的虛地址空間。動態鏈接程序將根據可執行程序中記錄的信息找到相應的函數代碼。
對於可執行文件中的函數調用，可分別採用動態鏈接或靜態鏈接的方法。使用動態鏈接能夠使最終的可執行文件比較短小，並且當共享對象被多個進程使用時能節約一些內存，因為在內存中只需要保存一份此共享對象的代碼。但並不是使用動態鏈接就一定比使用靜態鏈接要優越。在某些情況下動態鏈接可能帶來一些性能上損害。
我們在linux使用的gcc編譯器便是把以上的幾個過程進行捆綁，使用戶只使用一次命令就把編譯工作完成，這的確方便了編譯工作，但對於初學者了解編譯過程就很不利了，下圖便是gcc代理的編譯過程：

從上圖可以看到：
預編譯
將.c 文件轉化成 .i文件
使用的gcc命令是：gcc –E
對應於預處理命令cpp
編譯
將.c/.h文件轉換成.s文件
使用的gcc命令是：gcc –S
對應於編譯命令 cc –S
匯編
將.s 文件轉化成 .o文件
使用的gcc 命令是：gcc –c
對應於匯編命令是 as
鏈接
將.o文件轉化成可執行程序
使用的gcc 命令是： gcc
對應於鏈接命令是 ld
總結起來編譯過程就上面的四個過程：預編譯、編譯、匯編、鏈接。了解這四個過程中所做的工作，對我們理解頭文件、庫等的工作過程是有幫助的，而且清楚的了解編譯鏈接過程還對我們在編程時定位錯誤，以及編程時盡量調動編譯器的檢測錯誤會有很大的幫助的。

⑻ 編譯原理習題，下圖為什麼a為句柄, 而不是最左面的b為句柄怎樣理解句柄定義中的最左簡單子樹中的簡

baSb的最右推導為：S->AB->ASb->bBSb->baSb

根據句柄定義：

所以a為baSb的句柄。

只有單層分支的子樹稱為簡單子樹。最左簡單子樹末端結點組成的符號串為句柄。

⑼ 編譯原理——LR分析表

自底向上的語法分析

LR分析表的結構如上，其分為兩個部分 Action Goto

兩個參數狀態i，終結符號a（s(i)代表第i個狀態，r(i)代表第i條表達式）

Goto[i,A]=j

文法

容易得知這個文法可以推出 0 1 00 01 等的字元串。因為它是 左遞歸 。不適用於 LL 文法分析，只能使用 LR 分析。

因為本題入口有兩個—— S → L·L S → L ，所以需要構造額外的產生式 S'->S

2.1 第一次遍歷

我們從 [S -> . L·L] 開始，構造這個狀態的閉包，也就是加上所有能從這個產生式推出的表項。

首先，判斷 . 後面是否為 非終結符號A 。如果是，那我們就得找所有由 A-> 推出的產生式，並將它們添加進入 閉包 里(也就是State包里)。循環做即可。

因此我們可以得到 State 0 有

下一步，就是我的 . 往下一位移動。對每個符號X後有個 . 的項，都可以從 State 0 過渡到其他狀態。

由以上6條式子可以得知下一位符號可以是 S L B 0 1 。所以自然可以得到5個狀態。

State 1 是由 State 0 通過 S 轉移到這里的，所以我們找出所有 State 0 中在 S 前有 . 的項。

此狀態作為結束狀態 Accept ，不需要繼續狀態轉移了。

State 2 是由 State 0 通過 L 轉移到這里的，所以我們找出所有 State 0 中在 L 前有 . 的項。

S -> . L·L S -> . L L -> . LB

有3條式子，現在我們將 . 向後推一格，就得到 State 1 的項了。

但是 . 之後的符號分別是 · $ B ， B 為非終結符號，我們得包含 B -> 的項

State 3 是由 State 0 通過 B 轉移到這里的，所以我們找出所有 State 0 中在 B 前有 . 的項。

因為 . 後沒有其他符號了，因此這個狀態不需要繼續轉移了。

State 4 是由 State 0 通過 0 轉移到這里的，所以我們找出所有 State 0 中在 0 前有 . 的項。

因為 . 後沒有其他符號了，因此這個狀態不需要繼續轉移了。

很簡單，同樣的道理找 State 5

State 5 是由 State 0 通過 1 轉移到這里的，所以我們找出所有 State 0 中在 1 前有 . 的項。

因為 . 後沒有其他符號了，因此這個狀態不需要繼續轉移了。

好的，現在我們第一次遍歷完成。

2.2 第二次遍歷

第二次遍歷自然從 State 2 開始。

我們回到 State2 ，可以看出 . 之後的符號有 · B 0 1 。

State 6 是由 State 2 通過 · 轉移到這里的，所以我們找出所有 State 2 中在 · 前有 . 的項。

S -> L. ·L 只有1條，我們往後移發現 L 又為非終結符號，參考 State 0 做的操作，我們得找出所有的式子。

共有5條式子，共同組成 State 6 ，由上面的式子可以看出我們還得繼續下一次遍歷。先不管著，我們進行下一次狀態查找。

State 7 是由 State 2 通過 B 轉移到這里的，所以我們找出所有 State 2 中在 B 前有 . 的項。

L -> L. B 也是只有1條，我們往後移發現沒有非終結符號了，那就不需要再繼續添加其他式子了。

這個狀態也不需要繼續進行轉移了。

接下來很關鍵，因為我們通過 State2 的 . 後的符號找出了 State 6 State 7 ，接下來還差符號 0 1 ，那麼是否像之前一樣按例添加狀態呢， 答案是不是的 ，因為我們發現通過 0 1 找到的閉包集分別是 B -> 0 B -> 1 ，這與我們的之前的 State 4 State 5 相同。所以我們得將其整合起來，相當於 State 2 通過 0 1 符號找到了 State 4 State 5 狀態。

2.3 第三次遍歷

回頭看第二次遍歷，可以看出只有 State 6 可以進行狀態轉移了。

那麼就將 State 6 作為第三次遍歷的源頭，可以看出 . 之後的符號有 L B 0 1 。

State 8 是由 State 6 通過 L 轉移到這里的，所以我們找出所有 State 6 在 L 前有 . 的項。

S -> L· .L L -> . LB 有兩條式子，往後移發現有非終結符號 B ，所以經過整合可以得到

可以看出 . 的後面還有一個符號，所以這里我們還得再進行一次遍歷。

接下來，又是遇到重復的包的情況，可以看出我們由 State 6 通過 B 0 1 得到的閉包分別是 L->B B->0 B->1 ，很明顯，這分別對應於 State 3 State 4 State 5 。

第三次遍歷也就結束了。

2.4 第四次遍歷

回看第三次遍歷，可以看出只有 State 8 可以進行狀態轉移，其 . 之後的符號分別是 B 0 1 。

誒，感覺很熟悉，就是上面幾行剛說的情況，也就是說通過這三個符號找到的閉包是我們之前遇到的狀態，分別是 State 3 State 4 State 5 。

做到這里，我們發現我們已經全部遍歷完畢！

總共有8個狀態，通過以上流程做成個圖是什麼樣子的？來看看！

這么一看就很清晰明了了，我們就可以通過這個圖做出我們的 LR分析表

其實就是我們之前呈現的表

在狀態 I2 和 I8 中，既有 移入 項目，也有 規約 項目，存在 移入 - 規約的沖突 ，所以不是 LR(0) 文法，但是因為 FOLLOW(S) ∩ {0, 1} = ∅，所以可以用 FOLLOW 集解決沖突，所以該文法是 SLR(1) 文法。

上表我們發現還有 r1，r2，r3 等。這個其實就是代表狀態停止轉移時為 第幾條表達式 ，r3代表第三條表達式 L -> LB 。

當我們構建了表之後，我們如何運用起來呢？

下面我們通過一個例子來說明

以上字元串是如何被SLR分析器識別的呢？