arboles de derivacion
Post on 08-Jul-2015
2.439 Views
Preview:
TRANSCRIPT
Departamento de Ciencias de la Computación
Árboles de derivación
�Árboles de derivación
Departamento de Ciencias de la Computación
Derivaciones
Si A � � entonces �A� � ��� es una derivación
donde �,� son cadenas arbitrarias de símbolos gramaticales.
Si �1 � �
2 ... � � �
n se dice que �
1 deriva a �
n
� deriva en un paso
� deriva en cero o más pasos*
Departamento de Ciencias de la Computación
Derivaciones
Podemos decir:
� � � ��
� � � y � � ,� entonces � � �
Del mismo modo se puede decir
� deriva en uno o más pasos
*
*
*
+
Departamento de Ciencias de la Computación
Derivaciones
� Una derivación por la izquierda es aquella en la que se reemplaza el no terminal más a la izquierda en cada paso de la derivación.� análogamente para la derecha
� Una derivación por la izquierda corresponde a la numeración preorden de los nodos internos de su árbol de análisis gramatical asociado.� derecha � postorden inversa
Departamento de Ciencias de la Computación
Árboles de der ivación
� Toda derivación de las gramáticas de tipo 1, 2 ó 3 se puede representar mediante un árbol.
Departamento de Ciencias de la Computación
Ejemplo de árbol de der ivación
� Sea la gramática:G = ( 0,2,4,6,8),(N,C),N, {N � C | CNC � 0 | 2 | 4 | 6 | 8} )
� Sea la derivaciónN � CN � CCN � CCC � 4CC � 48C � 480
N
C N
C N
8
C
04
Departamento de Ciencias de la Computación
Ejercicio
� Sea la gramáticaS � ( L ) | aL � L , S | S� ¿Cuáles son los elementos no terminales?� ¿Cuáles son los elementos terminales?� ¿Cuáles es el símbolo inicial?� Realizar los árboles sintácticos de
� (a , a)� (a , (a , a))� (a , ((a , a) , (a , a)))
Departamento de Ciencias de la Computación
Ambigüedad
� Una gramática es ambiguaambigua si el lenguaje que define contiene alguna cadena que tenga más de un árbol de análisis sintáctico. (no ambigua implica un único árbol)
� No es posible construir analizadores eficientes para gramáticas ambiguas.
� Con ciertas restriccionesrestricciones a la gramática se podrá afirmar que no es ambigua.
Departamento de Ciencias de la Computación
Ejemplo de gramática ambigua
� Sea una gramática cuyas reglas de producción son las siguientes:
E � E + EE � E * EE � nE � (E)
� Se pide el o los árboles sintácticos de �7+4*2�.
Departamento de Ciencias de la Computación
Ejemplo de gramática ambigua
E
E E
EE
n n
+
*n
(7)
(4) (2)
(8)
(15) GramáticaE � E + EE � E * EE � nE � (E)
ProducciónE � E + E � n + E � n + E * E � n + n * E � n + n * n
Departamento de Ciencias de la Computación
Ejemplo de gramática ambigua
E
EE
EE
n n
*
+n
(2)
(7) (4)
(11)
(22)
ProducciónE � E * E � E + E * E � n + E * E � n + n * E � n + n * n
GramáticaE � E + EE � E * EE � nE � (E)
Departamento de Ciencias de la Computación
Ejemplo de gramática ambigua
� Solución a la ambigüedad � modificar las reglas de producción.
Distinguiendo factor y término (producto de dos factores)
E � E + T | TT � T * F | FF � (E) | n
árbol sintáctico de �7+4*2�
E
E T
FT
n n
+
*
n(7) (4) (2)
(8)
(15)
T
F F
Departamento de Ciencias de la Computación
Ejercicio
� Sea la gramáticaS � a S b SS � b S a SS � λ� Demostrar que es ambigua contruyendo dos
árboles sintácticos correspondientes a la frase abab
Departamento de Ciencias de la Computación
Gramáticas bien formadas
� Características de las gramáticas que se deben evitar para que no sea ambigua� Reglas innecesarias:
� A � A
� Símbolos innaccesibles: � U � A donde U ∈ �
N y no aparece en la parte derecha
de ninguna otra regla y U no es el símbolo del axioma.
� U es accesible ⇔ S ⇒ xUy, x,y ∈ �* *
Departamento de Ciencias de la Computación
Gramáticas bien formadas
� Regla superfluas� Para no ser superfluo U ∈ �
N debe cumplir
U ⇒ x, x ∈ �T
*
� Eliminación de símbolos no generativos: � G = (�
T, �
N, S, P)
para cada A ∈ �N se genera G(A)
si L(G(A)) es vacío A es un símbolo no generativo
� Eliminación de reglas de redenominación, A � B� para cada A ∈ �
N tal que A ⇒ B y para cada regla de la
forma B � x donde x ∈ �N se añadirá una regla de la forma
A � x
+
*
Departamento de Ciencias de la Computación
Gramáticas bien formadas
� Eliminación de reglas no generativas, A � λ: � Si L(G) no contiene λ
es posible eliminarlar todas� En caso contrario
se pueden eliminar todas menos S � λ
donde para cada A ∈ �N (A S) tal que A� ⇒ λ y
por cada regla B � xAy se añadirá otra regla de la forma B � xy excepto si x=y=λ
*
Departamento de Ciencias de la Computación
Gramáticas bien formadas
� Ciclos: � S � A� S � a� A � S
� Reglas que ofrezcan caminos alternativos: � S � A� S � B� A � B
Departamento de Ciencias de la Computación
Gramáticas bien formadas
� Producciones recursivas en las que las variables no recursivas de la producción pueden derivar a la cadena vacía:
� S � H R S� S � s� H � h | λ
� R � r | λ
� S � H R� H � h |
λ
� R � r | λ
Departamento de Ciencias de la Computación
Ejemplo
� Limpiar la siguiente gramática
G = ({0,1}, {S, A, B, C}, S, P)� S � AB | 0S1 | A | C
� A � 0AB | λ
� B � B1 | λ
Departamento de Ciencias de la Computación
Ejemplo
� G = ({0,1}, {S, A, B, C}, S, P)� S � AB | 0S1 | A | C
� A � 0AB | λ
� B � B1 | λ
Símbolo no generativo
� G = ({0,1}, {S, A, B, C}, S, P)� S � AB | 0S1 | A
� A � 0AB | λ
� B � B1 | λ
Departamento de Ciencias de la Computación
Ejemplo
Eliminación de reglas de la forma x � λ
� G = ({0,1}, {S, A, B, C}, S, P)� S � AB | 0S1 | A | B | λ
� A � 0AB | 0B | 0A | 0� B � B1 | 1
� G = ({0,1}, {S, A, B, C}, S, P)� S � AB | 0S1 | A
� A � 0AB | λ
� B � B1 | λ
Departamento de Ciencias de la Computación
Ejemplo
Eliminación de reglas de
redenominación S � A | B
� G = ({0,1}, {S, A, B, C}, S, P)� S � AB | 0S1 | 0AB | 0A | 0B | B1 | 0 | 1 | λ
� A � 0AB | 0B | 0A | 0� B � B1 | 1
� G = ({0,1}, {S, A, B, C}, S, P)� S � AB | 0S1 | A | B | λ
� A � 0AB | 0B | 0A | 0� B � B1 | 1
Departamento de Ciencias de la Computación
Ejercicio
� G = ({i,+}, {Z, E, F, G, P, Q, S, T}, Z, P)� Z � E + T� E � E | S + F | T� F � F | FP | P� P � G� G � G | GG | F� T � T * i | i� Q � E | E + F | T | S� S � i
Departamento de Ciencias de la Computación
Asociat ividad de los operadores
� La asociatividad de un operador binario define cómo se operan tres o más operandos.
� Por la izda: se evalúan de izda. a dcha. Es la que utilizan la mayoría de los lenguajes.
� Ejemplo �b#a#3.8�.� Primero se opera �b� con �a� y después
el resultado con �3.8�
� Muchos de los operadores no son conmutativos.
Departamento de Ciencias de la Computación
Asociatividad
� Cuando la asociatividad de un operador es por la izquierda, la regla sintáctica en la que interviene dicho operador debe ser recursiva por la izquierda, y análogamente por la derecha.
Departamento de Ciencias de la Computación
Precedencia
� La precedencia de un operador especifica el orden relativo de cada operador respecto a los demás operadores.
� Ej. �2%3#4� con mayor precedencia del #, primero se operaría el 3 y el 4, y el resultado con el 2
Departamento de Ciencias de la Computación
Precedencia
� En la mayoría de los lenguajes los operadores multiplicativos tienen mayor preferencia que los aditivos.
� Uso de paréntesisparéntesis para agrupar los operadores según la conveniencia del programador y eludir las precedencias y asociatividades definidas en el lenguaje.
Departamento de Ciencias de la Computación
Ejemplo de precedencia
� Supóngase los operador �+� y �-� con asociatividad por la izquierda y los operadores �*� y �/� con asociatividad por la derecha.
� Precedencia habitual: �*� y �/� mayor precedencia que �+� y �-� y los paréntesis la máxima preferencia.
� Gramática?
Departamento de Ciencias de la Computación
Solución a l e jemplo de precedencia
� E � E + T� E � E - T� E � T� T � F * T� T � F / T� T � F� F � (E)� F � n
¿Cómo sería el árbol asociado a la siguiente sentencia?12 - 4 - 6 / 2 / 2
Departamento de Ciencias de la Computación
Solución a l e jemplo de precedencia
� E � E + T� E � E - T� E � T� T � F * T� T � F / T� T � F� F � (E)� F � n
12 - 4 - 6 / 2 / 2
E
TE
T
-
/
(4)
T/
T
F
n
-
F
n
F
n
F
n(2)
(6)
(2)(12)
E
T
F
n
Departamento de Ciencias de la Computación
Gramática correcta
� La gramática debe reflejar la precedencia y asociatividad de los operadores puesto que la mayoría de los lenguajes objeto no tienen precedencia o asociatividad.
Departamento de Ciencias de la Computación
Lenguajes y procesadores de lenguaje
� Lenguaje naturales� Lenguajes artificiales� Lenguajes de programación
�Procesadores de lenguajeProcesadores de lenguaje�Compilador �Interprete�Compilador-Interprete
Departamento de Ciencias de la Computación
Procesador de lenguaje: partes
� Tabla de símbolos e identificadores� Analizador léxico� Analizador sintáctico� Analizador semántico� Generador de código� Optimizador de código� Gestión de memoria� Recuperación de errores detectados
Departamento de Ciencias de la Computación
Fases de un compilador
Programa fuente
Analizador léxico
Analizador sintáctico
Analizador semántico
Generación de código intermedio
Optimizador de código intermedio
Generador/optimizador de código objeto
Programa objeto
Gestión de
errores
Tabla de símbolos
An
ális
is
Departamento de Ciencias de la Computación
Organización de las fases en f ront end y
back endPrograma fuente
Front end
Análisis léxico
Análisis sintáctico
Generación de código intermedio
Análisis semántico
Código intermedio
Back end
Optimización código intermedio
Generación código objeto
Código objeto
Optimización código objeto
Departamento de Ciencias de la Computación
Front end y back end
� Front end:� fases de análisis y generación de código
intermedio.� depende del lenguaje fuente y es
independiente del lenguaje objeto.
� Back end:� fases de generación y optimización de código.� depende del lenguaje objeto y es
independiente del lenguaje fuente.
Departamento de Ciencias de la Computación
Tipos de análisis s intáctico .
� Descendente.� Análisis descendente: se parte de la raíz del
árbol (símbolo inicial de la gramática) y se van aplicando reglas por la izquierda obteniendo una derivación por la izda. del símbolo inicial. Las hojas del árbol tendrán los tokens que nos devuelve el analizador léxico.
� Ascendente� Análisis ascendente: se empieza por las hojas
(tokens) y se van creando los nodos intermedios hasta llegar a la raíz (símbolo inicial).
Departamento de Ciencias de la Computación
Ejemplo
� Ej.: Dada la entrada �num*num+num� y la gramática:� E � E + T | T� T � T * F | F� F � num
obtener las derivaciones por ambos métodos de análisis
Departamento de Ciencias de la Computación
Ejemplo de análisis s intáctico: descendente
Producciones:� E � E + T� E � T� T � T * F� T � F� F � num� F � num� T � F� F � num
E
T
T
FT
numnum
+
*num
E
F
F
GramáticaE � E + T | TT � T * F | FF � num
Departamento de Ciencias de la Computación
Ejemplo de anális is s intáct ico: ascendente
Producciones:� F � num� T � F� F � num� T � T * F� E � T� F � num� T � F� E � E + T
E
T
T
FT
num num +* num
E
FF
GramáticaE � E + T | TT � T * F | FF � num
Departamento de Ciencias de la Computación
Gramáticas que permiten un análi s is en t iempo
l ineal O(n)
� Análisis descendente: gramáticas LL(k)� Análisis ascendente: gramáticas LR(k)
� L es left to right: la secuencia de tokens de entrada se analiza de izquierda a derecha.
� L/R es left-most/right-most: obtiene la derivación por la izquierda/derecha.
� k es el número de símbolos de entrada que es necesario conocer en cada momento para poder hacer el análisis.
Departamento de Ciencias de la Computación
Gramáticas que permiten un análi s is en t iempo
l ineal O(n)
� Ej.: LL(2): cadenas� analizadas de izquierda a derecha� derivando el no terminal que quede por
derivar más a la izquierda� necesita mirar dos tokens.
Departamento de Ciencias de la Computación
Ejemplo
� Diseñar una gramática no ambigua que genere todos los números enteros sin signo que sean pares, considerando que el 0 es par también.
N � D NN � DigparD � 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9Digpar � 0 | 2 | 4 | 6 | 8
Departamento de Ciencias de la Computación
Ejercicio
� Sea la gramáticaS � c A dA � a bA � a
y la cadena de entrada cad� Construir el árbol sintáctico� ¿Qué paso realiza para la generación del
árbol?
Departamento de Ciencias de la Computación
Ejercicio
S
c A d
S
c A d
a b
S
c A d
a
error
A � a b
S � c A d
A � a
Gramática
S � c A dA � a bA � a
Departamento de Ciencias de la Computación
Ejercicio
� Sea la gramáticaS � a S b SS � b S a S
S � λy la cadena de entrada abab� Construir dos árboles sintáctico� ¿Qué paso realiza para la generación del
árbol?
Departamento de Ciencias de la Computación
Ejercicio
S
a S b S
λ
a S b S
λ λ
S
a S b S
λb S a S
λ λ
Gramática
S � a S b S
S � b S a S
S � λ
CadenaCadenaabab
Departamento de Ciencias de la Computación
Ejercicio
� Considerese la gramática independiente del contexto G = ({*,+, a}, {S}, S, P).� S � S S +
| S S *| a
� Demostrar como se puede generar la cadena aa+a*
� Construir el árbol sintáctico para esta cadena� ¿Qué lenguaje genera esta gramática?
Departamento de Ciencias de la Computación
Ejemplo
� Diseñar una gramática no ambigua para la declaración de variables enteras, carácter o real en C.
Debe admitir declaraciones del tipo:
int i,j; char c,r;
float f, f2;lista_decl � decl lista_decl
| decl
decl � tipo lista_var ';'
lista_var � ident ',' lista_var
| ident
tipo � int
| char
| float
Departamento de Ciencias de la Computación
Ejemplo
� Dada la gramática siguiente, escribe las derivaciones por la izquierda y los árboles de análisis gramatical para las siguientes expresiones:� 3 + 4 * 5 - 6� 3 * (4 - 5 + 6)� 3 - (4 + 5 * 6)
expr � expr opsuma term
| term
opsuma� '+'
| '-'
term � opmult factor
| factor
opmult � '*'
factor � '(' expr ')'
| num
Departamento de Ciencias de la Computación
Ejemplo
� Dada la siguiente gramática de expresiones simplificadas tipo LISP. Escribe una derivación por la izquierda y otra por la derecha para la cadena� ( a 23 ( m x y ) )� dibuja árbol de análisisgramatical para esta cadena
list � '(' list_exp ')'
list_exp� list_expr expr
| expr
expr � atomo
| list
atomo � numero
| identificador
top related