Parsec: Rückzieher nicht funktioniert
-
18-09-2019 - |
Frage
Ich versuche, F # Typ Syntax zu analysieren. Ich begann eine [F] Parsec Grammatik Schreiben und lief in Probleme, so dass ich vereinfachte die Grammatik unten zu diesem:
type ::= identifier | type -> type
identifier ::= [A-Za-z0-9.`]+
Nach dem Ausführen Probleme mit FParsec, wechselte ich zu Parsec, da ich habe voll Kapitel eines Buches gewidmet ist, es zu erklären . Mein Code für diese Grammatik ist
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"
Das Problem ist, dass Parsec nicht standardmäßig Rückzieher, so
> run "int"
Right "int"
-- works!
> run "int->int"
Left "F# type syntax"
unexpected "-"
expecting digit, letter, ".", "`" or end of input
-- doesn't work!
Das erste, was ich war versucht typeP neu zu ordnen:
typeP = choice [arrowP, identP]
Aber das nur überläuft stapeln, weil die Grammatik linksrekursive wird - typeP wird nie identP
zu versuchen, weil es arrowP
immer und immer wieder versucht immer wieder. Als nächstes habe ich versucht, try
an verschiedenen Orten, zum Beispiel:
typeP = choice [try identP, arrowP]
Aber nichts, was ich tun scheint die grundlegenden Verhaltensweisen (1) Stapelüberlauf oder (2) Nichtanerkennung zu ändern „->“. Im Anschluss an eine Kennung
Mein Fehler ist wohl offensichtlich für jeden, der eine Parsec Grammatik erfolgreich geschrieben hat. Kann es jemand darauf hinweisen?
Lösung
Ich denke, das Problem ist, dass, und ich mache eine Annahme für F # (weil ich weiß es nicht), Pfeile rechts assoziativ sind. Ich bin nicht sicher, wie genau die verknüpfte Grammatik sein soll, wie ich in verschiedenen Grammatiken versiert nicht gut bin. Aber wenn wir können davon ausgehen, Pfeile rechts assoziativ, dass das Problem leichter macht.
So mit dieser Annahme können wir triviale Weise tun:
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
So:
Haskell> run "int"
Right "int"
Haskell> run "int->int"
Right "(int -> int)"
Haskell> run "int->int->int->int"
Right "(int -> (int -> (int -> int)))"
Der Ausbau weiter, was Sie könnte verwirrend ist, dass in dieser Grammatik sagt Art -> Typ, das bedeutet, dass Sie einen Pfeil auf der linken Seite haben könnten. Das ist in Ordnung, aber es muss in Klammern sein. Welche hilft, vielleicht die folgend in Aktion ist hilfreich zu sehen. Es hat mir geholfen.
typeP = try arrowP <|> parens typeP <|> identP
arrowP = do
i <- parens typeP <|> identP
string "->"
t <- typeP
return $ "(" ++ i ++ " -> " ++ t ++ ")"
parens p = between (char '(') (char ')') p
Jetzt können wir die Pfeile auf der linken oder der rechten Seite eines Pfeils schreiben:
Haskell> run "int->int->int"
Right "(int -> (int -> int))"
Haskell> run "(int->int)->int"
Right "((int -> int) -> int)"
Andere Tipps
Ich denke, Sie sollten die Linksrekursion aus der Grammatik Faktor. Statt
type ::= identifier | type -> type
identifier ::= [A-Za-z0-9.`]+
Sie bekommen so etwas wie
typeStart ::= identifier
type ::= typeStart (-> type)?
identifier ::= [A-Za-z0-9.`]+
Dann wird dies einfacher zu übersetzen direkt in Parsec, denke ich. (Man würde denken, dass try
funktionieren würde, und ich erwarte, dass es irgendwie funktioniert, aber ja, meine Erfahrung war auch, dass ich mindestens hüfthoch in Parsec sein, bevor ich überhaupt verstanden „wo zu setzen try
“, um die Dinge funktionieren. )
Betrachten wir sehen auch Monadic Parser Kombinatoren in F # ( sowie die 7 vor # Blog-Einträge C) für einige Grundlagen. Ich denke, die Parsec docs (nur versuchen, sie zu lesen von oben nach unten , sie sind in Ordnung, wenn ich mich richtig) sowie einige der Beispiele in den verschiedenen Forschungsarbeiten sprechen über Themen wie die in Ihrer Frage wieder zu verwenden.
Dies wird nicht helfen, zu verstehen, wo Sie falsch gehen, aber ich würde vorschlagen, in der Suche sepBy1
mit Typen von ->
Symbolen getrennt zu analysieren. Dies wird Ihnen eine Liste der analysierten Typen, die Sie dann später wieder in Funktionstypen verwandeln.