Browse Prior Art Database

An Interpretive Technique for Evaluating Functional Attribute Grammars

IP.com Disclosure Number: IPCOM000128580D
Original Publication Date: 1986-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 8 page(s) / 30K

Publishing Venue

Software Patent Institute

Related People

Robert M. Herndon, Jr.: AUTHOR [+4]

Abstract

An algorithm for the dynamic, lazy evaluation of attribute grammars is presented. The algorithm is efficient in the time and space required to evaluate the output attributes. It requires space proportional to the size of the semantic tree plus a small constant times the number of attributes. The algorithm uses the space allocated for attributes to select attribute evaluation code and to store a return stack. As a result, very little storage beyond that r required for a semantic tree is required. Circularity is detected at run-time, making the method suitable for use with circular grammars. The evaluation code is easily modified after compila-tion, suggesting that the algorithm may be useful for interpretive attribute grammar develop-ment tools. Such tools would allow a user to perform translations, examine the results, modify semantic functions as desired, perform more translations, change semantic functions again, etc., without recompilation, greatly reducing development time for attribute grammars.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 13% of the total text.

Page 1 of 8

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

An Interpretive Technique for Evaluating Functional Attribute Grammars

by

Robert M. Herndon, Jr. Valdis A. Berzins

Computer Science Department

136 Lind Hall Institute of Technology University of Minnesota Minneapolis, Minnesota 554c5 s

TR 86-5

February 1986

Technical Report J nterpretive Technique ' for

Evaluating Functional Attribute Grammars

r Robert M. Herndon, Jr. and Valdis A. Berzins

Abstract

An algorithm for the dynamic, lazy evaluation of attribute grammars is presented. The algorithm is efficient in the time and space required to evaluate the output attributes. It requires space proportional to the size of the semantic tree plus a small constant times the number of attributes. The algorithm uses the space allocated for attributes to select attribute evaluation code and to store a return stack. As a result, very little storage beyond that r required for a semantic tree is required. Circularity is detected at run-time, making the method suitable for use with circular grammars. The evaluation code is easily modified after compila-tion, suggesting that the algorithm may be useful for interpretive attribute grammar develop-ment tools. Such tools would allow a user to perform translations, examine the results, modify semantic functions as desired, perform more translations, change semantic functions again, etc., without recompilation, greatly reducing development time for attribute grammars.

1. Introduction A context free grammar is a tuple (N,T,P,Z), where N and T are disjoint sets of symbols called the pore-terminal and terminal symbols of the grammar, Z E N, is a distinguished start symbol, and P is a set of productions. Each production p E P is a sequence of symbols

(Equation Omitted)

We will use the notation Pk to denote the symbol Xk in production p. An attribute grammar [Knuth 1968] is a context-free grammar, (N,T,P,Z), where each of the non-terminals in N has been augmented with a finite set of attributes, and each production n P has been augmented with a set of functions defining these attributes. The set of attributes that belong to a non- terminal X is denoted A(X). A specific attribute may be selected by its index; the attribute a belonging to X is written X$. Each of the functions fp k a, is specified by the production, p, it is associated with, an index, k, specifying symbol Xk in the production, and an index, a, selecting an attribute belonging to that symbol. Each function defines an attribute that belongs to a

University of Minnesota Page 1 Dec 31, 1986

Page 2 of 8

An Interpretive Technique for Evaluating Functional Attribute Grammars

symbol in a particular production in terms of other attributes that belong to symbols in that production. Each attribute may potentially be defined in two ways: either its defining equation may be found associated with the production whose left-hand symbol contains the attribute, in which case it is a synthesized attr...