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

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

On Mon, Nov 08, 2004 at 02:21:23PM +0100, GREGORY DYKE wrote:
> I have talked to the kind folks who are post-grads in the lab
> where the compiler course was given. They have never heard of PEG
> parsers 

That's hardly surprising, but they may want to look into them; it's
a very elegant formalism.

> and don't understand the problem:
> 
> rp-notation is not LL(1). This is clear. (well, it is LL1, but you
> can't easily generate the tree from it). 
> 
> rp-notation is however extremely simple to parse with a stack.
> They say that if PEG is LL(inf) in theory, why can't it do shift
> reduction like yacc? (I havn't looked into this, so I have no
> clue...)

I have no idea what shift reduction is.

I could easily solve the problem by attaching code to the
productions, which is what I think they are saying, but I'm trying
to keep the grammar as general as possible, i.e. not tied to any
particular parser generator or language.

Yacc is LR, btw; totally different case.

> > I have come up with a version that has no internal grammar at
> > all (i.e. is purely iterative), but that is not much more
> > satisfying. It is:
> > 
> > rp-expression <- operand / operand operand (operator operand /
> > operand operator)* operator
> 
> I see nothing wrong with this. 

Except that it's wrong.

> In fact, here is a demonstration of the proof of this grammar:

Which is interesting, since people have provided counter-examples,
such as:

1 2 3 + + + 4 5 +

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