View
260
Download
0
Category
Preview:
Citation preview
Teoría de lenguajes y compiladores
Análisis Sintáctico Ascendente
Semana 9
Unidad II
Analizador Sintáctico
Objetivo General
El alumno al finalizar el curso podrá desarrollar aplicaciones que le permitan determinar si una estructura gramatical corresponde a una sentencia valida en la definición de un lenguaje en particular, teniendo en cuenta el contexto sintáctico y semántico. Así mismo estará capacitado para proponer nuevas formas estructurales en la definición de lenguajes de programación.
Objetivos Específicos
Diseñar un analizador sintáctico.
Objetivos Específicos
Aplicar métodos de desarrollo ascendente para la construcción de
analizadores sintácticos
Objetivos Instruccionales
Aplicar el método ascendente para la creación de analizadores sintácticos.
Descendentes (Top-Down): Parten del axioma y aplican las reglas de la gramática hasta llegar a secuencia de símbolos terminales (tokens):
• Analizadores LL(1)• Analizadores recursivos
Ascendentes (Bottom-Up): Parten de las hojas (conjunto de tokens) para llegar a la raíz (axioma de la gramática):
• Analizadores de Precedencia de Operador• Analizadores LR(1)
TIPOS DE ANALIZADORES SINTACTICOS
ANÁLISIS ASCENDENTE Estilo general: Análisis sintáctico por
desplazamiento y reducción– Por precedencia de operadores (gramáticas muy
específicas)
– LR (generadores automáticos de AS), donde L significa que la entrada será leída de izquierda a derecha y R derivaciones por la derecha.
• Se construye el árbol de AS para una cadena w a partir de las hojas y se avanza hacia la raíz– Proceso: reducir w al símbolo inicial de la gramática– Cada reducción sustituye una subcadena (asidero o
mango) que concuerde con el lado derecho de un regla de producción por el símbolo no terminal del lado izquierdo de esa regla
Para una pequeña clase de gramáticas se puede construir con facilidad, eficientes analizadores sintácticos por desplazamiento y reducción.
Definición: Una Gramática es de operador cuando:
1.No tiene reglas de producción del tipo: A λ2.No tiene reglas con dos NO TERMINALES adyacentes: A α· B · C · β, donde A, B, C Є N
Ejemplos de gramáticas:
Gramáticas de operador
Inconvenientes:
• Es difícil de manejar componentes léxicos con dos precedencias distintas, como el signo menos (unario y binario)
• Solo una pequeña clase de gramáticas puede analizarse
Ventajas:
• Sencillez• Se pueden establecer relaciones de precedencia (* precede a +)
Se aplican con otros analizadores para la parte que no sean de operador
Gramáticas de operador
El análisis recorre la entrada de izquierda a derecha y se encuentra en dos posibles estados:
• Esperando un operador• Esperando un operando
El análisis mantiene dos pilas:
• Pila de operadores• Pila de operandos
Cuando un operador en la cima de su pila es de mas prioridad que el siguiente de la pila, entonces el pivote consiste en ese operador junto a los dos operandos situados mas arriba de la pila de operandos.
Análisis por Precedencia de Operador
Entrada: Id · + · id · * · id
Gramática: E ::= E · +· E | E · *· E |(· E· ) |id
La gramática es ambigua, pero este tipo de análisis proporciona una única derivación
Ejemplo de análisis simple
Entrada Pila de Operadores Pila de Operandos
Ida · + · idb · * · idc Ø Ø
+ · idb · * · idc Ø Ida
idb · * · idc + Ida
* · idc + Idb Ida
idc * + Idb Ida
Ø * + Idc Idb Ida
Relaciones de precedencia:
• a <· b , si a tiene menos precedencia que b• a b , si a tiene la misma precedencia que b• a · > b , si a tiene mayor precedencia que b
Ejemplo: + <· * , ( ) , /· > -
Algoritmo:1. Sustituir todos los símbolos no terminales por un único símbolo2. Insertar $ al principio y al final de la cadena de entrada3. Insertar las relaciones de precedencia en la cadena de entrada4. Mientras (entrada < > $S$) hacer4,1 Recorrer entrada desde la izquierda hasta encontrar · > 4.2 Buscar a la izquierda, a partir de ese punto , el primer <·4.3 Reducir el pivote que se encuentra en el medio mediante la aplicación
inversa de una de las reglas de derivación de la gramática cuya parte derecha coincida con dicho pivote
4.4 Reinsertar las relaciones de precedencia, ignorando los no terminales
Análisis por Precedencias
Cadena a evaluar: (id+id) Entrada = $· (· id · + · id · ) · $ Gramática: E ::= E · +· E | E · *· E |(· E· ) |id Tabla de Precedencia:
Ejemplo de análisis
Análisis: Entrada Derivación $<·(<· id· > + <· id· > )· > $ $·(· E· +· id· )· $
$<·(<· E + <· id· > )· > $ $·(· E· +· E· )· $ $<·(<· E + E· > )· > $ $·(· E· )· $ $<·( E )· > $ $· E· $
Si en el transcurso del reconocimiento se considera una pareja de símbolos para la que no esta definida ninguna relación precedencia se deduce entonces que ha sido detectado un error sintáctico en la cadena.
¿Cómo determinar las relaciones de precedencia entre un par de
terminales?
Definiciones:
• Cabecera(A) = {x/ (A* α· x· β) л (x Є ƩT) л (A Є ƩN) л (α Є Ʃ*N) л (β Є Ʃ*) }
• Ultimo(A) = {x/ (A* α· x· ß) л (x Є ƩT) л (A Є ƩN) л (α Є Ʃ*) л (β Є Ʃ*N) }
Ejemplo:
E ::= E · + · T | T T ::= T · * · F | F F ::= (· E · ) | Id
Propiedad:
V (A::= α · B · a · C · β) Є P, a Є ƩT, A,B,C Є ƩN, α,β Є Ʃ*, a siempre aparece en un nivel superior a los símbolos terminales de Cabecera (C) y Ultimo(B) en el árbol de derivación.
Definiciones de Cabecera y Ultimo
ƩN Cabecera Ultimo
E + , * , ( , Id + , *, ), Id
T * , ( , Id * , ) , Id
F ( , Id ) , Id
Reglas: (A::= α · B · a · C · ß) Є P, a Є ƩT, A,B,C Є ƩN, α,ß Є Ʃ*1. V c Є Cabecera(C), a <· c2. V b Є Ultimo(B), b ·> a3. V (A::= α · a · β · b · ϒ) Є P, a ,b Є ƩT, a b, β Є Ʃ* , ϒ Ʃ*4. Relacionar : $ <· a , V a Є cabecera(S), y b ·> $ , V b Є Ultimo(S),
donde S es el axioma de la gramática
Si existe mas de una relación de precedencia entre dos símbolos terminales, no es una gramática de precedencia
Algoritmo:V (A::= α · B · a · C · ß) Є P hacer Calcular Cabecera(C) Calcular Ultimo(B) Calcular las precedencias usando las reglas 1, 2 y 3V a Є Cabecera(S) hacer $<· aV b Є Ultimo(S) hacer b·> $
Construcción de la Tabla de Precedencias
Gramática: Calculo de Cabecera y Ultimo:
E ::= E · + · T | TT ::= T · * · F | FF ::= (· E · ) | Id
Calculo de la tabla
Calculo de la Tabla de Precedencias
ƩN Cabecera Ultimo
E + , * , ( , Id + , *, ), Id
T * , ( , Id * , ) , Id
F ( , Id ) , Id
Regla Precedencias (Regla1) Precedencias(Regla2)
E ::= E + T + <· * , ( , Id + , * , ), Id ·> +
T ::= T * F * <· (, Id *, ), Id ·> *
( id * + ) $
) ·> ·> ·> ·>
Id ·> ·> ·> ·>
* <· <· ·> ·> ·> ·>
+ <· <· <· ·> ·> ·>
( <· <· <· <·
$ <· <· <· <·
Investigar sobre la implementación de analizadores LR
Teoría de lenguajes y compiladores
Análisis Sintáctico Ascendente
Semana 9
Unidad II
Analizador Sintáctico
Recommended