ANALISIS SINTACTICO

Tipos de Análisis

De la forma de construir el árbol sintáctico se desprenden dos tipos o clases de analizadores sintácticos. Pueden ser descendentes o ascendentes.

Descendentes: Parten del axioma inicial, y van efectuando derivaciones a izquierda hasta obtener la secuencia de derivaciones que reconoce a la sentencia.

Pueden ser:

­Con retroceso.

­Con recursión.

­LL(1)

Ascendentes: Parten de la sentencia de entrada, y van aplicando reglas de producción hacia atrás (desde el consecuente hasta el antecedente), hasta llegar al axioma inicial.

Pueden ser:

­ Con retroceso.

­ LR(1)

Análisis descendente con retroceso.

Objetivo: 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)

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

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.

Análisis descendente con recursión. Diagramas de Conway.

Una gramática de contexto libre puede expresar un lenguaje al igual que puede hacerlo la notación BNF, y los diagramas de Conway.

Definición: Un diagrama de Conway es un grafo dirigido donde los elementos no terminales aparecen como rectángulos, y los terminales como círculos.

Para demostrar que permite representar las mismas gramáticas que la BNF, se hace por inducción sobre las operaciones básicas de BNF:

De esta forma todos los posibles caminos desde el inicio del grafo hasta el final, representan formas sentenciales válidas.

En todo diagrama de Conway hay un origen y un destino.

Análisis descendente de gramáticas LL(1)

Una gramática LL(1) es aquella en la que su tabla de chequeo de sintaxis no posee entradas múltiples, o sea, es suficiente con examinar sólo un símbolo a la entrada, para saber qué regla aplicar. Toda gramática reconocible mediante el método de los diagramas de Conway es LL(1)

El método consiste en seguir un algoritmo partiendo de:

- La cadena a reconocer, junto con un apuntador, que nos indica cual es el token actual.

- Una pila de símbolos (terminales y no terminales)

- Una tabla asociada de forma unívoca a una gramática. En esta asignatura no vamos a ver como calcular dicha tabla.

La cadena de entrada acabará en el símbolo $, que consideramos como si fuese un EOF( End Of File - Fin de Fichero).

Análisis Sintáctico Ascendente

Aquí se construye el árbol sintáctico de abajo hacia arriba, lo cual disminuye el número de reglas mal aplicadas con respecto al caso descendente (si hablamos del caso con retroceso).

Tanto si hay retroceso como si no, en un momento dado, la cadena de entrada estará dividida en dos partes. α y β

β. El trozo de la cadena de entrada (secuencia de tokens) por reconocer. Coincidirá siempre con algún trozo de la parte derecha de la cadena de entrada: βєT*.Vamos consumiendo tokens, y todos los tokens que nos queden por consumir constituyen β.

α. coincidirá siempre con el resto de la cadena de entrada, trozo al que se habrán aplicado algunas reglas de producción, α є (NυT)* en sentido inverso.

Análisis Ascendente con retroceso.

Cuando se da cuenta que llega a una situación en la que no puede continuar, entonces vuelve atrás deshaciendo todos los cambios.

En el análisis con retroceso no se permiten las reglas J, puesto que estas se podrán aplicar de forma indefinida.

Por desplazamiento y reducción

La entrada se “reduce” al símbolo inicial

Desplazando elementos de la entrada

Llegar de las hojas hacia la raíz

Procedimiento

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

Ejemplo

Gramática

S => aABe

A => Abc | b

B => d

Entrada “abbcde” se reduce a S por:

Abbcde

aAbcde

aAde

aABe

S

Diferencia

En el análisis sintáctico descendente se construye el árbol sintáctico arriba hacia abajo y se utiliza más reglas, en cambio en el análisis sintáctico ascendente se construye el árbol sintáctico de abajo hacia arriba, lo cual disminuye el número de reglas mal aplicadas con respecto al caso descendente

Fuente: http://www.lcc.uma.es/~galvez/ftp/tci/tictema3.pdf