Prev: UPDATE: TkTable 2.9 and MouseWheel bindings ...
Next: Regexp for tokens
From: Helmut Giese on 24 Jun 2008 14:07
Hello out there,
I have a parser for C (the version from http://wiki.tcl.tk/3906) which
has been lying in a corner for a couple of years.
Picking it up again I thought maybe ASTs could come in handy - and
here are 2 questions:
a) Where can I read up on using ASTs? I am aware of the intro at
wikipedia and followed some of the links from there, but I would like
to find some real world usage examples
b) I stumbled over tcllib's grammar_me: From http://wiki.tcl.tk/15511:
grammar::me::util - Manipulation and conversion of
abstract syntax trees (ASTs) between various
representations.
However, in the docs I found I didn't understand a word - is there
some background / additional material somewhere?

Any insight will be greatly appreciated.
Best regards
Helmut Giese
From: Neil Madden on 24 Jun 2008 15:54
Helmut Giese wrote:
> Hello out there,
> I have a parser for C (the version from http://wiki.tcl.tk/3906) which
> has been lying in a corner for a couple of years.
> Picking it up again I thought maybe ASTs could come in handy - and
> here are 2 questions:
> a) Where can I read up on using ASTs? I am aware of the intro at
> wikipedia and followed some of the links from there, but I would like
> to find some real world usage examples

Most compiler books will have a section on ASTs. An AST is simply a tree
data structure where the nodes match different elements in the abstract
syntax of the language. You can interpret a language directly during
parsing -- most parser frameworks have some facility for associating
"semantic actions" that are called when different types of entities are
parsed. However, you then tie the processing to the parsing. With an
AST, you instead build up a tree corresponding to the abstract syntax
and then different processors can work on that (e.g. interpreter,
compiler, type checker, pretty printer, etc).

See http://wiki.tcl.tk/16695 for a simple AST definition plus an
interpreter that operates directly as a function over the AST. I leave
out parsing from concrete syntax -> AST, but I guess you know how to do
that already.

If you use an OO representation of the AST then the Visitor pattern is
very useful -- you can implement interpreters, type checkers, pretty
printers, etc, all via that one mechanism. The equivalent for a
list-based datatype (like the one I use above) is a "fold" method, with
callback functions for each type of node that might be encountered --
better yet, an ensemble. (I'll update that page to show an example of this).

> b) I stumbled over tcllib's grammar_me: From http://wiki.tcl.tk/15511:
> grammar::me::util - Manipulation and conversion of
> abstract syntax trees (ASTs) between various
> representations.
> However, in the docs I found I didn't understand a word - is there
> some background / additional material somewhere?

I've not used the grammer_me stuff yet, so I can't help there.

-- Neil
From: Neil Madden on 24 Jun 2008 20:16
Neil Madden wrote:
....
> See http://wiki.tcl.tk/16695 for a simple AST definition plus an
> interpreter that operates directly as a function over the AST. I leave
> out parsing from concrete syntax -> AST, but I guess you know how to do
> that already.
>
> If you use an OO representation of the AST then the Visitor pattern is
> very useful -- you can implement interpreters, type checkers, pretty
> printers, etc, all via that one mechanism. The equivalent for a
> list-based datatype (like the one I use above) is a "fold" method, with
> callback functions for each type of node that might be encountered --
> better yet, an ensemble. (I'll update that page to show an example of
> this).
....

Page updated to show several examples plus even a simple parser from
concrete syntax -> AST!

-- Neil
From: Helmut Giese on 25 Jun 2008 10:05
Hi Neil,
>Most compiler books will have a section on ASTs. An AST is simply a tree
>data structure where the nodes match different elements in the abstract
>syntax of the language. You can interpret a language directly during
>parsing -- most parser frameworks have some facility for associating
>"semantic actions" that are called when different types of entities are
>parsed. However, you then tie the processing to the parsing. With an
>AST, you instead build up a tree corresponding to the abstract syntax
>and then different processors can work on that (e.g. interpreter,
>compiler, type checker, pretty printer, etc).
that's a very concise description of the advantages of using ASTs,
thank you.

>See http://wiki.tcl.tk/16695 for a simple AST definition plus an
>interpreter that operates directly as a function over the AST. I leave
>out parsing from concrete syntax -> AST, but I guess you know how to do
>that already.
>
>If you use an OO representation of the AST then the Visitor pattern is
>very useful -- you can implement interpreters, type checkers, pretty
>printers, etc, all via that one mechanism. The equivalent for a
>list-based datatype (like the one I use above) is a "fold" method, with
>callback functions for each type of node that might be encountered --
>better yet, an ensemble. (I'll update that page to show an example of this).
This gives me something to study.
Thanks a lot for the explanation and the link and best regards
Helmut Giese
 | 
Pages: 1
Prev: UPDATE: TkTable 2.9 and MouseWheel bindings ...
Next: Regexp for tokens