上下文有關文法

上下文有關文法（CSG，英語：context-sensitive grammar）是一種形式文法，其中任何產生式規則的左手端和右手端都可以被終結符和非終結符構成的上下文所圍繞。上下文有關文法比上下文無關文法更一般性，但仍足夠有秩序得可以被線性有界自動機所解析。

上下文有關文法的概念是諾姆·喬姆斯基在1950年代介入的，被作為描述自然語言的語法的一種方式，在自然語言中一個單詞是否可以出現在特定位置上，要依賴於上下文。可以被上下文有關文法描述的形式語言叫做上下文有關語言。

形式定義

形式文法 G = (N, Σ, P, S) 如果在 P 中所有的規則都有如下形式，則我們說它是上下文有關的

αAβ → αγβ

這裏的 A ∈ N（就是 A 是單一非終結符），α,β ∈ (N U Σ)*（就是 α 和 β 是非終結符和終結符的字符串）而 γ ∈ (N U Σ)⁺（就是 γ 是非終結符和終結符的非空字符串）。

上下文有關文法的某些定義只要求，對於任何形如 u → v 的產生式規則，u 的長度應當小於或等於 v 的長度。這個看起來要弱些的要求，被斷定為在實際上等價於上面的定義。

此外，還允許如下形式的規則

S → ε

這裏的 ε 表示空串，而 S 不出現在任何規則的右手端。增加空串允許聲明：上下文有關語言是上下文無關語言的真超集，而不是作出弱一些的聲明：沒有 →ε產生式的所有上下文無關文法也是上下文有關文法。

上下文有關這個名稱來源自 α 和 β 形成了 A 的上下文並且決定 A 是否可以被 γ 所替代。這不同於上下文無關文法，它不考慮非終結符的上下文。

如果把向語言增加空串的可能性增加到由不收縮文法所識別的那些字符串（永不包括空串的）中，則在這兩種定義下的語言是相同的。

例子

正規的非上下文無關語言 $\{a^{n}b^{n}c^{n}:n\geq 1\}$可由以下上下文有關文法生成:

1. S → aSBC
2. S → aBC
3. CB → HB
4. HB → HC
5. HC → BC
6. aB → ab
7. bB → bb
8. bC → bc
9. cC → cc

規則1和2允許將 S 拆分為 aⁿ(BC)ⁿ；規則3到5允許隨後將每個 CB 對換位置為 BC（需要用3個規則，因為1個 CB → BC 規則，不能適合 αAβ → αγβ 模式，即產生式左手端只有1個非終結符能被替換）；規則6到9允許將在適當位置上的非終結符 B 或 C 分別替代為其對應的終結符 b 或 c。

aaa bbb ccc 的產生鏈是：

S

→₁ aSBC

→₁ aaSBCBC

→₂ aaaBCBCBC（通過2次規則1和1次規則2，將 S 拆分為 a³(BC)³ 。）

→₃ aaaBHBCBC

→₄ aaaBHCCBC

→₅ aaaBBCCBC

→₃ aaaBBCHBC

→₄ aaaBBCHCC

→₅ aaaBBCBCC

→₃ aaaBBHBCC

→₄ aaaBBHCCC

→₅ aaaBBBCCC （通過3輪依次使用規則3、4、5，在a³(BC)³ 中進行了3次 CB 對換位置為 BC，形成a³B³C³。）

→₆ aaabBBCCC

→₇ aaabbBCCC

→₇ aaabbbCCC

→₈ aaabbbcCC

→₉ aaabbbccC

→₉ aaabbbccc

$\{a^{n}b^{n}c^{n}d^{n}:n\geq 1\}$ 和其他有更多字母的語言可以使用更複雜的上下文有關文法解析。

針對語言 $\{a^{2^{i}}:i\geq 1\}$ 也構造了上下文有關文法，可見於Hopcroft和Ullman在1979年書中例子 9.5 (p. 224)。

範式

不生成空串的所有上下文有關文法都可以被變換成等價的Kuroda範式的文法。這個「等價」意味着兩個文法生成同樣的語言。這種範式一般不是上下文有關的，但卻是不收縮文法。

計算的性質和使用

特定字符串 s 是否屬於特定上下文有關文法 G 的語言的判定問題是 PSPACE-完全的。實際上，甚至有些上下文有關文法的固定文法識別問題也是 PSPACE-完全的。

上下文有關文法的空虛（emptiness）問題（給定上下文有關文法 G，$L(G)=\emptyset$ 嗎？）是不可判定的。

已經證實幾乎所有自然語言一般的都可以用上下文有關文法來刻畫，但是整個 CSG 類好像比自然語言要大。更糟糕的是，因為上述 CSG 的判定問題是 PSPACE-完全的，這使得它們對於實際使用而言是完全不能運作的，因為一般算法將運行指數時間。關於計算語言學的當前進行中的研究關注於公式化是適度上下文有關語言的其他語言類，這種語言如樹-鄰接文法、組合範疇文法、連結上下文無關文法和線性上下文無關重寫系統的判定問題是可行的。這些形式化所生成的語言適當的位於上下文無關和上下文有關語言之間。

參見

• 喬姆斯基譜系
• 上下文有關文法
• 形式文法
• 分析表達式文法
• 隨機上下文無關文法

引用

• Introduction to Languages and the Theory of Computation by John C. Martin McGraw Hill 1996 (2nd edition)