Recursive expression problem

[caio ariede]

I have the following code:

call <- "call" spaces value;

op <- value "+" value;
value <- op / decimal / variable;

That is proposed to match:

call 1
call x
call 1+1 or
call 1+x or
call 1+1+1

But it's causing an infinite recursion.

The expected parsing is:

call 1+1 // "call" <op> // <value: 1> + <value: 1> // <decimal: 1> +
<decimal: 1>

But I think it's taking:

call 1+1 // "call" <op> // <value: 1+1> ...recursive

What I'm doing wrong?

Caio Ariede
http://caioariede.com/

[Sean Cribbs]

Neotoma and PEGs in general tend not to support left-recursion. Your
rule needs to reduce the leftmost term, while you could allow the
right to expand. The "arithmetic" parser has good examples of this.
Here's how I'd refactor your grammar:

call <- "call" spaces value;

value <- op / primitive;
op <- primitive "+" value / primitive;
primitive <- decimal / variable;

Sean

[caio ariede]

Nice, it worked.

Thanks!

Caio Ariede
http://caioariede.com/

[mikhailfranco]

Sean Cribbs wrote:
> Neotoma and PEGs in general tend not to support left-recursion.

"Packrat Parsers Can Support Left Recursion"
http://www.viewpointsresearch.org/pdf/tr2007002_packrat.pdf

It would be 'a piece of work' to implement, but worth it.

Mik

[Sean Cribbs]

Mik,

Thanks for the link. I was aware of that paper, but hadn't gotten
reading it closely yet. In many cases, you can factor left-recursion
into right-recursion anyway, so it's a little low on the list of todos.

Sean