2008
02.06

Estos últimos meses, he estado desarrollando, por diversión y en mis (pocos :-() ratos libres, mi propio kit para construir compiladores. Más que un compilador, es una herramienta para construir compiladores (existen otras como Lex y Yacc -Flex y Bison en su versión GNU). Su nombre es Bparser.

Lo he colgado en mi wiki.

La ventaja que tiene sobre el binomio LEX/YACC es que YACC genera analizadores sintácticos LALR. Por contra esta herramienta permite construir herramientas para gramáticas más potentes, del tipo LR(n). En principio utiliza un símbolo (Lookahead) para tomar decisiones ante las reglas de la gramática, así como prefijos viables.

Finalmente, si no consigue discernir qué regla es la adecuada, empezará a hacer backtracking (marcha atrás) para intentar averiguar cual qué reglas se deben aplicar.

Permite pues, gramáticas ambiguas, y es, de alguna forma, similar al GLR. Yacc también puede emplear el algoritmo GLR, pero es menos eficiente, y puede tomar en algunos casos tiempo y memoria exponencial.

El ejemplo de la calculadora

El ejemplo del programa que hace de calculadora es el “Hola Mundo” de los generadores de analizadores sintácticos. A continuación se pone un ejemplo de calculadora que procesa expresiones matemáticas. Simplemente se introducen las expresiones matemáticas, como 1+3.2*5^2 y el programa mostrará el resultado por pantalla (así como las reglas de análisis de las operaciones). El programa terminará cuando introduzcamos una entrada vacía.

Esta herramienta la estoy usando en el proyecto de Compilador de BASIC de ZX Spectrum, que servirá como lenguaje para probar a fondo esta herramienta.

Share
  1. Leo (#3):

    Bueno, no es del todo cierto. Esto es una herramienta para hacer compiladores, no un compilador concreto para un lenguaje particular. Y los errores semánticos siempre corren a cargo del programador.

    Respecto a la parte de errores sintácticos, es cierto que está incompleta (al menos con respecto a YACC), pero es mucho más complicado detectar errores sintácticos en gramáticas ambiguas o del tipo LR(n). De hecho es casi imposible.

    Por otra parte, me hubiera gustado que hubieras dejado un enlace a tu MINIJAVA, para echarle un vistazo. 🙂 Si vuelves por aquí, por favor, ponlo.

    Like or Dislike: Thumb up 0 Thumb down 0

  2. Es un compilador muy incompleto.
    No tienes la parte de errores Sintacticos y Semanticos.
    Yo en este momento estoy terminand un MINIJAVA, por asi decirlo donde tengo en cuenta casi todo.

    Like or Dislike: Thumb up 0 Thumb down 0

  3. Paul:

    Yes, that’s the plan. In fact is both an exercise of nostalgia and compilers skills. 🙂

    I think it will produce rather well optimized code. The syntaxis, on the other hand is much advanced (not like ZX BASIC). It follows the FreeBASIC syntax.

    Like or Dislike: Thumb up 0 Thumb down 0

  4. So, the plan is to make a cross compiler for ZX Basic? Wow! That would be so cool. I wish this existed 25 years ago 🙂

    I remember fighting with hisoft basic to cram as much as I could into memory. It will be interesting to see if I can find some of my old programs and run them through your example compiler when it’s done.

    One imagines that with faster processing and memory options, such a thing could be remarkably well optimized.

    Paul

    Like or Dislike: Thumb up 0 Thumb down 0