Static Inference of Regular Grammars for Ad Hoc Parsers
summary
Automatic system PANINI uses a lambda-Σ IR, refinement-type inference and a novel abstract-interpretation quantifier-elimination to turn string verification conditions into regular grammars. Evaluation on 204 Python ad hoc parsers yields 100% precision, 93% average recall, 92% success rate and average runtime 0.82 ± 2.85 s; failures trace to weak loop invariants or limited abstract domains. Artifacts and paper (DOI) are available.
AI-written summary · about
chapters (7)
- 0:00Panini and ad hoc parsers
- 2:07Lambda sigma IR
- 5:36String constraints analysis
- 8:01Benchmark results
- 9:27Comparison with dynamic systems
- 10:10Future work
- 11:33Q&A
related talks
29mGrammar Inference for Ad Hoc Parsers
12mToward Grammar Inference via Refinement Types (Extended Abstract)
23mA Verified Packrat Parser Interpreter for Parsing Expression Grammars
29mNanopass Attribute Grammars
12mAutomatic Grammar Repair
25mNano-parsing: A Data-parallel Architecture for Perverse Parsing Environments
37mThe Art of Parsing
15mFaster Reachability Analysis for LR(1) Parsers