1

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!

devoured elysium
  • 101,373
  • 131
  • 340
  • 557

1 Answers1

1

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.

Neil
  • 54,642
  • 8
  • 60
  • 72
  • I think I get your point, but I'm still not very sure of what happens with the parser. Does the parser, for any given state, try out all the possible reverse-derivations and if there are at least two that give valid derivations, raise a shift-reduce error, while if there is only one valid it doesn't raise a problem? – devoured elysium Apr 09 '11 at 17:04
  • I'm not sure what you mean by try out all the possible reverse-derivations. After you shift the int, you know you need to reduce to T. But you then use lookahead; if you see a times then you shift, otherwise you reduce to E. And you need to use lookahead here too; you expect to see either a plus (when you shift) or an EOF (when you reduce which in this case means terminate). (A more advanced parser would flag an error if it saw an int after a T, rather than reducing to E and then noticing the error.) – Neil Apr 10 '11 at 19:41