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?

The treetop examples contain an arithmetic grammar, see my example at github.com/cjheath/treetop/blob/master/examples/lambda_calculus/… — cliffordheath
@rici Thanks for the link! That helps illustrate the problem, and I think I see some ways that could be applied in this particular case. — LandonSchropp
@cliffordheath Thanks for the link! Is there a link available to documentation on head and tail? — LandonSchropp
head and tail are just node labels, they can be anything, but this is my idiom for list-like structures (one or more). Labels are in the normal documentation for Treetop syntax. — cliffordheath

Josh Voigts Josh Voigts · Accepted Answer · 2019-12-02T14:37:28

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

Simple Arithmetic Grammar with Treetop Infinitely Recursing

1 Answers