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. 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 ommitted] 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 1 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 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 attribute, or its defining equation may be found associated with the pro-duction whose right-hand side contains the symbol containing the attribute, in which case it is an inherited attribute. At most one of these two cases must hold for all attributes within an attribute grammar. An inherited attribute is defined in terms of attributes in its upper neigh-borhood, while a synthesized attribute is defined in terms of attributes in its lower neighborhood. Those attributes belonging to the root symbol of a parse are called the output attributes, and define a meaning or translation of the input string. Output attributes must be synthesized attributes. Since attributes may be defined in terms of each other, the potential exists for an attribute to be directly or indirectly defined in terms of itself. If any attribute within a gram-mar is defined in terms of itself, the grammar is said to be circular. We will assume that the attributes belonging to a particular instance of a grammar sym-bol are located in a block of storage associated with the occurrence of that symbol within a parse tree. A semantic tree is a parse tree augmented with these blocks of storage. Each sym-bol in a parse and the symbol's associated storage will be called a node for the remainder of this paper. 2

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...