一句话:提出上下文感知的制表算法,在CFL可达性推导中利用上下文避免生成无用边,从而提升静态分析效率。
上下文无关语言(CFL)可达性是静态程序分析的常用框架,它在边标记图上通过上下文无关制表迭代推导新边,以汇总标签符合文法产生式的路径。然而,正如“上下文无关”所示,标准算法在推导新边时不考虑已推导边的周围上下文,容易产生大量对最终可达性结果无贡献的无用边,造成计算浪费。本文提出上下文感知的制表方法,在推导过程中引入上下文信息,以更精准地判断哪些边值得生成,从而减少无用边的数量。摘要未给出具体实验数据,但该工作旨在提高CFL可达性分析的整体效率。
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.