Clasificación de gramáticas libres de contexto

L as gramáticas libres de contexto ( CFG ) se pueden clasificar en función de las siguientes dos propiedades:

1) Basado en el número de strings que genera.

• Si CFG genera un número finito de strings, entonces CFG es no recursivo (o se dice que la gramática es no recursiva)
• Si CFG puede generar un número infinito de strings, se dice que la gramática es gramática recursiva

Durante la compilación, el analizador utiliza la gramática del idioma para crear un árbol de análisis (o árbol de derivación) a partir del código fuente. La gramática utilizada debe ser inequívoca. No se debe utilizar una gramática ambigua para el análisis.
 
2) Basado en el número de árboles de derivación.

• Si solo hay 1 árbol de derivación, el CFG no es ambiguo.
• Si hay más de 1 árbol de derivación, entonces el CFG es ambiguo .

Ejemplos de gramáticas recursivas y no recursivas

Gramáticas recursivas

1) S->SaS    
   S->b

El idioma (conjunto de strings) generado por la gramática anterior es :{b, bab, babab,…}, que es infinito.

2) S-> Aa
   A->Ab|c

El lenguaje generado por la gramática anterior es :{ca, cba, cbba…}, que es infinito.
Nota: Una gramática libre de contexto recursiva que no contiene reglas inútiles necesariamente produce un lenguaje infinito.

Gramáticas no recursivas

   S->Aa
   A->b|c

El lenguaje generado por la gramática anterior es :{ba, ca}, que es finito.

 
Tipos de gramáticas recursivas

Según la naturaleza de la recursividad en una gramática recursiva, un CFG recursivo se puede dividir nuevamente en lo siguiente:

• Gramática recursiva izquierda (habiendo dejado la recursividad)
• Gramática recursiva derecha (que tiene recursividad derecha)
• Gramática recursiva general (con recursividad general)

 
Nota: Una gramática lineal es una gramática libre de contexto que tiene como máximo un no terminal en el lado derecho de cada una de sus producciones.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.