Re: Abstract syntax tree grammars and generator tools

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 (declarative.com) 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

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