Syntax Repair as Language Intersection

2025/07/16 by Breandan Considine, Considine, Breandan
Arts and Humanities · #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Programming Languages (cs.PL) #Syntax, Semantics, Linguistic Variation

paper · pdf · doi:10.48550/arxiv.2507.11873

openalex publication_date 2025/07/16 · openalex created_date 2025/10/18 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• A Word Sampler for Well-Typed Functions
• Edit Flows: Flow Matching with Edit Operations
• Syntactic and Semantic Control of Large Language Models via Sequential Monte Carlo
• Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling
• RE#: High Performance Derivative-Based Regex Matching with Intersection, Complement, and Restricted Lookarounds
• Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages
• OrdinalFix: Fixing Compilation Errors via Shortest-Path CFL Reachability
• Fine-grained reductions around CFL-reachability
• Sequential Monte Carlo Steering of Large Language Models using Probabilistic Programs
• Tighter Bounds on the Expressivity of Transformer Encoders
• The Fine-Grained Complexity of CFL Reachability
• Structured Denoising Diffusion Models in Discrete State-Spaces
• Saturated Transformers are Constant-Depth Threshold Circuits
• Thinking Like Transformers
• Break-It-Fix-It: Unsupervised Learning for Program Repair
• Self-Supervised Bug Detection and Repair
• Syntax and Stack Overflow: A methodology for extracting a corpus of syntax errors and fixes
• Generalized Convolution and Efficient Language Recognition
• Don't Panic! Better, Fewer, Syntax Errors for LR Parsers
• A Survey of Machine Learning for Big Code and Naturalness
• On the complexity and performance of parsing with derivatives
• Practical experiments with regular approximation of context-free languages
• Derivatives of Regular Expressions

Related

• Resolving conflicts with violable constraints: On the cross-modular parallelism of repairs
• Efficiently Computing Edit Distance to Dyck Language
• Repair Is Nearly Generation: Multilingual Program Repair with LLMs
• Automated Repair of Programs from Large Language Models
• An error correcting parser for context free grammars that takes less than cubic time