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