TIPOS DE GRAMATICA

Ø TIPO “0” O “No restringida o recursivamente enumerables”: 

     Incluye a todas las gramáticas formales. Estas gramáticas generan todos los lenguajes de ser reconocidos por una maquina de Turing. Y con este lenguaje se hacen los parser de un compilador

     

    CARACTERÍSTICAS: De este tipo es que del lado derecho de cada producción puede empezar con un símbolo terminal o con un no terminal y del lado izquierdo puedes empezar con más de un símbolo no terminal.

    

    RESTRICCIONES: Es que no tiene solamente que el del lado izquierdo debe haber por lo menos un símbolo no terminal  

NOTA: “+” significa “sin incluir la cadena vacía” y significa “incluyendo la cadena vacía”. “I” significa “o”.

Estos lenguajes también son denominados “recursivamente enumerables”

Ø TIPO “1” O “Sensible al contexto”:

Estos tipos de lenguajes se resuelven mediante autómatas lineales limitados. Con este tipo se hacen los parser (analizador sintáctico) de un compilador que transforma su entrada en un árbol de derivación.

El analizador sintáctico convierte el texto de entrada en otras estructuras (comúnmente árboles), que son más útiles para el posterior análisis y capturan la jerarquía implícita de la entrada

CARACTERÍSTICAS: Del lado derecho de cada producción puede empezar con un símbolo terminal o con un no terminal y del lado izquierdo puede empezar con más de un símbolo no terminal.

RESTRICCIONES: el número de no terminales del lado izquierdo de la producción debe ser menor o igual al número de símbolos del lado derecho

NOTA: Los lenguajes regulares y los libres de contexto también se puede resolver mediante autómatas lineales limitados

Ø TIPO “2” O “Libres o Independientes de contexto”:

Estos tipos de lenguajes se resuelven mediante autómatas descendentes y con este tipo de lenguaje se programa los parser en un compilador, permiten describir la mayoría de los lenguajes de programación, de hecho, la sintaxis de la mayoría de los lenguajes de programación está definida mediante gramáticas libres de contexto.

CARACTERISTICAS: Del lado derecho de cada producción puede empezar con símbolo terminal o con un no terminal

Los lenguajes regulares también se pueden resolver mediante autómatas descendentes  

Ø TIPO “3” O “Lenguajes regulares”:

Estos tipos de lenguajes se resuelven mediante autómatas finitos y con este tipo de lenguaje se hacen los scanners. Estas gramaticas se restrigen a aquellas reglas que tienen en la parte izquierda un no terminal, y en la parte derecha un solo terminal, posiblemente seguido de un no terminal y también esta familia de lenguajes pueden ser obtenidas por medio de expresiones regulares

CARACTERÍSTICAS: Del lado derecho de cada producción debe empezar con un símbolo terminal.

Aquí le dejo una tabla donde se representan los tipos de lenguaje según sus características.