解析：在F＃延迟初始化和相互递归单子

Question

我已经写在F＃一个小单子解析器组合子库（有点类似 FParsec ），现在试图实现用于编程语言编写的小解析器。

我第一在Haskell（与秒差距），其完美地运行良好实现的代码。 用于缀表达式解析器被设计相互递归的。

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由于无限循环或者甚至不编译源，因为“的值将是它自己的definion的一部分。”

什么是防止这种错误的最好方法。调试器通知：我使用的功能或代替lazys，但我应该怎么做懒吗？

Answer 1

什么是有关递归对象的警告？显示的文本;有一个这样的警告是可忽略的（实际上，在一定意义上所期望的）对于这种情况。

如果它不会因为递归值的编译，你只需要打开“语法值”到“句法功能”。即，而不是

...
and parseInfix2 = body
...

使用

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

尽管“parseInfix2”的类型是相同的功能型两种方式... F＃（不像哈斯克尔）有时会要求你要明确（做的 ETA-换算如上）。

我忽略建议有关将“懒”，解析器确实是功能，而不是价值，所以ETA-转换将覆盖同一个问题（没有这将急切地评估所有，这一切都需要“等待”直到你把这个字符串什么开始“跑”）之前被解析。

关于StackOverflowExceptions，如果您发布堆栈它可以帮助的循环片段，但你也许可以自己看到例如如果你有一个不消耗任何输入和被陷入了一个循环语法的左递归部分。我认为这是在大多数语言对于大多数分析技术，一个简单的陷阱。

Answer 2

η转换不一定是一个很好的解决方案 - 如果你这样做，你必须证明延迟功能运行最多一次，或付出很多额外的分析过程中调用它。

。

您想是这样的：

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

有一个更好的方式，如果你有一个工作流程的建设者，是定义所述延迟部件为你做到这一点：

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

无论是ETA重写也不懒惰延迟是肯定的事。 F＃编译器似乎有一个很难对付深递归。什么工作对我来说是折叠循环进入一个顶级功能（通过传递函数递归调用作为参数）。这个顶层写入ETA风格。

顶层，我有：

let rec myParser s = (parseExpr myParser) s

请注意维基说：“在像OCaml中严格的语言，我们可以通过强制使用一个封闭的避免无限递归问题。”这是对我工作。