Analizador Sintáctico

14 12 2010

Qué es el Analizador Sintáctico

Es la fase del analizador que se encarga de chequear el texto de entrada en base a una gramática dada. Y en caso de que el programa de entrada sea válido, suministra el árbol sintáctico que lo reconoce.

Gramática : G (N, T, P, S)

  • N = No terminales.
  • T = Terminales.
  • P = Reglas de Producción.
  • S = Axioma Inicial.

Tipos de análisis sintáctico

Estrategias para construir el árbol sintáctico:

  • Análisis ascendente llamado Análisis LR(n)
  • Análisis descendente llamado tambien  Análisis LL(n)

donde:

L =>Left to Right: la secuencia de tokens de entrada se analiza de izquierda a derecha

L => Left-most (R = Right-most): utiliza las derivaciones más a la izquierda (a la derecha)

n =>es el número de símbolos de entrada que es necesario conocer en cada momento para poder hacer el análisis.

Funcionamiento:

Lo primero que se debe hacer es :

  1. Busca aquellas subcadenas de la entrada que sean la parte derecha de una producción y las sustituye por la parte izquierda correspondiente.

Se nos presenta un pequeño problema: Que hay varias subcadenas que coinciden en una parte derecha.

Ademas se debe considerar que:

– No es lo mismo sustituir una u otra: una podría llevar al éxito.

Analizadores sintácticos descendentes (Top-down)

  • Parten del axioma inicial, y van efectuando derivaciones a izquierda hasta obtener la secuencia de derivaciones que reconoce a la sentencia.
  • Construyen el árbol sintáctico de la raíz (arriba) a las hojas (abajo).
  • Parten del símbolo inicial de la gramática (axioma) y van expandiendo producciones hasta llegar a la cadena de entrada.

Pueden ser:

  • Análisis Descendente con retroceso
  • Análisis de Gramáticas LL  (cadena por la izquierda y derivaciones a la izquierda)

Análisis  descendente con Retroceso

Este parte del axioma inicial y aplica todas las posibles reglas al no terminal más a la izquierda.

  • Usa retroceso para resolver la incertidumbre.
  • Sencillo de implementar.
  • Muy ineficiente.

Ejemplo:

Dada la gramática:

  • N = {S,A,B}
  • T = {a,b,c,d}
  • A = S
  • R
  • (1) S=>cAd
  • (2) A=>bcB
  • (3) A=>a
  • (4) B=>b
  • Y la cadena “cad”

Vamos a aplicar el análisis descendente con retroceso para comprobar si dicha cadena pertenece o no al lenguaje descrito mediante las reglas de la gramática.

Pasos para la resolución del problema

Paso 1. Se parte del axioma de la gramática: S

Paso 2. Se sustituye el símbolo no terminal situado más a la izquierda por la primera alternativa posible a dicho símbolo. Se anota en una pila el número de regla

Empleada.

–       El símbolo no terminal más a la izquierda es S y la única alternativa es S  cAd

–        La pila contiene el número 1.

Paso 3. La subcadena de símbolos terminales consecutivos que han aparecido a la izquierda de la forma sentencial es c y la tira a analizar es cad. Por tanto, se supone válida esta producción y se continúa.

Paso 4. Ahora la forma sentencial es cAd, cuyo primer símbolo no terminal es A, y la primera de las producciones para A es A  bcB.

–       Aplicando la nueva forma sentencial obtenemos cbcBd.

–        La pila de análisis contiene ahora 1-2

Paso 5. La subcadena izquierda de símbolos terminales es ahora cbc, que no encaja con el principio de la tira analizada.

Tenemos que aplicar el retroceso

Paso 6. Se anula la producción anterior, obteniendo nuevamente la forma sentencial cAd. Retiramos el símbolo superior de la pila de análisis, quedando ésta como antes (es decir, 1).

Paso 7. Se aplica ahora la segunda de las alternativas del símbolo no terminal A, que es A  a,

–       Se obtiene la forma sentencial cad.

–        En la pila de análisis se introduce el número de la regla aplicada quedando ésta como 1-3

Paso 8. La subcadena izquierda de símbolos terminales es cad, que coincide exactamente con la tira analizada.

Paso 9. La forma sentencial no incluye ningún símbolo no

terminal, por lo que el proceso termina satisfactoriamente.

–        El parse izquierdo de la cadena está contenido en la pila (1-3)

Condición para poder realizar este análisis

Que la gramática no sea recursiva por la izquierda, y en general que no tenga ciclos por la Izquierda.

Ejemplo:

A => Aa | a

Realizar el análisis descendente con retroceso

¿Qué ocurre?

Solución: Gramática equivalente no recursiva por la izquierda y sin ciclos.

Análisis de Gramáticas LL

El método de análisis consiste en leer la cadena de entrada de izquierda a derecha, (L: Left to rigth) utilizando reglas de producción izquierda (L: Left most) e inspeccionando un (1) solo

símbolo de la entrada para elegir la regla conveniente.

Este análisis se denomina LL(1).

  • Para cada símbolo terminal leído, se elige la regla más conveniente teniendo en cuenta dicho símbolo terminal

Inconveniente:

  • No puede aplicarse para cualquier gramática.
  • Debe ser una gramática que admita análisis LL(1).
  • Comprobar condición de gramática LL(1) antes de aplicar el análisis.

Ejemplo:

Ejemplo #2:

Analizadores sintácticos ascendentes (Bottom-up)

  • Construyen el árbol sintáctico comenzando por las hojas.
  • Parten de los terminales de la entrada y mediante reducciones llegan hasta el símbolo inicial.

Consideraciones:

  • Comprueban si una cadena de símbolos pertenece a un lenguaje aplicando reducciones sobre la entrada hasta alcanzar el axioma de la gramática.
  • En general son más potentes que los métodos descendentes.
  • Pueden manejar gramáticas recursivas a izquierdas.
  • Los algoritmos de implementación son más complejos que los de los métodos ascendentes.
  • La implementación “a mano” de estos algoritmos es demasiado compleja por lo que generalmente se utilizan generadores automáticos.

Análisis ascendente reducción – desplazamiento

  • La entrada se “reduce” al símbolo inicial
  • Desplazando elementos de la entrada
  • Llegar de las hojas hacia la raíz
  • A partir de la entrada

Se sustituye una subcadena

  • Adecuadamente elegida
  • Que concuerde con un lado derecho

Por el no terminal del lado izquierdo

  • Trazando una derivación inversa
  • Por el lado derecho.

Mangos

  • B es  Subcadena.
  • Concuerda con un lado derecho.
  • Se reduce al no terminal de la izquierda.
  • Avanza un paso en la derivación inversa.

De una derivación derecha.

  • Si la gramática no es ambigua.

Existe exactamente un mango.

  • Gramáticas LR
  • Left to Right

–   de izquierda a derecha

  • Rightmost production

–   La producción de más a la derecha

  • Variaciones: SLR, LALR, LR(k)

Diferencias

  • En un análisis top-down un parser hacer corresponder cadenas de entrada con sus correspondientes derivaciones izquierdas.
  • En un análisis bottom-up un parser hace corresponder cadenas de entrada con las inversas de las correspondientes derivaciones derechas.
  • Se basan su funcionamiento en la existencia de una tabla especial asociada de forma única a una gramática.
  • El principal inconveniente del método ascendente es que supone demasiado trabajo construir manualmente un analizador sintáctico para una gramática de un lenguaje de programación típico.

Fuente: Descendenete , Ascendente


Actions

Information

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: