Inicio > Sin categoría > Analizador Ascendente y Descendente

Analizador Ascendente y Descendente

Análisis sintáctico ascendente

Se usan dos técnicas de análisis ascendentes

  • Análisis por desplazamiento-reducción
  • Analisis por procedencia de operadores

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

Parte de la cadena de entrada para construir la inversa de una derivación por la derecha. Genera el árbol de análisis sintactico partiendo de las hojas hasta alcanzar el axioma

Análisis Ascendente General con Retroceso (AAGR)

Parte de las hojas del correspondiente árbol de derivación derecho (cadena de entrada)

Análisis de tipo shift-reduce (i.e. desplazamiento-reducción)

Usaremos una pila, en la que iremos almacenando las posibles alternativas con las que trabajamos.

Un movimiento consistirá en comprobar si la cabeza de la pila se puede reducir por un no-terminal. Si es así, se realiza una reducción.

Si coincide la cabeza de la pila con varias partes derechas de distintos símbolos no-terminales, éstas han de ordenanse en alguna forma, y aplicarlas según ese órden.

Si no hubiera reducción posible, hacemos un movimiento shift (apilar el siguiente símbolo a la entrada)

Siempre se ha de reducir antes de hacer un desplazamiento.

Si se agotan los símbolos a la entrada y no es posible hacer ninguna reducción más,

aplicamos retroceso hasta el punto de la última reducción.

Algunos problemas

Este método tiene serios problemas de terminación causados por las gramáticas con ciclos

Las gramáticas con ciclos pueden llevar a caer en

ciclos infinitos

Las que contienen  λ-  producciones pueden llevar aque el algoritmo no finalice (siempre podemos reducir λ por su correspondiente parte derecha)

Análisis sintáctico descendente

El  análisis  sintáctico  descendente  (ASD) intenta  encontrar  entre  las  producciones  de  la  gramática  la  derivación  por  la  izquierda  del  símbolo  inicial  para  una  cadena de entrada.

Ejemplo:

analizar  la  cadena  de  entrada  “cad”  dada  la  gramática siguiente:

S -> c A d

A ->a b | a

“cad”, se toma la primera producción.

Gramática

S ->c A d

A ->a b

A ->a

Diferencia

En el primero la construcción se inicia en la raíz de árbol y avanza hacia las hojas. En el segundo la construcción se inicia en las hojas y avanza hacia la raíz.
La diferencia entre uno y otro es que en el primero se pueden construir manualmente analizadores más eficiente con mayor facilidad mientras que en el segundo se puede manejar una mayor cantidad de gramáticas y esquemas de traducción.
Bibliografia

 

Categorías:Sin categoría
  1. Aún no hay comentarios.
  1. No trackbacks yet.

Responder

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

A %d blogueros les gusta esto: