Repairing Regular Expressions for Extraction
summary
A tool called R3 implements the first PBE-based synthesis and repair for extraction, supporting real-world extensions like backreferences and lookarounds. It defines a deterministic big-step semantics that uses continuations to model real regex engine disambiguation, generates SMT constraints accordingly, and adds two pruning techniques. Evaluation on 50 real GitHub-derived regex fixes finds solutions for 80% of 50 cases within the time limit; hardest instances time out when they require large structural edits.
AI-written summary · about
chapters (12)
- 0:00Introduction
- 1:06Regex problems in practice
- 2:51Deterministic extraction behavior
- 3:57R3 tool repairs regex
- 4:41Repair algorithm overview
- 6:49Regex semantics challenges
- 7:52Disambiguating with continuations
- 9:37Real-world regex extensions
- 11:47SMT constraints for repair
- 12:08R3 evaluation and efficiency
- 13:34Conclusion and future topics
- 13:56Q&A