Compiladores de compiladores en .net

Detalles

Compiladores: principios, técnicas y herramientasDe vez en cuando, hace falta que una aplicación sea capaz de entender e interpretar -a veces, incluso traducir- expresiones escritas en algún lenguaje.

No estamos hablando, necesariamente, de construir compiladores o intérpretes complejos de lenguajes de programación. Las mismas técnicas, aunque a distinto nivel, se aplican tanto para construir un compilador de Pascal, una pequeña calculadora capaz de evaluar expresiones aritméticas o un cliente de IRC capaz de aceptar scripts sencillos.

En general, estamos hablando de que un programa sea capaz de reconocer una serie de sentencias escritas en algún lenguaje y bien traducirlas a otro lenguaje (compilar) o realizar acciones a medida que las va reconociendo (interpretar).

 

Para diseñar un lenguaje -por muy sencillo que sea- que pueda ser reconocido por una aplicación no vale hacerlo de cualquier manera. Muchas reglas de los lenguajes naturales, como el español, no pueden ser formalizadas para que un ordenador las aplique sin un cierto nivel ambigüedad. Es mejor seguir unas normas algo más "rígidas". El lingüista Noam Chomsky fijó, en el siglo XX, las bases de la Gramática Generatíva, una teoría y técnica para describir las reglas de los lenguajes tanto naturales como artificiales, incluso reglas de construcción de expresiones sencillas. Dicho de otro modo, una gramática es un conjunto de reglas sintácticas que describen un lenguaje. Los lenguajes de programación caen casi todos dentro de la categoría que Chomsky denominó lenguajes independientes del contexto.

Las técnicas básicas para realizar un compilador/intérprete de un lenguaje formal son bien conocidas desde hace algúnas décadas, aunque en los últimos años se han producido algunos avances muy significativos.

El proceso para describir un lenguaje es, en términos generales, siempre el mismo. Es necesario tener claras dos cosas:

  • Los distintos tipos de elementos léxicos que va a tener un lenguaje. En español, por ejemplo, hay determinantes, sustantivos, verbos... en un lenguaje como Pascal hay enteros, palabras reservadas, cadenas... esta descripción identifica las unidades léxicas del lenguaje.
  • En segundo lugar, las reglas sintácticas que combinan unos elementos léxicos con otros... es decir, la propia gramática. La forma de expresar una gramática en aplicaciones computacionales suele hacerse, curiosamente, en un determinado lenguaje: BNF (Backus-Naur Form, en honor a sus diseñadores, John Backus y Peter Naur). A menudo, a BNF se le considera un metalenguaje, porque en realidad, es un lenguaje para describir lenguajes =:-o

La ilustración que acompaña este texto es del libro Compiladores: principios, técnicas y herramientas, de Aho, Sethi y Ullman, del año 1986 -la edición en español que yo tengo es de 1990-. Se le conoce popularmente como "el libro del dragón", por motivos obvios. Aunque hay mucha literatura, alguna bastante buena y más moderna que habla de lenguajes y la construcción de compiladores e intérpretes, éste libro es toda una referencia. En él hablan extensiva e intensivamente del análisis léxico y sintáctico de los lenguajes.

El mecanismo para reconocer sentencias escritas en un lenguaje siempre empieza por combinar dos piezas de software fundamentales: una de ellas debe hacer el análisis léxico, es decir, reconocer las "palabras" -a esta pieza de software se le llama analizador léxico, lexer o scanner; a las palabras se las denomina a menudo tokens- y pasar esos tokens a la siguiente pieza de software, el analizador sintáctico, que se encarga de ver si están bien combinadas y forman alguna estructura gramatical reconocible, como bucles asignaciones, o similares -al analizador sintáctico se le llama a menudo parser-.

Ambas piezas juntas son capaces de, por un lado, reconocer errores léxicos y sintácticos; o, si todo ha ido bien y no hay errores, generar el llamado árbol sintáctico abstracto (AST-Abstract Syntax Tree), o simplemente arbol sintáctico. El AST es una estructura de datos en memoria con forma de árbol que representa a la estructura sintáctica de la entrada -es decir, del programa o expresión que estamos intentando reconocer e interpretar.

A partir de ahí, el trabajo que se debe hacer depende del objetivo que se pretenda lograr: hacer algún tipo de interpretación o de traducción. Este trabajo se puede hacer recorriendo el AST o incluso "al vuelo" mientras el AST se está formando.

Pues bien, afortunadamente, desde los años 80 existen herramientas que a partir de unas reglas léxicas y sintácticas (una gramática) permiten construir de manera automática el analizador léxico -scanner- y el analizador sintáctico -parser-. Genéricamente se les ha llamado compiladores de compiladores -aunque esta denominación no es, a mi juicio, muy acertada-. Dos de las más populares han sido lex y yacc (o en sus versiones GNU: flex y bison). Tienen ya un chorro de años. Originalmente generaban analizadores léxicos y sintácticos respectivamente para el lenguaje C en plataformas Unix. A lo largo de las últimas décadas han surgido herramientas similares para distintos lenguajes y otras claramente superiores, que aprovechan las características y capacidades de los lenguajes y las plataformas más modernas.

Cuando surgió la plataforma .net y el lenguaje C# se veía claramente que el entorno era muy propicio para la creación o adaptación de éstas herramientas y otras similares. En efecto, así ha sido. Así que para terminar, una pequeña lista de aplicaciones que nos ayudan en la construcción de analizadores léxicos y sintácticos.... compiladores de compiladores. Todos ellos admiten C# como plataforma de desarrollo:

  • COCO/R Es un sistema que, a partir de una gramática LL(k) genera un lexer/parser. Existen versiones para diferentes lenguajes (C#, C++, Java, F#, Visual Basic.NET, Oberon, Pascal, Modula-2, Ada, Ruby y Unicon.
  • ANTLR Otro generador de analizadores léxicos y sintácticos en C#, C++, Java, Php, Objective C, Python, Ruby, Lisp, Perl, Oberon, Ada y Actionscript.
  • Linguistic Parsing System Este paquete, desarrollado por Fred Mellender permite generar analizadores léxicos/sintácticos de gramáticas LALR(k), LL(k), and LR(k), aunque sean ambigüas :-o
  • Compiler tools in C# (aka lex/yacc) Para los más tradicionales, en la página de Malcom Crowe se encuentra disponible para descarga una versión un generador de analizadores léxicos y parsers al estilo lex/yacc pero para C#.
  • NParsec Una versión del paquete Jparsec para C#. Permite analizar léxicamente y sintácticamente una entrada y generar un arbol sintáctico o realizar acciones a medida que se parsea. Las reglas se definen directamente mediante sentencias de C#. En la página se ilustra un atractivo ejemplo para construir un pequeño evaluador de expresiones aritméticas
  • Irony.net Irony es un sistema para crear compiladores/intérpretes a partir de una gramática, para C#. Como todos estos paquetes, es capaz de realizar un escáner léxico y un parseado, pero su manera de funcionar es muy particular con respecto a otros: las reglas de la gramática LALR(1) se codifican diréctamente en C#. A partir de ahí, puede generar el arbol sintáctico de una entrada.
  • Gardens Point Parser Generator & Scanner generator En ésta página de la universidad de Queensland se puede descargar un generador de analizadores léxicos y parsers, al estilo lex/yacc/bison para C#
  • GOLD Parsing System Un parser gratuito y multilenguaje, con muy muy muy buena pinta.
   

Síguenos  

   

¿Dónde estoy?  

Estás en La tecla de ESCAPE, un sitio web personal en el que nos gusta hablar de algoritmos, metodología de la programación, personajes de informática, tecnología, ingeniería del software, internet, y cualquier otra tontería que se nos ocurra.

[{modal url=url=index.php?option=com_content&view=article&id=1301}Leer más / Términos de uso (ToS){/modal}]

   

¿Quién está en línea?