🚀 go-pugleaf

>In article <1992Nov3.160104.5305@odin.diku.dk> torbenm@diku.dk
>(Torben AEgidius Mogensen) writes:
>>ptb@prg.ox.ac.uk (Peter Breuer) writes:
>>
>>>There is also a paper by Jonathan Bowen and myself (which I think has
>>>[...]
>>
>>Does this parser generator handle non-LL languages?
>
>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
LR(0) grammars are acceptable for precc, because LR(0) presentations can be
left recursive. I think all LR(0) languages are expressible, though,
if you choose the right grammar presentation.

two specifications:

(1) not using attributes

@ S = AB $

@ AB = a AB b
@    | a b

(2) using attributes

@ S = as\n b*n $

@ as = a as\n @n+1
     | a      @1

The latter is the more powerful technique, since it is computationally
complete, as I showed by specifying an interpreter for occam object
code. Admittedly, that was the worst possible example to choose! But
it's the basis of my claim that LR(0) languages are expressible.

If you want the functional programming interpretations, then (using the
operator notation from graham hutton's soon-to-be JFP paper - see this
thread)

(1)   S = AB $then EOL

      AB = (a $then AB $then b) $alt (a $then b)

(2)   S = as $into (n -> bs(n) $then EOL)
      
      as = (a $then as $into (n -> success(n+1)))  $alt (a $then success 1)

      bs(n) = b $then bs(n-1) , n>1
            = b               , otherwise

Has anyone done a speed comparison of the pure combinator approach (aka
Wadler (1985), Fairbairn (1987), etc.)  versus combinators which build new
state machines from old, Using cross products of the state spaces, and
so on?

Peter