Análisis sintáctico: inicialización perezosa y mutuamente recursivos mónadas en F #

Question

He escrito una pequeña biblioteca monádico analizador-combinador en Fa # (algo similar a FParsec ) y ahora tratado de implementar un pequeño analizador de lenguaje de programación.

La primera vez implementado el código en Haskell (con Parsec) que funcionó muy bien. Los programas de análisis de expresiones infijas están diseñados mutuamente recursivo.

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  

Dado que el orden de las funciones no importa y Haskell está evaluando de manera no estricto, esto está bien, pero F # está evaluando en sentido estricto.

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 # ahora se queja, ya sea sobre los objetos recursivos y simplemente lanza una StackOverflowException en tiempo de ejecución debido a un bucle infinito o que incluso no se compila la fuente porque "un valor sería parte de su propia definion".

¿Cuál es la mejor manera de prevenir esta errores. El depurador asesora que haga las funciones de uso o lazys lugar, pero lo que debería hacer perezoso aquí?

Answer 1

¿Cuál es la advertencia sobre objetos recursivos? Mostrar el texto; hay una tal advertencia que es ignorable (de hecho, en un sentido deseable) para este caso.

Si no compila debido a los valores recursivas, sólo hay que convertir los 'valores sintácticos' 'en funciones sintácticas. Es decir, en lugar de

...
and parseInfix2 = body
...

uso

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

a pesar de que el tipo de 'parseInfix2' es el mismo tipo de función de cualquier manera ... F # (a diferencia de Haskell) a veces será necesario que para ser explícita (ver eta-conversión como arriba).

Me ignoraría sugerencias sobre cómo insertar 'perezoso', analizadores son de hecho las funciones, no los valores, por lo que la conversión eta cubrirá el mismo problema (nada de esto será evaluado con entusiasmo en absoluto, todas las necesidades de 'espera' hasta que pase la cadena a ser analizado antes de que algo empieza a 'correr').

En cuanto a StackOverflowExceptions, si usted publica un fragmento de bucle de la pila puede ayudar, pero tal vez puede ver por sí mismo, por ejemplo, si tiene una porción izquierda recursiva de la gramática que no consume ninguna entrada y se ve atrapado en un bucle. Creo que es una trampa fácil para la mayoría de las tecnologías de análisis en la mayoría de idiomas.

Answer 2

η-conversión no es necesariamente una gran solución - si lo hace, tendrá que demostrar que la función retardada se ejecuta como máximo una vez, o pagar una gran cantidad de gastos generales para llamarlo durante el análisis

.

¿Quieres algo como esto:

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

Una mejor manera, si usted tiene un generador de flujo de trabajo, es definir el miembro de retardo para hacer esto para usted:

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 reescritura ETA ni el retraso perezoso es una cosa segura. El F # compilador parece tener dificultades para hacer frente a cambios repetidos con profundas. Lo que funcionó para mí fue el colapso de la recursividad en una única función de nivel superior (pasando la función a ser llamada recursiva como un argumento). Este nivel superior está escrito estilo eta.

nivel superior, que tengo:

let rec myParser s = (parseExpr myParser) s

Nota Wikipedia dice: "En un lenguaje estricto como OCaml, podemos evitar el problema de recursividad infinita al forzar el uso de un cierre.". Eso es lo que funcionó para mí.