librelist archives

Struggling with recursive rules causing Stack Level Too Deep

From:

Chris Corbyn

Date:

2011-11-04 @ 09:29

Hi All,

I'm familiar with parsers like yacc, that allow a rule to refer back to 
itself, which is really useful for cases where an expression, can in turn 
be composed of itself, with the idea being that logically each 
sub-expression reduces down to a single value at some point during 
reduction and recursion is therefore finite.

I'm having difficulty getting my head around how Parslet wants such 
expressions to be constructed, however.  I've set myself a simple problem 
in order to understand this and think I'm getting somewhere, but still not
quite there.

The grammar supports two operations:

  1. Simple infix addition like 1 + 2
  2. An add() function, that accepts a variable number of arguments, like 
add(1, 2, 3)

Standing by themselves with integer operands, these work fine.  But 
anywhere an integer appears, you should be able to use another expression 
in its place:

  add(1, add(2, 3))

I got the above to work fine, which gave me hope.

Then I got this to work, provided "+" only accepted integers, not sub-expressions:

  add(1 + 2, add(3, 4))

But I can't get this to work (which is confusing, since it's not the only 
rule that includes recursion):

  add(add(1, 2) + add(3, 4), add(5, 6))

Allowing add() to be nested didn't cause Stack Level too deep, but as soon
as I try to change "+" to use "expr" for its operands, Parslet can't 
handle the recursion.  How can I change this parser to avoid that 
recursion?


https://gist.github.com/1338851

Code included here, though no doubt badly formatted too:

require "parslet"

class MiniP < Parslet::Parser
  rule(:wsp)    { match("\\s").repeat(1) }
  rule(:wsp?)   { wsp.maybe }

  rule(:t_int)  { match("[0-9]").repeat(1).as(:int) }

  # this is causing Stack Level Too Deep
  rule(:sum)    { expr.as(:left) >> wsp? >> str("+") >> wsp? >> expr.as(:right) }

  # but this is fine
  rule(:arg_list) { expr >> wsp? >> (str(",") >> wsp? >> expr).repeat }
  rule(:add_call) { str("add") >> wsp? >> str("(") >> wsp? >> 
arg_list.as(:args) >> wsp? >> str(")") }

  rule(:expr)      { sum.as(:sum) | add_call.as(:add_call) | t_int }

  root(:expr)
end

class MiniT < Parslet::Transform
  rule(:int => simple(:int)) { |dict| Integer(dict[:int]) }
  rule(:args => sequence(:args)) { |dict| dict[:args] }
  rule(:sum => { :left => simple(:left), :right => simple(:right) }) { 
|dict| dict[:left] + dict[:right] }
  rule(:add_call => subtree(:args)) { |dict| dict[:args].reduce(&:+) }
end

expr = "add(add(4, 5), add(1, 1 + add(0, 1)))"
p MiniP.new.parse(expr) # debug
p MiniT.new.apply(MiniP.new.parse(expr))

Cheers,

Chris

Hei Chris, 

You have to think about what moves the parse forward, just as if you were 
coding it by hand. The two relevant functions would look something like 
this (in your grammar): 

def parse_sum
  parse_expr or return false
  parse_wsp
  parse('+') or return false
  parse_wsp
  parse_expr
end

def parse_expr
  return true if parse_sum
  return true if parse_add_call 
  parse_t_int
end

(Assuming that parse functions return a boolean indicating their success.)
So what you have there is direct mutual recursion between expr and sum. 
And put like this (in code), it is easy to see, isn't it?

I guess your sum doesn't really allow any kind of expression in front, but
rather something that can be an element of a sum, like integers or 
function calls. That avoids the recursion. 

Here's something that works, maybe that helps you along as well: 
https://gist.github.com/1339032

regards, 
kaspar

Hi Kaspar,

Thanks for the quick response, splitting up expr into a rule to break the 
recursion solves it.  All clear now.

Vieni per caso dalla Svizzera?  (Sorry if not, I just guessed Florian 
knows you from Switzerland because of the name… I'm in Melbourne too).

Cheers,

Chris

On 04/11/2011, at 9:11 PM, Kaspar Schiess wrote:

> Hei Chris, 
> 
> You have to think about what moves the parse forward, just as if you 
were coding it by hand. The two relevant functions would look something 
like this (in your grammar): 
> 
> def parse_sum
>  parse_expr or return false
>  parse_wsp
>  parse('+') or return false
>  parse_wsp
>  parse_expr
> end
> 
> def parse_expr
>  return true if parse_sum
>  return true if parse_add_call 
>  parse_t_int
> end
> 
> (Assuming that parse functions return a boolean indicating their 
success.) So what you have there is direct mutual recursion between expr 
and sum. And put like this (in code), it is easy to see, isn't it?
> 
> I guess your sum doesn't really allow any kind of expression in front, 
but rather something that can be an element of a sum, like integers or 
function calls. That avoids the recursion. 
> 
> Here's something that works, maybe that helps you along as well: 
https://gist.github.com/1339032
> 
> regards, 
> kaspar
> 

On 04.11.11 11:43, Chris Corbyn wrote:
> Vieni per caso dalla Svizzera?  (Sorry if not, I just guessed Florian 
knows you from Switzerland because of the name… I'm in Melbourne too).

Yes, I live and work in Switzerland; but I only speak two of the other 
three languages ;) I understand Italian though, so if you don't mind me 
answering in French, we can still converse. ;)

kaspar