Parsec: retours en arrière ne fonctionne pas
-
18-09-2019 - |
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?
La solution
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)"
Autres conseils
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.
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.