parsing - que - generadores para el hogar
¿Qué generador de analizador para enseñar a mis alumnos? (15)
Estoy enseñando (con otros) un curso relativamente introductorio en informática para profesionales de TI sin experiencia en CS. Desde que desarrollé los materiales del curso sobre autómatas y gramáticas, también soy responsable de enseñar sobre compiladores y construcción de compiladores.
Hace años, cuando estudiaba compilación en la universidad, todos nuestros ejemplos provenían de Lex y Yacc. ¿Todavía se usan ampliamente? ¿Hay algo que se use más comúnmente para Java? Los estudiantes son competentes en C y Java, pero nunca han usado generadores de analizadores.
Cualquier consejo sobre qué enseñar sería apreciado
Actualmente estoy tomando un curso de compiladores que usa Lex y Yacc. Realmente no sé de ningún otro tipo, pero la teoría que estamos aprendiendo parece corresponderse bastante bien con estas herramientas.
Lex y Yacc todavía están en uso. Uno de los idiomas más nuevos, F #, tiene sus propias versiones (fslex, fsyacc; mira aquí para ver un ejemplo). Por lo tanto, creo que enseñarlos sigue siendo relevante.
Los sistemas de análisis PEG como RATS son más simples que el combo lex / yacc. Esto puede o no ser una ventaja para su clase: ¿su objetivo es enseñar sobre expresiones regulares y autómatas finitos, y gramáticas LR y autómatas pushdown, etc.? ¿O quieres las herramientas de frontend de compilador más simples?
(Dado que no programo en Java actualmente, no he probado RATS en particular).
Puede omitir la parte del generador y echar un vistazo a los combinadores de analizadores Scalas.
Recuerdo haber usado CUP y me gustó. Eche un vistazo al CUP Parser Generator para Java .
CUP se mantiene en la Universidad Técnica de Munich. Creo que su objetivo principal es enseñar a los estudiantes.
También tiene un modelo de licencia libre.
... Se otorga permiso para usar, copiar, modificar y distribuir este software y su documentación para cualquier propósito y sin cargo, siempre que el aviso de copyright anterior aparezca en todas las copias y que tanto el aviso de copyright como este permiso y garantía descargo de responsabilidad aparece en la documentación de apoyo ...
Antlr es ampliamente utilizado, bien documentado y gratuito. Es compatible con Ant, y puede apuntar a Java entre muchos otros idiomas.
Es una pena que sus estudiantes no estén bien versados en C ++. Una vez que encontré la biblioteca Spirit con su concepto de una DSL rica en estilo EBNF, ¡dejé Antlr, Lex y Yacc atrás! Es mucho más flexible tener la gramática descrita junto con el código.
Brillante biblioteca, aunque con una curva de aprendizaje ciertamente no trivial.
Sin embargo, sin C ++, Antlr es probablemente tu mejor opción .
No uso generadores lexer y analizador. Son lo suficientemente simples como para generarlos a mano, y son las partes más fáciles de compilar para escribir. Además, cuando los construyes a mano, puedes hacerlos realmente rápidos.
Javacc es muy fácil.
En el mismo archivo tienes la gramática y la lista de tokens.
Recuerdo haber usado Bison en una de mis clases de compiladores. También usamos flex y YACC.
Todavía no lo he probado, pero encontré jparsec hace unos días. No es un generador de analizadores sintácticos, sino que el analizador sintáctico está construido en Java mediante combinators en un estilo EBNF.
Me gusta mucho el sistema de análisis GOLD , porque básicamente genera las tablas necesarias y solo tiene que usar una implementación (genérica) de un procesador que usa la información de la tabla para procesar los tokens. Este motor (como se lo llama) es bastante fácil de escribir y es básicamente una implementación pura utilizando las tablas LALR y DFA para procesar la entrada, y escribir dicha implementación puede ser un buen ejercicio para enseñarles.
OCaml tiene un fantástico conjunto de generadores de analizadores. Aquí hay algunos ejemplos simples.
JavaCC también es bastante bueno.
Recomiendo evitar C (y C ++) para este propósito porque son extraordinariamente dolorosos en este contexto.
Yacc y todos los demás analizadores LALR (1) datan de una época en que los recursos de la máquina eran escasos y era necesario dedicar mucho tiempo a la ingeniería de la gramática para poder ejecutar un analizador en un PDP-11 con 64K de RAM. . Hoy no tiene sentido enseñar una herramienta como yacc con una terrible interfaz humana y un conjunto muy limitado de gramáticas que puede usar.
Recomendaría cualquiera de los analizadores basados en PEG, como Rats !, o el analizador de GLR, Elkhound, desarrollado por George Necula y Scott McPeak (quark de agradecimientos). Lo siento, no puedo recomendar una herramienta específica para Java, ¡pero Ratas! es bueno para C.
ANTLR está bien, pero es demasiado complejo para mi gusto.
Si planea trabajar con Java, JavaCC o ANTLR deberían ser suficientes. Este último también es compatible con C y Python. Pero si planeas trabajar con C ++, tal vez deberías echarle un vistazo a Boost :: Spirit.