附标文法

附标文法是描述附标语言的形式文法。它们有三个无交集的符号集合: 普通终结符、非终结符和只出现在中间推导中的附标(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]