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

flap: A Deterministic Parser with Fused Lexing

flap:融合词法分析的确定性解析器
Jeremy Yallop, Ningning Xie, Neel Krishnaswami · 2023

把词法分析融合进确定性语法解析,生成比 ocamlyacc 快 2 到 6 倍的代码。

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 3 人首次 2023-04-14 · 最近 2026-06-29
3不同的人
3活跃月份
3讨论串
9被引(OpenAlex)

词法分析器和语法分析器通常分开定义、靠记号流连接,这有利于模块化,但把记号物化成数据结构并对其做分支判断有性能代价。论文展示了如何把分开定义的词法器与语法器融合,大幅提速而不牺牲模块性、不增加歧义。作者提出确定性的 Greibach 范式变体,保证单记号前瞻的确定性解析并使融合变得简单,证明把上下文无关表达式归一化到该范式保持语义;其分阶段的解析器组合子库 flap 生成无记号的特化代码,在一系列基准上比 ocamlyacc 快 2 到 6 倍。

HN 为什么提它

输入里只有一条摘录:评论者给出了这篇融合词法分析的解析器论文的 arXiv 扩展版链接,主要作为资料出处被引用。

方法难度 5 / 5约 60 分钟经得起时间
读之前最好知道
1上下文无关文法与 Greibach 范式(GNF)
2词法分析与语法分析(lexer/parser)
3解析器组合子(parser combinator)
4分阶段编程(staged programming)
5OCaml 语言

HN 书评

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

“There is an extended version on arXiv: flap.”

指出 arXiv 上有这篇论文的扩展版
Why Split Lexing and Parsing into Two Separate Phases?原评论 ↗
被提交为 story · 2 次