Lenguaje de contexto libre autómata de pila y análisis sintáctico

Universidad Tecnológica de Panamá
Facultad de Ingeniería de Sistemas Computacionales
Departamento De Computación Y Simulación De Sistemas

Lenguajes Formales, Autómatas Y Compiladores
LENGUAJE DE CONTEXTO LIBRE, AUTÓMATA DE PILA Y
ANÁLISIS SINTÁCTICO
ING. DORIS ELENA GUTIÉRREZ ROSALES
DORIS.GUTIERREZ@UTP.AC.PA
I SEMESTRE 2015

OBJETIVOS



Aplicar las reglas del lenguaje de
contexto libre y surelación con el
autómata de pila y el analizador
sintáctico



Diseñar el analizador sintáctico.

AGENDA


Lenguaje De Contexto Libre O
Independiente Del Contexto



Autómatas De Pila



Lenguaje De Contexto Libre Y
Lenguajes Que No Son De
Contexto Libre.



Analizador Sintáctico

GRAMÁTICAS Y LENGUAJES LIBRES DE
CONTEXTO
Lenguajes Libres de Contexto. Los LLC se describen mediante lasGramáticas Libres de Contexto (GLC):


Todos los LR son LLC, pero no todos los LLC son LR.



Los LLC (que no sean LR) no pueden denotarse mediante
expresiones regulares ni pueden ser reconocidos mediante AF.



Los LLC se utilizan para especificar la mayoría de los lenguajes de
programación

GRAMÁTICAS Y LENGUAJES LIBRES DE
CONTEXTO
Gramáticas Independientes del Contexto o Gramáticas Tipo 2
Una GFes Independiente del Contexto si sus producciones tienen las
siguientes restricciones:


el lado izquierdo debe tener un solo no terminal,



el símbolo distinguido puede o no derivar a λ

P={(S → λ) | (A → v) / A Є VN, v Є Σ+}
Ejemplo: P = {(S → λ), (S → 01S1), (S → 0S10), (S → A1), (A → 0S10)}

GRAMÁTICAS Y LENGUAJES LIBRES DE
CONTEXTO
Lenguaje Libre de Contexto (LLC)
Es el lenguaje generadopor una gramática GLC.

L(G)={w / w Є VT* y S ⇒* w}

es decir w Є L(G) si w está formado cadenas de cero o más
terminales y puede ser derivada desde el axioma.

GRAMÁTICAS Y LENGUAJES LIBRES DE
CONTEXTO
Ejemplos.
1.
G = (VN, VT, E, P) con
VT= {id, num,+,*,(,)}
P:
1. E→E+E
4. E→id
2. E→E*E
5. E→num
3. E→(E)
Derivar la palabra id * (id+num) * id

VN = {E}

2. Hallar gramática que genera el lenguajeregular denotado por la
expresión regular a*b*

3. Hallar la gramática que genera el lenguaje anbn, n >= 0
4. Hallar gramática que describe el lenguaje de los palíndromos
formados por a’s y b’s

GRAMÁTICAS Y LENGUAJES LIBRES DE
CONTEXTO
Árbol de derivación
Sea G = (VN,VT,S,P) una GLC. Un árbol es un árbol de derivación para G si:
1. Todo vértice tiene una etiqueta tomada de VT  VN  {}

2. Laetiqueta de la raíz es el símbolo inicial S

3. Los vértices interiores tienen etiquetas de VN

GRAMÁTICAS Y LENGUAJES LIBRES DE
CONTEXTO
Árbol de derivación
Sea G = (VN,VT,S,P) una GLC. Un árbol es un árbol de derivación para G si:
4. Si un nodo n tiene etiqueta A y n1n2...nk respectivamente son hijos del
vértice n, ordenados de izquierda a derecha, con etiquetas x1,x2..xk
respectivamente,entonces:
A  x1x2...xk
debe ser una producción en P

5. Si el vértice n tiene etiqueta , entonces n es una hoja y es el único hijo
de su padre.

GRAMÁTICAS Y LENGUAJES LIBRES DE
CONTEXTO
Árbol de derivación.

Ejemplo
Sea G=(VN,VT,S,P) una GLC con P: S  ab|aSb
La derivación de la cadena aaabbb será: S ⇒ aSb ⇒ aaSbb ⇒ aaabbb
y el árbol dederivación:
S
S

a

b
b

S

a
a

b

GRAMÁTICAS Y LENGUAJESLIBRES DE
CONTEXTO
Ejemplo:
S
S

A

a

S

a

a

A

b
b

a

Derivación a la izquierda:
S ⇒ aAS ⇒ aSbAS ⇒ aabAS⇒aabbaS⇒aabbaa
Derivación a la derecha:
S⇒aAS⇒aAa⇒aSbAa⇒aSbbaa⇒aabbaa

GRAMÁTICAS Y LENGUAJES LIBRES DE
CONTEXTO
Es posible que exista más de un árbol de derivación para una única cadena.
Ejemplo: G = (VN, VT, E, P) con VT= {id, num, +, *, (, )}
P:

VN = {E}

E→ E+E | E*E | (E) | id | num
EE
E

id

E

*
E
id

+

E
E

id

E
id

*

+

E
E

id

id

La cadena id*id+i+d tiene los dos árboles anteriores de derivación anteriores

GRAMÁTICAS Y LENGUAJES LIBRES DE
CONTEXTO
Ejemplo:
G = (VN, VT, E, P) con VT= {id , + , - , \ ,*, ( , ) } VN = {E, T, F}
P:

E→ E+T|E-T|T
T→ T*F|T/F|F
F → ( E ) | id

Estudiar los posibles árboles de derivación para la cadena: id*(id+id)/id - id

GRAMÁTICAS Y...