Analizador Sintactico Ascedente y Descendente

Análisis Sintáctico

Análisis Sintáctico Ascedente

Introducción.-El análisis ascendente se basaba en la  identificación de asideros.

  • Asidero: subcadena de forma sentencial que concuerda con el lado derecho de una producción y cuya reducción al no terminal del lado izquierdo representa un paso a lo largo de la inversa de una derivación por la derecha.
  • Prefijo viable:Sea xhy una forma sentencial por la derechacon h un asidero. Se dice que r es un prefijo viable de xhy si xh=rs (s puede ser ε). Es decir, r a lo sumo puede incluir h.

Se usan dos técnicas de análisis ascendente:

  • Análisis por desplazamiento-reducción.
  • Análisis por precedencia de operadores.

Existen tres tipos ampliamente usados de analizadores (parsers) LR por desplazamiento-reducción: SLR(k), LALR(k) y LR(k) canónico.

Análisis por desplazamiento/reducción

Un analizador sintáctico LR por desplazamiento reducción
consta de una entrada, una salida, una pila, un programa conductor y una tabla de análisis sintáctico con dos partes (acción y goto).

El programa conductor es el mismo para todos los analizadores sintácticos LR; sólo cambian las tablas de un analizador a otro.

El programa utiliza una pila para almacenar una cadena de la forma s0X1s1X2s2… Xmsm Donde sm esta en la cima. Cada Xi es un símbolo gramatical y cada si es un símbolo llamado estado.

Cada símbolo de estado resume la información contenida debajo de él en la pila, y se usan la combinación del símbolo de estado en la cima de la pila y el símbolo en  curso de la entrada para indexar la tabla  del análisis sintáctico y determinar la decisión de  desplazamiento o reducción del analizador. (los símbolos gramaticales en la práctica no son necesarios).

En cada paso dos opciones:

  • Poner el token actual en la cima de la pila y llamar al
    analizador léxico para obtener un nuevo token (SHIFT).
  • Decidir que los símbolos en la cima de la pila forman un
    asidero, y entonces desapilarlos y reemplazarlos por la parte izquierda de su producción. (REDUCE).

Pueden surgir conflictos SHIFT-REDUCE que podemos resolver mirando el siguiente símbolo de la entrada sin leerlo.

Configuraciones LR(0)

Configuraciones, items marcados o elementos del análisis sintáctico LR(0): es una producción con un punto en alguna posición del lado derecho.

  • Ejemplo: la producción A→XYZ da lugar a cuatro items
    marcados: [A→·XYZ], [A→X·YZ], [A→XY·Z], [A→XYZ·].

Los items marcados se van a agrupar en estados de un autómata capaz de reconocer asideros en la cima de la pila.

Los estados del autómata esta compuesto de una serie de elementos nucleares y elementos no nucleares.

Operaciones elementales para diseñar el autómata:

  • Inicio: Se amplia la gramática con un nuevo axioma y la
    producción S´→ S #. Formar el núcleo del primer conjunto de items (estado del autómata). [S´→·S#]∈Set(0).
  • Cierre: Completar el núcleo de un cto de items. Si el símbolo que precede la marca es un no terminal, se añaden sus reglas con la marca al principio.
    Si [A→x·By]∈Set(n)∧B∈N⇒ [B→·w]∈Set(n) ∀ B→w ∈P
  • Lectura: Obtener conjuntos de items a partir de otros
    conjuntos de items.
    ∀[A→x·Xy]∈Set(n)⇒[A→xX·y]∈Set(n´)

Ej. obtención ctos items

analizador sintactico

automata

Algoritmo de análisis sintáctico LR

La tabla acción, A[s,a] si desplazar, reducir, aceptar o señalar un error cuando el estado s esta en la cima de la pila y a es el siguiente token de la entrada.

La tabla goto, G[s,X], da el nuevo estado a poner en el la cima de la pila. Esta función, para los terminales, esta codificada en la propia tabla acción.

Para las acciones se van a utilizar los siguientes códigos:

  • di significa desplazar y meter en la pila el estado i,
  • rj significa reducir por la producción con número j,
  • acep significa aceptar,
  • el espacio en blanco significa error.

Entrada: Una cadena w y las tablas de análisis sintáctico LR acción y goto para la gramática G.
Salida: Si w está en L(G), un análisis sintáctico ascendente de w; sino indica error.
Método: Inicialmente, en la pila esta el estado inicial 0, y w# en la entrada.
apuntar ae al primer símbolo de w#
repeat forever begin
sea s el estado en la cima de la pila y a el símbolo apuntado por ae;
if A[s, a]=desplazar s´ then meter a y después s´ en la cima de la pila;
avanzar ae al siguiente símbolo de entrada;
else if A[s, a]=reducir A→β then sacar 2 × |β | símbolos de la pila;
sea s´ el estado que ahora está en la cima de la pila;
meter A y después G[s´, A] en la cima de la pila;
emitir la producción A→β ;
else if A[s, a]=aceptar then return
else error()
end

Algoritmo de análisis sintáctico LR Ejemplo

tabla

Ejemplo conflicto SHIFTREDUCE


shift red

ANALISIS SINTACTICO DESCENDENTE

Especificación de la sintaxis de un lenguaje mediante gramáticas independientes del contexto (GIC). Estas gramáticas permiten recursividad y estructuras anidadas. Por ejemplo: sentencias if-else anidadas, paréntesis anidados en expresiones aritméticas, que no pueden ser representadas mediante expresiones regulares.

La recursividad va a implicar:

  • Algoritmos de reconocimiento más complejos, que hagan uso de llamadas recursivas o usen explícitamente una pila, la pila de análisis sintáctico.
  • La estructura de datos usada para representar la sintaxis del lenguaje ha de ser también recursiva (el árbol de análisis sintáctico), en vez delineal (caso de un vector de caracteres para almacenar los lexemas enel analizador léxico).

Fundamento de los métodos descendentes:

En cada paso del proceso de derivación de la cadena de entrada se realiza una predicción de la posible producción a aplicar y se comprueba si existe una concordancia entre el símbolo actual en la entrada con el primer terminal que se puede generar a partir de esa regla de producción, si existe esta concordancia se avanza en la entrada y en el árbol de derivación, en caso contrario se vuelve hacia atrás y se elige una nueva regla de derivación.

PROBLEMAS EN EL ANÁLISIS DESCENDENTE:

La recursividad a izquierdas da lugar a un bucle infinito de recursión.

Problemas de indeterminismo cuando varias alternativas en una misma producción comparten el mismo prefijo. No sabríamos cuál elegir. Probaríamos una y si se produce un error haríamos backtracking. Si queremos que el método sea determinista hay que evitarlas.

Existen transformaciones de gramáticas para su la eliminación. Estas transformaciones no modifican el lenguaje que se está reconociendo, pero si que cambian el aspecto de la gramática, que es en general menos intuitiva.

GRAMÁTICAS LL(1)

Las gramáticas LL(1) permiten construir de forma automática un analizador determinista descendente con tan sólo examinar en cada momento el símbolo actual de la cadena de entrada (símbolo de preanálisis) para saber que producción aplicar.

  • L: método direccional, procesamos la entrada de izquierda a derecha (from left to rigth).
  • L: obtenemos derivación más a la izquierda (left-most derivation).
  • 1: usamos un símbolo de prean´alisis para decidir la producción a aplicar.

Teorema 1: Una gramática LL(1) no puede ser recursiva a izquierdas y debe estar factorizada.
Teorema 2: Una gramática LL(1) es no ambigua.

Las afirmaciones inversas no tienen porque ser ciertas.

Análisis descendente con retroceso.

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

Ejemplo: Utilizaremos la siguiente gramática (No recursiva por la izquierda)

  1. E –> T + E
  2. E –> T
  3. T –> F * T
  4. T –>F
  5. F–>a
  6. F –>b
  7. F –> (E)

para reconocer la cadena de entrada: (a + b) * a + b

 

automatas

Mediante este árbol se pueden derivar todas las posibles sentencias reconocibles por esta gramática y el objetivo de este algoritmo es hacer una búsqueda en este árbol de la rama que culmine en la sentencia a reconocer.

El mecanismo funciona mediante una búsqueda primero en profundidad. Mira si todos los tokens a la izquierda de un No Terminal coincide con la cabeza de la secuencia a reconocer.

En todo el árbol de derivaciones, se pretende profundizar por cada rama hasta llegar a encontrar una forma sentencial que no puede coincidir con lo que se busca, en cuyo caso se desecha, o que coincide con lo buscado, momento en que se acepta la sentencia. Si por ninguna rama se puede reconocer, se rechaza la sentencia.

Problemas : Este método no funciona con gramáticas recursivas a la izquierda, ya que puede ocurrir que entre en un bucle infinito.
No existen muchos analizadores sintácticos con retroceso. En parte, porque casi nunca se necesita el retroceso para analizar sintácticamente las construcciones de los lenguajes de programación. En casos como el análisis sintáctico del lenguaje natural, el retroceso tampoco es muy eficiente, y se prefieren otros métodos.

Diferencias entre Ascendente y Descendente

  • Gramáticas que pueden ser tratadas
  • RI no importa en LR. RD tampoco, pero es más eficiente RI
  • Sencillez de detección de conflictos
  • Sencillez de implementación
  • Sencillez de depuración

Bibliografia:

 

About these ads
Esta entrada fue publicada en Varios. Guarda el enlace permanente.

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