解析:F#中的惰性初始化和相互递归monad [英] Parsing: Lazy initialization and mutually recursive monads in F#

问题描述

我一直在用F#写一个Monadic解析器-组合器库(有点类似于 FParsec )，现在尝试为一种编程语言实现小型解析器.

I've been writing a little monadic parser-combinator library in F# (somewhat similar to FParsec) and now tried to implement a small parser for a programming language.

我首先在Haskell(使用Parsec)中实现了运行良好的代码. 中缀表达式的解析器被设计为相互递归的.

I first implemented the code in Haskell (with Parsec) which ran perfectly well. The parsers for infix expressions are designed mutually recursive.

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  

由于函数的顺序无关紧要，并且Haskell以非严格方式进行评估，所以可以，但是F#进行了严格评估.

Since the order of functions doesn't matter and Haskell is evaluating in a non-strict way, this is OK, but F# is evaluating strictly.

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#现在要么抱怨递归对象，要么由于无限循环而在运行时抛出StackOverflowException，或者甚至因为值将是其自身定义的一部分"而无法编译源代码.

F# now either complains about recursive objects and just throws a StackOverflowException at runtime due to an infinite loop or it even doesn't compile the source because "a value would be part of its own definion".

防止这种错误的最佳方法是什么.调试器建议我改用函数或lazy，但是在这里我应该使什么懒呢?

What's the best way to prevent this errors. The debugger advices me to make use functions or lazys instead but what should I make lazy here?

推荐答案

关于递归对象的警告是什么?显示文字；在这种情况下，有一种这样的警告是可以忽略的(实际上，在某种意义上是可取的).

What is the warning about recursive objects? Show the text; there's one such warning that is ignorable (indeed, in a sense desirable) for this case.

如果由于递归值而无法编译，则只需将语法值"转换为语法函数".也就是说，而不是

If it doesn't compile because of recursive values, you simply need to turn the 'syntactic values' into 'syntactic functions'. That is, rather than

...
and parseInfix2 = body
...

使用

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

即使'parseInfix2'的类型在两种方法中都是相同的函数类型... F#(与Haskell不同)有时也会要求您明确(执行

even though the type of 'parseInfix2' is the same function type either way... F# (unlike Haskell) will sometimes require you to be explicit (do eta-conversion as above).

我会忽略有关插入惰性"的建议，解析器的确是函数，而不是值，因此eta转换将涵盖相同的问题(所有这些都不会急切地进行评估，所有这些都需要等待"直到您传递要解析的字符串，然后一切都开始运行".

I'd ignore suggestions about inserting 'lazy', parsers are indeed functions, not values, so the eta-conversion will cover the same issue (none of this will be evaluated eagerly at all, it all needs to 'wait' until you pass the string to be parsed before anything starts to 'run').

关于StackOverflowExceptions，如果您发布堆栈的循环代码片段可能会有所帮助，但是您可以自己查看例如如果语法的左递归部分不消耗任何输入并陷入循环中.我认为对于大多数语言的大多数解析技术来说，这都是一个容易犯的错误.

Regarding StackOverflowExceptions, if you post a looping snippet of the stack it may help, but you maybe can see for yourself e.g. if you have a left-recursive portion of the grammar that doesn't consume any input and gets caught in a loop. I think that's an easy pitfall for most parsing technologies in most languages.

这篇关于解析:F#中的惰性初始化和相互递归monad的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！