[lojban] Re: Computer grammar question: non-left recursive RPN?

[Robin Lee Powell <lojban-out@lojban.org>]

On Tue, Nov 09, 2004 at 09:45:49AM +0100, Jo l'apache wrote:
> 
> rp-expression = rp-operand rp-operand operator
> rp-operand = operand / rp-expression
> 
> here is the version without left-recursion
> 
> rp-expression = rp-operand rp-operand operator
> rp-operand    = rp-operand' rp-operand
> rp-operand'   = () | rp-operand operator

Nope.

rp-operand    = rp-operand' rp-operand

which can be expanded to:

rp-operand    = ( () | rp-operand operator) rp-operand

which can be expanded to:

rp-operand    = rp-operand | rp-operand operator rp-operand

which is left recursive in both cases.

-Robin

-- 
http://www.digitalkingdom.org/~rlpowell/ *** http://www.lojban.org/
Reason #237 To Learn Lojban: "Homonyms: Their Grate!"
Proud Supporter of the Singularity Institute - http://singinst.org/