Treetop infinite recursion with negative rule

Question

I have the following treetop grammar:

grammar TestGrammar

    rule body
        text / expression
    end 

    rule text
        not_delimiter*
    end 

    rule expression
        delimiter text delimiter
    end 

    rule delimiter
        '$' 
    end 

    rule not_delimiter
        !delimiter
    end 

end

When I try to parse an expression, eg 'hello world $test$', the script goes in an infinite loop.
The problem seems to come from the not_delimiter rule, as when I remove it the expression get parsed.

What is the problem with this grammar?

Thanks in advance.

Answer 1

The problem seems to be where you are attempting to match:

rule text
    not_delimiter*
end

Since the * will also match nothing you have the possibility of matching [^$]*, which I think is what is causing the infinite loop.

Also, you need to match multiple bodies at the starting rule, otherwise it will return nil, since you will only ever match either a text rule or an expression rule but not both.

rule bodies
   body+
end

This will parse:

require 'treetop'
Treetop.load_from_string DATA.read

parser = TestGrammarParser.new

p parser.parse "hello world $test$"

__END__
grammar TestGrammar
   rule bodies
      body+
   end
   rule body
      expression / text
   end
   rule expression
      delimiter text delimiter
   end
   rule text
      not_delimiter+
   end
   rule not_delimiter
      [^$]
   end
   rule delimiter
      '$'
   end
end