Syntax Repair as Language Intersection
This work provides a formal, grammar-constrained approach to syntax repair for programming languages, offering a principled alternative to heuristic methods.
The paper formalizes bounded syntax repair as the intersection of a context-free language with an acyclic Levenshtein automaton, enabling a parallel decision procedure for repairability and fast enumeration via Brzozowski derivatives. Experiments on Python syntax errors show the approach yields practical candidate spaces that improve repair accuracy.
Syntax repair can be viewed as a question about finite languages: given an invalid string and a grammar, which nearby strings are syntactically valid? We formalize bounded syntax repair as the intersection of a context-free language with an acyclic Levenshtein automaton, obtaining a finite language that contains all and only repairs within a chosen edit radius. This approach leverages the classic Bar-Hillel construction for CFL-regular intersection, and specializes it to acyclic automata, and yielding a highly parallel decision procedure for deciding repairability. We then show how Brzozowski derivatives support fast incremental enumeration from this intersection, separating exact admissibility from probabilistic ranking. Experiments on Python syntax errors demonstrate the resulting candidate spaces are practical to construct and substantially improve repair accuracy when used as a grammar-constrained search space.