Re: Anyone got a yacc template generator ? (Chris F Clark)
22 May 1997 22:32:17 -0400

          From comp.compilers

Related articles
Anyone got a yacc template generator ? (Gianni Mariani) (1997-05-19)
Re: Anyone got a yacc template generator ? (1997-05-22)
Re: Anyone got a yacc template generator ? (1997-05-22)
Re: Anyone got a yacc template generator ? (Basim Kadhim) (1997-05-22)
| List of all articles for this month |

From: (Chris F Clark)
Newsgroups: comp.compilers
Date: 22 May 1997 22:32:17 -0400
Organization: The World Public Access UNIX, Brookline, MA
References: 97-05-227
Keywords: yacc, tools

> After the bazillionth time I've written an application using yacc I've
> come to the brink of writing a grammer -> application template
> generator and I thought before I go spend time on this effort, I would
> like to know if one is available. I have not come across one in my
> time so I may be tracking new territory.

You are talking about either one of two things. Either a wrapper
around the grammar that gets things set up or a set of data structures
to represent the parsed grammar.

Our solution to the wrapper problem was to embed all of the skeleton
code in what the oo people call an "application framework". That is a
set of cooperating classes which hook together to provide the
skeleton. In that framework there is one file, we call it
yy_main.cxx, which instantiates the interconnected classes. For most
applications, it is a simple matter of cloning that file (often
requiring no modifications at all, just copying it to the target
directory). Oh, yes, you also need to copy the makefile also, and in
the makefile change the name of the grammar in the makefile to match
the grammar for your application, and also the name of the resulting
executable, and add in any additional source files. (We have thought
about adding a generator for that, even though it is essentially
trivial. Having a generator would help in the Visual/Wizard world,
where people expect to point, click, and have a skeleton application
with little or no effort, not even the copying of a file.) By the
way, the point of making it a framework is that each supporting class
has several variations with different semantics, space/time tradeoffs,
or other distinquishing characteristics and that the application is
built by plug-and-play (or the Chinese menu approach of one from
column a, two from column b).

To the second problem of building classes, enums, et al to represent
the internal representation of a grammar, we have a solution also.
Our "dialect" of yacc, supports a "construct" declaration, which
allows the user to specify in the grammar what kinds of classes the
user wants built for each token or non-terminal. The generator than
writes the set of C++ classes which correspond to those specifications
and adds the code to the lexer and parser to construct the objects of
the classes. The end result is that the user can basically concieve
of the writing a grammar as a tool to build a specific tree (actually
the declarations allow building of arbitrary graphs, but trees are the
most common use) with traversal (and computation) functions for
accessing it after the parse is complete. It is common to think of
the resulting tree as an "abstract syntax tree" (and thus we call our
classes AST classes).

Of course, the idea is not unique. Our first inspiration came from
Steve Johnson's paper "Yacc meets C++". Another tool which did
essentially the same thing is "Meta-tool" which ATT marketed for a
while (and still might). PCCTS can build "lispy" trees from grammar
annotations. Attribute grammars solve some of the same problems, and
the Cocktail toolkit has an AST generator as a foundation for its
attribute grammars. FNC2 has a nice model for defining recursive
structures. I believe the tool OX builds an attribute grammar
framework around YACC.

The one thing which I think distinguishes our implementation from most
of the alternatives, is that we allow a fairly fine-tuned control over
the structure being built. The classes we generate are specifically
tailored to their own use in the grammar, with minimal overhead. We
only require that the class have a field to hold a type discriminator,
so that we can use the classes to implement the type discrimination
our parse stack needs. Other than that, the classes are totally tuned
to their use, having only the exact linking fields needed to make the
connections the user wants made and the exact value fields the user
has specified. (In addition, we take the OO paradigm very seriously
and define everything in terms of user specified class hierarchies.)

In contrast, the PCCTS structure has a left and down field in every
node. The Cocktail structure maps closely to the structure of the
grammar, using the variant record as the underlying idiom. Steve
Johnson's structure was close to the Cocktail model. (You can, of
course, get Yacc++ to generate either of those models.) I don't know
the details of the other alternatives.

Hope this helps,

Chris Clark Internet :
Compiler Resources, Inc. CompuServe : 74252,1375
3 Proctor Street voice : (508) 435-5016
Hopkinton, MA 01748 USA fax : (508) 435-4847 (24 hours)

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.