gramatica libre de contexto lenguaje libre de contexto marcela hernandez
TRANSCRIPT
GRAMATICA LIBRE DE CONTEXTO
LENGUAJE LIBRE DE CONTEXTO
Marcela Hernandez
Definición informal de Gramática
Es el mecanismo empleado para establecer la estructura de un lenguaje, es decir las sentencias que lo forman.
Consiste de un conjunto de reglas sintácticas que establecen la forma en la que se pueden combinar los símbolos del alfabeto:
ORACION es un SUJETO y un PREDICADO.
SUJETO es una FRASE NOMINAL.
FRASE NOMINAL es un GRUPO NOMINAL y un CALIFICATIVO que puede o no estar.
GRUPO NOMINAL es un ARTICULO que puede no estar y un NOMBRE.
CALIFICATIVO es un ADJETIVO o una CONJUNCIÓN y una ORACION.
Marcela Hernandez
Gramáticas Formales
Gramática regulares.
Gramáticas independientes de contexto.
Gramáticas sensibles al contexto.
Gramática sin restricciones o de estructura de frase.
Marcela Hernandez
Tipos de GramáticasN. Chomsky clasifica las gramáticas en cuatro tipos:
Gramáticas sin restricciones o gramáticas de estructura de frases (Tipo 0).
Gramáticas sensibles al contexto (Tipo 1).
Gramáticas independientes de contexto (Tipo 2).
Gramáticas regulares (Tipo 3).
Tipo 0Tipo 1 Tipo 2 Tipo 3
Marcela Hernandez
Tipos de Lenguajes
Conforme a la clasificación de N. Chomsky, los lenguajes se clasifican en cuatro tipos:
Lenguajes sin restricciones (Tipo 0).
Lenguajes sensibles (o dependientes) al contexto (Tipo 1).
Lenguajes independientes de contexto (Tipo 2).
Lenguajes regulares (Tipo 3).
Marcela Hernandez
Teoría de Autómatas - Lenguajes Formales
(Máquinas abstractas - Gramáticas Formales)
equivale
Gramática
Lenguajes
describe
genera
Máquina
reconoce
genera
equivale
Marcela Hernandez
Teoría de Autómatas - Lenguajes Formales
(Máquinas abstractas - Gramáticas Formales) Gramáticas Lenguajes Máquinas
Sin restricciones o de Tipo 0
Sin restricciones o de Tipo 0
Máquina de Turing
Sensible al contexto o de Tipo 1
Sensible al contexto o de Tipo 1
Autómata linealmente acotado
Libre de contexto o de Tipo 2
Libre de contexto o de Tipo 2
Autómata a pila
Regular o de Tipo 3
Regular o de Tipo 3
Autómata Finito
Marcela Hernandez
GRAMATICA REGULAR
Es aquella cuyas reglas de reescritura tienen las siguientes restricciones
1. El lado izq. debe de consistir en un solo no termnial
2. El lado derecho de un terminal o un terminal seguido por un no terminal, o cadena vacia
Ej.
Z yX
X y
X λ
Marcela Hernandez
Se interpreta como “puede ser”, “se compone de”, “es sustituida por”.
\ Se interpreta como “o”
Se interpreta como “derivar”, “produce” o “genera”
Marcela Hernandez
Gramatica independiente del contexto
A diferencia de las gramaticas regulares estas gramaticas no tienen reestricciones con respecto al lado derecho de sus reglas de reesritura, aunque se quiere que el lado izq sea un no terminal.
S zMNz
MaMa
Nz
NbNb
Nz
Marcela Hernandez
El termiano independiente del contexto refleja que , como el lado izq de cada regla de reescritura unicamente puede contener un nolo no teminal, la regla puede aplicarse sin importar el contexto donde se encuentre dicho no terminal.
Marcela Hernandez
Árbol de derivación
Un árbol de análisis sintáctico o árbol de derivación es un árbol cuyos nodos representan terminales y no terminales de la gramática, donde el nodo raíz es el símbolo de inicio y los hijos de cada nodo no terminal son símbolos que remplazan a ese no terminal en la derivación.
Ningún símbolo terminal puede ser nodo interior del árbol , ni ningún símbolo no terminal puede ser una hoja.
Marcela Hernandez
Marcela Hernandez
S
M N Z
x Z b b X N
ab x a b x
SMNZMxZbNbZXNZbaXxNabx
FORMA NORMAL DE CHOMSKY
Si L es un lenguaje independiente del contexto que no tiene la cadena vacia, entonces existe una gramatica G independiente del contexto tal que G(L)=L y el lado derecho de cada regla de reesritura en G consiste en un solo terminal o exactamente dos no teminales.
S XM
MSY
Xx
Yy
Marcela Hernandez
FORMA NORMAL DE GREIBACH
Se dice que una gramática independiente del contexto (GIC) está en Forma normal de Greibach (FNG), si todas y cada una de sus reglas de producción tienen un consecuente que empieza por un carácter del alfabeto, también llamado símbolo terminal. Formalmente, cualquiera de las reglas tendrá la estructura:
A − > aw
Donde "A" es el antecedente de la regla, que en el caso de las GIC debe ser necesariamente un solo símbolo auxiliar. Por su parte, "a" es el mencionado comienzo del consecuente y, por tanto, un símbolo terminal. Finalmente, "w" representa una concatenación genérica de elementos gramaticales, esto es, una sucesisión exclusivamente de auxiliares, inclusive, pudiera ser la palabra vacía; en este caso particular, se tendría una regla llamada "terminal":
A − > a
Marcela Hernandez
Definición: Una Gramática Libre de Contexto (GLC) está en Forma Normal de Greibach (FNG) si todas las producciones son de la forma:
A aB1B2…..Bk
Donde A es un símbolo no Terminal, a es un símbolo Terminal y B1B2…..Bk son símbolos no Terminales.
Ejemplo de FNG:
S → aSB | aB
B → b
Marcela Hernandez
ELIMINACION DE FACTORES COMUNES IZQUIERDOS
Marcela Hernandez
Se trata de rescribir las producciones de la gramática con igual comienzo para retrasar la decisión hasta haber visto lo suficiente de la entrada como para elegir la opción correcta
Procedimiento:
Marcela Hernandez
A := αβ1 |αβ2 | … | αβn | δi
A := αA’ | δiA’ := β1 | β2 | … | βn
ELIMINACION DE RECURSIVIDAD IZQUIERDATipos de recursividad
Directa. Una gramática G es recursiva si tiene alguna regla de producción que sea recursiva por la izquierda
Indirecta. Si, a partir de una forma sentencial que empieza por un no terminal se puede derivar una nueva forma no sentencial donde reaparece al principio el no terminal
Marcela Hernandez
A := Aα
Aα =>* Aβα
Eliminación de la recursividad
Directa
Indirecta
Marcela Hernandez
A := Aα | βA := βA’A’ := αA’A’ := ε
Ordenar No terminales: A1, A2, … AnFor i := 1 To n DoFor j := 1 To i – 1 DoSustituir cada Ai := Aj β por Ai := α1 β | α2 β | αk βdonde Aj := α1 | α2 | … | αk producciones actuales de AjEliminar la recursividad directa de Ai
ELIMINACION DE AMBIGÛEDAD
Marcela Hernandez
Marcela Hernandez
TIPOS DE AMBIGÜEDAD:
Dentro del estudio de gramáticas existen dos tipos fundamentales de ambigüedad, los cuales son:
Ambigüedad Inherente: Las gramáticas que presentan este tipo de ambigüedad no pueden utilizarse para lenguajes de programación, ya que por más transformaciones que se realicen sobre ellas, NUNCA se podrá eliminar completamente la ambigüedad que presentan.
Ambigüedad Transitoria: Este tipo de ambigüedad puede llegar a ser eliminada realizando una serie de transformaciones sobre la gramática original. Una vez que se logra lo anterior, la gramática queda lista para ser reconocida por la mayor parte de los analizadores sintácticos.
Autómata de pila
Un autómata con pila o autómata de pila o autómata a pila o autómata apilador es un modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto y determina si esa cadena pertenece al lenguaje que el autómata reconoce.
Marcela Hernandez
Marcela Hernandez
Marcela Hernandez
CaracterísticasLa Pila funciona de manera que el último carácter que se almacena en ella es el primero en salir (ordenLIFO).
Un aspecto crucial de la pila es que sólo podemos modificar el “tope” de la pila, que es el extremo por donde entran o salen los caracteres.
Los caracteres a la mitad de la pila no son accesibles sin quitar antes los que están encima de ellos
La pila tendrá un alfabeto propio que puede o no coincidir con el alfabeto de la palabra de entrada.
Esto se justifica porque puede ser necesario introducir en la pila caracteres especiales usados como separadores según las necesidades de diseño del autómata
Marcela Hernandez
Marcela Hernandez
Principio de Pre Análisis
Técnica que permite a los autómatas de pila observar uno o varios símbolos más allá de donde se encuentra la cabeza lectora del autómata, pero sin leerlos realmente.
Esta técnica permite superar el no determinismo de algunos autómatas de pila.
Marcela Hernandez
LENGUAJES NO REGULARES
Existen lenguajes no regulares, estos no pueden ser representados por medio de una expresion ni por un automata.
El Lema del bombeo es una técnica utililzada para demostrarlo
Marcela Hernandez