Ø 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.
