herndon@umn-cs.UUCP (02/23/86)
To persons interested in attribute grammars:
Over the last two years I've developed an attribute grammar
translator generator which will soon be available for release
from Media Distribution at the University of Minnesota.
The generator accepts an attribute grammar, which contains
a context-free grammar, sets of regular expressions for describing
a lexical scanner, attribute declarations, and sets of attribute
definitions, and builds a translator capable of recognizing the
specified language and generating the specified translation(s).
It has a number of advantages over any other similar systems that
I know of. These include:
1) Only one file is required to specify translation(s)
2) The parsers are generated by Yacc
3) The lexical scanners are generated by Lex
4) Attribute Evaluation uses Jalili's algorithm [SIGPLAN
Notices, Sep. 1983]. Evaluation is entirely lazy, conditional
expressions with proper termination semantics are supported,
and there are no ordering constraints such as those required by
stack evaluators. Circularity is detected at run-time.
5) The data types supported include strings, integers, and
maps. Maps are a class of functional data types that can
be used for performing symbol table operations. Strings
and maps are internally heaped and shared, so strings can
get long (often hundreds of thousands of characters) without
consuming inordinate amounts of memory.
6) The system has an applicative semantics, not a procedural
semantics. Since the language is side-effect free,
translator specifications are easy to understand.
7) The system is written primarily in itself. (Admittedly,
this is true of several other systems.) A few side-effect-
free "helper" functions and the run-time library are
written in C.
8) Output attributes can be directed to the standard output,
the standard error, and to files.
9) Debugging switches may be set from the generated translators'
command lines, allowing users to observe translators reducing
grammar rules and reducing input strings to terminals.
On the minus side, the translator generation process is slow
(5-60 minutes on VAXen and Suns). The translators also require
a fair amount of memory, since semantic trees are stored in memory.
The generated translators are reasonably fast, though, and have
been used in classes at the University of Minnesota for more than
a year on Sun workstations with 1 and 2 megabytes of memory.
Also on the minus side, the generator does not check grammars for
well-formedness or circularity. Both of these are detected by the
translators at run-time and cause translation-time errors. Finally,
the generator is not a production effort, and as such comes without
warranty or guarantees.
The generator is useful as an aid in teaching students basic
compiler theory (terminals, non-terminals, regular expressions,
and so on are all very immediate concepts with the generator), and
for creating ascii-to-ascii translators of various sorts, such as
front-ends to user-hostile programs, language-to-intermediate-
code translators, etc. Users unfamiliar with the generator but
familiar with compiler theory have created new, useful translators
in as little as a week or so. The most difficult aspect of using
the system is usually understanding and resolving Yacc's
shift/reduce and reduce/reduce conflicts.
The user's manual is available and I can mail interested persons
a copy. If there is enough interest, I could also post a copy of
the manualto this or some other appropriate newsgroup.
Robert Herndon
...!{stolaf|ihnp4}!umn-cs!herndonherndon@umn-cs.UUCP (03/02/86)
I've received quite a large number of responses expressing interest in the attribute grammar translator generator. I am responding to all the requests that I can, but I've gotten a few responses which did not include return addresses. The generator is now available from U of M Media Distribution. They may be telephoned at: (612) 376-8340 or written to at: University of Minnesota Media Distribution Box 734 Mayo 420 Delaware St. SE Minneapolis, MN 55455 Ask for the AG Attribute Grammar Translator Generator System (or the "Kodiyak" translator generator). The translator consists of roughly 5000 lines of AG and C source code. Distribution copies are available on 9-track 1600 BPI magtape in tar format for Sun workstations and VAXen. Binary and intermediate files in Yacc, Lex, and C are also included, as are the machine-readable AG manual and a sample AG program. Robert Herndon ...!ihnp4!umn-cs!herndon herndon.umn-cs@csnet-relay.ARPA Dept. of Computer Science University of Minnesota 136 Lind Hall, 207 Church St. SE Minneapolis, MN 55455