Context-Free Language Reachability via Skewed Tabulation

Explore a groundbreaking approach to context-free language reachability (CFL-reachability) in this 19-minute conference talk from PLDI 2024. Learn about skewed tabulation, a novel technique that significantly improves the scalability of CFL-reachability algorithms by reducing wasted and unnecessary summary edges. Discover how this method modifies parse trees either statically or dynamically to avoid edge generations caused by recursive nonterminals. Examine the implementation of skewed tabulation in alias analysis, value-flow analysis, and taint analysis, with impressive results showing substantial speedups and reduced memory consumption compared to traditional RHS-tabulation-based solvers. Gain insights into the negligible cost of grammar transformation for skewed tabulation and its potential impact on program analysis problems.