Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

A Method for the Construction of Dynamic, Lazy Evaluators for Functional Attribute Grammars

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

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 proprtional to the size of the semantic tree plus a small constant times the number of attributes. The algorithm is unique in that the space allocated for attributes is used to store evaluation information before and during evaluation. As a result, very little storage beyond that required for a semantic tree is required. Circularity is detected at run time, making the method suitable for use with circular grammars. The method may be used either to interpret attribute grammars direectly or to generate code for efficient evaluators.

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

Page 1 of 11

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

A Method for the Construction of Dynamic, Lazy Evaluators for 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 554m

TR 86-6

February 1986

Technical Report

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 proprtional to the size of the semantic tree plus a small constant times the number of attributes. The algorithm is unique in that the space allocated for attributes is used to store evaluation information before and during evaluation. As a result, very little storage beyond that required for a semantic tree is required. Circularity is detected at run time, making the method suitable for use with circular grammars. The method may be used either to interpret attribute grammars direectly or to generate code for efficient evaluators.

1.Introduction

A context free grammar is a tuple where N and T are dijoint of sets of symbols called the non terminal and terminal symbols of the grammar,

(Equation Omitted)

, is a distinguished start symbolc and P is a set of productions. Each production

(Equation Omitted)

is a sequence of symbols,

University of Minnesota Page 1 Dec 31, 1986

Page 2 of 11

A Method for the Construction of Dynamic, Lazy Evaluators for Functional Attribute Grammars

(Equation Omitted)

(Equation Omitted)

(Equation Omitted)

(Equation Omitted)

(Equation Omitted)

in production p.

An attribute grammar is a context free grammar,

(Equation Omitted)

where each of the non terminals in N has been augmented with a finite (and possibly empty) set of attributes, and each production in 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 wrring

(Equation Omitted)

. Each of the functions

(Equation Omitted)

is specified by the production

(Equation Omitted)

it is associated with,. An index, k specifying a particular instance of symbol

(Equation Omitted)

in the productin, 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 tghat production.

Each attribute may potentially be defined in two ways: 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 production

where

and

. We will use the notation

to denote the symbol

University of Minnesota Page 2 Dec 31, 1986

Page 3 of 11

A Method for the Construction of Dynamic...