Parsing: initialisation Lazy et mutuellement monades récursives en F #

Question

J'ai écrit une petite bibliothèque analyseur-Combinator monadique en F # (un peu similaire à FParsec ) et maintenant essayé de mettre en œuvre un petit analyseur pour un langage de programmation.

J'ai d'abord mis en œuvre le code dans Haskell (avec parsec) qui a fonctionné parfaitement. Les parseurs pour les expressions infixes sont conçus mutuellement récursive.

parseInfixOp :: Parser String -> Parser Expression -> Parser Expression
parseInfixOp operatorParser subParser = ignoreSpaces $ do
                                          x <- ignoreSpaces $ subParser
                                          do
                                            op <- ignoreSpaces $ operatorParser
                                            y  <- parseInfixOp operatorParser subParser
                                            return $ BinaryOp op x y
                                           <|> return x

parseInfix :: [String] -> Parser Expression -> Parser Expression
parseInfix list = parseInfixOp (foldl1 (<|>) $ map string list)

parseExpr :: Parser Expression
parseExpr = parseInfix0

parseInfix0 = parseInfix ["==", "<>", "And", "Or", "Xor", "<", ">", "<=", ">="] parseInfix1
parseInfix1 = parseInfix ["+", "-", "Mod"] parseInfix2
parseInfix2 = parseInfix ["*", "/", "\\"] parseInfix3
parseInfix3 = parseInfix ["^"] parseInfix4
parseInfix4 = parseFactor

parseFactor :: Parser Expression
parseFactor = parseFactor' <|> (betweenChars '(' ')' parseExpr)

parseFactor' :: Parser Expression
parseFactor' = parseString
           <|> parseBool
           <|> parseNumber
           <|> parseVariable
           <|> (try parseFunCall) <|> parseIdentifier  

Depuis l'ordre des fonctions n'a pas d'importance et Haskell évalue de manière non stricte, c'est OK, mais F # évalue strictement.

let rec parseExpr = parseInfix0
and parseFactor = (parseFactor') <|> (betweenChars '(' ')' parseExpr)
and parseInfix2 = parseInfix ["^"] parseFactor BinaryOp
and parseInfix1 = parseInfix ["*"; "/"] parseInfix2 BinaryOp
and parseInfix0 = parseInfix ["+"; "-"] parseInfix1 BinaryOp
and parseFunCall = parser {
        let! first = letter
        let! rest = many (letter <|> digit)
        let  funcName = toStr $ first::rest

        do! ignoreSpace
        let! args = betweenChars '(' ')' $ sepBy (parseExpr) ","

        return FunCall(funcName, args)
    }
and parseFactor' =
    parseNumber
<|> parseString
<|> parseBool
<|> parseFunCall
<|> parseIdentifier

F # maintenant se plaint soit sur les objets récursifs et jette juste un StackOverflowException lors de l'exécution en raison d'une boucle infinie ou il ne compile pas même la source, car « une valeur ferait partie de son propre définion ».

Quelle est la meilleure façon d'éviter ces erreurs. Le débogueur me conseille de faire à la place des fonctions d'utilisation ou lazys mais que dois-je faire paresseux ici?

Answer 1

Quel est l'avertissement sur les objets récursifs? Afficher le texte; il y a un tel avertissement est ignorable (en effet, dans un sens souhaitable) pour ce cas.

Si elle ne compile pas à cause de valeurs récursives, il vous suffit de tourner les « valeurs syntaxiques » dans « fonctions syntaxiques ». Autrement dit, plutôt que

...
and parseInfix2 = body
...

utilisation

...
and parseInfix2 x = (body) x
...

même si le type de « parseInfix2 » est le même type de fonction de toute façon ... F # (contrairement à Haskell) va parfois vous avez besoin d'être explicite (faire eta-conversion comme ci-dessus).

J'ignorer des suggestions sur l'insertion de « paresseux », parseurs sont en effet des fonctions et non des valeurs, de sorte que le eta conversion couvrira la même question (rien de tout cela sera évalué avec enthousiasme tout, tout doit « attendre » jusqu'à ce que vous passez la chaîne à analyser avant tout commence à « run »).

En ce qui concerne StackOverflowExceptions, si vous postez un extrait en boucle de la pile, il peut aider, mais vous pouvez peut-être voir par vous-même par exemple si vous avez une partie récursive gauche de la grammaire qui ne consomme pas d'entrée et se coince dans une boucle. Je pense que c'est un piège facile pour la plupart des technologies d'analyse syntaxique dans la plupart des langues.

Answer 2

η-conversion est pas nécessairement une bonne solution - si vous faites cela, vous devrez prouver que la fonction retardée est exécutée au plus une fois, ou de payer beaucoup de frais généraux pour l'appeler lors de l'analyse syntaxique

.

Vous voulez quelque chose comme ceci:

let rec p1 = lazy (...)
and p2 = ... p1.Value ..

Une meilleure façon, si vous avez un constructeur de flux de travail, est de définir le membre retard à faire pour vous:

type Builder() =
    member this.Delay(f: unit -> Parser<_>) : Parser<_> = 
        let promise = Lazy.Create f
        Return () |> Bind (fun () -> promise.Value)

let parse = new Builder()


let rec p1 =
    parse {
        ...
    }

and p2 =
    parse {
        ...
    }

Answer 3

Ni la réécriture eta ni le dilatoire paresseux est une chose sûre. Le compilateur F # semble avoir du mal à traiter avec des récurrences profondes. Ce qui a fonctionné pour moi était de réduire la récursivité en fonction de haut niveau unique (en passant la fonction à appeler récursive comme argument). Ce haut niveau est écrit style eta.

niveau supérieur, je:

let rec myParser s = (parseExpr myParser) s

wikipedia Note dit: « Dans une langue stricte comme OCaml, nous pouvons éviter le problème de récursion infinie en forçant l'utilisation d'une fermeture. ». C'est ce qui a fonctionné pour moi.