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

[GREGORY DYKE <lojban-out@lojban.org>]

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 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...)

In short, they say, a parser is as simple as

while(token=!ENDOFRP) {
switch (token) 
case first(operand): push(operand());
case first(operator): push(operator(),pop(),pop());  
} //first is the set of terminals which start a    //non-terminal
}
if (size()!=1) raise Exception();

return pop();

and if PEG can't do this as well as yacc can, then we're in for trouble...

> 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. In fact, here is a demonstration of the proof of this grammar:

* = 0
we know we have content of stack = 2. we know we have an operator at the end, so content of the stack will reduce to one.

so it works for *=0

assume it works for *=n (this means we have reduced to 2 on the stack just before that last operator)
, show that it works for *=n+1

case a) we added an operator operand:
operator reduces the stack to 1
operand goes on the stack. so size()==2

case b) we added an operand operator
operand brings stack size to 3
operator reduces stack size to 2

qed.

Greg
Greg