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]

 OM
Presentación de la materia.

.C
CLASE 1:

DD
Símbolos, Alfabeto, Palabras,
Concepto de compiladores e intérpretes. Estructura y componentes de un compilador, módulos y su función. LEER ANEXO DE
Lenguajes. COMPILADORES DEL LIBRO
CONTENIDOS

LA LEER ANEXO DE COMPILADORES DEL

FI LIBRO:
Concepto de compiladores e intérpretes.
Operaciones con Lenguajes. Estructura y componentes de un compilador,

módulos y su función.

Este archivo fue descargado de [Link]

 Gramáticas

OM
Jerarquía de Chomsky

Tipos de Lenguajes

.C
Lenguajes Regulares

DD
CLASE 2: Expresiones Regulares
CONTENIDOS

LA
Características de las Gramáticas

Gramáticas Limpias
FI
Gramáticas Bien Formadas


Conceptos de Compiladores

Este archivo fue descargado de [Link]

GRAMÁTICAS FORMALES

OM
• Regla de reescritura o producción: es un par ordenado (,  ) sobre . También se
denota como  :=  ( simplificación de BNF ).

.C
<A> := B

DD
<A> := B1 | B2 | B3 | … | Bn

• Derivación directa por aplicación de una producción:

LA

• Derivación (en un o más pasos):
FI
Operación que consiste en aplicar una secuencia finita de producciones a una cadena  dada
para obtener otra cadena ,   * .
(Es decir:  = 0  1  …  n-1  n =  ).


• Derivación por derecha o por izquierda y reducción directa:   

• Reducción (en un o más pasos):  * 
Este archivo fue descargado de [Link]
GRAMÁTICA FORMAL

OM
 Def: G = (T, N, S, P)

.C
Donde:
 T es el alfabeto de los símbolos terminales

DD
 N es el alfabeto de símbolos no terminales
 SN axioma de la gramática
 P es un conjunto de producciones ( :=  )

LA
 T  N = 
Nota:  debe tener al menos 1 símbolo no terminal
FI
Lenguaje Generado por G:
L(G) = { T* / S *  }

Forma sentencial (metapalabra ): i(TN)*
• Dos gramáticas G1 y G2son equivalentes si y sólo si generan exactamente
el mismo lenguaje: G1  G2  L(G1) = L(G2)
Este archivo fue descargado de [Link]
EJEMPLO DE GRAMÁTICA

OM
• Suponiendo la siguiente Gramática:

.C
G = ({0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, {N, D}, N, P)

DD
con:
P = {N := D | DN, D:= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9}
Luego, tenemos que:

LA
L(G) = { ??????? }
FI


Este archivo fue descargado de [Link]

 OM
.C
DD
LA
FI


Este archivo fue descargado de [Link]

 JERARQUÍA DE CHOMSKY

OM
 En su trabajo del 56’ Chomsky propuso una jerarquía (clasificación) de 4 tipos de lenguajes
formales.

.C
 Los lenguajes se distinguen por la forma de las producciones de la gramática que la genera.
 En cada nivel se establecen restricciones en el formato de las producciones.

DD
 Hay 4 tipos (0, 1,2 y 3).
 Las gramáticas toman los nombres y tipo de los lenguajes que generan.

LA
FI


Jerarquía de Chomsky: L3L2L1L0

Este archivo fue descargado de [Link]
JERARQUÍA DE CHOMSKY

OM
Tipo Lenguaje Producciones

.C
Lenguaje Estructurado
0 Sin restricciones

DD
por frases

Lenguaje dependiente
1 αAβ := αγβ
del contexto.

LA
Lenguaje Independiente
2 A := γ
FI de Contexto
A := aB
3 Lenguaje Regular
A := a

Donde: A es un no terminal, ,  y  son cadenas de terminales
y no terminales , a es un símbolo terminal.
Regla de reescritura o producción: es un par ordenado (,  ) sobre . También se
denota como  :=  (BNF).
Este archivo fue descargado de [Link]
 TIPOS DE LENGUAJES

OM
 Tipo 0: Lenguajes estructurados por frases
Las producciones son de la forma:
 := , con: (TN)* N (TN)*, (TN)*

.C
o equivalentemente:
A := , con: ,,(TN)*, AN

DD
- Es decir, pueden tener cualquier cadena de terminales y no terminales a ambos lados, pero con al
menos un símbolo no terminal en el lado izquierdo.

LA
- Las reglas pueden ser compresoras.
FI
 Tipo 1: Lenguajes dependientes del contexto
Las producciones son:

S :=  ó αAβ := αγβ, con: ,(TN)*, AN, (TN)+
- Es decir, A es un no terminal, ,  y  son cadenas de terminales y no terminales.
- Son reglas no compresoras.
- S :=  única regla compresora. Este archivo fue descargado de [Link]
TIPOS DE LENGUAJES

OM
 Tipo 2: Lenguajes independientes del contexto
Las producciones son:

.C
S :=  ó A :=  , con: AN, (TN)+
- Son reglas no compresoras.

DD
- No es necesario tener en cuenta el contexto de A para efectuar el reemplazo en una
derivación.

LA
 Tipo 3: Lenguajes Regulares (o Lineales)
FI
Las producciones son:
 Regular derecha: S:= ó A:=aB ó A:=a A, BN, aT

 Regular izquierda: S:= ó A:=Ba ó A:=a A, BN, aT

Este archivo fue descargado de [Link]

LENGUAJES REGULARES

OM
 Lenguajes Regulares:
- Lenguajes utilizados en la etapa de análisis léxico en los
compiladores.

.C
Las producciones son:

DD
 Regular derecha: S:= ó A:=aB ó A:=a A, BN, aT.
Definición recursiva de los Lenguajes Regulares:
A. Cualquier lenguaje finito L1 definido sobre un alfabeto , es

LA
regular.
B. Si L1 y L2 son lenguajes regulares, entonces también lo son L1L2 y
FI
L1°L2.
C. Si L1 es un lenguaje regular, entonces su estrella de Kleene L1*, también es

un lenguaje regular.
D. Sólo son lenguajes regulares, los construidos con a, b y c.

Este archivo fue descargado de [Link]

EXPRESIONES REGULARES

OM
 Def: es una notación que se utiliza para especificar un lenguaje regular(tipo 3).

.C
 Las expresiones regulares se definen recursivamente como :

DD
 Base: Sea  un alfabeto, entonces:
-  es una expresión regular que denota al lenguaje vacío: L()=.
-  es una expresión regular que denota al lenguaje cuyo único elemento es la cadena vacía:

LA
L()={}.
- Un símbolo a del alfabeto  es una expresión regular que denota al lenguaje cuya única
FI
palabra es la palabra de largo unitario formada por ese símbolo: L(a) = {a}.


Este archivo fue descargado de [Link]

EXPRESIONES REGULARES

OM
Paso recursivo: Si E y F son expresiones regulares, entonces:
A. E+F es una expresión regular que denota al lenguaje unión de los lenguajes
denotados por E y F: L(E+F) = L(E)  L(F).

.C
B. E.F es una expresión regular que denota al lenguaje concatenación de los lenguajes
denotados por E y F: L(E.F) = L(E) ° L(F).

DD
C. E* es una expresión regular que denota al lenguaje formado por la estrella de
Kleene del lenguaje denotado por E, entonces: L(E*) = [L(E)] *.

LA
D. (E) es una expresión regular que denota al lenguaje denotado por E: L((E)) =
L(E).
Por lo tanto, sólo son expresiones regulares las construidas con pasos del a al g.
FI
Ejemplos:
 a* . b que describe el lenguaje L = {anb /n >= 0}


 El alfabeto 2 ={0, 1}. El lenguaje de todas las cadenas binarias de longitud par puede
ser descripto como: ( 00 + 01 + 10 + 11 )* ó ( (0 + 1) (0 + 1) )*
Este archivo fue descargado de [Link]
CARACTERÍSTICAS DE LAS GRAMÁTICAS

OM
 Sea G = (T, N, S, P)
- El objetivo es “limpiar” a la gramática.

.C
- Generalmente se trabajará sobre GIC.

DD
- Se buscan gramáticas equivalentes a la original que no tenga reglas innecesarias, ni
símbolos inaccesibles, ni símbolos superfluos.
- Regla Innecesaria : Son las reglas del tipo A:=A .

LA
Estas reglas pueden ser eliminadas “con seguridad” de G.
FI


Este archivo fue descargado de [Link]

CARACTERÍSTICAS

OM
 Símbolos inaccesibles: Son terminales o no terminales que no
pueden ser alcanzados por una derivación desde S.

.C
Es decir:

DD
x es inaccesible   (S*x) con ,(TN)*
Luego, se podría quitar esa producción y las producciones que lo

LA
contengan sin alterar el lenguaje.
Ej:
FI
G = ( {a, b, c, d}, {S, A, X}, S,{S := aAb, A := aAb | c} )
Tiene X y d como símbolos inaccesibles.

- ¿ Cual es el lenguaje generado por G ?

Este archivo fue descargado de [Link]

CARACTERÍSTICAS

OM
 Símbolo Superfluo :
Cuando no permite llegar a una cadena de solo símbolos terminales.

.C
Por lo tanto:

DD
- X es superfluo  ( X* con T*)
 Ejemplo:

LA
- G = ( {a, b}, {S, A, B,C}, S,{S := aAb | bC, A := aAb | ab | aB, B := aBb, C:= aC} )
Los símbolos superfluos son:
- B y C.
FI
Luego, se puede obtener la gramática equivalente:
- G’ = ( {a, b}, {S, A}, S,{S:=aAb, A:= aAb | ab} )


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.


20
Este archivo fue descargado de [Link]
GRAMÁTICA BIEN FORMADA

OM
 Regla no generativa:
- Son reglas del tipo A:= con A distinto de S.

.C
- En las GIC solo se permite como excepción la regla lambda S:= para
generar .

DD
- Se busca eliminar las reglas no generativas.
- Para poder eliminar A:=, previamente tenemos que agregar la producción

LA
X:= por cada X:=A de la gramática.
Ejemplo: FI
G = ( {a, b}, {S, A}, S, {S := aAb, A := aAb | } )
Eliminando las reglas no generativas se obtiene:

G’=( {a, b}, {S, A}, S, {S := aAb | ab, A := aAb | ab} )

21
Este archivo fue descargado de [Link]
GRAMÁTICA BIEN FORMADA

OM
• Regla de redenominación:
- Son reglas de la forma A:=B, con A y B símbolos no terminales.

.C
- Se busca eliminar las reglas de redenominación.

DD
Procedimiento para eliminar A:=B :
- 1) Por cada B:= en G, agregar una regla A:=.
Por lo tanto en dos pasos A  B  .

LA
- 2) Se elimina A:=B del conjunto P.
Ejemplo: FI
G= ( {0, 1}, {S, T}, S, {S := 0S | S1 | T, T := 01 | 0T} )
Aquí la regla S:=T es de redenominación. Entonces, agregando S:=01 y

S:=0T obtenemos:
G’= ( {0, 1}, {S, T}, S, {S := 0S | S1 | 01 | 0T, T := 01 | 0T} )

22
Este archivo fue descargado de [Link]
GRAMÁTICA BIEN FORMADA

OM
• Regla de redenominación:
- Son reglas de la forma A:=B, con A y B símbolos no terminales.

.C
- Se busca eliminar las reglas de redenominación.

DD
Procedimiento para eliminar A:=B :
- 1) Por cada B:= en G, agregar una regla A:=.
Por lo tanto en dos pasos A  B  .

LA
- 2) Se elimina A:=B del conjunto P.
Ejemplo: FI
G= ( {0, 1}, {S, T}, S, {S := 0S | S1 | T, T := 01 | 0T} )
Aquí la regla S:=T es de redenominación. Entonces, agregando S:=01 y

S:=0T obtenemos:
G’= ( {0, 1}, {S, T}, S, {S := 0S | S1 | 01 | 0T, T := 01 | 0T} )

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


24
Este archivo fue descargado de [Link]
ESTRUCTURA DE UN COMPILADOR

OM
Etapas

.C
Análisis

DD
LA
FI Síntesis


Este archivo fue descargado de [Link]

 OM
.C
DD
FIN DE L A
CL ASE LA
FI


Este archivo fue descargado de [Link]