GRAMÁTICAS INDEPENDIENTES DEL CONTEXTO

TEMA 6

GRAMÁTICAS INDEPENDIENTES DEL CONTEXTO

TEMA 6.- GRAMÁTICAS INDEPENDIENTES DEL CONTEXTO
6.1. Gramáticas independientes del contexto.
6.2. Limpieza de Gramáticas Independientes del contexto.
6.3. Gramáticas limpias y gramáticas sucias.
6.4. Limpieza de gramáticas
6.4.1. Teorema de los símbolos vivos
6.4.2.Teorema de los símbolos accesibles
6.4.3. Análisis automático de lalimpieza de gramáticas
6.5 Gramáticas bien formadas
6.6. Formas Normales de Gramáticas Independientes del
contexto.

6.6.1. Forma Normal de Chomsky (FNC)
6.6.2. Forma Normal de Greibach (FNG)

TALF. Tema6

nº 2

6.1. Gramáticas independientes del contexto.

 Técnicas para preparar una gramática tipo 2 para
ser tratada eficientemente por un autómata con
pila:
 Gramáticas limpias
Gramáticas bien formadas
 Formas normales de Chomsky y Greibach

TALF. Tema6

nº 3

6.2. Limpieza de Gramáticas Independientes del contexto.

 Las gramáticas de los lenguajes de programación
están formadas por un conjunto de reglas BNF,
cuyo número suele ser bastante amplio, lo cual
incide en la ocultación de distintos problemas que

pueden producirse, tales como
tener reglas queproduzcan símbolos que no se usen



después, o
 que nunca se llegue a cadenas terminales.



Todo esto se puede solventar realizando la
transformación de la gramática inicial “sucia” a una
gramática “limpia”.

TALF. Tema6

nº 4

6.3. Gramáticas limpias y gramáticas sucias.


Definiciones.
 Símbolo muerto (superfluo): es un símbolo no terminal que
no genera ningunacadena de símbolos terminales.
 Símbolo vivo: es un símbolo no terminal del cual se puede
derivar una cadena de símbolos terminales. Todos los
símbolos terminales son símbolos vivos. Es decir son
símbolos vivos lo que no son muertos.
 Símbolo inaccesible: es un símbolo no terminal al que no
se puede llegar por medio de producciones desde el símbolo
inicial.
 Símbolo accesible: es un símboloque aparece en una
cadena derivada del símbolo inicial. Es decir, aquel símbolo
que no es inaccesible.
 Símbolo extraño: se denomina así a todo símbolo muerto o
inaccesible.
 Gramática sucia: es toda gramática que contiene símbolos
extraños.
 Gramática limpia: es toda gramática que no contiene
símbolos extraños.

TALF. Tema6

nº 5

6.4. Limpieza de gramáticas
 toda gramáticaen bruto ha de limpiarse con el objetivo
de eliminar todos los símbolos extraños.
 El método de limpiar las gramáticas sucias consiste


en detectar en primer lugar todos los símbolos muertos, y
a continuación



se detectan todos los símbolos inaccesibles. Es importante
seguir este orden, puesto que la eliminación de símbolos
muertos puede generar nuevos símbolos inaccesibles.

Los algoritmos que se utilizan en la limpieza de
gramáticas se basan en los teoremas que se enuncian a
continuación

TALF. Tema6

nº 6

6.4. Limpieza de gramáticas
6.4.1. Teorema de los símbolos vivos
 Si todos los símbolos de la parte derecha de una
producción son vivos, entonces el símbolo de la parte
izquierda también lo es.

 Algoritmo para detectar símbolos muertos:
1. Haceruna lista de no-terminales que tengan al
menos una producción sin símbolos no terminales en
la parte derecha.
2. Dada una producción, si todos los no-terminales de la
parte derecha pertenecen a la lista, entonces
podemos incluir al no terminal de la parte izquierda.
3. Cuando no se puedan incluir más símbolos mediante
la aplicación del paso 2, la lista contendrá todos los
símbolos vivos,el resto serán muertos.

TALF. Tema6

nº 7

6.4. Limpieza de gramáticas. Ejemplo.


Determinar los símbolos muertos de la gramática expresada en BNF:

::= a | d
::= b
::= e | d
::= g
::= f
::= t | v

1.

2.

3.

aplicando los pasos del algoritmo:
Confección de la lista: sólo hay un símbolo no terminal con el cual comenzar
la lista.

Aplicando el teorema...