AST creation in Bison

Question

I'm trying to create a scripting language using Bison and C and I'm wondering if I'm constructing the AST the right way. Here's the tree I'm trying to create:

+ 
└─ Steps
    └─ Step 1
    └─ Step 2
    ...
    └─ Step n

If that's not clear, I want to have a node that contains n steps. The grammar I have right now looks like this:

Steps:          { $$ = create_steps(); }    
    | Steps Step 
    ;

Step:
    IDENTIFIER  StepBody    { $$ = create_step($1); }

Where StepBody is parsed into a node like I expect it to be. In my code, I'm creating a linked list for steps to go into in create_steps(); but that doesn't seem like the best way to do this.

I think I should have a create_steps(node *inner_node); function that takes the output of all of the Step processing functions and adds them to an array, but I don't understand how I could achieve this.

Originally, I had Steps setup like this in Bison:

Steps:          
        | Steps Step { $$ = create_steps($Step); }  
        ;

but of course, that called create_steps every time a Step was found which is not what I'm going for. Plus, I got a warning for "empty rule for typed nonterminal, and no action" which is probably not good.

Brian Tompsett - 汤莱恩 Brian Tompsett - 汤莱恩 · Accepted Answer · 2015-10-06T19:17:15

Just get rid of the empty production (ε) in Steps:

Steps:  Step         { $$ = create_steps($1); }
        | Steps Step { $$ = create_steps($2); }  
        ;

.. and then the Step is appended to your growing tree. You can even pass on the growing tree this way:

Steps:  Step         { $$ = create_steps(NIL, $1); }
        | Steps Step { $$ = create_steps($1, $2); }  
        ;

This is so common in compiling (doing lists) that it occurs in most grammars.

AST creation in Bison

1 Answers