Optimal-time incremental semantic analysis for syntax-directed editors
Optimal-time incremental semantic analysis for syntax-directed editors
复制标题
语法导向编辑器的最佳时间增量语义分析
DOI：
10.1145/582153.582172
复制
发表时间：
1982
影响因子：
3.6
通讯作者：
T. Reps
中科院分区：
文献类型：
--
作者：
T. Reps
属性语法允许以应用和模块化方式指定静态语义，因此是语法导向编辑器的良好基础。此类编辑器将程序表示为属性树，并通过子树修剪和嫁接等操作进行修改。每次修改后，属性子集 AFFECTED 需要新值。 AFFECTED 中的成员身份事先未知；本文提出了一种算法，可以识别 AFFECTED 中的属性并计算它们的新值。该算法是时间最优的，其成本与 AFFECTED 的大小成正比。
Attribute grammars permit the specification of static semantics in an applicative and modular fashion, and thus are a good basis for syntax-directed editors. Such editors represent programs as attributed trees, which are modified by operations such as subtree pruning and grafting. After each modification, a subset of attributes, AFFECTED, requires new values. Membership in AFFECTED is not known a priori; this paper presents an algorithm that identifies attributes in AFFECTED and computes their new values. The algorithm is time-optimal, its cost is proportional to the size of AFFECTED.