Jerarquía de Jerarquía de ChomskyChomsky

Roberto Daniel Pantoja TovarRoberto Daniel Pantoja TovarDavid del Ángel RodríguezDavid del Ángel RodríguezKaren Ramírez RodriguezKaren Ramírez Rodriguez

IntroducciónIntroducción

En l ingüística la En l ingüística la jerarquía de jerarquía de Chomsky es una Chomsky es una clasif icación clasif icación jerárquica de jerárquica de distintos tipos de distintos tipos de gramáticas formales gramáticas formales que generan que generan lenguajes formales. lenguajes formales. Esta jerarquía fue Esta jerarquía fue descrita por Noam descrita por Noam Chomsky en 1956.Chomsky en 1956.

Expresiones regularesExpresiones regulares Una expresión regular, a menudo l lamada también Una expresión regular, a menudo l lamada también

patrón, es una expresión que describe un patrón, es una expresión que describe un conjunto de cadenas sin enumerar sus elementosconjunto de cadenas sin enumerar sus elementos

Para poder realizar expresiones regulares Para poder realizar expresiones regulares debemos tomar en cuenta esto:debemos tomar en cuenta esto:

Sea S y R símbolos cualquieraSea S y R símbolos cualquiera 1. entonces R y/o S son expresiones regulares1. entonces R y/o S son expresiones regulares 2. R*S=RS es una expresión regular2. R*S=RS es una expresión regular 3. (R) es una expresión regular3. (R) es una expresión regular 4. nulo (vacío) es una expresión regular4. nulo (vacío) es una expresión regular 5. R*=a que R puede repetirse 0 muchas veces5. R*=a que R puede repetirse 0 muchas veces 6. R+=R(R*) R se repite 1 o más veces6. R+=R(R*) R se repite 1 o más veces 7. R?=R o 7. R?=R o vacío quierevacío quiere decir que R puede decir que R puede venir venir 1 1

vez o no venir nuncavez o no venir nunca

EjemplosEjemplos :: Supongamos que se desea generar una expresión regulara Supongamos que se desea generar una expresión regulara

que reconozca un numero de cédula que reconozca un numero de cédula La solución seriaLa solución seria Formato de no. De cedula =A1-12354544Formato de no. De cedula =A1-12354544 Expresión regular que reconoce éste tipo de informaciónExpresión regular que reconoce éste tipo de información LD-DD*LD-DD* DondeDonde L representa al conjunto de todas las letras del alfabetoL representa al conjunto de todas las letras del alfabeto D representa el conjunto de todos los decimalesD representa el conjunto de todos los decimales Ejemplo2Ejemplo2 Supongamos que se desea generar una expresión regular Supongamos que se desea generar una expresión regular

que reconozca números decimalesque reconozca números decimales DD*.DD*DD*.DD* Aquí decimos que puede venir un digito (D) seguido de otro Aquí decimos que puede venir un digito (D) seguido de otro

digito que puede venir 0 o muchas veces (D*) hágase notar digito que puede venir 0 o muchas veces (D*) hágase notar que el (.) que se encuentra no es de concatenación sino que que el (.) que se encuentra no es de concatenación sino que es el punto decimal, después de esto viene otro digito (D) es el punto decimal, después de esto viene otro digito (D) obligatorio ya que no se acepta 3. ya que no seria un número obligatorio ya que no se acepta 3. ya que no seria un número decimal.decimal.

Jerarquía de ChomskyJerarquía de Chomsky Clasif ico las gramáticas en 4 familias.Clasif ico las gramáticas en 4 familias.- Las no restringidas (Tipo Las no restringidas (Tipo

0)0)- Sensibles al contexto (Tipo Sensibles al contexto (Tipo

1)1)- Independientes del contexto (Tipo 2)Independientes del contexto (Tipo 2)- Gramáticas Regulares (Tipo Gramáticas Regulares (Tipo

3)3)

Descripción de los t ipos de Descripción de los t ipos de jerarquíasjerarquías

Tipo3: lenguajes Tipo3: lenguajes regularesregulares

Estos t ipos de lenguajes se resuelven Estos t ipos de lenguajes se resuelven mediante autómatas f initos.mediante autómatas f initos.

Característ icasCaracteríst icas Del lado derecho de cada producción debe Del lado derecho de cada producción debe

empezar con un símbolo terminalempezar con un símbolo terminal Ejemplo:Ejemplo:

Con éste t ipo de lenguaje se hacen los scannersCon éste t ipo de lenguaje se hacen los scanners

Tipo2: Libres o Tipo2: Libres o Independientes de contextoIndependientes de contexto

Estos tipos de lenguajes se resuelven mediante Estos tipos de lenguajes se resuelven mediante autómatas descendentesautómatas descendentes

CaracterísticasCaracterísticas Del lado derecho de cada producción puede Del lado derecho de cada producción puede

empezar con un símbolo terminal o con un no empezar con un símbolo terminal o con un no terminalterminal

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

Ejemplo:Ejemplo:

Con éste tipo de lenguaje se programa los parser en un compiladorCon éste tipo de lenguaje se programa los parser en un compilador

Tipo1: Sensibles o Tipo1: Sensibles o Dependientes de contextoDependientes de contexto

Estos tipos de lenguajes se resuelven mediante Estos tipos de lenguajes se resuelven mediante autómatas l ineales l imitadosautómatas l ineales l imitados

CaracterísticasCaracterísticas Del lado derecho de cada producción puede Del lado derecho de cada producción puede

empezar con un símbolo terminal o con un no empezar con un símbolo terminal o con un no terminal y del lado izquierdo puede empezar con terminal y del lado izquierdo puede empezar con más de un símbolo no terminal.más de un símbolo no terminal.

RestricciónRestricción El número de no terminales del lado izquierdo de El número de no terminales del lado izquierdo de

la producción debe ser menor o igual al número de la producción debe ser menor o igual al número de símbolos del lado derechosímbolos del lado derecho

NotaNota Los lenguajes regulares y los l ibres de contexto Los lenguajes regulares y los l ibres de contexto

también se pueden resolver mediante autómatas también se pueden resolver mediante autómatas l ineales l imitados.l ineales l imitados.

Ejemplo:Ejemplo:

Con éste tipo de lenguajes se hacen los parser de un compilador.Con éste tipo de lenguajes se hacen los parser de un compilador.Un analizador sintáctico (en inglés Un analizador sintáctico (en inglés parserparser ) es una de las partes ) es una de las partes de de un compilador que transforma su entrada en un árbol de un compilador que transforma su entrada en un árbol de derivación.derivación.El análisis sintáctico convierte el texto de entrada en otras El análisis sintáctico convierte el texto de entrada en otras estructuras (comúnmente árboles), que son más úti les para el estructuras (comúnmente árboles), que son más úti les para el posterior análisis y capturan la jerarquía implícita de la entrada.posterior análisis y capturan la jerarquía implícita de la entrada.

Tipo0: Recursivamente Tipo0: Recursivamente enumerableenumerable

Estos tipos de lenguajes se resuelven mediante Estos tipos de lenguajes se resuelven mediante maquinas de Turínmaquinas de Turín

CaracterísticasCaracterísticas Del lado derecho de cada producción puede Del lado derecho de cada producción puede

empezar con un símbolo terminal o con un no empezar con un símbolo terminal o con un no terminal y del lado izquierdo puede empezar con terminal y del lado izquierdo puede empezar con más de un símbolo no terminal.más de un símbolo no terminal.

Restricción Restricción No tiene ninguna restricción solamente que del No tiene ninguna restricción solamente que del

lado izquierdo debe haber por lo menos un lado izquierdo debe haber por lo menos un símbolo no terminalsímbolo no terminal

NotaNota Todos los demás tipos de lenguajes también se Todos los demás tipos de lenguajes también se

pueden resolver mediante maquinas de Turínpueden resolver mediante maquinas de Turín

Ejemplo:Ejemplo:

Con éste tipo de lenguajes se hacen los parser de un compiladorCon éste tipo de lenguajes se hacen los parser de un compilador