No Shot in the Dark: Efficient Context-Free Language Reachability via Context-Aware Tabulation

Context-free language (CFL) reachability is a widely used framework for formulating static program analyses. Operating over edge-labeled graphs, the standard algorithm performs context-free tabulation by iteratively deriving new edges that summarize paths whose labels conform to the production rules of a context-free grammar. However, as the term “context-free” suggests, these derivations are made without considering the surrounding context of inferred edges, often resulting in unproductive edges that do not contribute to the final reachability result.