ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Automatic Generation of Near-Optimal Translators for Noncircular Attribute Grammars.

Rina S. Cohen, E. Harry: Automatic Generation of Near-Optimal Translators for Noncircular Attribute Grammars. POPL 1979: 121-134
@inproceedings{DBLP:conf/popl/CohenH79,
  author    = {Rina S. Cohen and
               E. Harry},
  title     = {Automatic Generation of Near-Optimal Translators for Noncircular
               Attribute Grammars},
  booktitle = {POPL},
  year      = {1979},
  pages     = {121-134},
  ee        = {db/conf/popl/CohenH79.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Attribute grammars are an extension of context-free grammars devised by Knuth as a formalism for specifying the semantics of a context-free language along with the syntax of the language. The syntactic phase of the translation process has been extensively studied and many techniques are available for automatically generating efficient parsers for context-free grammars. Attribute grammars offer the prospect of similarly automating the implementation of the semantic phase. In this paper we present a general method of constructing, for any non-circular attribute grammar, a deterministic translator which will perform the semantic evaluation of each syntax tree of the grammar in time linear with the size of the tree. Each tree is traversed in a manner particularly suited to the shape of the tree, yielding a near optimal evaluation order for that tree. Basically, the translator consists of a finite set of "Local Control Automata", one for each production; these are ordinary finite-state acyclic automata augmented with some special features, which are used to regulate the evaluation process of each syntax tree. With each node in the tree there will be associated the Local Control Automaton of the production applying at the node. At any given time during the translation process all Local Control Automata are inactive, except for the one associated with the currently processed node, which is responsible for directing the next steps taken by the translator until control is finally passed to a neighbour node, reactivating its Local Control Automaton. The Local Control Automata of neighbour nodes communicate with each other.

Copyright © 1979 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.


POPL Proceedings Compendium

CDROM Version: Load the CDROM "POPL, The First Ten Years" and ... BibTeX

Printed Edition

Conference Record of the Sixth Annual ACM Symposium on Principles of Programming Languages, San Antonio, Texas, January 1979. ACM 1979 BibTeX
Contents

Online Edition: ACM Digital Library


BibTeX

Copyright © Sat May 16 23:34:35 2009 by Michael Ley (ley@uni-trier.de)