Fixing the grammar

The test that was failing was this one:

  def test_left_compound # "((500*20)+16)"
  tokens = [LeftParenToken.new(), LeftParenToken.new(), IntegerToken.new(500), MultiplicationToken.new(), IntegerToken.new(20), RightParenToken.new(), AdditionToken.new(), IntegerToken.new(16), RightParenToken.new()]
  assert(tokens_are_valid(tokens))
end

Why? Well, do what I did - try to build the expression ((500*20)+16) by hand using the rules. Here they are again:

E => (E) | nT T => +E | -E | * E | /E | ε

Give up yet? It can't be done! Also, for the same reason, this grammar cannot generate (1)+2. The simple fact is that I botched the job of making the grammar LL(1) compatible. So how to fix it? Well its simple really, especially when you take the (1)+2 example. Seems to me that a slight tweak to the production rules for E is necessary:

E => (E)T | nT

Great! Lets modify the lookup table accordingly:

lookup[:E][LeftParenToken] = [:lpar, :E, :rpar, :T]

The tests all pass! Now I can turn my attention to using the same algorithm for building the tree. However I have some more reading to do before I can proceed. Come on CS164 lectures notes, don't let me down!