Simple Arithmetic Grammar with Treetop Infinitely Recursing

Question

I'm trying to write a simple calculation grammar with Treetop. To simplify my example for this question, I'm only using variables, numbers and the + operator. I'd like to be able to write expressions like this:

• A
• 1
• A+B
• A+1
• A+1+B

Here's my grammar:

grammar Calculation

  rule expression
    (plus / number / variable)
  end

  rule plus
    expression "+" expression
  end

  rule number
    '-'? [0-9]+ ('.' [0-9]+)?
  end

  rule variable
    [A-Za-z0-9]+
  end
end

When I run this, it infinitely recurses. After googling for a while, I think my problem has something to do with left-recursion, but I'm new to parsers and I don't really understand what that means. Could somebody explain why my particular example isn't working and how I can fix it?

Answer 1

To avoid the left recursion, you can break up the expression rule into two parts like below:

grammar Calculation

  rule expression
    plus / symbol
  end

  rule symbol
     number / variable
   end

  rule plus
    symbol "+" expression
  end

  rule number
    '-'? [0-9]+ ('.' [0-9]+)?
  end

  rule variable
    [A-Za-z0-9]+
  end
end