c# - 手动编写解析器的最佳方法是什么？

Question

<分区>

Answer 1

我强烈推荐 F# 语言作为在 .NET 平台上进行解析的首选语言。它起源于 ML 语言家族，这意味着它对面向语言的编程提供了出色的支持。

有区别的联合和模式匹配允许对您的 AST 进行非常简洁和强大的规范。高阶函数允许定义解析操作及其组合。对 monadic 类型的一流支持允许隐式处理状态管理，从而大大简化了解析器的组合。强大的类型推断极大地帮助了这些(复杂)类型的定义。所有这些都可以交互方式指定和执行，让您可以快速制作原型(prototype)。

Stephan Tolksdorf 已通过他的解析器组合器库将其付诸实践 FParsec

从他的示例中我们可以看出 AST 是如何自然地指定的:

type expr =
    | Val of string
    | Int of int
    | Float of float
    | Decr of expr

type stmt =
    | Assign of string * expr
    | While of expr * stmt
    | Seq of stmt list
    | IfThen of expr * stmt
    | IfThenElse of expr * stmt * stmt
    | Print of expr

type prog = Prog of stmt list

解析器的实现(部分省略)同样简洁:

let stmt, stmtRef = createParserForwardedToRef()

let stmtList = sepBy1 stmt (ch ';')

let assign =
    pipe2 id (str ":=" >>. expr) (fun id e -> Assign(id, e))

let print = str "print" >>. expr |>> Print

let pwhile =
    pipe2 (str "while" >>. expr) (str "do" >>. stmt) (fun e s -> While(e, s))

let seq =
    str "begin" >>. stmtList .>> str "end" |>> Seq

let ifthen =
    pipe3 (str "if" >>. expr) (str "then" >>. stmt) (opt (str "else" >>. stmt))
          (fun e s1 optS2 ->
               match optS2 with
               | None    -> IfThen(e, s1)
               | Some s2 -> IfThenElse(e, s1, s2))

do stmtRef:= choice [ifthen; pwhile; seq; print; assign]


let prog =
    ws >>. stmtList .>> eof |>> Prog

在第二行，例如stmt和 ch是解析器和 sepBy1是一个单子(monad)解析器组合器，它接受两个简单的解析器并返回一个组合解析器。在这种情况下 sepBy1 p sep返回一个解析器，该解析器解析一次或多次出现的 p用sep分隔.因此，您可以看到从简单的解析器中组合出强大的解析器的速度有多快。 F# 对重写运算符的支持还允许使用简洁的中缀表示法，例如排序组合器和选择组合器可以指定为 >>.和 <|> .

祝你好运

丹尼