編譯原理單詞的文法

Ⅰ 編譯原理：LL, LR 文法淺析

在編譯原理的學習中，文法概念常令人困惑，尤其是LL(k)、SLR(k)、LALR(k)、LR(k)等。首先，澄清一下，context-free grammar（上下文無關文法）並不等同於無二義性文法。上下文無關文法允許任意替換，每個非終結符號下的產生式是等價的，即使在解析過程中，主語或賓語的改變也不會影響合法性。二義性則是文法內部的一種特性。

關鍵的疑惑在於文法類型的相互關系。LL和LR演算法之間的差異主要體現在解析過程的策略上：LL演算法（類似於先序遍歷）在線性推進輸入時，通過有限的前瞻預測子節點的父節點，而LR（如後序遍歷）則在完全看到子節點後決定插入父節點。LR(k)文法在前瞻相同的情況下，由於看完整個子結構，優勢更明顯。

LL(0)和LR(0)分別代表在解析初期不依賴前瞻信息和僅根據當前輸入的子結構做出決策，LL(0)由於缺乏前瞻無實用價值，而LR(0)雖然簡單，卻能處理更多文法。SLR(0)和LR(0)的不同在於前瞻字元的處理方式，理論上SLR(0)等於LR(0)。然而，判斷文法是否無二義性是一個復雜問題，LL和LR演算法可以在無沖突的文法中保證線性復雜度，但並非所有無二義文法都能被它們處理。

GLR解析器可以處理任意CFG，但不直接處理文法的二義性問題，它通過全面遍歷來生成可能的抽象語法樹。工業界中的編譯器在實際應用中可能需要結合LL和LR的特性，如LR處理運算符優先順序，LL優化錯誤報告，通過層次化設計來平衡性能和復雜性。在編寫自定義解析器時，需要通過測試來確保正確性，如與已有的解析器生成的AST序列進行對比。

Ⅱ 編譯原理的LL（1）文法是什麼意思

1.文法不含左遞歸，沒有公共左因子
2.對於文法中的每個非終結符A的產生式的候選首符集兩兩不相交。
3.對於文法中的每個非終結符A，它存在某個候選首符集包括ε，則FIRST（A）∩FOLLOW（A）=空
滿足以上條件的文法為LL（1）文法

Ⅲ 編譯原理文法定型規則

編譯原理中的文法定型規則是指將任意上下文無關文法（Context-Free Grammar, CFG）轉化為某個特定形式的上下文無關文法的規則。這個特定形式的上下文無關文法通常是Chomsky範式或Greibach範式。
以下是文法定型規則的具體步驟：
1. 消除文法中的ε產生式（epsilon-proction），即產生空串的產生式。
2. 消除文法中的單一產生式（unit-proction），即右側只有一個非終結符的產生式。
3. 消除文法中的左遞歸產生式（left-recursive proction）。
4. 將文法轉化為無二義性的文法。
上述步驟的具體實現方法如下：
1. 消除文法中的ε產生式：
1. 對於所有含有ε產生式的非終結符，將其ε產生式刪除。
2. 對於所有產生式右側含有已刪除非終結符的產生式，將其右側的已刪除非終結符替換為ε。
3. 重復執行上述步驟，直到所有含有ε的產生式都被消除為止。
2. 消除文法中的單一產生式：
1. 對於所有單一產生式A → B，將其刪除。
2. 對於所有產生式右側含有被刪除產生式的非終結符的產生式，將其替換為被刪除產生式的右側符號B。
3. 重復執行上述步驟，直到所有單一產生式都被消除為止。
3. 消除文法中的左遞歸產生式：
1. 對於每個非終結符A，將所有形如A → Aα的產生式改為A → β1A'、A' → β2A' | ε的形式。
2. 其中，β1是所有右側不含有A的A產生式的右側符號串，β2是所有右側含有A的A產生式的右側符號串，α是所有產生式右側不含有A的符號串。
3. 重復執行上述步驟，直到所有左遞歸產生式都被消除為止。
4. 將文法轉化為無二義性的文法：
1. 消除文法中的二義性產生式，即產生式右側存在兩個或以上的不同符號串。
2. 引入新的非終結符，將二義性產生式拆分為多個不同的產生式。
3. 對於所有產生式右側含有多個符號的產生式，使用括弧或其他符號進行明確區分。
4. 重復執行上述步驟，直到文法不存在二義性為止。
以上是文法定型規則的具體步驟和實現方法。通過執行這些步驟，可以將任意上下文無關文法轉化為某個特定形式的上下文無關文法，從而方便進行語法分析和編譯。

Ⅳ 什麼是文法(編譯原理)

【定義】

文法G定義為四元組（VN，VT，P，S）

其中 VN   ：非終結符號(即語法變數)集

        VT   ： 終結符號集

                   VN∩VT =Φ，令V= VN∪VT，V稱為文法G的字母表或字匯表。

        P  ：產生式(α→β)集

        S ：開始符號，且S∈VN ，S至少要在一條規則的左部出現。

【約定】

一般地，文法G的 四元組 不用全部給出 ，而只將產生式寫出。

約定：

    （1）第一條產生式的左部是開始符號

    （2）用尖括弧括起來的（或 大寫字母 ）是非終結符號

    （3）不用尖括弧括起來（或 小寫字母 ）是終結符號

    （4）還有一種習慣寫法，即 G[S] ，其中 S 是 開始符號 。

【舉例】

    例: G=（VN，VT，P，S）

           其中  VN={S}，

           VT ={0，1}，

           P={S→0S1，S→01}

           S是開始符號

Ⅳ 編譯原理中文法二義性問題

二義性文法

【定義】 若文法中存在這樣的句型，它具有兩棵不同的語法樹，則稱該文法是二義性文法。

二義性文法會引起歧義，應盡量避免之！

E E

E + E E * E

i E * E E + E i

i i i i

都可以表示i+i*i

所以G(E)：E -> E+E | E*E | (E) | i ;文法具有二義性。

文法二義性的消除：

【方法1】不改變文法的原有規則,加進一些非形式規定。

加進運算符的優先順序和結合規則對G(E)，規定*優於+，*和+服從左結合

【方法2】構造一個等價的無二義性文法，將排除 二義性的規則合並到文法中

G(E) -> G´(E) : E -> E+T | T T -> T*F | F F -> (E) | i ;

Ⅵ 編譯原理的文法

「文法是以有窮的集合刻畫無窮的集合的一個工具」，有窮的集合應該是已經出現的，人們普遍接受的詞、片語或句子，無窮的集合就是有窮的集合的詞、片語或句子，創造新的集合過程和結果，有待進一步認識接受。
我們的文法規定內涵是已經明確定義的和正在定義（聲明）的內容。反映到計算機語言程序中就是編程時已經定義的和正在定義（聲明）的字元或字元串。文法可以以表的形式，或詞典形式存放。

Ⅶ 編譯原理中，形式語言里怎麼區分2型文法與3型文法

二型文法，也稱為上下文無關文法，其產生式的特點是左部僅包含一個非終結符。例如，給定的文法可以表示為：S->Ac, S->Sc, A->ab, A->aAb。這些產生式定義了如何從初始符號S推導出字元串，其中A, S是文法中的非終結符，a, b, c是終結符。

三型文法則更具體地分為幾種類型：左線形文法、右線形文法和正規文法。左線形文法的產生式右部要麼為空，要麼只有一個非終結符且位於最左端，如S->aS, B->cB。右線形文法則相反，其產生式右部要麼為空，要麼只有一個非終結符且位於最右端，如B->cB, A->Bb。正規文法是右線形文法的一個子集，其產生式右部只能是空串、一個終結符或一個終結符後接一個非終結符，如S->aS, A->bA, B->cB, B->c, A->Bb。

在文法分類中，所有的三型文法都屬於二型文法。這意味著所有三型文法的產生式結構都滿足二型文法的定義。因此，二型文法的范圍比三型文法廣，涵蓋了所有的三型文法以及更多類型的產生式。通過理解這兩種文法的區別，可以更好地分析和設計形式語言。

值得注意的是，二型文法允許產生式中非終結符出現在右部的任意位置，這為定義更復雜的語言提供了靈活性。而三型文法則通過限制產生式右部的形式，使得生成的語言更加受限，適用於定義更簡單、更直接的字元串。

在實際應用中，理解二型文法和三型文法的區別有助於構建解析器和編譯器，尤其是在處理自然語言處理和編程語言編譯時，這些文法類型對於語法分析至關重要。

總之，二型文法與三型文法之間的主要差異在於產生式右部非終結符的位置和數量的限制，這直接關繫到生成語言的復雜度和靈活性。通過掌握這些文法類型，可以更有效地構建和優化形式語言。

Ⅷ 編譯原理簡單文法歸約計算

編譯原理中的語法和文法是不一樣的，但卻融會貫通。
在計算機科學中，文法是編譯原理的基礎，是描述一門程序設計語言和實現其編譯器的方法。
文法分成四種類型，即0型、1型、2型和3型。這幾類文法的差別在於對產生式施加不同的限制。
形式語言，這種理論對計算機科學有著深刻的影響，特別是對程序設計語言的設計、編譯方法和計算復雜性等方面更有重大的作用。
多數程序設計語言的單詞的語法都能用正規文法或3型文法（3型文法G=(VN，VT，P，S)的P中的規則有兩種形式：一種是前面定義的形式，即：A→aB或A→a其中A，B∈VN ，a∈VT*，另一種形式是：A→Ba或A→a，前者稱為右線性文法，後者稱為左線性文法。正規文法所描述的是VT*上的正規集）來描述。
四個文法類的定義是逐漸增加限制的，因此每一種正規文法都是上下文無關的，每一種上下文無關文法都是上下文有關的，而每一種上下文有關文法都是0型文法。稱0型文法產生的語言為0型語言。上下文有關文法、上下文無關文法和正規文法產生的語言分別稱為上下文有關語言、上下文無關語言和正規語言。

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

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

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

產生式

可以簡寫為：

如上例中，

可以簡寫為：

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

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

推導的反過程稱為 歸約 。

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

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

例
文法

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

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

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

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

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

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

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

例：（右線性文法）

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

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

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

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

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

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

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

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