Attribute storage optimization by stacks

DOI10.1007/BF00277390MaRDI QIDQ1121674zbMATH OpenOpenAlexFDO

Authors Joost Engelfriet, Willem R. de Jong

Publication date 1990

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf00277390

zbMATH Keywords

(\(\ell -)ordered\)attribute grammarsevaluatorsmulti-visit

Mathematics Subject Classification ID

Theory of software (68N99) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Review text

Storage optimization is considered for evaluators of simple multi-visit, or (\(\ell\)-)ordered, attribute grammars. A necessary and sufficient condition is formulated which has to be satisfied by such an evaluator to enable it to store the instances of a given attribute on a global stack. A simple algorithm is given that decides this condition in polynomial time. A similar algorithm can be used to decide whether the instances of the attribute can be stored in a global variable. These algorithms are static, i.e., they are used at evaluator construction time.

Recommendations

• scientific article; zbMATH DE number 3913715
• Lifetime analysis for attributes
• Sublinear-space evaluation algorithms for attribute grammars
• Global storage cells for attributes in an attribute grammar
• A comparison of storage optimizations in automatically-generated attribute evaluators

Cited in

(5)

• A comparison of storage optimizations in automatically-generated attribute evaluators
• Lifetime analysis for attributes
• An attribute-grammar framework for specifying the accessibility in Java programs
• scientific article; zbMATH DE number 3913715 (Why is no real title available?)
• Sublinear-space evaluation algorithms for attribute grammars

This page was built for publication: Attribute storage optimization by stacks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1121674)