compiler-constructiongrammarsablecc

Problem with reverse derivation with a simple sum and multiply grammar

I am having some trouble understanding how to, using a bottom up parser and for example, the input string 1 + 2 * 3, go from the "bottom" to the "top".

Here's the grammar I'm using (I'd say it's correct as it's the one found in Crafting a Compiler)

E = E plus T
  | T;

T = T times integer
  | integer;

This is my reverse derivation:

int(1)
T(1)
E(1)
E(1) plus int(2)
E(1) plus T(2)
E(1) plus E(2)
E(1) plus E(2) times int(3)
E(1) plus E(2) times E(3) <-- can't do anything here

The problem is that every time I get an integer as input, it will get automatically "transformed" in a E.

I'm pretty positive that the given grammar is correct. I've also tried it out in sablecc with some input strings(making use of a Pretty Printer visitor I've made) and they all yield the correct result.

That way, I know the problem is in me, not the grammar itself. What am I doing wrong, then?

Thanks!

Solution

  • The shift-reduce conflict is the most common type of conflict found in grammars. In your case, the T(2) could be reduced to E(2), or the times could be shifted. By default, most parser generators will prefer to shift rather than reduce. But they will still reduce the T(1) to E(1), because they know that there's no point shifting a plus after a T.