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

Yacc is dead

Yacc 已死
Matthew Might, David Darais · 2010

用导数法解析任意上下文无关文法的轻量解析库

开始阅读 ↗PDFalphaXiv 讨论
被推荐 · 5 人首次 2010-11-28 · 最近 2024-01-24
5不同的人
3活跃月份
5讨论串
7被引(OpenAlex)

论文提出两种解析上下文无关语言的新方法:一是把 Brzozowski 的正则表达式导数推广到上下文无关文法,二是把导数推广到解析器组合子。成果是一个不到 250 行、易于实现的解析库,能把任意上下文无关文法解析成惰性的解析森林,并给出 Scala 和 Haskell 的实现。对 S-表达式的初步实验每秒可解析数百万个 token,说明效率足以实用。

HN 为什么提它

有评论者把它推荐为入门起点,用来解析 Yacc 力不从心的上下文无关与有歧义的文法。

方法难度 3 / 5约 40 分钟经得起时间
读之前最好知道
1上下文无关文法(context-free grammar)
2Brzozowski 正则表达式导数
3解析器组合子(parser combinators)
4惰性求值(lazy evaluation)

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
推荐Locke1689 · 2013-02

“My recommendation is to start here[1].”

推荐从这里入手,解析 Yacc 处理不了的上下文无关和歧义文法
C++ Grandmaster Certification原评论 ↗
被提交为 story · 4 次