¿Qué generador de analizador para enseñar a mis alumnos?

Question

Estoy enseñando (con otros) un curso relativamente introductorio en ciencias de la computación 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.

Algún consejo sobre qué enseñar sería apreciada

Answer 1

Antlr es ampliamente utilizado, bien documentada, y libre. Es compatible con Ant, y puede apuntar a Java entre muchos otros idiomas.

Answer 2

Recuerdo haber usado CUP y me gustó. Eche un vistazo al CUP Parser Generator for 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.

... permiso para usar, copiar, modificar y distribuir este software y su documentación para cualquier propósito y sin Gastos de la presente se otorga, siempre que el anterior aviso de derechos de autor aparezca en todas las copias y que tanto el aviso de copyright y este aviso de permiso y garantía descargo de responsabilidad aparezcan en la documentación ...

Answer 3

Lex y Yacc todavía están en uso . Uno de los idiomas más nuevos, F #, tiene sus propias versiones (fslex, fsyacc, ver here para ver un ejemplo). Por lo tanto, creo que enseñarlos sigue siendo relevante.

Answer 4

Puede omitir la parte del generador y echar un vistazo a los combinadores de analizadores Scalas.

Answer 5

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?

(Ya que no programar en Java en estos días no he probado ratas en particular.)

Answer 6

Actualmente estoy tomando un curso de compiladores que utiliza 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.

Answer 7

Es una lástima que sus alumnos 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é atrás Antlr, Lex y Yacc! Es mucho más flexible teniendo la gramática descrita junto con el código.

Biblioteca brillante, aunque con una curva de aprendizaje ciertamente no trivial.

Sin embargo, sin C++, Antlr es probablemente su mejor opción.

Answer 8

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.

Answer 9

Javacc es muy fácil.
En el mismo archivo tiene la gramática y la lista de tokens.

https://javacc.dev.java.net/

Answer 10

recuerdo usando bisonte en una de mis clases de compiladores. También usamos flex y YACC.

Answer 11

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.

Answer 12

No lo he intentado todavía, 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.

Answer 13

Yacc y todos los demás analizadores LALR (1) datan de una época en la que los recursos de la máquina eran escasos y era necesario dedicar mucho tiempo a 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 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.

Answer 14

OCaml tiene un fantástico conjunto de generadores de analizadores. Here son algunos ejemplos simples.

JavaCC también es bastante bueno.

Recomiendo encarecidamente evitar C (y C++) para este propósito porque son extraordinariamente dolorosos en este contexto.

Answer 15

Me gusta mucho el GOLD Parsing System, porque básicamente genera las tablas necesarias y solo tiene que usar una implementación (genérica) de un procesador que utiliza 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 usando las tablas LALR y DFA para procesar la entrada, y escribir dicha implementación puede ser un buen ejercicio para enseñarles.