什么是手工编写一个解析器的最佳方法？ [英] What's the best way to write a parser by hand?

问题描述

我们已经使用ANTLR来创建一个类似于SQL的语法分析器，虽然结果在大多数情况下是令人满意的，还有，我们需要解决一些边缘情况;因为我们没有写解析器自己，我们并不真正了解的不够好，能够作出明智的变化。

We've used ANTLR to create a parser for a SQL-like grammar, and while the results are satisfactory in most cases, there are a few edge cases that we need to fix; and since we didn't write the parser ourselves we don't really understand it well enough to be able to make sensible changes.

所以，我们想写我们自己的解析器。什么是去手工编写一个解析器的最佳方法？我们应该用什么样的解析器 - 递归下降已建议;是对的吗？我们会在C＃在写，所以以该语言书写的解析器任何教程将受到欢迎。

So, we'd like to write our own parser. What's the best way to go about writing a parser by hand? What sort of parser should we use - recursive descent has been recommended; is that right? We'll be writing it in C#, so any tutorials for writing parsers in that language would be gratefully received.

更​​新：我也很想在涉及答案F＃ - 我一直在寻找一个理由来使用，在一个项目

UPDATE: I'd also be interested in answers that involve F# - I've been looking for a reason to use that in a project.

推荐答案

我会极力推荐的F＃语言您所选择的语言解析.NET平台上。它在ML家族的语言根源意味着它面向语言编程的很好的支持。

I would highly recommend the F# language as your language of choice for parsing on the .NET Platform. It's roots in the ML family of languages means it has excellent support for language-oriented programming.

识别联合和模式匹配允许的非常简洁和强大的规格您AST。高阶函数允许解析业务和它们的组成的定义。对于一元类型的一流支持，允许被处理状态管理隐大大简化解析器的组成。强大的类型推断大大这些助手（复杂）类型的定义。 。而这一切都可以被指定并执行交互，让您可以快速原型

Discriminated unions and pattern-matching allow for a very succinct and powerful specification of your AST. Higher-order functions allow for definition of parse operations and their composition. First-class support for monadic types allows for state management to be handled implicitly greatly simplifying the composition of parsers. Powerful type-inference greatly aides the definition of these (complex) types. And all of this can be specified and executed interactively allowing you to rapidly prototype.

斯蒂芬Tolksdorf已经把这种实践与他的解析器组合库的FParsec

Stephan Tolksdorf has put this into practice with his parser combinator library FParsec

从他的例子，我们看到一个AST是如何自然地指定：

From his examples we see how naturally an AST is specified:

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

实施解析器（部分消隐）也同样简洁：

the implementation of the parser (partially elided) is just as succinct:

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

在第二行中，作为一个例子，语句和 CH 是解析器和 sepBy1 是一元解析器组合，它有两个简单的解析器，并返回一个组合分析器。在这种情况下 sepBy1 p月返回解析 P 的一个或多个出现由月。因此，你可以看到如何迅速强大的解析器可以从简单的解析器相结合。 F＃的为覆盖运营商的支持也允许简洁的中间符号如排序组合子而选择组合子可以被​​指定为>> 和< |>

On the second line, as an example, stmt and ch are parsers and sepBy1 is a monadic parser combinator that takes two simple parsers and returns a combination parser. In this case sepBy1 p sep returns a parser that parses one or more occurrences of p separated by sep. You can thus see how quickly a powerful parser can be combined from simple parsers. F#'s support for overridden operators also allow for concise infix notation e.g. the sequencing combinator and the choice combinator can be specified as >>. and <|>.

祝你好运，

丹尼

这篇关于什么是手工编写一个解析器的最佳方法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！