索引式语法

索引式语法是无语境语法的一种泛化，它的非端点都配有标志列表，或索引符号。由索引式语法产生的语言被称为索引式语言。Hopcroft和Ullman的现代定义在Hopcroft和Ullman（1979）之后的当代出版物中。索引语法的正式定义是一个5元组G=⟨N,T,F,P,S⟩其中N是一组变量或非终端符号，T是一组终端符号（字母表），F是一组所谓的索引符号，或索引，S∈N是起始符号，P是一个有限的生成集。在生成和索引语法的推导中，每一个非终端符号A∈N都有一串（栈）σ∈F*的索引符号，用A[σ]表示。终端符号后面不能有索引堆栈。对于索引栈σ∈F*和非终端和终端符号的字符串α∈（N∪T）*，α[σ]表示将[σ]附加到α中每个非终端的结果。例如，如果α等于aBCdE，a,d∈T终端，B,C,E∈N个非终端符号，那么α[σ]表示aB[σ]C[σ]dE[σ]。使用这个符号，P中的每个生产都必须是这样的形式A[σ]→α[σ]，A[σ]→B[fσ]，或者A[fσ]→α[σ]，其中A、B∈N是非终端符号，f∈F是索引，σ∈F*是一串索引符号，而α∈（N∪T）*是一串非终端和终端符号。有些作者在生产规则中用......代替σ来表示索引栈；那么类型1、2、3的规则分别为A[...]→α[...]，A[...]→B[f...]，以及A[f...]→α[...]。除了附加在每个非终端符号上的索引栈之外，派生与无语境语法中的派生相似。当应用像A[σ]→B[σ]C[σ]这样的生产时，A的索引栈被复制到B和C。此外，一个规则可以将索引符号推到栈上，或弹出其最上面（即最左边）的索引符号。形式上，关系⇒（直接派生）在句法形式的集合（N[F*]∪T）*上定义如下。如果A[σ]→α[σ]是类型1的生产，那么βA[φ]γ⇒βα[φ]γ，使用上述定义。如果A[σ]→B[fσ]是一个类型2的生产，那么βA[φ]γ⇒βB[fφ]γ。也就是说，右边的索引栈是通过将f推到左边的栈φ上而得到的。如果A[fσ]→α[σ]是一个类型3的生产，那么βA[fφ]γ⇒βα[φ]γ，再次使用α[σ]的定义。也就是说，xxx个索引f从左手边的堆栈中弹出，然后分配给右手边的每个非终端。像往常一样，派生关系∗⇒被定义为直接派生⇒的反身转义闭合。语言L（G）={w∈T*:S∗⇒w}是可从起始符号派生的所有终端符号串的集合。

历史上，索引语法的概念是由AlfredAho（1968）用不同的形式主义首次提出的。Aho将索引语法定义为一个5元组（N,T,F,P,S），其中N是变量或非终端符号的有限字母表T是终端符号的有限字母表F⊆2N×(N∪T)*是所谓旗子的有限集合（每个旗子本身是所谓索引生产的集合）P⊆N×(NF*∪T)*是生产的有限集合S∈N是起始符号直接衍生如下。一个来自P的生产p=(A→X1η1...Xkηk)与一个非术语A∈N及其（可能是空的）标志串ζ∈F*匹配。在上下文中，γAζδ，通过p，派生为γX1θ1...Xkθkδ，其中θi=ηiζ，如果Xi是一个非终端，否则就是空字。

因此，A的旧标志被复制到由p产生的每个新的非终端。每个这样的生产都可以由霍普克罗夫特/乌尔曼形式主义中的适当的1和2型生产来模拟。一个索引生产p=(A→X1...Xk)∈f匹配Afζ（它来自的标志f必须匹配非终端A后面的xxx个符号），并将剩余的索引字符串ζ复制到每个新的非终端：γAfζδ派生到γX1θ1...Xkθkδ，其中当Xi是终端时，θi是空字，当它是非终端时ζ。每个这样的生产都对应于Hopcroft/Ullman形式主义中的第3类生产。