🚀 go-pugleaf

ptb@eng.cam.ac.uk (P.T. Breuer) writes:
>>
>>I don't mind admitting that I don't know what a non-LL language looks like.


>Thanks to Debora Weber-Wulff for offering a test case.
>The language { a^n b^n | n>=0 } apparently definitely has no LL grammar
>(but does have a LR(0) one) and is specifiable in pre-cc. But not all

No, Peter, the language I gave you was
{a^n b^n | n >=1} \cup [that's the LaTeX union operator] {a^n c^n | n >=1}
This is not LL because you have to get all the way down to the b's or
c's before you can decide which way you needed to go. In LR parsing,
we are constructing the reverse of a right-derivation, we shift a's
onto the stack until we see a b or a c, and they we *know* which
set of productions to use. 


>it's the basis of my claim that LR(0) languages are expressible.
How about a proof including the time and space complexities of
your system? I so enjoyed the strangesucc function, which has proved
to me that, yes, it is nice to express things with backtracking and no,
I do not want my systems to use it, because I prefer termination to
stack overflow.

-- 
Debora Weber-Wulff                       dww@inf.fu-berlin.de
Institut fuer Informatik                 +49 30 89691 124
Nestorstr. 8-9                           (INCLUDE "standard.disclaimer")
D-W-1000 Berlin 31                       (PRINTN (WITTY-MESSAGE TODAY))