🚀 go-pugleaf

In article <NVT8YHL@math.fu-berlin.de> dww@inf.fu-berlin.de writes:
>>Thanks to Debora Weber-Wulff for offering a test case.
>>The language { a^n b^n | n>=0 } apparently definitely has no LL grammar
>
>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. 

Duh. Sorry Debora. I apologised to you privately for this very public
mistake and misattribution of mine, and I'll do it again now.

I must have had my brain cell go on holiday that day. Yes, you did tell
me that it was the union language that was the LR--LL example, and I
unforgivably misread your statement.

However, the union is still expressible by top-down functional parsers:

S = AB $ | AC $
AB = a AB b
   | a b
AC = a AC c
   | a c

and always will be provided that the functional `union of two parsers'
operator induces an equivalent union in the corresponding sets of
accepted parses.

To be completely honest, that is not always the case. All the
combinator semantics I know of induce a subset of the union operator
in general. It just so happens that in this particular case, all the
usual combinator semantics give spot-on results. The general `subset of the
union' claim boils down to having to consider what happens with \bot,
(and I'll be more specific in private correspondence).

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

This is a good point. My  implementation (pre-cc) of functional parsers
is in straight C and doesn't use garbage collection. Nevertheless, it
can still blow the top off the C stack if it gets into a left recursive
loop (i.e., if you give a left recursive spec). Even without an unending
loop recursion, it can sometimes demand a lot of space. Each call from the
combinator-kernel costs about 20 bytes, so a C stack of 64K can accommodate
3000 nested calls. You then have to prove that the parse spec gives rise to
a parser that can never go more than 3K calls deep when evaluating a valid
(or invalid) phrase of the language.

That's possible, though. If the language has the form 
   A | B
then you have to prove that it takes at most 3K-1 calls to decide A and
at most 3K-1 calls to decide accept/reject by B, because it's going to
cost one more call to do the `alt' combinator.

When it comes to recursive specs, then I'm afraid we're going to need
expressions for how many calls it takes to decide all phrases of length n,
or possibly all calls of length n starting with `a', etc., depending on
the structure of the spec, but I hope that one can do it for most
reasonable specs. I haven't sat down to work out a calculus - but my
original `example' of a grammar that acted as an abstract
interpretation of occam object code, accepting only terminating codes,
showed that there is certainly no algorithmic method that can treat all the
specs expressible by functional top-down parsers and give close-fitting
results.

Peter