編譯器語法分析

Ⅰ 編譯器筆記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)分析法 。

Ⅱ 編譯器是什麼意思，是做什麼的

編譯器
編譯器是一種特殊的程序，它可以把以特定編程語言寫成的程序變為機器可以運行的機器碼。我們把一個程序寫好，這時我們利用的環境是文本編輯器。這時我程序把程序稱為源程序。在此以後程序員可以運行相應的編譯器，通過指定需要編譯的文件的名稱就可以把相應的源文件（通過一個復雜的過程）轉化為機器碼了。

下面我們看看它是如何工作的。首先編譯器進行語法分析，也就是要把那些字元串分離出來。然後進行語義分析，就是把各個由語法分析分析出的語法單元的意義搞清楚。最後生成的是目標文件，我們也稱為obj文件。再經過鏈接器的鏈接就可以生成最後的可執行代碼了。有些時候我們需要把多個文件產生的目標文件進行鏈接，產生最後的代碼。我們把一過程稱為交叉鏈接。

有一個稱為LCC的編譯器，還挺不錯的；還有一個用於分析其規則的小工具；

Ⅲ 編譯器筆記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分析下是不存在的。

Ⅳ 編譯器的組成及各部分的功能及作用

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

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

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

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

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

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

Ⅵ 編譯器的功能是什麼

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

Ⅶ C語言的語法分析器

先做個LL(1)或者LALR的語法分析器，然後先把教材上的幾個LL(1)的例子調通過。然後網上有C語言子集的文法，有人做了轉成大小寫這樣的表述。通過那個的測試就差不多了。。。。其實做語法分析也沒多大用 編譯器的難點在於語法制導、代碼優化之類的，真要做C語言的完整編譯器，普通的學生都幾乎不可能實現。。。。就不多說了 你可以動手開始做了 如果你有較強的程序設計能力，做個漂亮的LR(1)分析器還是可以的，實在不會就做SLR(1)這樣的分析器，如果程序設計能力比較差，建議先做LL(1)，那個比較好做。碼字不易，望採納！