Yacc 已死

导读

这篇论文指出传统解析器生成器 Yacc 存在局限，并提出一种新的解析技术（基于导数）来更灵活地处理语法。作者在 HN 评论中分享了论文未能正式发表的背景，并呼吁社区参与实现和改进。

HN 关注点：HN 读者被“Yacc is dead”这一挑衅性标题吸引，同时作者亲自参与讨论并提供了论文评审和实现细节，引发了关于解析技术现状和未来发展的讨论。

关键词　Yaccparsingderivative parsingScala

HN 评论精选

这几条评论里：补充 3　亲历 1

亲历作者说明论文未正式发表的缘由，并呼吁社区参与实现和优化，以推动技术获得科学界认可。

（本文作者）很高兴看到这篇文章受到关注。我非常喜欢这些解析技术，但我的主要研究领域是静态分析，所以一直没时间修改并重新提交论文。照目前情况看，我可能永远没时间了。我把论文发在 arXiv 上是为了让 David 能在博士申请中引用。既然有人问起，这里是评审意见：http://matt.might.net/papers/reviews/esop2010-derivatives.txt。我有一个更新、更干净且更快的实现，一直计划写篇博客文章介绍（可惜还没机会）。David 还用 Haskell 做了一个实现，在很多受限文法类（如 LL(k)）上速度极快且高效。我会鼓励他也发布出来。如果你有兴趣在科学出版物上署名，并帮助这项技术获得科学界关注，你可以用你喜欢的语言实现这两种技术中的任意一种，并反复测试以帮助发现低效之处。（例如，本文链接的原始 Scala 版本由于缓存导数的方式存在内存泄漏。我们通过手动展开顶层重复来规避。）如果你有兴趣，请给我发邮件。HN 能做科学吗？我很想看看。

mattmight查看英文原文

(Article author here.) I'm delighted to see this get some attention here. I absolutely love these techniques for parsing, but as my primary research areas is static analysis, I haven't had time to revise this paper and resubmit. As it stands, I may never get the time to do so. :( I posted it on arxiv so that David could reference it for his Ph.D. school apps. Since some of you have asked, here are the reviews: http://matt.might.net/papers/reviews/esop2010-derivatives.txt I do have an updated implementation that's much cleaner and faster, and I've been planning to do that in a blog post. (Alas, no opportunity yet.) David's also done another implementation in Haskell that's screaming fast and efficient on many restricted classes of grammars (like LL(k)). I'll encourage him to post that as well. If you're interested in getting your name on a scientific publication and helping this get the attention of the scientific community, you can help us by creating an implementation of either technique in your favorite language and beating on it to help find the inefficiencies. (For instance, the original Scala version linked from this paper has memory leaks from the way it caches derivatives. We got around them by rolling top-level repetition by hand.) Please email me if that's something you're interested in doing. Can HN do science? I'd love to find out.

补充展示该解析技术在 Scala 中的具体语法写法，并指出实现中类型转换可能多余。

这是他们 Scala 版本中语法实际的样子。这个语法用于处理 x 代表 1、s 代表 + 的算术语言，只生成解析树，不计算最终结果。注释是我加的：（代码略）// 解析树节点 abstract class Exp; case object One extends Exp; case class Sum(e1: Exp, e2: Exp) extends Exp; // 终结符 lazy val S: Parser[Char,Char] = new EqT[Char]('s'); lazy val X: Parser[Char,Char] = new EqT[Char]('x'); // 表达式定义 lazy val EXP: Parser[Char,Exp] = rule(X) ==> { case x => One.asInstanceOf[Exp] } || rule(EXP ~ S ~ EXP) ==> { case e1 ~ s ~ e2 => Sum(e1,e2).asInstanceOf[Exp] } || ... // 运行 val xin = Stream.fromIterator("xsxsxsxsx".elements); EXP.parseFull(xin) // 返回值 => Stream(Sum(One,Sum(Sum(One,One),Sum(One,One))), ?)。我认为所有 asInstanceOf 都可以避免。

fizx查看英文原文

Here's what a grammar actually looks like in their scala version. This grammar is for arithmetic over the language where x represents 1, and s represents +. This only generates the parse tree, not the final answer. Comments are added by me: // The Nodes in the parse tree abstract class Exp case object One extends Exp case class Sum(e1 : Exp, e2 : Exp) extends Exp // Terminals lazy val S : Parser[Char,Char] = new EqT[Char] ('s') lazy val X : Parser[Char,Char] = new EqT[Char] ('x') // Definition of an expression // I'm pretty sure all the asInstanceOfs are avoidable/unnecessary. lazy val EXP : Parser[Char,Exp] = rule(X) ==> { case x => One.asInstanceOf[Exp] } || rule(EXP ~ S ~ EXP) ==> { case e1 ~ s ~ e2 => Sum(e1,e2).asInstanceOf[Exp] } || rule(EXP ~ S ~ X) ==> { case e1 ~ s ~ e2 => Sum(e1,One).asInstanceOf[Exp] } || rule(X ~ S ~ EXP) ==> { case e1 ~ s ~ e2 => Sum(One,e2).asInstanceOf[Exp] } || rule(X) ==> { case x => One.asInstanceOf[Exp] } || rule(EXP) ==> { case e => e } || rule(Epsilon[Char]) ==> { case () => One } // Actually run the rule val xin = Stream.fromIterator("xsxsxsxsx".elements) EXP.parseFull(xin) // return value => Stream(Sum(One,Sum(Sum(One,One),Sum(One,One))), ?)

补充询问当前解析技术的最先进方案，并提及 PEG、OMeta 和 Parsec。

解析领域最先进的技术究竟是什么？作为业余爱好者，我上次研究时发现 PEG 和 OMeta 之类的扩展似乎是最好的选择，也听说过 Parsec 不错。

johkra查看英文原文

What is actually state-of-the-art in parsing? When I, as an Amateur, last looked into it, PEG[1] and extensions like OMeta[2] seemed to be the best options. I've heard good things about Parsec[3], too. [1](http://en.wikipedia.org/wiki/Parsing_expression_grammar) [2](http://www.tinlizzie.org/ometa/) [3](http://legacy.cs.uu.nl/daan/parsec.html)

补充指出 Antlr 已取代 yacc，并提到 parser combinators 和 GLL 解析器的优势，但新技术的实际采用仍然缓慢。

Antlr 已经在大多数实际工作中取代了 yacc。Daniel Spiewak 也提到 parser combinators，以及 GLL 解析器如何更易用且多数时候足够快。他提到 parser combinators 是创建解析器的领域特定语言。尽管如此，更好的技术采用起来真的很慢，一如既往。

DanielRibeiro查看英文原文

Well, Antlr (http://www.antlr.org/) has replaced yacc for most of the practical work already. Daniel Spiewak also mentions parser combinators and how GLL parsers can be much easier to use and yet fast enough most of the time (http://www.codecommit.com/blog/scala/unveiling-the-mysteries-of-gll-part-1). He mentions parser combinators as domain specif languages for creating parsers (http://www.codecommit.com/blog/scala/the-magic-behind-parser-combinators). Despite all of these, adoption of better techniques is really slow. As usual.

历次讨论

2010Hacker News 讨论帖154 分 · 44 评

HN 二十年，最值得读的论文。

朋友分享的书单

专题阅读路线

本周最多人读

我的书单

必读 30 篇

论文库

这些论文是怎么挑出来的

全量扫一遍

只留论文本身

写导读、译评论

导读

HN 评论精选

历次讨论

同领域还值得读

Google 的软件工程（2017）

Peter Naur：编程作为理论构建 (1985)

SciPy 1.0：Python 科学计算的基础算法

Lisp 的历史（1979）

使用 NumPy 进行数组编程

打赏支持

关注向阳乔木