How to parse an if statement in bison

Question

I'm using bison to build a compiler for a simple language. Here's part of the grammar:

stmt: IF '(' exp ')' stmt{
        if(exp) $$=$5;
      }
      |PRINT ';' {
        cout<<"hi";
       }
;

exp: true|false
;

I encountered a problem in parsing this if statement: Say I have this code:

if(false) print;

"hi" will be printed anyway because the stmt->PRINT is parsed before stmt-> IF (exp) stmt. What can I do? (I'm new to bison and to compilation so feel free to correct errors in my question).

Answer 1

That's natural. You're parsing the print statement, so the 'cout' gets executed. What you're looking to do is to create some sort of byte code, where you store a print instruction. This print instruction can then be combined with the if-expression to form an if-statement-instruction.

Off the top of my head, I can't remember the exact statements in Bison (you'll need to look into the documentation), but you generally want to define a type for your value stack, typically a union of structs, something like this (there's a bison command for it, though, which will make it the type for the value stack).

union {
 int type;
 struct {
  int type; // must always be first, this is a union
  union stmt *stmt; // conditional stmt to execute
  union expr *expr; // expression to evaluate
 } if_stmt;
 struct {
  int type;
 } print_stmt;
} stmt;

Which will allow you to put a rule in your grammar, something like this

stmt: IF '(' expr ')' stmt   { $$.type = IF_STMT; $$.if_stmt.expr = copy ($3); $$.if_stmt.stmt = copy ($5); }

and so on (there might be an off-by-one error in there, can't remember if the $s start at 0 or 1). You'll need to implement the copy function yourself to manage memory allocations, bison will only provide a stack for values. In the end you'll have a tree (commonly referred to as a syntax tree, I believe), which you can run through, for nodes with type IF_STMT, evalute if_stmt.expr, and if it returns true, evaluate if_stmt.stmt, and so on.

Then when you're finished parsing your language, you can 'execute' your byte code, when you hit an if-statement, evaluate the expression, if true (which it isn't), execute the statement as outlined above, and then when you hit a print-instruction (which you won't as the expression is false), you print your 'hi', and you have the result you're looking for (that is, nothing gets printed).

That's pretty much how you need to go about it. You cannot (easily) do conditional execution while parsing with bison.