Parsec: backtracking non funziona

Question

Sto cercando di analizzare F # tipo di sintassi. Ho iniziato a scrivere una grammatica [F] Parsec e corse in problemi, così ho semplificato la grammatica riduce a questo:

type ::= identifier | type -> type
identifier ::= [A-Za-z0-9.`]+

Dopo l'esecuzione in problemi con FParsec, sono passato a Parsec, dal momento che ho un pieno capitolo di un libro dedicato a spiegarla . Il mio codice per questa grammatica è

typeP = choice [identP, arrowP]
identP = do
   id <- many1 (digit <|> letter <|> char '.' <|> char '`')
   -- more complicated code here later
   return id
arrowP = do
  domain <- typeP
  string "->"
  range <- typeP
  return $ "("++domain++" -> "++range++")"
run = parse (do t <- typeP
                eof
                return t) "F# type syntax"

Il problema è che Parsec non marcia indietro per impostazione predefinita, in modo

> run "int"
Right "int"
-- works! 
> run "int->int"
Left "F# type syntax"
unexpected "-"
expecting digit, letter, ".", "`" or end of input
-- doesn't work!

La prima cosa che ho provato è stato quello di riordinare typeP:

typeP = choice [arrowP, identP]

Ma questo solo pila overflow perché la grammatica è lasciato ricorsiva - typeP non viene mai a cercare identP perché continua a cercare arrowP più e più volte. Poi ho provato try in vari luoghi, per esempio:

typeP = choice [try identP, arrowP]

Ma nulla che faccio sembra cambiare i comportamenti di base di (1) overflow dello stack o (2) non riconoscimento di "->". A seguito di un identificatore

Il mio errore è probabilmente evidente a chiunque abbia scritto con successo una grammatica Parsec. Qualcuno può farlo notare?

Answer 1

Credo che il problema è che, e sto facendo un presupposto per la F # (perché io non lo so), le frecce sono associativi a destra. Io non sono sicuro di come precisa la grammatica collegato dovrebbe essere, come io non sono esperto in diverse grammatiche. Ma se siamo in grado di assumere le frecce hanno ragione associativa che rende il problema più semplice.

Quindi, con questo presupposto banalmente possiamo fare:

identP = many1 (digit <|> letter <|> char '.' <|> char '`')

typeP = try arrowP <|> identP

arrowP = do
  i <- identP
  string "->"
  t <- typeP
  return $ "(" ++ i ++ " -> " ++ t ++ ")"

run = flip parse "F# type syntax" $ do
        t <- typeP
        eof
        return t

Haskell> run "int"
Right "int"
Haskell> run "int->int"
Right "(int -> int)"
Haskell> run "int->int->int->int"
Right "(int -> (int -> (int -> int)))"

l'ulteriore espansione, quello che potrebbe essere fonte di confusione che si è che in grammatica che si dice tipo -> tipo, il che significa che si potrebbe avere una freccia sul lato sinistro. Va bene, ma ha bisogno di essere tra parentesi. Che aiuta, forse vedendo il seguente in azione è utile. Mi ha aiutato.

typeP = try arrowP <|> parens typeP <|> identP

arrowP = do
 i <- parens typeP <|> identP
 string "->"
 t <- typeP
 return $ "(" ++ i ++ " -> " ++ t ++ ")"

parens p  = between (char '(') (char ')') p

Ora possiamo scrivere le frecce a sinistra o il lato destro di una freccia:

Haskell> run "int->int->int"
Right "(int -> (int -> int))"
Haskell> run "(int->int)->int"
Right "((int -> int) -> int)"

Answer 2

Credo che si dovrebbe fattore la ricorsione sinistra fuori della grammatica. Invece di

type ::= identifier | type -> type 
identifier ::= [A-Za-z0-9.`]+ 

si ottiene qualcosa come

typeStart ::= identifier 
type ::= typeStart (-> type)?
identifier ::= [A-Za-z0-9.`]+ 

Allora questo sarà più facile da tradurre direttamente in parsec, credo. (Si potrebbe pensare che try avrebbe funzionato, e mi aspetto lo fa in qualche modo, ma sì, la mia esperienza è stato anche che dovevo essere almeno cintola in Parsec, prima che io abbia mai capito "dove mettere try" per far funzionare le cose. )

Si consideri vedere anche monadiche Parser combinatori in F # ( così come le 7 voci # blog precedenti C) per alcuni principi fondamentali. Credo che il parsec docs (provate solo leggendo loro top-down , essi sono decenti, se non ricordo male), così come alcuni degli esempi dei vari documenti di ricerca parla di questioni come quella nella sua interrogazione.

Answer 3

Questo non vi aiuterà a capire dove si sta andando male, ma io suggerirei di guardare in utilizzando sepBy1 per analizzare i tipi separati da simboli ->. Questo vi darà un elenco dei tipi analizzati, che è quindi possibile tornare indietro in tipi di funzioni in seguito.