Archivo | Compiladores RSS feed for this section

JavaCC

3 Feb

JavaCC

El JavaCC (Java Compiler Compiler) es un generador de programa de parsers (analizadores) de la fuente abierta para el lenguaje de programación de Java. JavaCC es similar al Yacc en que genera un programa de análisis para una gramática proporcionada en la notación EBNF, a menos que la salida sea código fuente de Java. Es semejante de Yacc, sin embargo, JavaCC genera programas de análisis de arriba hacia abajo, que lo limita al LL (k) clase de de gramáticas (particularmente, la repetición dejada no se puede utilizar). El constructor que lo acompaña, JJTree, construcciones del árbol sus árboles de la parte inferior para arriba.

JavaCC se autoriza debajo de una licencia del DEB.

En el 1996, el Sun Microsystems lanzó un generador de programa de análisis llamado Gato . Los reveladores responsables del Gato crearon a su propia compañía llamada Metamata y cambiaron el nombre de Gato del a JavaCC. Metamata se convirtió en eventual parte de WebGain . Después de que WebGain cerrara sus operaciones, JavaCC fue movido a su hogar actual.

La especificación proporcionada al generador JavaCC puede contemplar distintos aspectos del lenguaje para el que se quiere obtener el analizador:
– Características lexicográficas y sintácticas
es la forma más frecuente de uso del generador; la especificación proporcionada define las característi¬cas sintácticas y lexicográficas de un lenguaje y se genera un analizador léxico-sintáctico del lenguaje especificado.
– Características lexicográficas
en la especificación proporcionada al generador sólo se definen características lexicográficas del lengua¬je; con el código generado se puede obtener un analizador lexicográfico.
Características lexicográficas y sintácticas y comprobaciones semánticas
también es posible completar una especificación léxico-sintáctica con la inclusión de código Java com-plementario para que el programa generado (que incorpora adecuadamente ese código auxiliar) pueda hacer un análisis completo (léxico, sintáctico y semántico) del lenguaje especificado.

HERRAMIENTAS

Dado que el código generado por JavaCC está escrito en Java, es necesario disponer de una versión del sis-tema Java (compilador de Java e intérprete de la Máquina Virtual Java). Son programas de libre distribución y fáciles de conseguir. Estos son:

javacc: generador de analizadores
jjdoc: productor de documentación
jjtree: preprocesador de apoyo para tareas semánticas

Acción lexicográfica. Acción sintáctica

• acción lexicográfica: bloque de código Java asociado a una pieza sintáctica nominal (TOKEN) o a una secuencia de caracteres (SKIP); se ejecuta cuando se detecta en la entrada la pieza o la secuencia corres­pondiente; no se puede aplicar a piezas sintácticas anónimas (autodefinidas con comillas),

• acción sintáctica: bloque de código Java asociado a un punto de la estructura sintáctica (el punto indica­do por el sitio de la producción donde se inserta el bloque); se ejecuta cuando el análisis de la entrada pa­sa por ese punto de la estructura.

Valor de una pieza sintáctica comunicada

El analizador lexicográfico comunica al analizador sintáctico una pieza a través de un valor de la clase Token (fichero Token.java); un objeto de la clase Token representa las características de la pieza comunicada. En la clase Token, entre otros, se tienen los campos

String image

lexema de la pieza

int beginLine, beginColumn, endLine, endColumn

posición del lexema en el fichero analizado (indicada por los números de fila y de columna de su comienzo y de su terminación)

Valor asociado a un símbolo

En las producciones que especifican la sintaxis se pueden incluir asignaciones que sirven para dejar ano­tado el valor asociado a un símbolo:

• símbolo no terminal              valor = nombreSimbolo()

el método de análisis asociado a nombreSimbolo se ha declarado de un cierto tipo (distinto del tipo void); valor ha de ser una variable del mismo tipo que el método

• símbolo terminal                   dato = < nombrePieza >

el valor asignado es el valor de la clase Token representativo de la pieza sintáctica (nominal); dato ha de ser una variable de tipo Token

Pieza sintáctica comunicada

La pieza sintáctica comunicada puede mirarse desde cada uno de los dos analizadores:

• analizador sintáctico

la pieza comunicada (desde el analizador lexicográfico) se tiene anotada en un campo de la clase del analizador sintáctico declarado como

(static) public Token token

este valor es accesible desde el código de todos los métodos de análisis sintáctico; el contenido del campo varía cuando se recibe una nueva pieza sintáctica

• analizador lexicográfico

la pieza dispuesta para ser comunicada (al analizador sintáctico) se tiene anotada en una variable local declarada como

Token matchedToken

este valor es accesible para el código de todas las acciones lexicográficas

Lexema de la pieza comunicada

El lexema de la pieza sintáctica comunicada se encuentra disponible en dos sitios distintos que compar­ten el mismo nombre pero que son de distinto tipo y se usan de distinta manera:

• String image

es un campo de la clase TOKEN; puede consultarse en relación con un objeto de esa clase que esté disponible

• StringBuffer image

es un campo de la clase del analizador lexicográfico ( ∙ ∙ ∙ ∙ TokenManager.java); es accesible desde el código de la clase y, por lo tanto,  desde todas las acciones lexicográficas (bloques de có­digo que están incorporados al analizador lexicográfico);

se trata de un valor disponible tanto para las piezas sintácticas nominales (TOKEN) como para las secuencias que se saltan (SKIP)

Lexicografía

TOKEN    pieza sintáctica nominal

“∙ ∙ ∙”  pieza sintáctica anónima

SKIP     secuencia de caracteres que no forman pieza

1acción

lexicográfica

común

Commom –

TokenAction

2acción

lexicográfica

propia

(acción ligada

a una pieza)

3bloque de

declaraciones

lexicográficas

TOKEN_

MGR_DECLS

4declaraciones

lexicográficas

predefinidas

(disponibilidad

de uso)

TOKEN si si si si
“∙ ∙ ∙” si no
SKIP no si si si

▫ Las indicaciones “si” de las columnas 3 y 4 son consecuencia de las indicaciones de la columna 2.

▫ La acción lexicográfica común se ejecuta después de la acción lexicográfica propia.

 

Precisiones sobre el analizador sintáctico generado

Puede decirse que, en su funcionamiento más sencillo, cuando no se emplean las posibilidades de examen por adelantado (“lookahead”), JavaCC comprueba que las reglas sintácticas cumplen la condición LL(1) y generan un analizador descendente-predictivo-recursivo. Pero esta apreciación hay que matizarla, ya que el analizador sintáctico generado no se ajusta en sentido estricto al modelo de analizador LL(1).

En el modelo de análisis LL(1), el orden del examen de las distintas alternativas de expansión de un símbo­lo no terminal es indiferente ya que se conocen los símbolos directores de cada una de ellas (que resultan ser conjuntos disjuntos); en la implementación del subprograma de análisis asociado al símbolo no terminal <NombreSimb> cuyas producciones son

<NombreSimb> ::= α1

| α2

∙  ∙  ∙

| αn

se podría preguntar en cualquier orden si la pieza actual pertenece al conjunto de símbolos directores de las distintas reglas. Sin embargo, en el analizador sintáctico generado por JavaCC, la implementación del mé­todo asociado al símbolo no terminal <NombreSimb> no sigue esa pauta.

Si las anteriores reglas sintácticas se transcriben en JavaCC de la forma

void nombreSimb () :

{  }

{

α1-jcc

| α2-jcc

∙  ∙  ∙

| αn-jcc

}

el método de análisis generado procede de la siguiente manera:

se van considerando las alternativas, sucesivamente, en el mismo orden en el que están especifica­das: primero la de α1 (α1-jcc), después la de α2 (α2-jcc),  etc,

para cada alternativa seleccionada, se comprueba si la pieza por adelantado coincide con alguno de los símbolos iniciales de la parte derecha, y si hay coincidencia se prosigue el análisis con ella; si no hay coincidencia se pasa a la alternativa siguiente,

siguiendo con este orden, si se llega al final de las alternativas sin haberse encontrado coincidencia alguna, se produce un error sintáctico.

En el analizador generado por JavaCC hay una peculiaridad que no se tiene en los analizadores LL(1) es­trictamente considerados: la palabra vacía sí se considera como posible símbolo inicial de la parte derecha una regla (esto ocurre siempre que la parte derecha es anulable). De esta peculiaridad se deriva una conse­cuencia que ha de tenerse en cuenta al escribir la especificación: dado que siempre es posible considerar la palabra vacía como la siguiente pieza por adelantado, si se llega a examinar la alternativa correspondiente a una producción anulable, el analizador generado siempre seleccionará esa alternativa con independencia de la siguiente pieza que esté presente en la entrada que queda por analizar.

Así pues, si alguna de las producciones que definen un símbolo no terminal es anulable, es importante el or­den en que se escriben las alternativas en una especificación sintáctica JavaCC: el funcionamiento del ana­lizador generado sí depende de la colocación elegida para las reglas.

LINKS

  papar

ANTLR

2 Feb

ANTLR

(ANother Tool for Language Recognition – otra herramienta para reconocimiento de lenguajes)


ANTLR es un generador de parsers (analizadores) , donde se admiten solamente gramáticas LL (gramática independiente de contexto).  Actualmente ANTLR genera código Java, C, C++, C#, Python, Perl, Delphi, Ada95, JavaScript y Objective-C. Otros lenguajes como Ruby, php, etc. son generados por medio de extensiones planteadas por la comunidad.
Apareció en: 1988. Su desarrollador fue Terence Parry . La última versión estable es la 3.2 (23-09-2009) Los sistema operativo que lo soportan son  Linux, Windows, Mac OS X.  BSD es la licencia de software
La ventaja más importante es la “estandarización” con ANTLR basta con comprender el paradigma de análisis una vez para poder implementar todas las fases de análisis.

NIVELES

ANTLR es capaz de actuar a tres niveles a la vez (cuatro si se tiene en cuenta la generación de código):

  • Análisis léxico
  • Análisis sintáctico
  • Análisis semántico

CARACTERÍSTICAS

  • El nombre de los tokens es en mayúscula y el nombre de las variable de la gramática en minúsculas.
  • Las reglas llevan : y acaban con ;
  • Para incluir clases o paquetes hay que incluirlos dentro de un campo header @ header { import java.util.*; }
  • En caso de querer poner atributos a la clase, a~nadir un campo que se llame members. por ejemplo @members { int j;}
  • Muestra el diagrama de las reglas gramaticales
  • Permite testear nuestras gramáticas con ejemplos
  • Podemos ejecutar directamente nuestros programas
  • Las gramáticas tienen que ser LL
  • La variable inicial no deberia ser incluida en la parte derecha de ninguna producción
  • Las acciones se denen en la gramática por medio de llaves y son simplemente codigo java
  • Los tokens tienen un atributo llamado texto y se les puede repetir
  • Para ignorar tokens es necesario utilizar el metodo {skip();}

ANTLR y los tokens

  • ‘x’..’y’ cualquier cosa en este rango.
  • (‘x’|’y’) una de las dos opciones.
  • ˜ ‘x’ cualquier cosa menos ‘x’
  • Operadores: +   *

APLICACIÓN

Es una herramienta que proporciona un marco de trabajo para la construcción de reconocedores, intérpretes, compiladores y traductores de lenguajes
a partir de gramáticas enriquecidas con acciones. En resumen proporciona todo lo necesario para el desarrollo de:
· Construcción de analizadores léxicos.
· Construcción de analizadores sintácticos.
· Mecanismos de construcción y recorrido de árboles de sintaxis abstracta (AST).
· Mecanismos de tratamiento de plantillas.
· Mecanismos de detección y recuperación de errores.

ANTLR y las reglas gramáticales
Se admite cualquier tipo de reglas denidas por medio de expresiones regulares.

LINKS

Apareció en: 1988
Desarrollador: Terence Parr y Colaboradores
Última versión estable: 3.2 (23-09-2009)
Influido por: PCCTS
Sistema operativo: Linux, Windows, Mac OS X
Licencia de software: licencia BSD
Web: http://www.antlr.org

DEFINICIONES DIRIGIDAS POR LA SINTAXIS

31 Ene

Hay dos notaciones para asociar las reglas semánticas con las reglas de producción:

  • Las definiciones dirigidas por la sintaxis
  • Los esquemas de traducción

En este post se hablará sobre las definiciones dirigidas por la sintaxis.

.

DEFINICIÓN DIRIGIDA POR LA SINTAXIS (DDS)

  • Es una generalización de una gramática independiente de contexto en la que cada símbolo gramatical tiene asociado un conjunto de atributos
  • Especifica la traducción de una construcción en función de los atributos asociados con sus componentes sintácticos
  • Utiliza una gramática independiente de contexto para especificar la estructura sintáctica de la entrada
  • A cada símbolo de la gramática se le asocia un conjunto de atributos
  • A cada regla de la gramática se le asocia un conjunto de reglas semánticas para calcular los valores de los atributos asociados con los símbolos de esa regla
  • La gramática y el conjunto de reglas semánticas constituyen la definición dirigida por la sintaxis

TRADUCCIÓN: Una traducción es una transformación de una entrada en una salida. La salida para cada entrada W se especifica como sigue:

  • Se construye un árbol sintáctico para W
  • Suponiendo que un nodo n del árbol está etiquetado con el símbolo X de la gramática se escribe X.a para indicar el valor del atributo a de X en ese nodo
  • El valor de X.a en n se calcula por la regla semántica para el atributo a asociado a la regla X utilizada en el nodo n
  • El árbol de análisis sintáctico que muestra los valores de los atributos en cada nodo se denomina árbol de análisis sintáctico con anotaciones

ATRIBUTOS
El conjunto de atributos asociado a cada símbolo gramatical se divide en dos subconjuntos

  • Atributos sintetizados. Se pueden calcular durante un solo recorrido ascendente del árbol de análisis sintáctico
  • Atributos heredados. Sirven para expresar la dependencia de una construcción en de un lenguaje en el contexto en el que aparece

Si se considera un nodo de un símbolo gramatical de un árbol sintáctico como un registro para guardar información entonces un atributo se corresponde con el nombre de un campo
Un atributo puede representar cualquier cosa (una cadena, un número, un tipo, una posición de memoria…)

  • El proceso de calcular los valores de los atributos en los nodos se denomina anotar o decorar el árbol de análisis sintáctico
  • El valor de un atributo se define mediante la regla semántica asociada a la regla de producción utilizada en ese nodo
  • El valor de un atributo sintetizado se calcula a partir de los valores de los atributos de los hijos de ese nodo en el árbol de análisis sintáctico
  • El valor de un atributo heredado se calcula a partir de los valores de los atributos de los hermanos y el padre de ese nodo
  • En una definición dirigida por la sintaxis, se asume que los terminales sólo tienen atributos sintetizados (la definición no proporciona ninguna regla semántica para los terminales)
  • Los valores para los atributos de los terminales son proporcionados generalmente por el analizador léxico

REGLAS SEMÁNTICAS

  • Las reglas semánticas establecen las dependencias entre los atributos que serán representadas mediante un grafo
  • El grafo de dependencias proporciona el orden de evaluación de las reglas semánticas
  • La evaluación de las reglas semánticas define los valores de los atributos de los nodos del árbol
  • Una regla semántica puede tener también efectos colaterales (imprimir un valor, actualizar una variable global…)
  • Una gramática con atributos es una definición dirigida por la sintaxis en la que las funciones de las reglas semánticas no pueden tener efectos colaterale.

Ejemplo de reglas semánticas:

Producción

Reglas Semánticas

L → E n

print (E.val)

E → E1 + T

E.val := E1.val + T.val

E → T

E.val := T.val

T → T1 * F

T.val := T1.val x F.val

T → F

T.val := F.val

F → ( E )

F.val := E.val

F → digito

F.val := digito.valex

EJEMPLO: Definición Dirigida por la Sintaxis de una calculadora de escritorio sencilla

APLICACIÓN DE UNA DDS

• Construcción de árboles sintácticos
• Mas general, la generación de código intermedio
• Chequeo de tipos
• Evaluación o interpretación de código

.

LINKS:

Compiladores: Sesión 15. Análisis semántico, traducción dirigida por sintaxis

Compiladores: Traducción dirigida por la sintaxis

Análisis Semántico: Traducción dirigida por la Sintaxis

Capítulo 5: Traducción Dirigida por Sintaxis

INICIONES DIRIGIDAS POR LA SINTAXIS

Juego de Memoria….

17 Ene

Vamos a Jugar…..

Este juego a parte de ser muy entretenido e interesante, ayuda a mejorar la concentración.

Es muy recomendado especialmente para los niños.

NUMERO DE JUGADORES: 1 jugador

LICENCIA: GPL 2

REGLAS DEL JUEGO

1. Se presentan todas la imagenes boca abajo.

2. El jugador destapa las imagenes de dos en dos  tratando de hacer las parejas

2.1 Si coinciden, es decir si tienen el mismo dibujo, quedan levantadas; el jugador continuara destapando las imagenes hasta que haya formado todas las parejas.

2.2 Si por el contrario no coinciden las imagenes regresaran a su posición normal (boca abajo).

3. Según el nivel en el que se este jugando, se gana si ha formado todas las parejas, si no ha sobrepasado el número de intentos o haya cumplido con el tiempo correspondiente.

HERRAMIENTAS

Las herramientas que se utilizaron para la elaboración del mismo fuerón: IDE Netbeans 6.8, Plataforma Java, y las librerias adicionales Liquid, Nimrod y JavaHelp.

Para crear el instalador para Windows CreateInstaller.

Para crear el instalador para Linux se  uso  InstallJamer.

.

Descargar JuegoMemoria para Windows

Descargar JuegoMemoria para Linux

.

mini_manual Juego de Memoria….

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