算法与理论计算机2016arxiv.org
论解析导数法的复杂度与性能
On the Complexity and Performance of Parsing with Derivatives
进阶 · 约 60 分钟读完前置知识：形式语言与自动机基础、上下文无关文法、Brzozowski 导数概念
导读
这篇论文研究基于导数（derivatives）的解析算法的复杂度与性能。针对 Might 等人 2011 年提出的解析导数算法实现极慢的问题（如 31 行 Python 文件解析需三分钟），作者证明了该算法最坏情况为立方时间复杂度，并给出一个简洁的立方时间 Racket 实现，性能比以往实现快数个数量级，但仍远慢于 Bison 等传统解析器。
HN 关注点：解析导数这一优雅理论的实际可用性，讨论焦点是其 O(n³) 复杂度和与主流解析器（如 Bison、递归下降）的性能差距。
HN 评论精选
这几条评论里：质疑 1 补充 3
补充科普解析导数原理，指出论文证明了立方复杂度并给出大幅提速的实现
为不熟悉的读者总结解析导数（Brzozowski 1964）：对字符 f，语言 {foo, frak, bar} 的导数是 {oo, rak}——保留以 f 开头的词并去掉首字符。对输入逐字符求导，若最终结果语言包含空串则接受输入。全部处理在解析时进行，无需解析器生成阶段。Might 2011 年的算法加入了记忆化和惰性求值以支持递归，但原实现慢得离谱（31 行 Python 要解析三分钟）。本文证明最坏情况是立方时间，并提供了简洁的 Racket 实现（快数个数量级），但仍比同语法的 Bison 解析器慢数个数量级，作者归因于语言选择（C vs Racket）。
heydenberk查看英文原文
Summary of parsing with derivatives (Brzozowski 1964) for the unfamiliar (like me): For example, with respect to the character f, the derivative of the language for which [[L]] = {foo, frak, bar} is Df (L) = {oo, rak}. Because foo and frak start with the character f and bar does not, we keep only foo and frak and then remove their initial characters, leaving oo and rak. We repeat this process with each character in the input until it is exhausted. If, after every derivative has been performed, the resulting set of words contains the empty word, then there is some word in the original language consisting of exactly the input characters, and the language accepts the input. All f this processing takes place at parse time, so there is no parser-generation phase. The specific algorithm they build off (Might 2011) has extended this to memoize repeated derivations of the same arguments and to allow for lazy evaluation in the case of recursion. But this algorithm was implemented in a mind-bendingly-slow way: For example, they report that a 31-line Python file took three minutes to parse! They prove that the worst case is actually cubic time and provide a concise cubic-time implementation in Racket: https://bitbucket.org/ucombinator/derp-3 Their implementation is orders of magnitude faster of prior PWD implementations, but still orders of magnitude slower than a Bison parser of the same grammar, which they attribute to language choice (C vs Racket). Please correct me if I'm wrong about any of this! Summarizing research like this helps me understand it, but that doesn't mean I actually understand it.
质疑质疑实用性：O(n³) 复杂度和解析树生成困难使其难以用于实际，性能比主流解析器慢千倍
注意复杂度仍是 O(n³)，高于多数真实语法所用算法的复杂度。导数解析相比自底向上解析起初显得很优雅，但问题在于解析树的生成比其他方法更棘手，在我看来大大削弱了其优雅性——当然若只需识别则很直接。论文中实现的性能是每秒几百行代码（小语言），而生成式递归下降或自底向上解析器对真实语言可达每秒几十万行。所以尽管概念有趣，我认为它对注重效率和可扩展性的实际解析器生成意义不大。我自己在做一个描述性解析器生成器，想看看能否接近我目前使用的 PEG 解析器（用条件记忆化即 packrat 解析加速）的性能。
ThePhysicist查看英文原文
Note that the complexity is still O(n^3), which is higher than that of other algorithms for most "real-world" grammars. I read Might's initial paper on derivative parsing a while ago, and I agree that it really seems very elegant at first when compared e.g. to bottom-up parsing. The problem of the approach though is that parse tree generation is more tricky than for other methods and (IMHO) renders the technique considerably less elegant. Of course, if only recognition is needed then this technique is straightforward, but in most practical use cases the user will want to generate a parse tree as well. Also, the performance of the parser implementations dicsussed in the paper (and in Might's original work) are able to parse a few hundred lines of code per second (for a small language), which is very slow compared to e.g. generated recursive-descent or bottom-up parsers, which can achieve several hundred thousand of lines of code per second for real-world languages. So although it's an interesting concept I personally think it will not be of very high relevance to practical parser generation, at least for use cases where efficiency and scalability matters. I have been working on a descriptive parser generator though to see if I can get anywhere near the performance of my currently used PEG parser (which uses conditional memoization -i.e. packrat parsing- to speed up the parsing).
补充推荐 GLL 解析作为兼顾易实现性与通用性的替代方案
如果相关的话，各位解析专家怎么看 GLL 解析？它保留了 LL 解析器易于实现和调试的优点，同时消除了部分 LR 风格的限制，算是一种混合方案，结果是立方时间。
nickpsecurity查看英文原文
So, if applicable here, what do you parsing experts think of GLL parsing? http://dotat.at/tmp/gll.pdf It mentions retaining easy implementation and debugging of LL parsers while knocking out limitations with some LR-style stuff. A hybrid of sorts. Result is cubic time.
补充从跨学科角度猜测解析与自动微分/神经网络之间的潜在联系
我不是科班出身的计算机科学家，感觉自己像盲人摸象，只有零散信息没有整体图景。我猜测解析导数与有理多项式和正则语言之间的一一对应有关。让我觉得诱人的是：鉴于正则语言与神经网络的联系，其他（非基于求导的）快速解析技术或许能对快速反向传播与自动微分有所启示。希望听到更多讨论。
srean查看英文原文
Not trained as a computer scientist I find myself in the position of those six blind men and an elephant. I have bits and pieces of information but not a coherent whole. I would suspect that this parsing by derivative thing is connected to the fact that there is one to one correspondence between rational polynomials and regular languages. What feels tantalizing to me is the following: given the connection between regular languages and neural networks other (meaning those that are not based on differentiation) fast parsing techniques probably would have imply something about fast back-propagation with automatic differentiation. Would love hearing more on this.
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2016Hacker News 讨论帖182 分 · 114 评
同领域还值得读
哲学家为何应关注计算复杂性
Why Philosophers Should Care About Computational Complexity (2011)
Scott Aaronson 的这篇长文论证计算复杂性理论（如 P vs NP、停机问题的复杂度视角）对哲学问题（如知识的本质、中文房间、水槽论证等）具有实质意义，而不仅是技术细…
算法与理论计算机2015 · 552 分 · 120 评进阶 · 约 90 分钟编辑精选通信的数学理论
A Mathematical Theory of Communication
是香农1948年的《通信的数学理论》，为通信建立数学框架：把信息量定义为不确定性或自由度（信息熵），并讨论信源编码、信道容量与可靠传输。
算法与理论计算机2020 · 495 分 · 91 评进阶 · 约 120 分钟编辑精选物理、拓扑、逻辑与计算：罗塞塔石碑
Physics, Topology, Logic and Computation: A Rosetta Stone (2009)
用范畴论充当“罗塞塔石碑”，试图在量子物理、拓扑、逻辑与计算四个领域之间建立统一的结构性类比：物理中的量子过程、拓扑中的配边、逻辑中的证明和计算中的程序，都可被视为某类范畴中的态…
算法与理论计算机2009 · 390 分 · 55 评 · 引用 13专业 · 约 180 分钟编辑精选一种快速、极小内存的一致性哈希算法
A Fast, Minimal Memory, Consistent Hash Algorithm
论文给出一种快速、省内存的一致哈希方案，目标是在桶数量变化时保持较小的键迁移成本，同时降低计算和内存开销。
算法与理论计算机2014 · 327 分 · 57 评 · 引用 4进阶 · 约 25 分钟编辑精选第五个 Busy Beaver 值的确定
Determination of the fifth Busy Beaver value
宣布确定了第五个 Busy Beaver 值 BB(5)：即 5 状态图灵机中停机前运行步数最多的机器（Champion）在 47,176,870 步后停机。
算法与理论计算机2025 · 288 分 · 116 评 · 引用 1专业 · 约 75 分钟编辑精选