Toward Grammar Inference via Refinement Types (Extended Abstract)
summary
Prototype system converts Python ad hoc parsers into a small lambda IR called Panini IR and infers precise refinement types, then solves unknowns using a fusion algorithm plus SMT to produce a minimal grammar. The prototype automatically reconstructs grammars for several examples (including comma-separated integers and branchy string checks), produces readable productions, and uncovers contradictions; work is sound but incomplete — needs a library of string specs, source-location tracking, and a formalized solver.
AI-written summary · about
chapters (6)
- 0:00Start
- 1:39Applications
- 2:07Goal: Automatic Grammar Inference
- 3:48Refinement Inference
- 5:08Grammar Solving
- 10:18Status / Future Work
related talks
29mGrammar Inference for Ad Hoc Parsers
16mStatic Inference of Regular Grammars for Ad Hoc Parsers
23mAnswer Refinement Modification: Refinement Type System for Algebraic Effects and...
30mConstrained generation of well-typed programs
29mExplicit Refinement Types
01h 05mAll the Languages Together
19mType Inference Logics
56mOn Type-Based Techniques for Program Manipulation