Parsec: Rückzieher nicht funktioniert

Question

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?

Answer 1

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)"

Answer 2

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.

Answer 3

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.