按年被提到
20162016 · 1 次2026
编程语言与编译器›类型系统与函数式语言·arXiv:1604.04695 · cs.PL

On the Complexity and Performance of Parsing with Derivatives

Michael D. Adams, Celeste Hollenbeck, Matthew Might · 2016
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2016-06-25 · 最近 2023-05-04
2不同的人
2活跃月份
2讨论串
19被引(OpenAlex)
arXiv 摘要(候选层不写导读)

Current algorithms for context-free parsing inflict a trade-off between ease of understanding, ease of implementation, theoretical complexity, and practical performance. No algorithm achieves all of these properties simultaneously. Might et al. (2011) introduced parsing with derivatives, which handles arbitrary context-free grammars while being both easy to understand and simple to implement. Despite much initial enthusiasm and a multitude of independent implementations, its worst-case complexity has never been proven to be better than exponential. In fact, high-level arguments claiming it is fundamentally exponential have been advanced and even accepted as part of the folklore. Performance ended up being sluggish in practice, and this sluggishness was taken as informal evidence of exponentiality. In this paper, we reexamine the performance of parsing with derivatives. We have discovered that it is not exponential but, in fact, cubic. Moreover, simple (though perhaps not obvious) modifications to the implementation by Might et al. (2011) lead to an implementation that is not only easy to understand but also highly performant in practice.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论1letterunixname · 2023-05

“There is more to translation of text to AST than parsing and lexing. There are semantic checks. In addition, most languages are not CFG and require nested contexts. "# {"\tThis is some # {'damn'} string".to_upper_case + " hello"}\n" Also, there are lexerless parsers such as derivative parsing that can be combined together and don't produce a stream of …”

Why Split Lexing and Parsing into Two Separate Phases?原评论 ↗
被提交为 story · 1 次