附标文法 附标文法是描述附标语言的形式文法它们有三个无交集的符号集合 普通终结符非终结符和只出现在中间推导中的附标index的集合产生式可以如上下文无关文法那样把一个非终结符替代为终结符和非终结符的字符串但是它还把非终结符替代为跟随着一个附标的非终结符把跟随着一个附标的非终结符替代为非终结符 附标只可以出现在非终结符之后或其他附标之后所以所有非终结符都可以被看作跟随它之后的这些附标的所有者它们形成了一个栈产生式在非终结符之后增加或去除附标 实际上附标的栈可以计数并记住应用了和以何种次序应用了什么规则例如附标文法可以描述非上下无关语言 L   a n b n c n  n    displaystyle Lanbncnngeq  通过如下规则f 和 g 是附标 S  a A f c displaystyle Sto aAfc A  a A g c      B displaystyle Ato aAgcB B f  b displaystyle Bfto b B g  b B displaystyle Bgto bB 在中间增长的 g 的栈计数 A 已经被展开来增加一个 a 和一个 c 的次数  n   displaystyle n 在结束时所有 g 变成终结符 b 判定一个附标文法是否识别一个字符串是NP完全的