代码之家 › 专栏 › 技术社区 › Dario

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

lazy-evaluation recursion f# parsing

Dario · 技术社区 · 16 年前

我在f(有点类似于 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

现在,要么抱怨递归对象,只抛出一个 StackOverflowException 在运行时,由于一个无限循环,或者它甚至不编译源代码,因为“一个值将是它自己定义的一部分”。

防止这种错误的最佳方法是什么?调试器建议我使用函数或 lazy 相反,我该怎么做才懒惰呢?

3 回复 | 直到 15 年前

Brian 16 年前

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

如果由于递归值而无法编译,只需将“语法值”转换为“语法函数”。那是,而不是

...
and parseInfix2 = body
...

使用

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

即使“parseinfix2”的类型在任何方面都是相同的函数类型…F(与haskell不同)有时会要求你明确(do eta-conversion 如上所述)。

我会忽略关于插入“lazy”的建议,解析器实际上是函数,而不是值,因此eta转换将涵盖相同的问题(所有这些都不会被急切地评估,它都需要“等待”直到传递要分析的字符串,然后才开始“运行”)。

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

t0yv0 16 年前

_-转换不一定是一个很好的解决方案-如果您这样做,您必须证明延迟的函数最多只运行一次,或者在解析期间为调用它支付大量开销。

你想要这样的东西:

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 {
        ...
    }

user519985 15 年前

ETA重写和延迟都不是一件确定的事情。F编译器似乎很难处理深度递归。对我来说有效的方法是将递归折叠成一个顶级函数(通过将要递归调用的函数作为参数传递)。这个顶层是ETA风格的。

顶层,我有:

let rec myParser s = (parseExpr myParser) s

注:维基百科说:“在像ocaml这样的严格语言中,我们可以通过强制使用闭包来避免无限递归问题。”这对我很有用。