È possibile utilizzare la libreria Parsec di Haskell per implementare un parser di discesa ricorsivo con backup?

Question

Ho preso in considerazione l'utilizzo della libreria di analisi Parsec di Haskell per analizzare un sottoinsieme di Java come parser di discesa ricorsivo come alternativa alle soluzioni di parser-generator più tradizionali come Happy. Parsec sembra molto facile da usare e la velocità di analisi non è sicuramente un fattore per me. Mi chiedo, tuttavia, se è possibile implementare il "backup" con Parsec, una tecnica che trova la produzione corretta da utilizzare provandone uno a turno. Per un semplice esempio, prendere in considerazione fin dall'inizio della grammatica JLS Java:

Literal: 
    IntegerLiteral 
    FloatingPointLiteral 

Vorrei un modo per non dover capire come devo ordinare queste due regole per ottenere il parse di avere successo. Così com'è, un'implementazione ingenua come questo: ""

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

non Lavoreranno ... ingressi come "15.2" farà sì che il parser intero per avere successo prima, e poi il tutto sarà soffocare sul simbolo. In questo caso, ovviamente, è ovvio che puoi risolvere il problema riordinando le due produzioni. Nel caso generale, però, trovare cose come questa sarà un incubo ed è molto probabile che mi mancherà alcuni casi. Idealmente, mi piacerebbe un modo per far sì che Parsec riesca a capire cose del genere per me. È possibile o sto semplicemente cercando di fare troppo con la biblioteca? La documentazione di Parsec afferma che è in grado di "analizzare grammatiche sensibili al contesto e all'infinito", quindi sembra che dovrei essere in grado di fare qualcosa qui.

Answer 1

usare sia Parsec di notFollowedBy per garantire che integer consumato tutto fino a qualche separatore per memoria (questo approccio scalare per scenario arbitraria maggior parte del tempo), o dare un'occhiata a combinatori parser che esplorano tutte le possibili alternative di analisi. Il primo a venire in mente è la libreria UU_Parsing.

Answer 2

Un modo per eseguire questa operazione è utilizzare il combinatore try, che consente a un parser di utilizzare input e fallire senza esito negativo dell'intero processo.

Un altro è utilizzare Text.ParserCombinators.ReadP, che implementa un operatore di scelta simmetrica, in cui è dimostrato che a +++ b = b +++ a, quindi non importa quale ordine. Sono piuttosto parziale a ReadP, poiché è minimo ma fornisce ciò che è necessario per creare un parser veramente potente.