Flap: A deterministic parser with fused lexing
Flap introduces a deterministic parser with fused lexing that combines lexical analysis and parsing into a single phase, aiming to improve efficiency and eliminate the traditional separation between lexing and parsing in language processing.
Background
- Parsing is how computers turn source code (text written by a programmer) into a structured representation the computer can understand. "Lexing" is the first step—splitting text into tokens (like keywords, numbers, operators). "Parsing" is the next step—arranging those tokens into a tree structure that reflects the grammar of the programming language.
- Most parsers today do these two steps separately, which is simple but not always the fastest approach. Flap proposes a novel design that "fuses" lexing and parsing into a single phase.
- "Deterministic" means the parser always knows exactly what to do next without guessing or backtracking, which makes it faster and more predictable in performance—important for tools like code editors, linters, and compilers that need to process code quickly.
- ArXiv is a preprint server where researchers share papers before peer review. This is a computer science paper from 2023 presenting a new algorithm and implementation.