paperbot · PL 论文追踪

全部论文 待读 收藏

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

拒绝盲猜:基于上下文感知制表的高效上下文无关语言可达性
ICSE Proceedings of the 2026 IEEE/ACM 48th International Conference on Software Engineering2026匹配度 3/10 · 论文属于静态分析中的CFL可达性算法优化,是程序分析基础技术,但未涉及LLM/Agent、ML系统与Agentic程序分析、浮点程序分析或贝叶斯程序分析,与用户当前核心研究问题的交叉有限。引用 0 inbox
Chenghang Shi, Lian Li
crossref: 2026-09-12

AI 速览

一句话:提出上下文感知的制表算法,在CFL可达性推导中利用上下文避免生成无用边,从而提升静态分析效率。

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

问题
标准CFL可达性算法在制表推导新边时忽略上下文,产生大量对最终结果无贡献的无用边,导致分析效率低下。
方法
提出上下文感知的制表(context-aware tabulation),在推导过程中利用已推导边的上下文信息,避免无用边的生成。
评估
摘要未提供具体评估细节;该工作属于算法改进,预期通过实现原型并在静态分析基准上对比标准制表算法的效率。
原文摘要(Abstract)

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.

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@inproceedings{paperbot11867,
  title = {No Shot in the Dark: Efficient Context-Free Language Reachability via Context-Aware Tabulation},
  author = {Chenghang Shi and Lian Li},
  booktitle = {ICSE},
  year = {2026},
  doi = {10.1145/3744916.3773222}
}