Ranga.Vemuri@UC.EDU (Dr. Ranga R. Vemuri) (11/20/90)
Some time ago I have posted a request to this news group
for info on compiler-generators which can handle attributed grammars.
Since I received several requested for a summary of responses, here it
goes. Thanks to everyone who replied.
- Ranga
PS: Note that I have edited the responses to save space.
_________________________________________________
Dr. Ranga Vemuri ranga@uceng.uc.edu
Laboratory for Digital Design Environments (513)-556-4784
M.L. 30, Dept. Electrical & Computer Engineering (513)-556-4769
University of Cincinnati, Cincinnati, OH 45221, USA
_________________________________________________
I have used the GAG system from University of Karlsruhe, W. Germany. They
sell licenses for educational use at US$200. You will probably need their
parser generator PGS, which also sells for US$200. Josef Grosch, one of the
main implementors of these systems, told me he was working on another system
for attribute grammars called AG.
_______________
try to contact prof.Cormack at University of Waterloo. His email is:
gvcormack@watdragon.waterloo.edu
________________
There is a special issue on Compilers, Languages coming in mid- 1991
in IEEE Transactions on Computers.
_________________
MetaTool(tm) Specification-Driven Tool Builder is a tool that
generates text-to-text translators of any type (i.e., you can use it as a
compiler generator). MetaTool SDTB supports attribute grammars -- any number
of attributes can be associated with any type of parse tree node. The
MetaTool SDTB run-time library contains a number of functions and operations
that allow you to perform parse tree traversals that evaluate the attributes.
MetaTool does not formalize the notion of synthesized or inherited
attributes. You must construct the evaluators from the operations provided
in the run-time library, and the way you do this defines the attribute type.
These operations make it trivial to build evaluators for synthesized,
inherited and hybrid attributes.
MetaTool SDTB is an AT&T product that has been in internal use for a
couple of years, and that has just been announced for external license (see
recent article in comp.newprod, and my recent article in comp.compilers).
The cost is not cheap.
_________________
I don't know the current status of their system, but MetaWare's TWS was
enhanced to support affix grammars for SofTech several years ago. The major
limitation in the implementation is that the parser skeleton is written in
Ada and the parse tables produced are in the form of Ada aggregates.
__________________
I know of OPTRAN from the Universitat des Saarlandes in Germany (Wilhelm and
Moncke show up as authors on a lot of their papers) and the Incremental
Compiler Compiler from MCC (TR PP-412-86 by Michael Tiemann).
__________________
Get the Eli tech report. (ftp binary mode) from
boulder.colorado.edu 128.138.240.1 in ~ftp/tmp/eli.paper.me.Z
It is about 53k. The eli system is currently available via tape
and soon will be available via ftp.
For more info mail compiler@boulder.colorado.edu
__________________
MetaWare sells the Translator Writing System, a commercial version of Dr.
Frank DeRemer and Dr. Tom Pennello's work in parser generators and error
recovery. It is arguably one of the best parser generators in the world. It
supports attribute grammars. Normally it sells for $6000 for a single user
licence, but I believe there are some steep university discounts. If you are
interested, contact our sales department. 2161 Delaware Ave. Santa Cruz, Ca.
95060 (408) 429-6382 or sales@metaware.com.
__________________
See PCCTS, the Purdue Compiler-Construction Tool Set, as announced as a
Public Domain Beta release some time ago in this very newsgroup. It's
available via annon. ftp, etc.
__________________
This may not sound at first glance like what you're interested in, but you
might want to check out a Prolog interpreter/compiler. It's relatively easy
in Prolog to prototype a compiler, writing the attribute grammer including
actions as Prolog clauses. I've done this experimentally, although not on a
production basis. Compiled Prolog may even offer reasonable performance.
Cheap Prologs for UNIX are available (e.g. C-Prolog), albeit (when I used
them) with pretty poor development and debugging tools. Sorry, I can't cite a
reference on it...
__________________
TOOLBOX(1) GMD-Forschungsstelle-Karlsruhe TOOLBOX(1)
NAME
toolbox - tool box for compiler construction
DESCRIPTION
Toolbox is a set of program generators or compiler
construction tools for nearly all phases of a compiler. The
compiler construction tools support the automatic generation
of compilers for imperative programming languages. The
design goals for this tool box were practical usability,
significantly reduced construction effort for compilers, and
high quality of the generated compilers. Especially with
respect to efficiency the tools are competitive to
programming by hand. Currently the tools can generate
compiler modules in the target languages C and Modula-2.
First realistic applications demonstrate the excellent
performance of the tools and show that the tools allow the
construction of production quality compilers.
TOOLS
Rex generator for lexical analyzers
Lalr LALR(1) parser generator
Ell LL(1) parser generator
Ast generator for abstract syntax trees
Ag generator for attribute evaluators
Estra transformation of abstract syntax trees
Beg generator for code generators
Reuse library of reusable modules
IMPLEMENTATION LANGUAGES
Modula-2 or C
TARGET LANGUAGES
Modula-2 or C
PLATFORMS
DEC Station / ULTRIX
VAX / ULTRIX or BSD UNIX 4.2
SUN 3 or SUN 4 / SunOS
PCS Cadmus / MUNIX
DISTRIBUTION
Medium: DC 300 A data cartridge or TK 50 in tar format
source programs in Modula-2 as well as in C
binaries for SUN 3
documentation in troff- und Postscript-format
example specifications
CONTACT
J. Grosch, H. Emmelmann
GMD Forschungsstelle an der Universitaet Karlsruhe
Vincenz-Priesznitz-Str. 1
D-7500 Karlsruhe
Germany
Tel: +721-6622-26/15
E-Mail: grosch@gmdka.uucp, emmel@karlsruhe.gmd.dbp.de
PRICE
Source licence excluding Beg: 500 DM or 250 US $
Source licence for Beg : 500 DM or 250 US $
Rex, Lalr, Ell, Ast, and Ag - Compiler Construction Tools
=========================================================
Rex (Regular EXpression tool) is a scanner generator whose
specifications are based on regular expressions and arbitrary
semantic actions written in one of the target languages C or
Modula-2. As scanners sometimes have to consider the context to
unambiguously recognize a token the right context can be speci-
fied by an additional regular expression and the left context can
be handled by so-called start states. The generated scanners
automatically compute the line and column position of the tokens
and offer an efficient mechanism to normalize identifiers and
keywords to upper or lower case letters. The scanners are table-
driven and run at a speed of 180,000 to 195,000 lines per minute
on a MC 68020 processor.
Lalr is a LALR(1) parser generator accepting grammars writ-
ten in extended BNF notation which may be augmented by semantic
actions expressed by statements of the target language. The gen-
erator provides a mechanism for S-attribution, that is syn-
thesized attributes can be computed during parsing. In case of
LR-conflicts unlike other tools Lalr provides not only informa-
tion about an internal state consisting of a set of items but it
prints a derivation tree which is much more useful to analyze the
problem. Conflicts can be resolved by specifying precedence and
associativity of operators and productions. The generated parsers
include automatic error recovery, error messages, and error
repair. The parsers are table-driven and run at a speed of
560,000 lines per minute. Currently parsers can be generated in
the target languages C and Modula-2.
Ell is a LL(1) parser generator accepting the same specifi-
cation language as Lalr except that the grammars must obey the
LL(1) property. It is possible to evaluate an L-attribution
during parsing. The generated parsers include automatic error
recovery, error messages, and error repair like Lalr. The
parsers are implemented following the recursive descent method
and reach a speed of 900,000 lines per minute. The possible tar-
get languages are again C and Modula-2.
Ast - A Generator for Abstract Syntax Trees
- generates abstract data types (program modules) to handle trees
- the trees may be attributed
- besides trees graphs are handled as well
- nodes may be associated with arbitrary many attributes of arbitrary type
- specifications are based on extended context-free grammars
- common notation for concrete and abstract syntax
- as well as for attributed trees and graphs
- an extension mechanism provides single inheritance
- trees are stored as linked records
- generates efficient program modules
- generates modules in Modula-2 or C
- provides many tree operations (procedures):
- node constructors combine aggregate notation and storage management
- ascii graph reader and writer
- binary graph reader and writer
- reversal of lists
- top down and bottom up traversal
- interactive graph browser
Ag - An Attribute Evaluator Generator
- processes ordered attribute grammars (OAGs)
- processes higher order attribute grammars (HAGs)
- operates on abstract syntax
- is based on tree modules generated by Ast
- the tree structure is fully known
- terminals and nonterminals may have arbitrary many attributes
- attributes can have any target language type
- allows tree-valued attributes
- differentiates input and output attributes
- allows attributes local to rules
- allows to eliminate chain rules
- offers an extension mechanism (single inheritance)
- attributes are denoted by unique selector names
instead of nonterminal names with subscripts
- attribute computations are expressed in the target language
- attribute computations are written in a functional style
- attribute computations can call external functions
- non-functional statements and side-effects are possible
- allows to write compact, modular, and readable specifications
- AGs can consist of several modules
- the context-free grammar is specified only once
- checks an AG for completeness of the attribute computations
- checks for unused attributes
- checks an AG for the classes SNC, DNC, OAG, LAG, and SAG
- the evaluators are directly coded using recursive procedures
- generates efficient evaluators
- generates evaluators in Modula-2 (or C)
A comparison of the above tools with the corresponding UNIX tools shows that
significant improvements in terms of error handling as well as efficiency
have been achieved: Rex generated scanners are 4 times faster than those of
LEX. Lalr generated parsers are 2-3 times faster than those of YACC. Ell
generated parsers are 4 times faster than those of YACC. The input languages
of the tools are improvements of the LEX and YACC inputs. The tools also
understand LEX and YACC syntax with the help of preprocessors. They have
been tested by generating scanners and parsers for e. g. Pascal, Modula,
Oberon, Ada and found stable.
The tools have been developed using our own Modula-2 compiler called MOCKA on
a MC 68020 based UNIX workstation. They have been ported to the SUN
workstation and been compiled successfully using the SUN Modula-2 compiler.
They also run on VAX/BSD UNIX and VAX/ULTRIX machines. This should assure a
reasonable level of portability.
References:
1. J. Grosch, `Generators for High-Speed Front-Ends', LNCS,
371, 81-92 (Oct. 1988), Springer Verlag.
2. W. M. Waite, J. Grosch and F. W. Schroeer, `Three Compiler
Specifications', GMD-Studie Nr. 166, GMD Forschungsstelle an
der Universitaet Karlsruhe, Aug. 1989.
3. J. Grosch, `Efficient Generation of Lexical Analysers',
Software-Practice & Experience, 19, 1089-1103 (Nov. 1989).
________________________
--
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.