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
