Análisislexicográfico

Análisissintáctico

Análisis semántico

Generación de código

Optimización

Preparación para la

generación de código

Manejo de tablas-Tabla de símbolos-Tabla de literales-Tabla de ciclos iterativos-Tabla de representación intermedia

Manejo de

ErroresE/S

Árbol del Análisis

sintácticoTokens

ANALISIS SINTACTICO ASCENDENTE

Introducción Como repaso breve, el problema del

análisis sintáctico es la construcción del árbol de análisis sintáctico dada una cadena de símbolos dada una cadena de símbolos en un lenguaje y una gramática para ese lenguaje.

Los analizadores Sintácticos Ascendentes construyen un árbol de análisis sintáctico desde abajo hacia arriba, es decir, desde las hojas hasta la raíz

Gramáticas LR

•En Correspondencia con las Gramáticas LL para el análisis sintáctico descendente , se tiene las gramáticas LR para el análisis sintáctico ascendente.• La L indica que la cadena de entrada se rastrea de izquierda a derecha, y la R que se esta construyendo una derivación derecha en realidad la derivación se construye en reserva

Gramáticas LR(k)•Estas se definen como:Una gramática es LR(k) si, para cualquier forma sentencia en una derivación derecha•Donde w y pueden ser nulas y w (si es no vacía)se compone por entero de símbolos terminales, el manejador B puede identificarse al buscar los k símbolos mas ala izquierda de w•La gramáticas LR(1)describen construcciones que se encuentran por lo regular en lenguajes de programación.

1. E E + T2. E T3. T T * F4. T F5. F (E)6. F Id

Considérese de forma sentenciaE + T * IdSin una búsqueda hacia adelante, podríamos decir que “ E + T” es el manejador y empleando la producción 1, reducir la forma sentencia a:

E * IdEntonces Id seria el controlador que reduce a F y luego a TT y posteriormentea E, dejándonos con E * E Esta forma sentencia no puede reducirse

Ejemplo 2Una gramática LR(0)

S a S aI b S bI c

Es mas difícil demostrar que una gramática es LR(k) que demostrar que no lo es. Este Ejemplo genera cadenas simétricas de a’s y b’s con una c en medio.Para cualquier forma sentencia siempre es posible identificar y reducir el manejador sin examinar ninguno de los símbolos pasadosExiste una interesante clase de gramáticas entre LR(0) y LR(1)se conocen como Gramáticas SLR(1) donde “S” significa simple

Análisis Sintáctico LRUn analizador sintáctico (en inglés parser) es una de las partes

de un compilador que transforma su entrada en un árbol de derivación.

Se analiza la técnica eficiente de análisis sintáctico ascendente que se puede utilizar para una clase mas amplia de gramáticas independientes del contexto:TECNICA: ANALISIS SINTACTICO LR(k)Donde: “L” es por el examen de entrada de izquierda a derecha.

“R” por construir una derivación por la derecha en orden inverso.

“k” por el numero de símbolos de entrada de examen por anticipado utilizados para tomar las decisiones del análisis sintáctico.

Nota: Cuando se omite se asume que “k” es 1.

Análisis Sintáctico LR

El análisis sintáctico es atractivo por varias razones: Se pueden construir analizadores sintácticos LR para

reconocer prácticamente todas las construcciones de los lenguajes de programación.

Se puede aplicar tan eficientemente como los otros métodos de desplazamiento y reducción.

La clase de gramáticas que pueden analizarse con los métodos LR es un supra conjunto de la clase de gramáticas que se pueden analizar con analizadores sintácticos predictivos.

Un analizador sintáctico Lr puede detectar un error sintáctico con gran velocidad.

Análisis Sintáctico LRLos analizadores sintácticos LR, también conocidos como Parser LR,

son untipo de analizadores para algunas gramáticas libres de contexto. Pertenece

ala familia de los analizadores ascendentes, ya que construyen el árbolsintáctico de las hojas hacia la raíz. Utilizan la técnica de análisis pordesplazamiento reducción. Existen tres tipos de parsers LR: SLR (K), LALR (K) y LR (K) canónico:

Un analizador LR consta de: Un programa conductor Una entrada Una salida Una tabla de análisis sintáctico, compuesta de 2 partes (ACCION Y

GOTO)

Análisis Sintáctico LREjemplo:

Análisis "top-down"Se parte del axioma y se va realizando la reducción. La palabra x (normalmente una

instrucción) se llama metau objetivo del análisis. La primera fase del análisis consiste en encontrar, entre las reglas

cuya parte izquierda esel axioma, la que conduce a x. Análisis "top-down" con vuelta atrás lentaSea el axioma S y las reglas cuya parte izquierda es el axioma: S ::= X1 X2 ... Xn | Y1 Y2 ... Ym | ... Sea x la palabra a reconocer. El objetivo del análisis

es encontrar una derivación tal que S ->* x Probaremos primero la regla S ::= X1 X2 ... Xn Debemos descomponer x en la forma x = x1 x2 ... xn y tratar de encontrar las derivaciones X1 ->* x1 X2 ->* x2 ... Xn ->* xn Cada

una de las derivaciones anteriores es una submeta. Pueden ocurrir los siguientes casos:

Xi = xi: submeta reconocida. Pasamos a la submeta siguiente. Xi != xi y Xi en AT*: submeta rechazada. Intentamos encontrar otra submeta válida en X(i-

1). Si i=1, elegimos la siguiente parte derecha para el mismo símbolo no terminal a cuya parte derecha pertenece Xi. Si es el último, elegimos la siguiente parte derecha del símbolo no terminal anterior. Si éste es el axioma, la cadena x queda rechazada.

Xi es un símbolo no terminal. Buscamos las reglas de las que Xi es parte izquierda: Xi ::= Xi1 Xi2 ... Xin | Yi1 Yi2 ... Yim | ... elegimos la primera opción:

Análisis Sintáctico LREjemplo:

Algoritmo para generar un autómata LR(0) [editar]Para generar un autómata LR(0) en base a una gramática G, primero se

debe definir:Gramática ampliada: Dado una gramática G, se define la gramática

ampliada G'a: 1. Se agrega una producción S'->S# donde S es el símbolo inicial.(el #

representa el fin de cadena) 2. Se pasan todas las producciones a ítems de configuración (veremos este concepto en un instante) con el punto al principio de la cola 3. Se define S' como el símbolo inicial de la gramática. Ítem de configuración: un ítem de configuración es una producción que tiene un carácter especial (generalmente un punto) en algún lugar de la cola. Por ejemplo: la producción S->ABC genera los siguientes ítems,{ S->.ABC, S->A.BC, S->AB.C S->ABC.}. Como veremos en un instante, y hablando informalmente el punto representa el lugar actual en donde me puedo encontrar en un momento en el parseo en una producción.

Clausura de un ítem: se define a la clausura de un ítem (y de forma informal) a: dado un ítem S->A.cB (A, B e V*, c e Vt unión VN) al conjunto formado por

Análisis Sintáctico LR1. S->A.cB 2. Si c es un no terminal, se agregan todos los ítems

que tengan a c como cabeza de la producción y el punto al principio de la cola, 3. Si p es un ítem que pertenece a la clausura, la clausura de p pertenece a la clausura, siempre y cuando ya no este agregada. En otras palabras, y para que se entienda el concepto, la clausura de un ítem representa todas las producciones que se pueden aplicar a una cadena valida a partir del punto del ítem.

Finalmente, la construcción del autómata es así:

Se amplía la gramática

Dado el símbolo inicial de la gramática ampliada, se calcula su clausura y este se define como un estado inicial.

Análisis Sintáctico LRPara cada estado: se agrupan las producciones según el

carácter que está después del punto, si todavía no se definió el estado, se corre el punto un carácter a la derecha, se crea el nuevo estado con esta producciones, y la clausura de cada una de ellas, se define el carácter que estaba después del punto en el estado de origen como el carácter de la transición.

Si el estado tiene en alguna producción el punto al final, este estado se marca como un estado final del autómata.

Se sigue hasta que ya no se tenga más estados nuevos posibles.

Estrictamente hablando, el autómata LR es un autómata determinista, aunque, en general, su utilidad radica en ser la base para la construcción de la tabla LR(0).

Elección de un Método de Análisis SintácticoMétodos de Análisis Ascendente:

• Método de Reducción-Desplazamiento (no predictivo).

• Métodos Predictivos:

• Análisis de Precedencia de Operador.

• Análisis de Precedencia Simple.

• Análisis LR.

Método de Reducción y DesplazamientoMétodo de Reducción y DesplazamientoSe basa en una máquina de pila donde:• El alfabeto de la pila está formado por los símbolos terminales y no

terminales.• El alfabeto de entrada está formado por los símbolos terminales.• La función de transición se define en base a las siguientes acciones

sobre la pila:{ Desplazar, Reducir, Aceptar, Error }Parte de la secuencia de símbolos de la entrada.El proceso de análisis consiste en ir explorando el tope de la pila y los

elementos siguientes en la pilahasta encontrar una subcadena τ que coincida con la parte derecha de una

producción dada A → τ.Si se encuentra τ en la pila, entonces se sustituye τ por A en el tope de la

pila. A este proceso se ledenomina reducción. Y el proceso de pasar símbolos de entrada al tope de

la pila se llamadesplazamiento.

Método de Reducción y DesplazamientoProblemas:

• Que existe más de una producción para aplicar reducción (conflicto reduce/reduce).

• Incertidumbre si es posible aplicar desplazamiento en vez de reducción (conflicto desplaza/reduce).

Siempre es posible aplicar desplazamiento, ampliando las posibles subcadenas en el tope de la pila

suceptibles de ser reducidas en base a un mayor número de producciones. ¿Qué acción es la más

apropiada?.

Método de Reducción y DesplazamientoDescripción Funcional del Método de Reducción y

Desplazamiento

Descripción funcional: Sea D la descripción instantánea de la máquina de pila representada por la

terna que forman el estado de la pila, la secuencia de entrada y las producciones aplicadas.

Método de Reducción y DesplazamientoEjemplo 5.1: Sea G una gramática definida por las

producciones siguientes:

Análisis Ascendente Predictivo de Precedencia de OperadorResuelve la acción alternativa (ante posibles conflictos

desplaza/reduce) enbase a criterios de precedencia entre operadores.El análisis de precedencia de operador es aplicable a lenguajes

definidos porgramáticas con las siguientes restricciones:

1. No podrán aparecer dos símbolos no terminales consecutivos en las producciones.2. No podrán existir producciones a la cadena vacía.3. Las relaciones de precedencia deben ser disjuntas.

La tabla de análisis de precedencia de operador está formada únicamente por

símbolos terminales puestos de la siguiente forma:

Análisis Ascendente Predictivo de Precedencia de OperadorLa tabla de análisis de precedencia de operador está formada

únicamente por

símbolos terminales puestos de la siguiente forma:

Método para Obtener las Relaciones precedencia de OperadorMétodo para Obtener las Relaciones de Precedencia de

Operador

Otros Métodos para Obtener las Relaciones de Precedencia de OperadorOtros Métodos para Obtener las Relaciones de Precedencia de Operador1. Método Intuitivo: Basado en el sentido común y asociado con las reglas

del cálculo en dondese aplica una precedencia de cálculo según una precedencia de operadores. Se

conoce ellenguaje en virtud de la gramática y es sencillo extraer las relaciones de

precedencias.2. Método Deductivo: Basado en el análisis de las gramáticas mediante el

desarrollo de losárboles de análisis. Como requisito, las gramáticas deben ser no ambiguas. Útil

cuando lagramática no permite determinar las precedencias.3. Método Asociativo: Basado en la asociatividad de los operadores y en

las reglas deprecedencia de operadores para el cálculo [Aho90]. Método general de

resolución de conflictosen base a precedencia y asociatividad.