En publicaciones contemporáneas siguiendo a Hopcroft y Ullman (1979), [2] una gramática indexada se define formalmente como un 5-tuplo G = ⟨N, T, F, P, S⟩ donde Tanto en producciones como en derivaciones de gramáticas indexadas, una cadena ("pila") σ ∈ F * de símbolos de índice se adjunta a cada símbolo no terminal A ∈ N, denotado por A [σ].
Los símbolos terminales pueden no ser seguidos por pilas de índice.
Para una pila de índices σ ∈ F * y una cadena α ∈ (N ∪ T) * de símbolos no terminales y terminales, α [σ] denota el resultado de unir [σ] a cada no terminal en α; por ejemplo si α es igual a B C d E con a, d ∈ T terminal, y B, C, E ∈ N símbolos no terminales, entonces α [σ] denota un B [σ] C [σ] d E [σ].
Usando esta notación, cada producción en P tiene que ser de la forma donde A, B ∈ N son símbolos no terminales, f ∈ F es un índice, σ ∈ F * es una cadena de símbolos de índice, y α ∈ (N ∪ T) * es una cadena de símbolos no terminales y terminales.
Cuando una producción como, por ejemplo, A [σ] → B [σ] C [σ] es aplicada, la pila de índice de A se copia a B y C. Además, una regla puede insertar un símbolo de índice en la pila o extraer su "máximo" (es decir, , más a la izquierda) símbolo de índice.
Históricamente, Alfred Aho (1968) introdujo la gramática indexada utilizando un formalismo diferente.
Aho definió una gramática indexada como un 5-tuplo (N, T, F, P, S) donde Las derivaciones directas fueron las siguientes: Este formalismo es, por ejemplo utilizado por Hayashi (1973, p 65-66)..[3] En la práctica, montones de índices pueden contar y recordar qué reglas se aplicaron y en qué orden.
Por ejemplo, las gramáticas indexadas pueden describir el lenguaje contextual de palabras triples {www: w ∈ {a, b} *}: Una derivación de abbabbabb es entonces Como otro ejemplo, la gramática G = ⟨{S, T, A, B, C}, {a, b, c}, {f, g}, P, S⟩ produce el lenguaje {
Hopcroft y Ullman tienden a considerar los lenguajes indexados como una clase "natural", ya que son generados por varios formalismos distintos de las gramáticas indexadas, a saber.
[4] Hayashi generalizó el lema de bombeo a gramáticas indexadas.
[8][9] da un "lema de contracción" para los idiomas indexados.
Gerald Gazdar ha definido una segunda clase, las gramáticas indexadas lineales (LIG), al requerir que se especifique como máximo recibir un no terminal en cada producción, mientras que en una gramática indexada ordinaria, todos los no terminales reciben copias de la pila.
Formalmente, una gramática indexada lineal se define similar a una gramática indexada ordinaria, pero los requisitos de la forma de la producción se modifican para: donde A, B, f, σ, α se usan como arriba, y β ∈ (N ∪ T) * es una cadena de símbolos no terminales y terminales como α.
Además, la relación de derivación directa ⇒ se define similar a la anterior.
El lenguaje {www: w ∈ {a, b} *} es generable por una gramática indexada, pero no por una gramática indexada lineal, mientras que {ww: w ∈ {a, b} *} y {
: n ≥ 1} son generables por una gramática indexada lineal.
| n ≥ 1} como Para derivar la cadena abc tenemos los pasos S [] ⇒ aS [f] c ⇒ aT [f] c ⇒ aT [] bc ⇒ abc.
Los lenguajes indexados linealmente son un subconjunto de los lenguajes indexados y, por lo tanto, todos los LIG se pueden recodificar como IG, lo que hace que los LIG sean estrictamente menos poderosos que los IGs.
Una conversión de un LIG a un IG es relativamente simple.
Las reglas LIG en general se ven aproximadamente como
representan cadenas de símbolos terminales y / o no terminales, y cualquier símbolo no terminal en cualquiera de ellos debe tener una pila vacía, por la definición de un LIG.
Esto es, por supuesto, en contra de cómo se definen los IGs: en un IG, los no terminales cuyas pilas no se empujan o se sacan deben tener exactamente la misma pila que el no terminal reescrito.
que, a pesar de tener pilas no vacías, se comporten como si tuvieran pilas vacías Consideremos la regla
Al convertir esto en un IG, el reemplazo de
no esté vacío, y muestre símbolos de la pila.
Entonces, cuando la pila está vacía, se puede volver a escribir como
Podemos aplicar esto en general para derivar un IG de un LIG.
A diferencia de los IGs de Aho, que distribuyen la pila de símbolos completa a todos los no terminales durante una operación de reescritura, los DIG dividen la pila en subbases y distribuyen las subbases a no terminales seleccionados.