Search code examples
bisonyacc

bison grammar execution order

I have a grammar like this: 

A : a B {int i = 0; printf("%d",i);};

B: and b B {i++; printf("%d",i);}
 | %empty 
 ;

input a and b and b and b

output : 1230

my question is : how to change the order of execution to have 0123

Solution

  • Use left recursion instead of right recursion.

    Bison executes actions exactly in the way you tell it to. Each non-terminal's action is executed exactly as soon as the non-terminal is completed.

    If you use a right-recursive rule:

    B: "and" b B

    then the outer B's action, which prints the semantic value of b, executes after the inner B's action, which prints the semantic values of the bs which follow.

    A much more natural way to write that grammar, which has the further advantage of producing correct associativity, is:

    A: a
 | A "and" b

    Moreover, the actions in that grammar will execute left-to-right, because the inner A's action is executed as soon as it is complete, which is before the associated b has even been seen.