🚀 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.
Can someone enlighten me? Given an example of one, I probably could answer
this question affirmatively.

In the meantime, here is what may be a more satisfactory answer. I have
in front of me the definition of the compiler for occam. The
significant bits tell me that (=> is the `can compile to' relation)

(1) skip        => [Jump N,ins1,...,insN-1]
(2) let X=Y     => [Load Y,Store Y]
(3) if X then P else Q
		=> [Load X,Cond N1,ins1,...,insN1-1,Jump N2,ins'1,...,ins'N2-1]
(4) while X P   => [Load X,Cond N,ins1,...,insN-1,Jump -N]
(5) P;Q         => what you imagine

and it occurs to me that I can define a grammar which will interpret
the object code from this fragment of the compiler. The object code
forms a sequence of tokens, Jump N, ..., and the object code will be
a valid phrase of the grammar iff the occam program which compiled to
it should terminate. This seems to me to
say that I can express grammars which are computationally as complex
as one might wish, and which therefore must be more than LL.

The only proviso is that I'm going to define a CONTEXT-DEPENDENT
grammar. The context will be the current state of the machines memory
- all the values stored in the variables. Since this will be a finite
set for any given program, I'm sure that some bright spark will tell me
how I can do without it.

This is a spec as accepted by the utility (pre-cc):

T(mem) = <JUMP>\N )N>=0( ?*N T(mem)                        @mem    /*(1)skip*/
       | <LOAD>\Y <STORE>\X T(mem')                        @mem'   /*(2)let*/
       | <LOAD>\X <COND>\N1 {  )lookup(mem,X)( T(mem)      @mem    /*(3)if*/
			    | )!lookup(mem,X)( ?*N1 T(mem) @mem
			    }
       | while(mem)\mem'                                   @mem'   /*(4)while*/
       | <JUMP>\N )N<0(                                    @mem    /*stop*/

(in the above, on line (2), mem' stands for overwrite(mem,(X,lookup(mem,Y))),
and on line (4), it is the synthetic value returned from the while parse)
I had to introduce a stop on a negative jump. Negative jumps are only
put in the object code by the compiler at the end of the loop in a
while. I want a sub-parser to be able to scan the loop code once and then
stop. Because I'm lazy, I reuse the spec of T, having added the
otherwise harmless condition that a negative jump should be just eaten
and ignored. Then the stop happens because there is no recursion into a
T(foo) parse specified just to the right.

I have assumed that the lexer attachex the appropriate N, X, Y, etc.
synthetic values to the `tokens'.

while(mem)
       = ]onepass(mem)[\mem' while(mem')
       | <LOAD>\X <COND>\N )!lookup(mem,X)( ?*N T(mem)

onepass(mem)
       = <LOAD>\X <COND>\N )lookup(mem,X)( T(mem)

The ]P[ construction is `a phantom parse of P'. It checks whether P would
parse the coming tokens, but doesn't eat up any. It's used here to make
one pass over the loop body if the conditional test is OK, and then get
ready for another pass over the same code. I rely on the Jump -N at the
end of the loop body to stop the parse.

Any comments? I realize, BTW, that using the context has made things
easy for me. I could define a `Turing machine' grammar with far less
trouble, using the whole tape as the parameter. But the grammar here uses
only a finite data structure as its context.

Peter