OM

.C
SINTA XIS Y
SEMÁNTICA DE

DD
LOS LENGUAJES

LA
(SSL)
FI


MGTR. ING. MARINA E. CARDENAS

Este archivo fue descargado de [Link]

 Gramáticas

OM
Jerarquía de Chomsky

.C
Tipos de Lenguajes

DD
CLASE 2: Lenguajes Regulares

CONTENIDOS Expresiones Regulares

LA
FI Características de las Gramáticas

Gramáticas Limpias


Gramáticas Bien Formadas

2
Este archivo fue descargado de [Link]
 OM
Decimos que una gramática independiente del

.C
contexto está limpia si y sólo si no tiene reglas

DD
innecesarias, ni símbolos inaccesibles, ni símbolos
GRAMÁTICA superfluos.
LIMPIA

LA
 Regla Innecesaria : Son las reglas del tipo A:=A.
FI  Símbolos inaccesibles: Son terminales o no terminales que no pueden
ser alcanzados por una derivación desde S.
 Símbolo Superfluo: Cuando no permite llegar a una cadena de solo
símbolos terminales.


3
Este archivo fue descargado de [Link]
 OM
.C
Una gramática independiente del contexto se dice que
está bien formada, si y sólo si, está limpia y no tiene

DD
GRAMÁTICA BIEN reglas no generativas ni reglas de redenominación.
FORMADA

LA
 Regla no generativa: Son reglas del tipo A:= con A distinto
FI de S.
 Regla de redenominación: Son reglas de la forma A:=B, con A y
B símbolos no terminales.


4
Este archivo fue descargado de [Link]
 OM
Árboles de Derivación

.C
Recursión

DD
CLASE 3:
CONTENIDOS

LA
Forma Normal de Chomsky
FI
Forma Normal de Greibach


7
Este archivo fue descargado de [Link]
ARBOLES DE DERIVACIÓN
• Se llama Análisis Sintáctico de la cadena  al proceso de búsqueda de la

OM
derivación: S* .
• Objetivo del análisis sintáctico: ¿   L(G) ?

.C
Caso general:
• S := a1a2…an

DD
LA
• ai := b1b2…bm
FI
Una cadena  de símbolos terminales pertenece al lenguaje L(G) generado por la gramática

G, si y sólo si, es posible construir su árbol de análisis sintáctico, con el axioma S como raíz y la
cadena leída en las hojas de izquierda a derecha.

8
Este archivo fue descargado de [Link]
EJEMPLO: ÁRBOL DE DERIVACIÓN

OM
• Ejemplo:

.C
G = ({0,2,4,6,8},{N,C},N,P1)
con

DD
P1={N:= C | CN, C:= 0 | 2 | 4 | 6 | 8 }
Luego la derivación:

LA
N->CN-> CCN-> CCC-> 4CC-> 48C -> 480
Presenta el siguiente árbol de derivación:
FI


9
Este archivo fue descargado de [Link]
 OM
• Gramática Ambigua:

.C
Una gramática es ambigua si el lenguaje que define
contiene alguna cadena ambigua.

DD
GRAMÁTICAS Nota: No es posible construir analizadores eficientes para
gramáticas ambiguas.
AMBIGUAS

LA
• Cadena Ambigua si puede ser generada por derivaciones que
tienen distintos árboles de análisis sintáctico.
FI


10
Este archivo fue descargado de [Link]
EJEMPLO DE AMBIGUEDAD:

OM
 Sea la gramática de “expresiones”:
G = ( {num, +, *, (, )}, {E}, E,{E:= E + E | E * E | (E) | num} )
 Veamos las derivaciones que dan origen a la expresión: num + num * num

.C
DD
Dos derivaciones posibles son:
 E  E+E  num+E  num+E*E 
num+num*E  num+num*num

LA
FI
 E  E*E  E+E*E  num+E*E 


num+num*E  num+num*num

11
Este archivo fue descargado de [Link]
RECURSIÓN

OM
 Una producción de G = (T, N, S, P) se dice que es recursiva si el no
terminal de su lado izquierdo se encuentra también en el lado derecho.
 Ej: A := A , S:= 1S, B:=1BA

.C
 Recursión en un paso: Si la gramática tiene una regla de reescritura

DD
recursiva. (ej. ant).

 Recursión en mas de un paso: Si la gramática tiene un no terminal del lado

LA
izquierdo de una producción que pueda derivar en k-pasos una cadena que lo
contenga. FI
 Ej:
A 1  2  … A


con AN , y ,,i(TN)*

12
Este archivo fue descargado de [Link]
REGLAS Y ELIMINACIÓN DE LA

OM
RECURSIÓN

.C
Reglas

DD
• Recursiva por la izquierda:
A:=A si  es vacía (es decir: A:=A)

LA
• Recursiva por la derecha:
A:=A
FI
Eliminación de recursión izquierda en un paso


13
Este archivo fue descargado de [Link]
 ELIMINACIÓN DE LA RECURSIÓN

OM
Sea G = (T, N, S, P) una GIC con AN tq:
 A := A1 | A2 | … | An | 1 | 2 | … | m
con i, j  (TN)* .

.C
 Pasos para obtener una gramática equivalente sin recursión izquierda :
1. Crear un nuevo símbolo no terminal X y agregarlo al alfabeto de símbolos no terminales:

DD
N’=N{X}
2. Eliminar todas las producciones en P para el no terminal A, y

LA
3. Agregar:
A := 1X | 2X | … | mX | 1 | 2 | … | m
FI
X := 1X | 2X | … | nX | 1 | 2 | … | n
Se obtendrá G’ = (T, N’, S, P’) equivalente a G y con

reglas no recursivas por izquierda (aunque si por derecha).
Nota: Es posible aplicar el algoritmo anterior para la Eliminación de recursión izquierda en más de un
paso.
14
Este archivo fue descargado de [Link]
ELIMINACIÓN DE RECURSIÓN IZQUIERDA
EN MÁS DE UN PASO

OM
 Sea G = (T, N, S, P) una GIC con recursión izquierda en más de un paso. Se aplica el
siguiente procedimiento para obtener una gramática equivalente sin recursión

.C
izquierda :

DD
1. Asignar un orden cualquiera a los símbolos no terminales:
A1, A2, …, Ak.
2. Para cada i=1, 2, …, k, hacer:

LA
2.1. Para cada j=1, 2, …, k, hacer:
Si ij, reemplazar cada Ai := Aj en P (eliminarla y agregar) por Ai := 1 | 2 |…| h
FI
donde los m son los lados derechos de todas las producciones de Aj.
2.2. Eliminar recursión izquierda en un paso de Ai usando el procedimiento de eliminación

de recursión en 1 paso.
Al terminar el proceso, las recursiones izquierdas habrán sido
eliminadas y la gramática obtenida será equivalente a la original. 15
Este archivo fue descargado de [Link]
FACTORIZACIÓN POR IZQUIERDA

OM
Otra situación que trae problemas a algunos de los analizadores sintácticos

.C
descendentes:
A :=  y A := 

DD
donde ,  y  son cadenas cualesquiera de terminales y no terminales.

LA
Se crea un nuevo no terminal X y se reemplazan las anteriores producciones
FI
por:


A := X y X :=  | 

16
Este archivo fue descargado de [Link]
 OM
G está en forma normal de Chomsky si y sólo sí,
todas sus producciones son de la forma:
A := BC ó A := a ó S := 

.C
FORMA con A, B, C, SN, S es el axioma, y aT

DD
NORMAL DE
Nota 1: Solo se puede generar  desde el axioma.
CHOMSKY

LA
Nota 2: Obsérvese que los árboles sintácticos que se
(FNC) FI generan a partir de una FNC son binarios.

Toda gramática libre de contexto es equivalente a una
gramática libre de contexto en Forma Normal de
Chomsky.
17
Este archivo fue descargado de [Link]
GIC A FORMA NORMAL DE CHOMSKY - ALGORITMO

OM
1) Para comenzar el algoritmo, G debe ser una gramática bien formada(limpia y
sin reglas no generativas ni de redenominación).

.C
2) Para cada símbolo terminal aT, crear un nuevo símbolo no terminal <a> y
una nueva producción <a> := a. Es decir:

DD
N’ = N  { <a> } P’ = P  { <a> := a }

LA
3) Para cada producción de la gramática que contenga en su lado derecho tanto
símbolos terminales y no terminales, reemplazarla por una nueva que tenga en
lugar del terminal a su correspondiente nuevo no terminal <a>. Es decir:
FI
A := a es reemplazada por A := <a>, para cualquier  y .


4) Para cada producción con más de dos símbolos no terminales en su lado

derecho, A:=B donde  contiene dos o más no terminales, crear un nuevo
símbolo no terminal X y reemplazar la producción por el par A:=BX y X:=. 18
Este archivo fue descargado de [Link]
 EJEMPLO:
 Sea G = ( {a, b, c}, {A,B,C}, A, P)

OM
P={A := CBc | bB | , B := BC | b, C := c}. Obtener su FNC.
 1) Chequear si G está bien formada.
G no tiene reglas innecesarias(X:=X). El terminal a es
innacesible. No tiene símbolos superfluos ( X*, T*).

.C
No tiene reglas de redenominación(X:=Y), ni reglas no
generativas (X:= ). Luego G’ es: G’ = ( {b, c}, {A,B,C},A, P)

DD
P={A := CBc | bB | , B := BC | b, C := c} )

 2) Se crean los no terminales <b> y <c> y las producciones:

LA
<b> := b, y <c> := c

 3) A:=CBc  A:=CB<c>, A:=bB  A:=<b>B . Las producciones B:=BC, B:=b, C:=c y A

:=  están ok.
FI
 4) A:=CB<c>  se crea X tq: A:=CX y X:=B<c>


Por lo tanto:
G’ = ( {b,c}, {A,B,C,X,<b>,<c>}, A, P)
P = {A := CX |<b>B |, B:=BC|b, C:=c, X:=B<c>,<b>:=b, <c>:= c}) 19
Este archivo fue descargado de [Link]
PROCESAMIENTO POS-ALGORÍTMICO

OM
• G’ = ( {b,c}, {A,B,C,X,<b>,<c>}, A, P)
P = {A:=CX |<b>B |, B:=BC|b, C:=c, X:=B<c>,<b>:=b, <c>:= c})

.C
Notar que <c>:= c es redundante con C:=c. Entonces se puede

DD
reemplazar <c> por C. Entonces:
• G’’ = ( {b,c}, {A,B,C,X,<b>}, A, P)

LA
P={A:=CX|<b>B| ,B:=BC|b, C:=c, X:=BC, <b>:=b} )

• Finalmente:
FI
G≡G’ ≡G’’ ⇔ L(G)=L(G’)=L(G’’)


20
Este archivo fue descargado de [Link]
 OM
• G esta en FNG si y sólo si, todas sus
producciones son:

.C
FORMA A := a ó S:=

DD
NORMAL DE con A, SN, S axioma, N* y aT.
GREIBACH

LA
(FNG) - Nota:  puede ser vacía.
FI
Toda gramática libre de contexto es equivalente a una

gramática libre de contexto en Forma Normal de
Greibach.

23
Este archivo fue descargado de [Link]
 GIC A FORMA NORMAL DE GREIBACH - ALGORITMO:
 1) Transformar G en una gramática bien formada(limpia, sin reglas no generativas ni de

OM
redenominación).
 2) Eliminar la recursividad izquierda de la gramática.
 3) Asignar un orden cualquiera a los símbolos no terminales de la gramática, por ej. A1, A2, …,

.C
Ak.

DD
 4) Particionar P en tres conjuntos disjuntos(grupoi):
◦ Grupo1: producciones que comiencen con un terminal A:=a ,con (TN)* y, si
existiere en la gramática G, la regla lambda S:=.

LA
◦ Grupo2: producciones Ai:=Aj con (TN)+ y con el símbolo Ai anterior a Aj en el
ordenamiento (i < j).
◦ Grupo3: producciones Ai:=Aj con (TN)+ y con el símbolo Ai posterior a Aj en el
FI
ordenamiento (i > j).


 Notar que el caso i=j no puede darse ya que se ha eliminado la recursión por izquierda en el
paso 2.
24
Este archivo fue descargado de [Link]
 GIC A FNG(CONTINUACIÓN)
• 5) Para cada producción del grupo3 Ai:=Aj, para i=1..N, reemplazarlas por Ai: = 1 | 2 | … |

OM
h, para cada Aj := l|2| … | h , es decir k son los lados derechos de las producciones de Aj.
Luego, todas las producciones pertenecerán al grupo1 o grupo2.
• 6) Repetir el paso 5 para las producciones del grupo2. Luego, todas las producciones

.C
pertenecerán al grupo1.
• 7) Para cada aT que esté en el lado derecho de las producciones resultantes, (pero no al inicio

DD
de las mismas), crear un nuevo símbolo no terminal <a> y una nueva producción <a>:=a. Es
decir:

LA
N’ = N  { <a> } P’ = P  { <a> := a }
• 8) Para cada producción de G que contenga en su lado derecho, luego del primer símbolo
terminal, tanto símbolos no terminales como símbolos terminales, reemplazarla por una nueva
FI
producción que tenga en lugar del terminal no inicial a su correspondiente nuevo no terminal
<a>. Es decir:


A := xa es reemplazada por A := x<a>

con x el primer símbolo terminal del lado derecho, a otro terminal de la producción y
cualesquiera  y . 25
Este archivo fue descargado de [Link]
EJERCICIO: GIC A FNG

OM
.C
 Sea G = ( {0, 1, 2}, {A, B, C}, A, P)

DD
P = { A := CB|2, B := A1|1, C := 0|C1}, obtener la FNG.
Solución:
1) La gramática está bien formada (sin reglas innecesarias, símbolos inaccesibles, símbolos

LA
superfluos, sin reglas de redenominación, ni reglas no generativas).
2) C presenta recursividad a la izq., entonces se crea X (no terminal )y se reemplazan las
producciones de C por: X:=1|1X y C:=0|0X. Entonces tenemos:
FI
 G’= ( {0, 1, 2 }, {A, B, C, X}, A, P’)
P’= { A := CB|2, B:=A1|1, C :=0|0X , X := 1|1X }


26
Este archivo fue descargado de [Link]
EJERCICIO: GIC A FNG

OM
.C
Sea G’= ( {0, 1, 2 }, {A, B, C, X}, A, P’)
P’= { A := CB|2, B:=A1|1, C :=0|0X , X := 1|1X }, obtener la FNG.

DD
Solución:
1) La gramática está bien formada (sin reglas innecesarias, símbolos inaccesibles, símbolos

LA
superfluos, sin reglas de redenominación, ni reglas no generativas).
2) No presenta recursividad a la izq.
FI


27
Este archivo fue descargado de [Link]
 EJERCICIO: GIC A FNG(CONTINUACIÓN)
G’= ( {0, 1, 2 }, {A, B, C, X}, A, P’)

OM
P’= { A := CB|2, B:=A1|1, C :=0|0X , X := 1|1X }
 3-8)
Grupo 1: producciones que comiencen con un terminal A:= a (teniendo en cuenta regla 
desde el axioma, si existiera).

.C
DD
X := 1|1X, C :=0|0X, B:=1, A:= 2

Asumamos el orden lexicográfico A, B, C, X para los no terminales, entonces:

LA
Grupo 2: producciones Ai:=Aj con (TN)+ y con el símbolo Ai anterior a Aj en el
ordenamiento.
FI B := CB1 y A := CB

Grupo 3: producciones Ai:=Aj con (TN)+ y con el símbolo Ai posterior a Aj en el


ordenamiento.
B := A1

28
Este archivo fue descargado de [Link]
 EJERCICIO: GIC A FNG(CONTINUACIÓN)
G’= ( {0, 1, 2 }, {A, B, C, X}, A, P’)

OM
P’= { A := CB|2, B:=A1|1, C :=0|0X , X := 1|1X }
 3-8) Asumamos el orden lexicográfico A, B, C, X para los no terminales, entonces:
Grupo3: B := A1, se reemplazan por B:= CB1 (ahora pertenece al grupo2) y por B:= 21 (ahora
del grupo1) que a su vez se reemplaza por B:= 2Y (ahora en FNG), donde Y es un nuevo no

.C
terminal que produce únicamente Y:= 1.

DD
 Grupo2: B := CB1 y A := CB
-B := CB1 se reemplaza por B:= 0B1 y B := 0XB1 (ahora del grupo 1) y, haciendo uso del no
terminal Y creado recién, éstas a su vez se transforman en B:= 0BY y B:= 0XBY (ahora en FNG).

LA
- A := CB se reemplaza por A:= 0B y A:= 0XB (que están en FNG).
FI
 Grupo1: X := 1|1X, C :=0|0X, B:=1, A:= 2, los cuales ya están en FNG.
Por lo tanto:

 G’’ = ( {0, 1, 2 }, (A, B, C, X, Y}, A, P’’)
P’’ = { A := 0B | 0XB | 2, B := 0BY | 0XBY | 1, C := 0 | 0X, X := 1 | 1X, Y := 1 }
Donde G’’ está en FNG.
29
Este archivo fue descargado de [Link]
 OM
.C
DD
FIN DE L A
CL ASE LA
FI


30
Este archivo fue descargado de [Link]