Re: Forming an AST node for a sequence or list

Hans Aberg <haberg@matematik.su.se>
15 Jun 2004 01:00:31 -0400

          From comp.compilers

Related articles
Forming an AST node for a sequence or list jeff.lasslett@datataker.com.au (2004-06-09)
Re: Forming an AST node for a sequence or list rbates@southwind.net (Rodney M. Bates) (2004-06-12)
Re: Forming an AST node for a sequence or list TommyAtNumba-Tu.Com--not@yahoo.com (Tommy Thorn) (2004-06-14)
Re: Forming an AST node for a sequence or list jlasslett@optusnet.com.au (Jeff Lasslett) (2004-06-14)
Re: Forming an AST node for a sequence or list haberg@matematik.su.se (Hans Aberg) (2004-06-15)
| List of all articles for this month |

From: Hans Aberg <haberg@matematik.su.se>
Newsgroups: comp.compilers
Date: 15 Jun 2004 01:00:31 -0400
Organization: Compilers Central
References: 04-06-033
Keywords: analysis
Posted-Date: 15 Jun 2004 01:00:31 EDT

jeff.lasslett@datataker.com.au (Jeff Lasslett) wrote:


> I have a couple of grammar elements of the following form:
>
>A -> Ab | b ( or in yacc form A : A "b" | "b"; )
>
>I am planning to form strings matched by this type of rule into AST
>nodes that look like this (given the input string "bbb"):-
>
> A
> /|\
> b b b
>
>I plan on representing list of statements this way and also comma
>separated lists of function arguments.
>
>I have two questions.
>
>(1) Is this a reasonable form for the AST node representing the
>abovementioned sequences?


This is not a parse tree you have indicated above, but a semantic list
object that you want create. Thus, the answer of your question depends on
whether the tree above is correct for your particular implementation
purposes.


>(2) How do I write the semantic actions to acheive the desire tree
>shape?
>
>This is my guess. It isn't real code.
>
>A : A "b" {
> if ( $$ == NULL ) {
> /* Make a new A and attach new leaf b */
> $$ = makeNode( A_NODE, makeLeaf( $2 ) ) ;
> } else {
> /* 'A' already exists so just attach new leaf b */
> addChild( $$, makeleaf( $2 ) )
> }
> }
> | "b" {
> if ( $$ == NULL ) {
> $$ = makeNode( A_NODE, makeLeaf( $1 ) ) ;
> } else {
> addChild( $$, makeLeaf( $1 ) ) ;
> }
> }
> ;


You can't (in a typical LR parser) assume that $$ has a values before you
have assigned it one. Assuming that $$ will contain a copy of the tree you
are constructing, you merely write:
    A:
        | A "b" { $$ = $1.append_leaf($2); }
        | "b" { $$ = tree($1); }
    ;
The actual code will depend on which implementation language you are using:
For example, in C++, one easily make the code above work using classes with
suitable copy constructors. Under C, one will have to emulate those copy
constructors somehow.


    Hans Aberg



Post a followup to this message

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