Indexed grammar

Indexed grammars are a generalization of context-free grammars in that nonterminals are equipped with lists of flags, or index symbols. The language produced by an indexed grammar is called an indexed language.

In contemporary publications following Hopcroft and Ullman (1979), an indexed grammar is formally defined a 5-tuple G = ⟨N,T,F,P,S⟩ where

In productions as well as in derivations of indexed grammars, a string ("stack") σ ∈ F^* of index symbols is attached to every nonterminal symbol A ∈ N, denoted by A[σ]. Terminal symbols may not be followed by index stacks. For an index stack σ ∈ F^* and a string α ∈ (N ∪ T)^* of nonterminal and terminal symbols, α[σ] denotes the result of attaching [σ] to every nonterminal in α; for example if α equals $a B C d E$ with a,d ∈ T terminal, and $B, C, E \in N$ nonterminal symbols, then α[σ] denotes $a B [σ] C [σ] d E [σ].$ Using this notation, each production in P has to be of the form

where A, B ∈ N are nonterminal symbols, f ∈ F is an index, σ ∈ F^* is a string of index symbols, and α ∈ (N ∪ T)^* is a string of nonterminal and terminal symbols. Some authors write ".." instead of "σ" for the index stack in production rules; the rule of type 1, 2, and 3 then reads $A [..]\to α [..], A [..]\to B [f ..]$ , and $A [f ..]\to α [..]$ , respectively.

Derivations are similar to those in a context-free grammar except for the index stack attached to each nonterminal symbol. When a production like e.g. A[σ] → B[σ]C[σ] is applied, the index stack of A is copied to both B and C. Moreover, a rule can push an index symbol onto the stack, or pop its "topmost" (i.e., leftmost) index symbol.

Formally, the relation ⇒ ("direct derivation") is defined on the set (N[F^*]∪T)^* of "sentential forms" as follows:

...
Wikipedia