Parsec: retours en arrière ne fonctionne pas

Question

Je suis en train d'analyser la syntaxe F # type. Je commencé à écrire une grammaire parsec [F] et a couru dans des problèmes, donc je simplifié la grammaire à ceci:

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

Après avoir des problèmes avec FParsec, je suis passé à parsec, depuis que je suis un complète chapitre d'un livre consacré à l'expliquer . Mon code pour cette grammaire est

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"

Le problème est que parsec ne pas faire marche arrière par défaut,

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

La première chose que j'ai essayé était de modifier l'ordre typep:

typeP = choice [arrowP, identP]

Mais ce juste pile déborde parce que la grammaire est laissée récursif - typep ne fait jamais d'essayer identP parce qu'il continue d'essayer arrowP plus et plus. Ensuite, j'ai essayé try dans divers endroits, par exemple:

typeP = choice [try identP, arrowP]

Mais rien que je ne semble changer les comportements de base de (1) débordement de pile ou (2) non-reconnaissance de « -> ». Suivant un identifiant

Mon erreur est probablement évidente à tout le monde qui a écrit avec succès une grammaire parsecs. Quelqu'un peut-il le signaler?

Answer 1

Je pense que le problème est que, et je fais une hypothèse pour F # (parce que je ne sais pas), les flèches sont associatives droite. Je ne sais pas comment la grammaire précise liée est censé être, comme je suis peu familiarisés avec différentes grammaires. Mais si on peut supposer des flèches sont associatives droite qui rend le problème plus facile.

Donc, avec cette hypothèse, nous pouvons faire trivialement:

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'expansion de plus, ce qui pourrait être source de confusion vous est que dans cette grammaire de type il est dit -> type, qui signifie que vous pourriez avoir une flèche sur le côté gauche. C'est bien, mais il doit être entre parenthèses. Ce qui aide, voir peut-être ce qui suit dans l'action est utile. Cela m'a aidé.

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

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

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

Maintenant, nous pouvons écrire des flèches sur la gauche ou le côté droit d'une flèche:

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

Answer 2

Je pense que vous devez tenir compte de la récursivité gauche de la grammaire. Au lieu de

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

vous obtenez quelque chose comme

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

Ensuite, ce sera plus facile de traduire directement dans parsec, je pense. (On pourrait penser que try travaillerait, et j'espère qu'il ne en quelque sorte, mais oui, mon expérience aussi était que je devais être au moins la taille dans parsec avant que je compris « où mettre try » pour faire fonctionner les choses. )

Pensez à voir aussi monadiques Parser Combinators en F # ( ainsi que les 7 entrées avant C # blog) pour quelques notions de base. Je pense que le parsec docs (juste essayer de les lire de haut en bas , ils sont décents, si je me souviens bien), ainsi que quelques-uns des exemples dans les différents documents de recherche parlent de problèmes comme celui de votre question.

Answer 3

Cela ne vous aidera à comprendre où vous allez mal, mais je vous suggère de regarder en utilisant sepBy1 pour analyser les types séparés par des symboles ->. Cela vous donnera une liste des types analysés, que vous pouvez ensuite faire demi-tour dans les types de fonctions après.