解析:F#中的延迟初始化和相互递归的monad

Question

我一直在F#中编写一个小的monadic解析器 - 组合器库(有点类似于FParsec),现在尝试为编程语言实现一个小的解析器.

我首先在Haskell(使用Parsec)中实现了代码,该代码运行得非常好.中缀表达式的解析器是相互递归设计的.

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#正在严格评估.

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由于无限循环而在运行时抛出一个,或者甚至不编译源,因为"一个值将成为其自身定义的一部分".

什么是防止这种错误的最佳方法.调试器建议我使用函数或lazys代替但是我应该在这里做什么？

Answer 1

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

如果由于递归值而无法编译,则只需将"语法值"转换为"语法函数"即可.那就是,而不是

...
and parseInfix2 = body
...

使用

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

即使'parseInfix2'的类型是相同的函数类型,任何一种方式...... F#(与Haskell不同)有时需要你是显式的(如上所述进行eta转换).

我忽略了关于插入'lazy'的建议,解析器确实是函数,而不是值,因此eta转换将涵盖相同的问题(根本不会对这些问题进行评估,所有这些都需要'等待'直到你通过在任何事情开始"运行"之前要解析的字符串.

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