Re: Abstract syntax tree grammars and generator tools

"Ralph P. Boland" <rpboland@math.uwaterloo.ca> wrote
> Is there such a thing as an abstract syntax tree grammar
> and the generator tools to process them?


The Spirit Parser framework (http://spirit.sourceforge.net) uses C++
expression templates to let you express your grammar in C++ code with
a syntax that is very reminescent of EBNF, augmented with semantic
rules. Parser generation is actually performed in terms of template
instantiation at compile time: in a sense, the grammar is the parser.


The framework provides a specialized parsing driver that builds an AST
from your grammar, where nodes can be parameterized to carry the
"payload" you desire.


A 'symbols' construct is available that allows you to both recognize
elements already inserted in its symbol table and insert a newly
recognised token.


[...]
> 1) There is no need to place attributes or semantic actions in the
> grammar for the language.
> I think such attributes and semantic actions should be in the
> abstract syntax tree grammar (if not later in the compile process).


This is not true for Spirit. However, the way this is achieved allows
you to express your grammar in a relatively uncluttered way. On the
other hand you are not forced to express both the language syntax and
the AST attributes and semantic rules in the same grammar. You might
define a two stage process where the language parser generates a
stream of tokens that are parsed by the AST generating parser (the
process becomes three stage if you plan to separate the lexical
analyzer from the parser proper).


> 2) Based on the parse syntax grammar and the abstract syntax grammar
> much work can now be done automatically (and thus programming language
> independantly) by the abstract syntax tree builder generated by the
> abstract syntax tree builder generator tool.
> This reduces the amount of programming work needed to be done by
> the compiler writer.


I believe Spirit provides different ways to achieve similar languages.
The fact that your grammar specification is actually a fragment of C++
code makes it possible to combine 'micro-parsers' either at compile
time in the form of template arguments or at runtime, e.g. by using
inheritance based polymorphism. It is certainly very easy to factor
together the common elements of different languages.


I think I'd better stop here rather than try and explain if and how
Spirit can help you in the cases you exemplified. If C++ is an
acceptable choice for an implementation language I definitely think
you should check Spirit out.


Cheers,
Nicola Musatti

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