CODEWITHSUNDEEP
parsingif-statementcompiler-constructionwhile-loopbison
tech_s
tech_s

Reputation: 11

Bison parser problems with if and while

I'm trying to write a compiler for C using flex-bison and GCC. Lexer and parser have both been created, which I believe is an OK-OK rule. The problem lies in the conditions and loops, i.e. if-else statements and simple while loops. I have come to the understanding that when we execute the lexer and the parser an entire static AST is created, hence the conditional values are not changed.

To be more clearer my if-else will execute but both the statements for the IF and ELSE are executed... I tried adding %prec to check for the precedence, but it didn't make any changes.

My if-else code is:

statement:  IF  '(' conditions ')' '{'statements '}' %prec IF { if($3==1) $$=$6;}
        |   IF  '(' conditions ')' '{'statements '}' ELSE '{' statements '}' {
                int *p,*s,*e;
                p=&($3);
                s= &($6);
                e=&($10);
                if(*p==1) {
                    $$=*s;
                    printf("%d",*s);
                } else {
                    $$=*e;
                    printf("%d",*e);
                };
            }
        |   WHILE '(' conditions ')' '{' statements '}' { while($3==1) $$=$6; }
        ;

conditions: condition  AND  condition   {if($1==1 && $3==1) $$=1; else $$=0;}
        |   condition  OR   condition   {if($1==1 || $3==1) $$=1; else $$=0;}
        |   condition            
        ;


condition:  expression CMPEQ expression {if($1==$3) $$=1; else $$=0;}
        |   expression GT   expression  {if($1>$3)  $$=1; else $$=0;}
        |   expression LT   expression  {if($1<$3)  $$=1; else $$=0;}  
        |   expression NEQ  expression  {if($1!=$3) $$=1; else $$=0;} 
        |   expression GTEQ expression  {if($1>=$3) $$=1; else $$=0;}
        |   expression LTEQ expression  {if($1<=$3) $$=1; else $$=0;}    
        |   expression
        ;

I'm sorry for lengthening the question, but I did read about other interpreters and compilers being added to the lexer and parser to make the loops work, yet I only have information on lexer and parser, even a small idea of those could really help a lot.

If you need the entire flex and bison file, ill post it :). Thank you in advance :).

Upvotes: 1

Views: 1496

Answers (1)

rici
rici

Reputation: 241861

That's not a compiler. It's an interpreter.

In other words, you're not compiling the input into a program you can execute later. You're interpreting it immediately. And you're not building an AST, either. You're just directly executing the code.

The most important thing about the actions in bison productions is that they are executed when the production is reduced, which is when the entire production has been recognized [Note 1]. Consequently, the actions are executed after any actions for non-terminals which make up the the production. In particular, when the action for if condition then on_true else if_false is executed, the actions for condition, on_true and on_false have already been executed. And the actions for on_true and on_false will evaluate those expressions.

So the if will correctly return the appropriate value, but only after evaluating both alternatives, which is generally undesirable.

In order to avoid this, you need to defer the evaluation of any expression until it is actually needed, which means evaluating top-down, which means you actually need to build the AST so that you can evaluate it. (Or you could generate, for example, three-address code and evaluate that.)

It is actually possible to interpret if expressions, and other short-circuiting operators, correctly in a bottom-down evaluator by making use of mid-rule actions and maintaining a global evaluation flag. But that won't work for loops, because the loop needs to evaluate the loop body several times, which means that it needs to have a parsed but unevaluated representation of the loop body. In any event, the bookkeeping needed to maintain the "evaluate-or-skip" state correctly is error-prone and opaque.

[1] Bison also allows mid-rule actions, which are evaluated more or less when they are encountered, since they are actually translated into empty non-terminals. But that alone won't save the naïve design.

Upvotes: 2

Related Questions