University of Helsinki Department of Computer Science
 

Department of Computer Science

Department information

 

Attribute grammars for one-pass compilation

Jorma Tarhio: Attribute grammars for one-pass compilation. PhD Thesis, Report A-1988-11, Department of Computer Science, University of Helsinki, 1988. 71 pages. <http://www.cs.helsinki.fi/TR/A-1988/11>

Full paper:
Metadata: XML file

Abstract

Three topics concerning one-pass compilation based on attribute grammars are studied. For the first, right-to-left dependencies are considered. In one-pass compilation all attributes are evaluated from the left to the right in conjunction with parsing, and therefore right-to-left dependencies between at tributes are normally forbidden. A formalization is given in the form of two grammar classes for such local right-to-left dependencies that can be handled during parsing. These grammar classes are considered as extensions of S- and L-attributed grammars. For the second, a transformation is presented for replacing certain attribute references in an L-attributed grammar by upward remote references, which are references to a distant attribute above in the attributed tree. As a result of the transformation, these distant attributes will function as variables. The purpose of the transformation is to facilitate easy storage allocation and to enhance readability of an attribute grammar. For the third, the evaluation of inherited attributes during LR parsing is studied. An evaluation method which allows only copy rules for inherited attributes is completed with a transformation from L-attributed grammars to the restricted form. An implementation of the method is reviewed. Related evaluation methods are discussed and relations of the grammar classes connected with them are analyzed.

Index Terms

Categories and Subject Descriptors:
D.3.4 [Programming Languages]: Processors - Translator Writing Systems and Compiler Generators
D.3.1 [Programming Languages]: Formal Definitions and Theory - Semantics
F.4.2 [Mathematical Logic and Formal Languages]: Grammars and Other Rewriting Systems - Parsing

General Terms: languages

Additional Key Words and Phrases: compiler generation, attribute grammars, one-pass compilation, LR parsing


Online Publications of Department of Computer Science, Anna Pienimäki