Perché sembra che l'operatore Parsec Choice dipenda dall'ordine dei parser?

Question

Sto cercando di analizzare un linguaggio molto semplice che consiste solo di numeri decimali o binari. Ad esempio, qui ci sono alcuni input validi:

#b1 
#d1 
#b0101 
#d1234 

Sto avendo un problema utilizzando del Parsec dell'operatore scelta: <|>. Secondo il tutorial: Write yourself a Scheme in 48 hours:

[L'operatore di scelta] prova il primo parser, quindi se fallisce, prova il secondo. Se uno dei due riesce, restituisce il valore restituito da quel parser.

Ma nella mia esperienza, vedo che l'ordine dei parser ha fornito argomenti. Qui è il mio programma:

import System.Environment 
import Text.ParserCombinators.Parsec 

main :: IO() 
main = do 
    (x:_) <- getArgs 
    putStrLn ("Hello, " ++ readExp x) 

bin :: Parser String 
bin = do string "#b" 
     x <- many(oneOf "01") 
     return x 

dec :: Parser String 
dec = do string "#d" 
     x <- many(oneOf "") 
     return x 

-- Why does order matter here? 
parseExp = (bin <|> dec) 

readExp :: String -> String 
readExp input = case parse parseExp "test" input of 
         Left error -> "Error: " ++ show error 
         Right val -> "Found val" ++ show val 

Ecco come sto facendo funzionare il programma:

Installazione dipendenze

$ cabal sandbox init 
$ cabal install parsec 

Compilazione

$ cabal exec ghc Main 

Run

$ ./Main "#d1" 
Hello, Error: "test" (line 1, column 1): 
unexpected "d" 
expecting "#b" 

$ ./Main "#b1" 
Hello, Found val"1" 

.210

Se cambio l'ordine dei parser come segue: vengono rilevati

parseExp = (dec <|> bin) 

allora solo numeri binari e il programma non identifica il numeri decimali.

Con i test che ho eseguito, vedo che questo problema si verifica solo quando uno dei parser ha iniziato l'analisi di un input, ad es. se viene trovato un carattere hash #, viene attivato il parser bin che termina con esito negativo in quanto il carattere successivo previsto è b e non d. Sembra che dovrebbe esserci una specie di backtracking che dovrebbe accadere, cosa di cui non sono a conoscenza.

Apprezzo l'aiuto!

Answer 1

Parsec ha due tipi di "guasto": ci sono errori che consumano input e guasti che non lo fanno. Per evitare il backtracking (e quindi trattenere gli input più a lungo del necessario/essere generalmente ostili al garbage collector), (<|>) si impegna al primo parser non appena consuma input; in modo che se il suo primo argomento consuma input e fallisce, il suo secondo parser non avrà mai la possibilità di avere successo. È possibile richiedere esplicitamente backtracking comportamento con try, in tal modo:

Text.Parsec> parse (string "ab" <|> string "ac") "" "ac" 
Left (line 1, column 1): 
unexpected "c" 
expecting "ab" 
Text.Parsec> parse (try (string "ab") <|> string "ac") "" "ac" 
Right "ac" 

Purtroppo, try ha alcune riduzioni di prestazioni abbastanza fastidioso, il che significa che se si vuole un parser performante, si dovrà refactoring la grammatica un po '. Vorrei farlo con il parser sopra in questo modo:

Text.Parsec> parse (char 'a' >> (("ab" <$ char 'b') <|> ("ac" <$ char 'c'))) "" "ac" 
Right "ac" 

Nel tuo caso, è necessario scomporre il marchio "#" in modo simile.

Answer 2

LEGGERE CON ATTENZIONE:

[L'operatore scelta] cerca il primo parser, quindi se non riesce, tenta il secondo. Se uno riesce, allora restituisce il valore restituito da che parser ..

Questo implica che il primo parser viene provato per primo, e in caso di successo, il secondo parser NON è cercato a tutti! Ciò significa che il primo parser ha una priorità più alta, quindi <|> non è commutativo, in generale.

Un semplice controesempio può essere creato con alcuni parser sempre riusciti, ad es.

dummy :: Parser Bool 
dummy = return True <|> return False 

Quanto sopra è equivalente a return True: dal primo riesce, il secondo è irrilevante.

---

Oltre a ciò, parsec è progettato per eseguire il commit tempestivo del primo ramo quando questo ha consumato con successo alcuni input. Questo design sacrifica il perfetto non-determinismo per l'efficienza. Altrimenti, il parsec dovrebbe spesso conservare in memoria tutto il file che viene analizzato, perché se si verifica un errore di analisi, è necessario provare qualche nuova alternativa.

Per esempio,

p = (char 'a' >> char 'b' >> ...) <|> 
    (char 'a' >> char 'c' >> ...) 

non funziona come ci si potrebbe aspettare. Non appena 'a' viene consumato con successo dal primo ramo, parsec si impegna su di esso. Ciò significa che se segue 'c', il primo ramo fallirà ma è troppo tardi per provare il secondo. L'intero parser semplicemente fallisce.

Per risolvere questo problema è possibile calcolare il prefisso comune, ad es.

p = char 'a' >> ((char 'b' >> ...) <|> (char 'c' >> ...)) 

o resort a try,

p = (try (char 'a' >> char 'b') >> ...) <|> 
    (char 'a' >> char 'c' >> ...) 

try dice fondamentalmente parsec non commettere al ramo fino a quando tutto il parser sotto try riesce. Se abusato, può fare in modo che parsec mantenga in memoria una grande porzione del file, ma l'utente ha almeno un certo controllo su questo. Teoricamente, il perfetto nondeterminismo può essere recuperato aggiungendo sempre try all'intero ramo sinistro di <|>. Ciò tuttavia non è raccomandato, poiché stimola il programmatore a scrivere un parser inefficiente, sia a causa del problema di memoria sia del fatto che si può facilmente scrivere una grammatica che richiede un numero esponenziale di backtracks per analizzare correttamente.