附標文法

附標文法是描述附標語言的形式文法。它們有三個無交集的符號集合: 普通終結符、非終結符和只出現在中間推導中的附標(index)的集合。產生式可以如上下文無關文法那樣把一個非終結符替代為終結符和非終結符的字符串，但是它還把非終結符替代為跟隨著一個附標的非終結符，把跟隨著一個附標的非終結符替代為非終結符。

附標只可以出現在非終結符之後或其他附標之後，所以所有非終結符都可以被看作跟隨它之後的這些附標的所有者，它們形成了一個棧(產生式在非終結符之後增加或去除附標)。

實際上，附標的棧可以計數並記住應用了和以何種次序應用了什麼規則。例如，附標文法可以描述非上下無關語言:

${\displaystyle L=\{a^{n}b^{n}c^{n}|n\geq 1\}}$ ^[1]

通過如下規則(f 和 g 是附標):

${\displaystyle S\to aAfc}$

${\displaystyle A\to aAgc~|~B}$

${\displaystyle Bf\to b}$

${\displaystyle Bg\to bB}$

在中間增長的 g 的棧計數 A 已經被展開來增加一個 a 和一個 c 的次數 (${\displaystyle n-1}$)；在結束時所有 g 變成終結符 b。

判定一個附標文法是否識別一個字符串是NP-完全的。 ^[1]

線性附標文法

Gerald Gazdar 已經定義次級類線性下標文法，通過要求在每個產生式中最多一個非終結符可以被指定為收到這個棧；在普通附標文法中，所有非終結符都收到這個棧的一個複本。他證明了這個新的文法類定義嚴格更小的語言類適度上下文有關語言。在線性附標文法中成員關係可以在多項式時間內判定。^[2]

參見

• 喬姆斯基層級
• 附標語言