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 在为其 [ 消耗了一些输入后将无法找到 * =18=]，所以整个解析会被标记为失败。

您通常希望尽可能多地使用 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 可以将消耗性故障转换为非消耗性故障，但应尽可能少用。

F# FParsec 解析乘法

F# FParsec parsing multiplication

f#

parsing

fparsec