tutorial - ¿Hay algún generador de analizadores LL para lenguajes funcionales como Haskell o Scala?

scala lenguaje

Question

Me he dado cuenta de una clara falta de analizadores de LL que crean analizadores sintácticos en lenguajes funcionales. El hallazgo ideal para lo que he estado buscando sin éxito es algo para generar un analizador Haskell para una gramática LL (*) de estilo ANTLR (reformateo de la gramática modulo menor), y me sorprendió que cada último generador de analizadores con un funcional El objetivo de idioma que encontré fue algún tipo de analizador LR.

Quiero hacer una transición del analizador sintáctico de este idioma en el que estoy trabajando, que tiene características funcionales de ANTLR para autohospedarse en el idioma en sí, y sería de gran ayuda si pudiera transferir a mi idioma algo que seguramente sería correcto en otro lenguaje funcional. (preferiblemente con los que estoy familiarizado, Haskell y Scala), en lugar de tener que volver a escribirlo completamente desde cero, aunque al final podría hacerlo, ya que el lenguaje central es pequeño.

En este momento, más que una solución a esto, tengo mucha curiosidad sobre por qué no hay tales generadores de analizadores LL (*) o LL (k), pero muchos generadores LR, dado que LL parece inherentemente más fácil.

Answer 1

Puede usar ANTLR que genera analizadores LL * en Java (entre otros), por lo tanto, archivos .class resp .jar .

Answer 2

La razón principal de esto es que la mayoría de los analizadores LL (k) que se escriben en lenguajes funcionales simplemente se implementan utilizando los combinadores de analizadores, porque la ruta más fácil para generar una biblioteca combinadora de analizadores es el descenso recursivo .

Parsec de Haskell, attoparsec , y polyparse y los combinadores de analizador de stock de Scala producen todos lo que son analizadores de LL (*).

Tanto parsec como attoparsec requieren que uses un combinador de intentos explícito para retroceder, pero esto solo se hace por eficiencia y los combinadores scala parser también pueden tratar el análisis de paquetes .

Considere el siguiente fragmento del anuncio del reciente paquete independiente de Brent Yorgey:

parseAtom = parens parseTerm
    <|> var <$> ident
    <|> lam <$> brackets ident <*> parseTerm

es bastante fácil ver la gramática original.

Los analizadores LR requieren un preprocesamiento mucho más complicado para generar las tablas para que se ejecuten de manera eficiente, ya que la codificación manual directa de uno que usa algo así como el ascenso recursivo es bastante horrible.

Al implementar los combinadores de analizadores como EDSL en lugar de una herramienta externa, permite un mayor uso de las características avanzadas de su lenguaje de programación. Puede hacer porciones de la gramática de orden superior, crear el hacker de lexer directamente en el analizador, etc. Los generadores de analizadores de LR típicos no pueden hacer estas cosas, o solo pueden ofrecerlas de forma ad hoc en contextos limitados debido a la necesidad de ser capaz de emitir las tablas al final.

Answer 3

Con Scala podría usar todas las herramientas Java existentes sin demasiada sobrecarga. JavaCC es un generador de analizadores LL (k). Puede usarlo para crear un árbol de sintaxis concreto automáticamente y hacer todo lo demás en Scala. De hecho, hice eso para un proyecto pequeño, simplemente porque la gramática JavaCC ya existía.

Answer 4

SML ha tenido ml-antlr desde hace un par de años:

http://www.classes.cs.uchicago.edu/archive/2007/winter/22610-1/docs/lpt-manual.pdf

También hay sllgen para Scheme.

En cuanto a por qué hay muchos más generadores de analizadores LR que LL, es difícil escribir analizadores LR a mano, por lo que realmente necesita un generador. Con los analizadores de LL, una implementación codificada a mano aún coincide con la gramática, por lo que hay mucha menos necesidad de un generador.

Answer 5

Me has inspirado a publicar un viejo proyecto de pasatiempo en https://github.com/nrnrnr/ebnf . Es compatible con la generación de analizador LL (1) para ML estándar. Adaptarse a Haskell no sería difícil, siempre que pueda encontrar a alguien que entienda Icon.

El comentario de Edward de que la gente tiende a preferir los combinadores para el análisis es bastante correcto, pero hay ventajas para una herramienta que encontrará los conjuntos FIRST y FOLLOW y se quejará de la ambigüedad.

La principal ventaja de EBNF es su notación: las secuencias, los tipos Maybe y las palabras reservadas son compatibles de forma nativa, sin ningún problema adicional.

Answer 6

Antes de describir una solución LL (k) en desarrollo , explicaré por qué no usé las otras opciones disponibles que conozco.

1. Las bibliotecas de combinador de analizadores, es decir, los analizadores de descenso recursivos, no:

   • garantizar una gramática libre de contexto (CFG), ya que no calculan los primeros conjuntos y los conjuntos de seguimiento.
   • hacer tokens k de k-view controlados por tablas eficientes. En cambio, hacen un rastreo ineficiente.
   • no haga el algoritmo de análisis basado en la pila más eficiente.

   La falta de libertad de contexto se manifiesta como ambigüedades en la sintaxis , por ejemplo, si un operador al comienzo de una línea de código fuente (siguiendo una línea que no envió con un punto y coma) es un prefijo unario en la expresión a su lado derecho, o un operador binario infijo en la expresión al final de la línea de código fuente anterior.

2. JavaCC tiene las siguientes desventajas:

   • combina el lexer y la generación del analizador.
   • la sintaxis gramatical BNF demasiado detallada.
   • saca Java y quiero Scala (eventualmente Copute).
   • afaics no hace un acoplamiento apretado de nombres en la gramática y en el AST.
   • un código fuente monolítico de afaics, por ejemplo, no puede (fácilmente) extraer módulos para generar el primero y los conjuntos de seguimiento (para poder agregar mi propia generación de analizador).

Intento crear un generador de analizadores LL (k) que genere salida a Scala, y luego arranque para dar salida al lenguaje que estoy desarrollando (Copute, que compilará para Scala).

Mi intento actual es usar un subconjunto de la sintaxis de la gramática SLK, por lo que la herramienta SLK se puede usar para verificar que la gramática no tenga contexto.