Re: Forming an AST node for a sequence or list

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

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