一句话：提出确定性 Greibach 范式，将词法与语法分析融合，实现无 token 流的高效确定性解析器组合子库 flap。
词法器和解析器通常分开定义、通过 token 流连接，这种分离有利于模块化并减少解析歧义，但物化 token 数据结构并对其做 case 分支会带来开销。本文提出一种确定性的 Greibach 范式变体，保证仅用单个 token 的前瞻即可进行确定性解析，并使词法与语法分析的融合变得异常简单；作者证明将上下文无关表达式规范化为该确定范式是保语义的。基于此实现了分阶段的解析器组合子库 flap：它对外提供标准接口，但生成特化的、无 token 的代码。在多个基准测试上，flap 生成的解析器比 ocamlyacc 快 2 到 6 倍。
Lexers and parsers are typically defined separately and connected by a token stream. This separate definition is important for modularity and reduces the potential for parsing ambiguity. However, materializing tokens as data structures and case-switching on tokens comes with a cost. We show how to fuse separately-defined lexers and parsers, drastically improving performance without compromising modularity or increasing ambiguity. We propose a deterministic variant of Greibach Normal Form that ensures deterministic parsing with a single token of lookahead and makes fusion strikingly simple, and prove that normalizing context free expressions into the deterministic normal form is semantics-preserving. Our staged parser combinator library, flap, provides a standard interface, but generates specialized token-free code that runs two to six times faster than ocamlyacc on a range of benchmarks.
@article{paperbot1989,
title = {flap: A Deterministic Parser with Fused Lexing},
author = {Jeremy Yallop and Ningning Xie and Neel Krishnaswami},
journal = {Proceedings of the ACM on Programming Languages},
volume = {7},
number = {PLDI},
year = {2023},
doi = {10.1145/3591269}
}