Translation of if then else in compiler grammar

Question

...
IF LP assignment-expression RP marker statement {
    backpatch($3.tlist,$5.instr);
    $$.nextList = mergeList($3.flist,$6.nextList);
}
|IF LP assignment-expression RP marker statement ELSE Next statement {
    backpatch($3.tlist,$5.instr);
    backpatch($3.flist,$8.instr);
    YYSTYPE::BackpatchList *temp = mergeList($6.nextList,$8.nextList);
    $$.nextList = mergeList(temp,$9.nextList);
} 
...

Assignment-expression is any assignment expression that is possible using the C operators =, +=, -=, *=, /=.

LP = (
RP = )

marker and Next are both EMPTY rule

The problem with above grammar rule and implementation is that it can't generate correct code when expression is as

bool a;
if(a){
  printf("hi");
}
else{
  prinf("die");
}

It expects that assignment-expression must contain relop or OR or AND to generate correct code . Since in this case we do comparison for relop same case apply to OR and AND.

But as in above code doesn't contain any thing out of this , So it's unable to generate correct code. The correct code can be generated by using following rule but this leads to two reduce-reduce conflict .

  ...
  IF LP assignment-expression {
     if($3.flist == NULL && $3.tlist == NULL)
       ...
      } RP marker statement {
            ...
  }
  |IF LP assignment-expression{
    if($3.flist == NULL && $3.tlist == NULL)
    ...
    } RP marker statement ELSE Next statement {
      ...
  } 
  ...

What are the modification I should do in the grammar rule so that it will work as expected ?

I tried IF ELSE grammar rule from here as well as from dragon book but unable to solve this . Whole grammar can be found here Github

I've used flex bison some years ago and remember this kind of situation. I think the solution is to use start conditions in lexer for introducing different rules. The sintax with my old flex-bison is sligtly different. I hope this can help. — Mel Viso Martinez, Apr 09 '15 at 17:17

score 1 · Answer 1 · edited Feb 22 '20 at 12:42

1

It looks like your grammar has an incorrect definition of expression.

An assignment expression is only one of many non-terminals that should be able to reduce to an expression. For an if/then/else construction you generally need to allow any expression to occur between the parens. Your first example, as you point out, is perfectly valid C but doesn't contain an assignment.

In your grammar, you have this line:

/*Expression list**/
expression:
assignment-expression{}
|expression COMMA assignment-expression{}
;

However, an expression should be able to have more than assignment-expressions. Not being terribly familiar with yacc/bison, I would guess you need to change this to something like the following:

/*Expression **/
expression:
assignment-expression{}
|logical-OR-expression{}
|logical-AND-expression{}
|inclusive-OR-expression{}
|exclusive-OR-expression{}
|inclusive-AND-expression{}
|equality-expression{}
|relational-expression{}
|additive-expression{}
|multiplicative-expression{}
|exponentiation-expression{}
|unary-expression{}
|postfix-expression{}
|primary-expression{}
|expression COMMA expression{}
;

I can't really validate that this is going to work for you, and it may be imperfect, but hopefully you get the idea. Each different type of expression needs to be able to reduce to an expression. You have something very similar for statement earlier in your grammar, so this should hopefully make sense.

It might be helpful to do some reading or watch some tutorials on how LR grammars work.

edited Feb 22 '20 at 12:42

Cœur

37,241
25
195
267

answered Apr 09 '15 at 17:17

seanmk

1,934
15
28

I have taken grammar from C programming by Dennis Ritchie . – sonus21 Apr 09 '15 at 17:20
I don't have K&R in front of me, though. If you'd like a more detailed answer, can you update your question with more of the relevant grammar? For example, all of the rules that reduce to `assignment_expression`? – seanmk Apr 09 '15 at 17:26
Right, I don't need to see the whole grammar. Let's just start with the rules where the left-hand-side is `assignment_expression`. – seanmk Apr 09 '15 at 17:28
https://github.com/sonun/3-Address-Code-For-subset-of-C-Programming-Language-Using-LEX-YACC/blob/master/yaccrule.y . – sonus21 Apr 09 '15 at 17:28
There is nothing special with your new grammar rule for `expression` if you look at assignment expression due to rule it automatically get's all these expression . – sonus21 Apr 10 '15 at 01:57
@sonukumar Sorry, but I don't see that in the grammar. I might just be unfamiliar with the exact syntax of Bison though, so maybe I'm looking in the wrong place. – seanmk Apr 10 '15 at 03:01
What's happen `E->E+T | T ; T-> ID | ( E ) | NUM ;` In this case `E` automatic gates `ID` and `NUM` and parenthesized expressions . Similar to this if you look carefully at grammar rule then you will find that it's get all grammar rules that you mentioned. – sonus21 Apr 10 '15 at 03:35

score 1 · Answer 2 · answered Apr 09 '15 at 22:33

In order to insert the mid-rule action, you need to left-factor; otherwise, the bison-generated parser cannot decide which of the two MRAs to reduce. (Even though they are presumably identical, bison doesn't know that.)

if_prefix: "if" '(' expression ')' { $$ = $3; /* Normalize the flist */ }
if: if_prefix marker statement { ... }
  | if_prefix marker statement "else" Next statement { ... }

(You could left factor differently; that's just one suggestion.)

Translation of if then else in compiler grammar

2 Answers2