Analizador Sintáctico

14 dic

Estrategias para analizadores sintácticos

El analizador sintáctico debe verificar si la entrada corresponde a alguna derivación de S

•Primera aproximación:
–generar todas las derivaciones de S posibles
–comprobar si la entrada corresponde con alguna de ellas
Inviable, incluso para gramáticas muy sencillas

Son necesarias estrategias más “astutas”
•Las estrategias son de dos categorías análisis DESCENDENTE y ASCENDENTE.

Diferencias:
–análisis DESCENDENTE(Top-Down)
»construye el árbol desde la raíz (S) hasta llegar a las hojas

–análisis ASCENDENTE(Bottom-Up)
»construye el árbol desde las hojas hacia la raíz (S)

•Propiedades deseables en un analizador sintáctico

–eficiente
»en general, se buscarán polinomiales en el tamaño del programa a reconocer

–determinar la acción reconociendo unos pocos tokens de entrada
»como máximo, un k preestablecido
»en la práctica, suele ser k=1

–no necesitar “marcha atrás”(backtracking)
»i.e., evitar decisiones
»las acciones semánticas son difíciles de deshacer

–no ocupar mucha memoria
»actualmente, esto no es tan importante

 

ANALISIS   DESCENDENTE

Básicamente, es un intento de encontrar una derivación por la izquierda.
Desde el punto de vista del árbol de sintaxis, correspondería a un recorrido en pre-orden
•Método:
–Objetivo: reconocer S

»se divide el objetivo en subobjetivos
(de acuerdo a las producciones)
»se trata de cumplir cada subobjetivo
»se sigue con cada subobjetivo, hasta que se encuentren concordancias de terminales (o se detecte un error)

 

Implementación de analizadores descendentes:
La forma más natural es asociar un procedimiento con cada no terminal
–cada procedimiento:
»comprueba la corrección del token en estudio con el que el propio procedimiento representa
•incorrecto: mensaje de error y/o estrategia de recuperación
»hacer avanzar al siguiente token
–afinando un poco más:
»no terminal: genera invocaciones
»terminal: concordancia entre terminales
•error sintáctico ó
•avanzar a token siguiente

Analizador sintáctico descendente recursivo

Ideas básicas del método:
–construir un conjunto de procedimientos (recursivos si necesario)
»uno por cada no terminal de la gramática–cada procedimiento:
»determina la producción a aplicar
»invoca los proc. correspondientes
»detecta error o pasa al siguiente token–la secuencia de invocaciones

Incovenientes:
–necesidad de backtracking: cuando la regla elegida no es la correcta “devolver”a la entrada todos los tokens recorridos
–recursividad a izda.: si alguna regla se define con recursividad a izda., el analizador sintáctico construído entra en un bucle infinito

Soluciones:
–Factorización a izda.
»Idea: retrasar la decisión, de manera que siempre se tome la buena decisión
–Eliminación de recursividad a izda
»En analizadores descendentes, la recursividad a izda. da lugar a bucles infinitos
»La recursividad directa a izda. se puede eliminar mediante una transformación de la gramática
 

Analizadores sintácticos predictivos

Un analizador sintáctico predictivo es un analizador sintáctico descendente recursivo que NO necesita marcha atrás
•Condición exigible a una gramática para que sea posible:
–que en todo momento, a partir del siguiente token de entrada, sea posible determinar qué regla aplicar
•Esto es posible cuando (una de dos):
–ningún no terminal tiene alternativas en su parte derecha
»gramáticas poco interesantes
–no terminales con alternativas que empiecen por distintos símbolos
-Hay más casos en que también es posible

Analizadores sintácticos predictivos no recursivos

El hecho de que haya reglas recursivas hace que el analizador predictivo implementado directamente sea recursivo
•Sin embargo, la recursividad se puede evitar mediante el uso explícito de una pila
•Un analizador predictivo sabe, a partir del símbolo que estáanalizando y el siguiente símbolo de entrada, quéregla aplicar

Construcción de una tabla para el análisis
•Lo fundamental para la construcción de un analizador sintáctico predictivo no rec.”construcción de la tabla”
•Idea básica: uso de las funciones “primero”y “siguiente”
•Objetivo: utilizar dichas funciones para construir la tabla de análisis predictivo
Una gramática es LL(1) si la tabla construída tiene una única salida para cada entrada
Construcción de la tabla:
–filas indexadas por no terminales
–columnas indexadas por terminales

Una gramática es LL(1) cuando en la tabla construída según el método anterior cada elemento es una de las dos cosas siguientes:
*ERROR
*un conjunto con una única producción.

 

ANALISIS ASCENDENTE (LR, LALR)

Algunos problemas no se pueden resolver de forma descendente ya que no están fácil quitar la ambigüedad. En algunos casos es más fácil demostrar algo ya existente.
• Generalmente los analizadores sintácticos LR(k) son del tipo “bottom-up”
• El analizador trata de reducir la cadena de entrada w al símbolo inicial S. En un proceso que recorre el árbol de derivación en sentido
inverso que se llama reducción.
• No sólo es necesario una gramática que no presente ambigüedades sino que también tenga el valor de k más pequeño.

Ejemplo:

Reducción                      Regla a aplicar

(b)+b
(T)+b                                    T->b
(A)+b                                    A->T
T+b                                       T->(A)
A+b                                       T->b
A                                            A->A+T
S                                             S->A

 

Existen tres técnicas diferentes para construir analizadores LR.
1. Un primer método es el SLR (Simple LR), el más sencillo de construir pero es el menos potente de los tres.
2. Por otro lado tenemos el método LR canónico, que es el más costoso y potente de los tres.
3. Por último, el método LALR (Look-Ahead LR) está entre los otros dos, en términos de su complejidad y potencia.

Bondades de los Analizadores LR

  • El conjunto de gramáticas LL es un subconjunto propio de las gramáticas LR.
  • Es posible construir un analizador sintáctico LR para reconocer prácticamente la totalidad de las
  • construcciones de los lenguajes de programación que se pueden definir mediante gramáticas CFG.
  • El método de análisis LR es el método del tipo shift-reduce, sin retroceso, más general que se conoce pero además su aplicación es tan eficiente como la de otros métodos shift-reduce menos generales.
  • Los errores pueden detectarse tan pronto como sea posible hacerlo, en un examen de la entrada de izquierda a derecha.

Desventajas de los Analizadores LR
Como desventaja principal podemos indicar la de que construir un analizador sintáctico de este tipo para una gramática dada es demasiado complejo como para intentar hacerlo a mano.
Para ello se deben usar generadores de analizadores automáticos como YACC.

 

EJEMPLOS

 

DESCENDENTE

Derivación izquierda:
• S->aA->aaBbC->aabbC->aabbc (1234)
• S->aA->aaBbC->aaBbc->aabbc (3421)
• LL(k) traductores “top-down”
• Un análisis anticipado de k caracteres

• S->aS|cA
• A->bA|cB|epsilon
• B->cB|a| epsilon
• Construir cadena acbb
• S->aS o S->cA; al anticipar el primer símbolo

 

Prefijo     Anticipación      Regla a Aplicar     Derivación
epsilon              a                                 S->aS                       S->aS
a                          c                                  S->cA                         ->acA
ac                        b                                 A->bA                        ->acbA
acb                     b                                 A->bA                        ->acbbA
Acbb                 E                                 A->epsilon               ->accbb

L={a^n.a.b.c^n | n>0}
• S->aSc|aabc
• Se requiere una anticipación de por los
menos tres símbolos LL(3)
• S->aaAc

 

ASCENDENTE

Entrada = abcdef
Pila vacía

 

…………….S                                                                                                                                                                                                                                                                        .

/            /             \          \

B             c              E               F

/   \                         /   \

A    b                      d      D

|                                      |

a                                      C

/   \

e       f

Avanza
Pila = a

Reduce A->a
Pila = A

Avanza
Pila = Ab

Reduce B->Ab
Pila = B

Avanza
Pila = Bc

Avanza
Pila = Bcd

Avanza.
Pila = Bcde
(Secuencia de prefijos de partes derechas)

Avanza
Pila = Bcdef

Reduce C->ef
Pila = BcdC

Reduce D->C
Pila = BcdD

Reduce E->dD
Pila = BcE

Reduce F->epsilon
Pila = BcEF
(Pila crece sin consumir
entrada)

Reduce S->BcEF
Pila = S
(Fin del reconocimiento)

 

 

Webgrafia:

-OLIVARES Juan- Unidad IV: Análisis Sintáctico, [en línea], vease en: http://antares.itmorelia.edu.mx/~jcolivar/courses/ps207a/ps2_u4.pdf [Fecha de consuta: 2010-12-14]

-EZPELETA J.- Universidad de Zaragoza,  Compiladores, [en línea], vease en: http://webdiis.unizar.es/~ezpeleta/lib/exe/fetch.php?media=misdatos:compi:4.asll1.pdf [Fecha de consuta: 2010-12-14]

- FORTES Jose- Generación de analizador sintáctico ascendente, [en línea], vease en: http://serdis.dis.ulpgc.es/~ii-pl/ftp/transp/tr-asint-ver.pdf [Fecha de consuta: 2010-12-14]

Derivación izquierda:
• SaAaaBbCaabbCaabbc (1234)
• SaAaaBbCaaBbcaabbc (3421)
• LL(k) traductores “top-down”
• Un análisis anticipado de k caracteres
About these ads

Deja un comentario

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.

%d personas les gusta esto: