編譯原理中什麼叫推導

Ⅰ 【編譯原理】第二章：語言和文法

上述文法 表示，該文法由終結符集合 ，非終結符集合 ，產生式集合 ，以及開始符號 構成。
而產生式 表示，一個表達式（Expression） ，可以由一個標識符（Identifier） 、或者兩個表達式由加號 或乘號 連接、或者另一個表達式用括弧包裹（ ）構成。

約定 ：在不引起歧義的情況下，可以只寫產生式。如以上文法可以簡寫為：

產生式

可以簡寫為：

如上例中，

可以簡寫為：

給定文法 ，如果有 ，那麼可以將符號串 重寫 為 ，記作 ，這個過程稱為 推導 。
如上例中， 可以推導出 或 或 等等。

如果 ，
可以記作 ，則稱為 經過n步推導出 ，記作 。

推導的反過程稱為 歸約 。

如果 ，則稱 是 的一個 句型（sentential form ）。

由文法 的開始符號 推導出的所有句子構成的集合稱為 文法G生成的語言 ，記作 。
即：

例
文法

表示什麼呢？
代表小寫字母；
代表數字；
表示若干個字母和數字構成的字元串；
說明 是一個字母、或者是字母開頭的字元串。
那麼這個文法表示的即是，以字母開頭的、非空的字元串，即標識符的構成方式。

並、連接、冪、克林閉包、正閉包。
如上例表示為：

中必須包含一個 非終結符 。

產生式一般形式：
即上式中只有當上下文滿足 與 時，才能進行從 到 的推導。

上下文有關文法不包含空產生式（ ）。

產生式的一般形式：
即產生式左邊都是非終結符。

右線性文法 ：
左線性文法 ：
以上都成為正則文法。
即產生式的右側只能有一個終結符，且所有終結符只能在同一側。

例：（右線性文法）

以上文法滿足右線性文法。
以上文法生成一個以字母開頭的字母數字串（標識符）。
以上文法等價於 上下文無關文法 ：

正則文法能描述程序設計語言中的多數單詞。

正則文法能描述程序設計語言中的多數單詞，但不能表示句子構造，所以用到最多的是CFG。

根節點 表示文法開始符號S；
內部節點 表示對產生式 的應用；該節點的標號是產生式左部，子節點從左到右表示了產生式的右部；
葉節點 （又稱邊緣）既可以是非終結符也可以是終結符。

給定一個句型，其分析樹的每一棵子樹的邊緣稱為該句型的一個 短語 。
如果子樹高度為2，那麼這棵子樹的邊緣稱為該句型的一個 直接短語 。

直接短語一定是某產生式的右部，但反之不一定。

如果一個文法可以為某個句子生成 多棵分析樹 ，則稱這個文法是 二義性的 。

二義性原因：多個if只有一個else；
消岐規則：每個else只與最近的if匹配。

Ⅱ 求最左推導和最右推導

最左推導（Leftmost Derivation）

最左推導是一種從文法的起始符號開始，總是優先替換最左邊的非終結符的推導過程。具體步驟如下：

• 從文法的起始符號開始。

• 在每一步中，找到當前字元串中的最左邊的非終結符，並用其某個產生式進行替換。

• 重復第2步，直到得到一個只包含終結符的字元串為止。

最右推導（Rightmost Derivation）

最右推導與最左推導相反，它總是優先替換最右邊的非終結符。具體步驟如下：

• 從文法的起始符號開始。

• 在每一步中，找到當前字元串中的最右邊的非終結符，並用其某個產生式進行替換。

• 重復第2步，直到得到一個只包含終結符的字元串為止。

示例

考慮以下簡單的上下文無關文法：

• S → A B

• A → a A

• A → ε

• B → b B

• B → ε

最左推導示例：

• S （起始符號）

• A B （S → A B）

• a A B （A → a A，替換最左邊的A）

• a a A B （A → a A，替換最左邊的A）

• a a b B （B → b B，替換最左邊的B）

• a a b b B （B → b B，替換最左邊的B）

• a a b b （B → ε，替換最左邊的B）

最右推導示例：

• S （起始符號）

• A B （S → A B）

• A a B （A → a A，替換最右邊的A）

• A a b B （B → b B，替換最右邊的B）

• A a b b B （B → b B，替換最右邊的B）

• A a b b （B → ε，替換最右邊的B）

• a A b b （A → a A，替換最右邊的A）

• a a A b b （A → a A，替換最右邊的A）

• a a b b b b （A → ε 和 B → ε，分別替換最右邊的A和B）

Ⅲ 編譯原理

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

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

(3)編譯原理中什麼叫推導擴展閱讀：

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

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

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

Ⅳ 編譯原理的LL(1)文法是什麼意思

LL(1)的含義：第1個L表明自頂向下分析是從左向右掃描輸入串，第2個L表明分析過程中將用最左到推倒，1表明只需向右看一個符號便可決定如何推倒即選擇哪個產生式（規則）進行推導，類似也可以有LL（k）文法，也就是需要向前查看k個符號才能確定選用哪個產生式。
這是從我們編譯原理課本上抄來的，希望對你有幫助

Ⅳ 什麼叫活前綴,用通俗的話解答下,或者簡單的例子。 這個題是編譯原理的。

活前綴：右句型的前綴，而且其右端不會超過該句型的最右邊句柄的末端。
右句型：最右推導可得到的句型。
最右推導：每步推導都替代最右非終結符的推導。
推導：我們說αBγ推導出αβγ，是說存在產生式B->β。
產生式：左邊為非終結符，右邊為終結符與非終結符組合成的串。
非終結符：是字元串的集合。
終結符：組成語言的詞。如c語言中的2，a，int，if等。
句型：開始符經過若干步推導後得到的串。
前綴：如abc的前綴為a、ab、abc。
開始符：開始符是整個語言的集合。
句柄：非形式的，句柄是和某個產生式右部匹配的字元串，把句柄歸約成產生式左部的非終結符，可以得到最右推導的逆過程的一步。形式的定義為：開始符s經過若干步最右推導得到αBγ，αBγ經過一步最右推導得到αβγ，若γ為終結符的集合，則β為句柄。舉例：
E->E+E|E*E|-E|(E)|id，對於id+id*id，其中一個最右推導為E->E+E->E+E*E->E+E*id->E+id*id->id+id*id。在id+id*id歸約成E+id*id的過程中，最左邊的id是句柄。E+id*id歸約成E+E*id時，最左邊的id是句柄，把E+E*id歸約成E+E*E時，id是句柄。把E+E*E歸約成E+E時E*E是句柄。E+E歸約成E時，E+E是句柄。
歸約：可理解為把產生式右邊的串用產生式左邊的非終結符代替。
注1：再說一下活前綴，舉個例子，比如E+E*E歸約成E+E，句柄是E*E，那麼它的活前綴就是E、E+、E+E、E+E*、E+E*E。又比如id+id*id歸約成E+id*id，句柄是最左邊的id，那麼它的活前綴是id，因為不能超過句柄。
注2：至於為什麼要給出活前綴的定義和如何用歸約的方法實現語法分析，還要進一步學習。

Ⅵ 什麼是*＝>星推導(編譯原理) 星推導和加推導的區別

在編譯原理中，產生式的推導可以細分為  *=>  "星推導"和 +=> "加推導"，

那麼這兩個分別是什麼意思呢？

其實，'*' 和 '+' 這兩個符號是來自 正則表達式 的，正則表達式是什麼大家可以先不了解，弄懂這個問題暫時只需要知道 '*' 和 '+' 這兩個符號的意思就可以了。

符號 * ：[1, n)  1到多

符號 + ：[0, n) 0到多

則， *=>  "星推導" 為對產生式進行1到多次推導； +=> "加推導" 為對產生式進行0到多次推導。

【舉例】

（1）v +＝> w：意為產生式左端的 v 經過1到多次推導後能得到右端的 w

（2）v * => w： 意為產生式左端的 v 經過0到多次推導後能得到右端的w(其實，

                 就是比第（1）條多了一種情況，即 v= w，當 v= w 時，v不需要推導即可得到w，所以推導的次數為0)