Browse Prior Art Database

Attribute Coding Technique

IP.com Disclosure Number: IPCOM000087736D
Original Publication Date: 1977-Mar-01
Included in the Prior Art Database: 2005-Mar-03
Document File: 4 page(s) / 118K

Publishing Venue

IBM

Related People

Goldmann, HF: AUTHOR [+4]

Abstract

Generally, the compiler writer associates with each identifier-encountered constraints for the actual attributes of the identifier. These constraints are determined by the syntactic context in which the identifier occurs. They are coded in some manner and entered into the dictionary at compile time. All identifier entries are compared and, in the case of a mismatch, an error message is generated or the actual attributes are evaluated, whereby default conventions have to be used in some cases.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 54% of the total text.

Page 1 of 4

Attribute Coding Technique

Generally, the compiler writer associates with each identifier-encountered constraints for the actual attributes of the identifier. These constraints are determined by the syntactic context in which the identifier occurs. They are coded in some manner and entered into the dictionary at compile time. All identifier entries are compared and, in the case of a mismatch, an error message is generated or the actual attributes are evaluated, whereby default conventions have to be used in some cases.

The actions of coding and validation can be rendered more effective by the attribute coding scheme described, which allows the representation or declarative and contextual attributes by means of bit strings. Consistency checking is performed by the AND instructions throughout the bit strings.

Assumption The basis of an attribute representation technique, as suggested, is a BNF grammar for attribute expressions. As will be seen, the choice of grammar determines the range of the attribute sets that may be represented by the coding scheme.

Example: attr : :=scalar I array I proc scalar : :=arith I logical

arith : :=real I integer

array : :=dim scalar

dim : :=dim dim I dim

proc : :=no-parm-spec I no-parms I parm-spec

parm-spec: :=parm-spec attr I attr

Contextual Attribute Constraints
The compiler writer can express the constraints by classes of trees:
(a) One element class (complete derivation tree). Examples are shown in Figs. 1A and 1B.
(b) Class of alternatives. This is a derivation tree in which some subtrees are replaced by a selection of possible alternatives at the indicated positions.

Examples are shown in Figs. 2A to 2D.

Constraints Coding Scheme

Let T be the smallest (infinite) tree, so that each derivation tree of the grammar is a subtree of T - disregarding the node names - assuming the following additional conditions: - The root of T is also the root of the subtree. - If e is a common edge with a left brother edge e', then e' is also a common edge. An example of tree T is shown in Fig. 3.

Each node of T is labelled by bit string templates whose length is the maximum of the number of alternatives of all nonterminals that may occur at this node.

In the example, only attr and dim can occur at nodes 9, 10, 13, ..., so that the length is 3; only terminals can occur at 8, 36, so that the length is zero; scalar, array or proc can occur in 2, so that the maximum is 3.

1

Page 2 of 4

By means of an arbitrary, but fixed, ordering of all templates, an infinite bit string template is created whose parts correspond 1:1 to the templates attached to the nodes of T. The attribute constraints can be represented in two steps: (a) Starting with the derivation tree, the constraints are en...