上下文無關文法簡介

---

---

定義 − 上下文無關文法 (CFG) 由一組有限的語法規則組成，是一個四元組 (N, T, P, S)，其中

• N 是一組非終結符。

• T 是一組終結符，其中 N ∩ T = NULL。

• P 是一組規則，P: N → (N ∪ T)*，即產生式規則 P 的左邊沒有任何右上下文或左上下文。

• S 是起始符。

示例

• 文法 ({A}, {a, b, c}, P, A)，P：A → aA，A → abc。
• 文法 ({S, a, b}, {a, b}, P, S)，P：S → aSa，S → bSb，S → ε
• 文法 ({S, F}, {0, 1}, P, S)，P：S → 00S | 11F，F → 00F | ε

生成推導樹

推導樹或語法分析樹是一個有序的根樹，它以圖形方式表示從上下文無關文法匯出的字串的語義資訊。

表示技術

• 根頂點 − 必須用起始符標記。

• 頂點 − 用非終結符標記。

• 葉子 − 用終結符或 ε 標記。

如果 S → x₁x₂ …… x_n 是 CFG 中的產生式規則，則語法分析樹/推導樹如下所示：

有兩種不同的方法可以繪製推導樹：

自頂向下方法：

• 從起始符 S 開始

• 使用產生式向下到樹葉

自底向上方法：

• 從樹葉開始

• 向上進行到根，即起始符 S

樹的推導或結果

語法分析樹的推導或結果是從左到右連線樹葉的標籤而獲得的最終字串，忽略空值。但是，如果所有葉子都是空值，則推導為空值。

示例

設 CFG {N,T,P,S} 為

N = {S}，T = {a, b}，起始符 = S，P = S → SS | aSb | ε

來自上述 CFG 的一個推導是“abaabb”

S → SS → aSbS → abS → abaSb → abaaSbb → abaabb

句子形式和部分推導樹

部分推導樹是推導樹/語法分析樹的子樹，其所有子節點都在子樹中或都不在子樹中。

示例

如果在任何 CFG 中，產生式為：

S → AB，A → aaA | ε，B → Bb | ε

則部分推導樹可以是：

如果部分推導樹包含根 S，則稱為句子形式。上述子樹也處於句子形式。

字串的最左推導和最右推導

• 最左推導 − 最左推導是透過在每一步都應用產生式到最左邊的變數而獲得的。

• 最右推導 − 最右推導是透過在每一步都應用產生式到最右邊的變數而獲得的。

示例

設 CFG 中的任何一組產生式規則為

X → X+X | X*X |X| a

在字母表 {a} 上。

字串 "a+a*a" 的最左推導可能是：

X → X+X → a+X → a + X*X → a+a*X → a+a*a

上述字串的分步推導如下所示：

上述字串 "a+a*a" 的最右推導可能是：

X → X*X → X*a → X+X*a → X+a*a → a+a*a

上述字串的分步推導如下所示：

左遞迴文法和右遞迴文法

在上下文無關文法 G 中，如果存在形式為 X → Xa 的產生式，其中 X 是非終結符，而 ‘a’ 是終結符串，則稱為左遞迴產生式。具有左遞迴產生式的文法稱為左遞迴文法。

並且，如果在上下文無關文法 G 中，如果存在形式為 X → aX 的產生式，其中 X 是非終結符，而 ‘a’ 是終結符串，則稱為右遞迴產生式。具有右遞迴產生式的文法稱為右遞迴文法。