Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!linus!philabs!cmcl2!seismo!lll-crg!lll-lcc!qantel!ihnp4!stolaf!umn-cs!herndon From: herndon@umn-cs.UUCP Newsgroups: net.lang Subject: Attribute Grammar Tool Message-ID: <7500006@umn-cs.UUCP> Date: Sat, 22-Feb-86 17:41:00 EST Article-I.D.: umn-cs.7500006 Posted: Sat Feb 22 17:41:00 1986 Date-Received: Wed, 26-Feb-86 07:37:44 EST Lines: 68 Nf-ID: #N:umn-cs:7500006:000:3649 Nf-From: umn-cs!herndon Feb 22 16:41:00 1986 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!herndon