Automatic Repair of Regular Expressions
summary
Tool enumerates AST templates with holes and uses automata-based and regex-based SMT encodings plus three pruning tests (Sigma/Top/Bottom) to synthesize minimal AST edits under an AST-node-count distance metric and a MaxSMT objective that prefers common classes (letters, digits). Implementation repairs about 75% of AutomataTutor examples in under 10s and 23/25 RacketLib benchmarks in 7.3s while a genetic-tool baseline fixes only 3 in >3 minutes; repaired expressions double average F1 on held-out tests.
AI-written summary · about
chapters (18)
- 0:00Intro
- 0:22Use case deep dive 1
- 1:42The repair problem
- 2:28Distance between expressions
- 3:39Enumerating Regular Expressions
- 4:10Enumerating Templates
- 4:43Template generation
- 5:09Outline of repair algorithm
- 5:48Template pruning 1
- 6:08Template pruning 2
- 7:50Solving templates using SMT: Intuition
- 9:19Running examples on template automata
- 10:27From run constraints to string constraints
- 11:14Finishing automaton-based SMT encoding
- 13:34Benchmarks and baselines
- 14:32Research questions
- 16:25Which of the two SMT encodings has better performance?
- 17:00Conclusion
related talks
12mAutomatic Grammar Repair
04mFTFY: Research advances in automatic bug repair
20mAutomatic Invariant Testing for Finite-State Machines
59mAutomatic Grammar Repair
21mValidating SMT Solvers for Correctness and Performance via Grammar-based Enumeration
30mGenerating Conforming Programs With Xsmith
15mGrammar-Based Testing for Little Languages: An Experience Report with Student Compilers
18mSMT2Test: From SMT Formulas to Effective Test Cases