ScholarLens Back to search
1982•Unpublished venueOpen access

Optimal-time incremental semantic analysis for syntax-directed editors

Thomas Reps

Open full text 114 citations

Abstract

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.

Open-access reader

About this research paper

What this paper is about

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.

Why it matters

OpenAlex reports 114 citations for this work. Citation counts describe recorded attention and do not establish research quality.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

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.

Key concepts: Computer science, Syntax, Semantics (computer science), Pruning, Rule-based machine translation, Modular design, Programming language, A priori and a posteriori

Related papers

Related paper 1Related paper 2Related paper 3
Back to paper searchBrowse research topicsOriginal source
Optimal-time incremental semantic analysis for syntax-directed editors — Research Paper | ScholarLens