Re: Abstract syntax tree grammars and generator tools

David Chase <>
17 Mar 2003 00:00:36 -0500

          From comp.compilers

Related articles
Combinator/Monadic parsing tools. (Thaddeus L Olczyk) (2003-02-24)
Re: Combinator/Monadic parsing tools. peteg@cse.unsw.EDU.AU (Peter Gammie) (2003-03-09)
Abstract syntax tree grammars and generator tools (Ralph P. Boland) (2003-03-14)
Re: Abstract syntax tree grammars and generator tools (2003-03-16)
Re: Abstract syntax tree grammars and generator tools (David Chase) (2003-03-17)
Re: Abstract syntax tree grammars and generator tools (2003-03-22)
| List of all articles for this month |

From: David Chase <>
Newsgroups: comp.compilers
Date: 17 Mar 2003 00:00:36 -0500
Organization: Little or none
References: 03-02-148 03-03-009 03-03-048
Keywords: parse, attribute
Posted-Date: 17 Mar 2003 00:00:36 EST

Ralph P. Boland wrote:

>Is there such a thing as an abstract syntax tree grammar
>and the generator tools to process them?
>What I want is a grammar that:
>1) specifies the abstract syntax trees of a language.
> This probably means additional things such as types of the nodes.
>2) supports some standard attribute evaluation and semantic actions such as
> add this variable name and its type to the symbol table.

Would an attribute grammar fit your needs? I see "attribute" and
"grammar" appearing in different parts of your post, but you never put
the two words together.

Even if this is not a perfect fit for your needs, it might be "good
enough", and the advantage is that it is a long-studied problem that
has canned solutions available. For instance, you can get an
Attribute Grammar Evaluator Generator called "linguist" from
Declarative Systems ( that will process inputs that
look like this:

stmts ::= stmt.; ญญ -- empty semantics
expr ::= primary.{} -- ญญ also empty semantics
stmts ::= stmts1 stmt.
stmts.LEN = stmts1.LEN + 1;
stmts.DEFS = unionLbl(stmts1.DEFS, stmt.DEFS);
stmts1.ENV, stmt.ENV = stmts.ENV;

That's a simple example; linguist supports things like functional
attributes. The attribute grammar evaluator generator deals with
order of evaluation and how many times a node needs to be "visited" to
ensure that all of its attributes are evaluated.

Disclaimer: I have no financial interest in Declarative Systems, but I
am friend of the guy (Rodney Farrow) who runs it. However, if your
time is worth anything at all, I would look into Linguist. It is not
a toy -- it has supported AGs for VHDL and C++ (compared to those,
everything else is easy).

David Chase

Post a followup to this message

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