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

Question

我们使用ANTLR为类似SQL的语法创建解析器,虽然在大多数情况下结果令人满意,但我们需要修复一些边缘情况.因为我们自己没有编写解析器,所以我们并不能很好地理解它,以便能够做出明智的改变.

所以,我们想编写自己的解析器.手动编写解析器的最佳方法是什么？我们应该使用什么样的解析器 - 建议使用递归下降; 是对的吗？我们将用C#编写它,所以任何用该语言编写解析器的教程都会感激不尽.

更新:我也对涉及F#的答案感兴趣 - 我一直在寻找在项目中使用它的理由.

Answer 1

我强烈建议使用F#语言作为在.NET平台上解析的首选语言.ML系列语言的根源意味着它对面向语言的编程提供了出色的支持.

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

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是一个monadic解析器组合器,它接受两个简单的解析器并返回一个组合解析器.在这种情况下,sepBy1 p sep返回一个解析器,该解析器解析一个或多个出现的p分隔符sep.因此,您可以看到可以从简单的解析器中快速组合强大的解析器.F#对重写的运算符的支持也允许简洁的中缀表示法,例如序列组合器和选择组合子可以指定为>>.和<|>.

祝你好运,

丹尼

Answer 2

可以由理智的人类手写的唯一一种解析器是递归下降.也就是说,手写自下而上的解析器仍然是可能的,但这是非常不可取的.

如果您正在使用RD解析器,则必须验证SQL语法不是左递归的(并在必要时消除递归),然后基本上为每个语法规则编写一个函数.有待进一步参考,请参阅此

Answer 3

递归下降会给你最简单的方法,但我不得不同意mouviciel那种flex和bison,绝对值得学习.当你发现你的语法有错误时,在flex/bison中修复语言的定义将比重写你的递归下降代码容易得多.

仅供参考,C#解析器是递归下降的,它往往非常健壮.

Answer 4

将我的声音添加到合唱中,支持递归下降(LL1).它们简单,快速,而且IMO,完全不难维护.

但是,请仔细查看您的语言以确保它是LL1.如果你有像C这样的语法,比如((((type))foo)[])你可能需要先删除多层括号,然后才能发现你是在查看类型,变量还是表达式, LL1将非常困难,自下而上获胜.

Answer 5

递归下降解析器确实是最好的,也许是唯一的,可以手动构建的解析器.您仍然需要了解正式的,无上下文的语言,并将您的语言置于正常形式.我个人建议您删除左递归并将您的语言放在Greibach Normal Form中.当你这样做时,解析器只是写自己.

例如,这个生产:

A => aC 
A => bD
A => eF

变成简单的东西:

int A() {
   chr = read();
   switch char
     case 'a': C();
     case 'b': D();
     case 'e': F();
     default: throw_syntax_error('A', chr);
}

而且这里没有更难的案例(更难的是确保你的语法形式正确,但这可以让你控制你所提到的).

Anton's Link也很出色.