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语法。最大的区别是，当您有一个替代方案(<|> in FParsec)时，案件将按顺序进行审判。如果左解析器成功，则返回该解析器，而不尝试右解析器。如果左解析器在使用某些输入后失败，则返回故障，也不会尝试右解析器。只有当左解析器失败而不消耗任何输入时，才会尝试右解析器。1

在您的pNumber <|> pMultiply中，pNumber成功并立即返回，而不尝试执行pMultiply。您可能会考虑通过编写pMultiply <|> pNumber来解决这个问题，但这也不太好:在解析最后一个数字时，pMultiply在为parseExpr使用了一些输入之后将无法找到一个*，因此整个解析将被标记为失败。

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

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

如果您的目标是学习如何使用BNF语法，那么您可能希望查看FsLex和FsYacc而不是FParsec。

1有一个函数attempt可以将消费故障转化为非消费故障，但应该尽可能少地使用它。