附标文法

维基百科，自由的百科全书

附标文法是描述附标语言的形式文法。它们有三个无交集的符号集合: 普通终结符、非终结符和只出现在中间推导中的附标(index)的集合。产生式可以如上下文无关文法那样把一个非终结符替代为终结符和非终结符的字符串，但是它还把非终结符替代为跟随着一个附标的非终结符，把跟随着一个附标的非终结符替代为非终结符。

附标只可以出现在非终结符之后或其他附标之后，所以所有非终结符都可以被看作跟随它之后的这些附标的所有者，它们形成了一个栈(产生式在非终结符之后增加或去除附标)。

实际上，附标的栈可以计数并记住应用了和以何种次序应用了什么规则。例如，附标文法可以描述非上下无关语言:

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

通过如下规则(f 和 g 是附标):

$S\to aAfc$

$A\to aAgc ~|~ B$

$Bf\to b$

$Bg\to bB$

在中间增长的 g 的栈计数 A 已经被展开来增加一个 a 和一个 c 的次数 ( $n - 1$ )；在结束时所有 g 变成终结符 b。

判定一个附标文法是否识别一个字符串是NP-完全的。 ^[1]

[编辑] 线性附标文法

Gerald Gazdar 已经定义次级类线性下标文法，通过要求在每个产生式中最多一个非终结符可以被指定为收到这个栈；在普通附标文法中，所有非终结符都收到这个栈的一个复本。他证明了这个新的文法类定义严格更小的语言类适度上下文有关语言。在线性附标文法中成员关系可以在多项式时间内判定。^[2]

[编辑] 参见

[编辑] 引用

^ ^1.0 ^1.1 Hopcroft, John，Jeffrey Ullman（1979）．Introduction to automata theory, languages, and computation．Addison-Wesley，390．ISBN 020102988X．
^ Gazdar, Gerald（1988）．“Applicability of Indexed Grammars to Natural Languages”，U. Reyle and C. Rohrer 编：Natural Language Parsing and Linguistic Theories，69-94．

[编辑] 外部链接

"NLP in Prolog" chapter on indexed grammars and languages

自动机理论: 形式语言和形式文法
乔姆斯基层级	文法	语言	极小自动机
类型 0	无限制	递归可枚举	图灵机
n/a	(无公用名)	递归	判定器
类型 1	上下文有关	上下文有关	线性有界
n/a	附标	附标	嵌套堆栈
n/a	树-邻接	适度上下文有关	嵌入下推
类型 2	上下文无关	上下文无关	非确定下推
n/a	确定上下文无关	确定上下文无关	确定下推
类型 3	正则	正则	有限
每个语言或文法范畴都是其直接上面的范畴的真子集。

[_note-Hopcroft_and_Ullman-0] 1.0 ^1.1 Hopcroft, John，Jeffrey Ullman（1979）．Introduction to automata theory, languages, and computation．Addison-Wesley，390．ISBN 020102988X．

[_note-gazdar1998-1] Gazdar, Gerald（1988）．“Applicability of Indexed Grammars to Natural Languages”，U. Reyle and C. Rohrer 编：Natural Language Parsing and Linguistic Theories，69-94．

[1]

[2]