If the scanning stage pairs the tokens it returns with
their positions, then scanning can be done once before
parsing begins. I've done this with a parser implemented
with parser combinators, these combinators then decide
whether or not to accept a token based on which token
it is and how far it is indented. I think this means
the grammar being parsed is a context sensitive one,
since the state of the parser is represented by more than
just a single stack. We need a stack telling us what to
do next, and a stack of indentation levels, although
the way in which these stacks grow and shrink is related
they could not be replaced by a single stack, so the
grammar is not context free.
Now that I write this, I think that we could combine these
stacks as a stack of stacks, although this isn't how I did it.
I don't think this satisfies the requirements for a context free
grammar (CFG) but I don't have a definition to hand at the moment.
Mike
Simon Marlow wrote:
> I believe you're right in that a true two-phase implementation of
> the Haskell grammar is impossible. This is consistent with Haskell's
> policy of making life easy for programmers and hard for compiler
> writers :)
