V-Star: Learning Visibly Pushdown Grammars from Program Inputs
summary
A tool called V-Star learns visibly pushdown grammars from sample inputs without prior knowledge of call/return tokens by detecting nesting patterns, inferring compatible call/return tags, and adapting an L-style algorithm to K-single-entry VPAs. It also infers a partial tokenizer to operate at token level, proves exact learnability (polynomial membership/equivalence queries) for minimal K-SE VPAs, and evaluates on JSON, XML, S-exprs showing substantially higher precision/recall than Glade/Avada at the cost of many more membership queries and wall-clock time; artifacts are available.
AI-written summary · about
chapters (13)
- 0:00V-Star intro and grammar inference
- 2:31Nesting in visibly pushdown grammars
- 5:43V-Star algorithm overview
- 9:41Learning automata with L-Star
- 13:41Evaluation vs prior work
- 15:48Performance trade-offs
- 16:53Summary and future
- 17:14Q&A: Call/return symbols
- 18:16Q&A: Seed set sensitivity
- 19:22Q&A: Call-return inference impact
- 20:47Q&A: Non-VPD grammars
- 21:50Q&A: Sample strings role
- 22:34Q&A: Equivalence query approx
related talks
14mA Derivative-based Parser Generator for Visibly Pushdown Grammars
23mA Verified Packrat Parser Interpreter for Parsing Expression Grammars
17mV, as in Vautledétour
28mVirtual Domain Specific Languages via Embedded Projectional Editing
53mSemantics-based program manipulation in the age of LLMs
44mParsing Text with a Virtual Machine
19mVelvet: A Multi-Modal Verifier for Effectful Programs
23mSynthesizing Efficient Super-Instruction Sets for Ethereum Virtual Machine