parsing - F# FParsec 解析乘法

Question

我正在努力解决我编程中最可怕的部分，那就是解析和 AST。我正在处理一个使用 F# 和 FParsec 的简单示例。我想解析一系列简单的乘法。不过，我只是回到了第一个学期。这是我目前所拥有的:

open FParsec

let test p str =
    match run p str with
    | Success(result, _, _) -> printfn  "Success: %A" result
    | Failure(errorMsg, _, _) -> printfn "Failure: %s" errorMsg

type Expr =
| Float of float
| Multiply of Expr * Expr

let parseExpr, impl = createParserForwardedToRef ()

let pNumber = pfloat .>> spaces |>> (Float)
let pMultiply = parseExpr .>> pstring "*" >>. parseExpr
impl := pNumber <|> pMultiply

test parseExpr "2.0 * 3.0 * 4.0 * 5.0"

当我运行它时，我得到以下信息:

> test parseExpr "2.0 * 3.0 * 4.0 * 5.0";;
Success: Float 2.0
val it : unit = ()

我希望得到一组嵌套的乘法。我觉得我错过了一些非常明显的东西。

Answer 1

像 FParsec 这样的解析器组合器不等同于 BNF 文法。最大的区别在于，当您有替代方案时(FParsec 中的 <|>)，案例会按顺序 进行尝试。如果左解析器成功，则返回它并且不尝试右解析器。如果左解析器在处理一些输入后失败，则返回失败并且不尝试右解析器。只有当左解析器在没有消耗任何输入的情况下失败时，才会尝试右解析器。 [1]

在你的pNumber <|> pMultiply , pNumber成功并立即返回而不尝试做 pMultiply .你可能会想通过写 pMultiply <|> pNumber 来解决这个问题相反，但这也不好:解析最后一个数字时，pMultiply将无法找到 *在为其 parseExpr 消耗了一些输入之后, 因此整个解析将被标记为失败。

您通常希望尽可能多地使用 FParsec 的组合器函数，在这种情况下最好的解决方案可能是使用 chainl1 .

let pNumber = pfloat .>> spaces |>> Float
let pTimes = pstring "*" .>> spaces >>% (fun x y -> Multiply (x, y))
let pMultiply = chainl1 pNumber pTimes

如果您的目标是学习如何使用 BNF 语法，您可能想看看 FsLex and FsYacc而不是 FParsec。

[1] 有一个函数 attempt 将消耗性故障变成非消耗性故障，但应尽可能谨慎使用。