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

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

On Tue, Nov 09, 2004 at 06:49:14AM +0100, Rapha?l Poss wrote:
> Le 7 nov. 04, ? 09:18, Robin Lee Powell a ?crit :
> >Lojban has a reverse polish (i.e. postfix math) mode built in.
> >
> >The ABNF form of this rule is:
> >
> >rp-expression = rp-operand rp-operand operator
> >
> >rp-operand = operand / rp-expression
> >
> >which does exactly what you'd expect.
> >
> >I can't figure out a way to convert this into a version without
> >left recursion.  I've got:
> >
> >rp-expression = operand rp-expression-tail
> >rp-expression-tail = rp-expression operator rp-expression-tail / ()
> >
> >(where () is the empty production), but I'm not at all certain
> >it's equivalent, and the parse trees it produces look very wrong
> >(i.e. not left recursive at all).
> >
> >Help?
> 
> (I assume from the ABNF grammar above that a RP expression has at
> least 2 operands and 1 operator)

*Excatly* 2 operands per operator.

> What about :
> 
> rp-expression = operand operand rp-tail
> rp-tail = operand rp-tail / operator

Umm, that's just:

rp-expression = operand operand+ operator

These are nested reverse polish notation expressions; very
different.

For example:

1 2 + 3 4 + +

is (1 + 2) + (3 + 4)

-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/