Faster Reachability Analysis for LR(1) Parsers
summary
A new algorithm reframes LR(1) reachability as recursive matrix equations (using the min,+ semiring) and replaces Pottier 2016 with a naive cost matrices prototype and a final compact cost matrices version that groups lookaheads into partitions. On real-world grammars it cuts runtime and memory by up to two–three orders of magnitude (many grammars run in a fraction of a second), while worst cases like a huge C++ grammar take ≈1 minute and ~3 GB. Implementation and tests exist and will be available in Menhir.
AI-written summary · about
chapters (15)
- 0:00Intro
- 0:35What is the problem?
- 0:59Why solve it?
- 2:13Pottier's algorithm (2016)
- 3:32Our contribution: speeding up the analysis!
- 5:31An example grammar
- 5:52The automaton
- 6:19Conflict resolution
- 8:47LR(1) matrix-based cost equations
- 9:40Big matrices?
- 10:10Classifying terminals
- 11:29Compacting columns
- 12:01Compacting rows
- 13:36In practice...
- 14:17Conclusion
related talks
19mContext-Free Language Reachability via Skewed Tabulation
17mA Better Approximation for Interleaved Dyck Reachability
17mIterative-Epoch Online Cycle Elimination for Context-Free Language Reachability
15mRecursive State Machine Guided Graph Folding for Context-Free Language Reachability
12mImplementing Hybrid Resource Analysis in Resource Aware ML
14mFast Client-Driven CFL-Reachability via Regularization-Based Graph Simplification
23mA Verified Packrat Parser Interpreter for Parsing Expression Grammars
18mGraph IRs for Impure Higher-Order Languages: Making Aggressive Optimizations Af...