Grammar Inference for Ad Hoc Parsers
summary
A system translates ad hoc string code (split/map/trim pipelines) into a small lambda IR, runs refinement-type inference to produce verification templates, and rewrites those constraints into a minimized grammar-like predicate; a prototype implements Panini intermediate representation and solves the examples shown, yielding concrete grammars that enable grammar-aware fuzzing and CI alerts. It currently handles simple programs using integer-range and string abstract domains, and ongoing work focuses on formalizing the solver, richer string domains, provenance, and end-to-end engineering.
AI-written summary · about
chapters (15)
- 0:00Grammar inference intro
- 2:30Inferring grammars from parsers
- 5:20Refinement types and Panini IR
- 7:50Challenges with grammar variables
- 10:17Minimizing string predicates
- 11:21Implementation and future work
- 13:49Applications and evaluation
- 15:34Q&A: Automating grammar specs
- 16:38Q&A: User study on comprehension
- 18:03Q&A: Relation to regex
- 19:26Q&A: Inferring output grammars
- 21:34Q&A: Defining grammar comprehension
- 23:20Q&A: Platform grammar mind
- 25:27Q&A: String manipulation ubiquity
- 29:04Closing remarks
related talks
12mToward Grammar Inference via Refinement Types (Extended Abstract)
16mStatic Inference of Regular Grammars for Ad Hoc Parsers
21mSynthesizing Formal Semantics from Executable Interpreters
12mAutomatic Grammar Repair
17mEfficient Bottom-Up Synthesis for Programs with Local Variables
01h 05mAll the Languages Together
37mThe Art of Parsing
18mGraph IRs for Impure Higher-Order Languages: Making Aggressive Optimizations Af...