3

我一直在用 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

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

防止此错误的最佳方法是什么。调试器建议我改用函数或lazys，但我应该在这里做什么懒惰？

4

3 回答 3

8

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

如果由于递归值而无法编译，则只需将“句法值”转换为“句法函数”即可。也就是说，而不是

...
and parseInfix2 = body
...

采用

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

即使 'parseInfix2' 的类型无论哪种方式都是相同的函数类型... F#（与 Haskell 不同）有时会要求您明确（如上所述进行eta 转换）。

我会忽略有关插入“懒惰”的建议，解析器确实是函数，而不是值，因此 eta 转换将涵盖相同的问题（根本不会急切地评估这些，这一切都需要“等待”直到你通过在任何东西开始“运行”之前要解析的字符串）。

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

于 2009-07-05T18:14:05.137 回答
2

η-conversion 不一定是一个很好的解决方案——如果你这样做，你必须证明延迟函数最多运行一次，或者在解析期间调用它会付出很多开销。

你想要这样的东西：

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

如果您有工作流构建器，更好的方法是定义 Delay 成员来为您执行此操作：

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 {
        ...
    }
于 2010-03-03T10:15:46.130 回答
1

eta 重写和延迟延迟都不是确定的事情。F# 编译器似乎很难处理深度递归。对我有用的是将递归折叠为单个顶级函数（通过将要递归调用的函数作为参数传递）。这个顶层是 eta 风格的。

顶级，我有：

let rec myParser s = (parseExpr myParser) s

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

于 2010-11-25T10:51:49.807 回答