附标文法

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

参见

• 乔姆斯基层级
• 附标语言

引用

1. Hopcroft, John; Jeffrey Ullman. Introduction to Automata Theory, Languages, and Computation（英语：Introduction to Automata Theory, Languages, and Computation）. Addison-Wesley. 1979: 390. ISBN 020102988X.  引文使用过时参数coauthors (帮助)
2. Gazdar, Gerald. Applicability of Indexed Grammars to Natural Languages. U. Reyle and C. Rohrer (编). Natural Language Parsing and Linguistic Theories. 1988: 69-94. 

外部链接