¿Se puede usar la biblioteca Parsec de Can Haskell para implementar un analizador de descenso recursivo con copia de seguridad?

Question

He estado considerando el uso de la biblioteca de análisis Parsec de Haskell para analizar un subconjunto de Java como un analizador de descenso recursivo como una alternativa a soluciones de generador de análisis sintáctico más tradicionales como Happy. Parsec parece muy fácil de usar, y la velocidad de análisis definitivamente no es un factor para mí. Me pregunto, sin embargo, si es posible implementar "copia de seguridad" con Parsec, una técnica que encuentra la producción correcta para usar probando cada una por turno. Para un ejemplo simple, considere el inicio de la gramática JLS Java:

Literal: 
    IntegerLiteral 
    FloatingPointLiteral 

Me gustaría tener una manera de no tener que averiguar cómo debería pedir estas dos reglas para obtener el análisis sintáctico para tener éxito. En su forma actual, una aplicación ingenua de esta manera: ""

literal = do { 
    x <- try (do { v <- integer; return (IntLiteral v)}) <|> 
     (do { v <- float; return (FPLiteral v)}); 
    return(Literal x) 
} 

no va a funcionar ... insumos como "15.2" hará que el analizador entero para tener éxito en primer lugar, y luego todo el asunto se ahogue en el símbolo. En este caso, por supuesto, es obvio que puede resolver el problema reordenando las dos producciones. En el caso general, sin embargo, encontrar cosas como esta va a ser una pesadilla, y es muy probable que extrañe algunos casos. Idealmente, me gustaría una forma de que Parsec descubra cosas como esta para mí. ¿Es esto posible, o simplemente estoy tratando de hacer demasiado con la biblioteca? La documentación de Parsec afirma que puede "analizar gramáticas de look-ahead infinitas sensibles al contexto", por lo que parece que algo así como yo podría hacer algo aquí.

Answer 1

De cualquier uso de Parsec notFollowedBy para asegurar que integer consumió todo lo que hasta cierto separador de token (este enfoque se escalará al escenario arbitraria mayor parte del tiempo), o echar un vistazo a los combinadores de analizadores sintácticos que exploran todas las posibles alternativas de análisis. Lo primero que viene a la mente es la biblioteca UU_Parsing.

Answer 2

Una forma de hacerlo es utilizar el combinador try, que permite que un analizador consuma datos de entrada y falle sin fallar el análisis completo.

Otra es utilizar Text.ParserCombinators.ReadP, que implementa un operador de opción simétrica, en el que se prueba que a +++ b = b +++ a, por lo que realmente no importa qué orden. Soy bastante parcial con ReadP, ya que es mínima pero proporciona lo que necesita para crear un analizador realmente potente.