That's something I've been thinking about, too. There are a lot of
"interesting" languages that cannot be described by context free
grammars (such as {empty, 012, 001122, 000111222, ...} but very simple
enhancements do make them easy to recognize. In the case of the
"indentation grammar", then the (one) stack in a push-down automaton is
basically used up keeping track of the indentation level. But you don't
need a whole stack to keep track of indntation level, just a register
that can be used to track the current level.

BTW, I'm new to this list. I haven't done that much with Perl recently,
but of late, I've become a lot more interested in the language. I
recently picked ot the Perl 6/Parrot book from O'Reilly but had really
meant to finish reading the book before jumping in. It's just that this
topic is too interesting!

--- Larry Wall <[EMAIL PROTECTED]> wrote:

> On Thu, Sep 08, 2005 at 08:37:21AM -0700, Dave Whipp wrote:
> : If I want to parse a language that is sensitive to whitespace 
> : indentation (e.g. Python, Haskell), how do I do it using P6
> rules/grammars?
> : 
> : The way I'd usually handle it is to have a lexer that examines
> leading 
> : whitespace and converts it into "indent" and "unindent" tokens. The
> : grammer can then use these tokens in the same way that it would any
> : other block-delimiter.
> This is the multi-pass approach, which even in Perl 6 is still
> certainly one way to do it.  Or actually, two ways, one of which is
> to use source filters to mung the input text, and the other way of
> which is to make one lexer pass to transform into a list or tree of
> tokens, and then do a list/tree transformation on that.  Given that
> tree transformation is something that a number of us are currently
> thinking about for various other reasons, I suspect that can be made
> to work pretty well.  But we will have to describe how rule matching
> can be extended to lists and trees, and what happens when you
> intermix
> text elements with non-textual objects.  But essentially, just think
> what it would take to match against the tree of match objects
> returned
> by a prior match instead of against a string.
> : This requires a stateful lexer, because to work out the number of 
> : "unindent" tokens on a line, it needs to know what the indentation 
> : positions are. How would I write a P6 rule that defines <indent>
> and 
> : <unindent> tokens? Alternatively (if a different approach is
> needed) how 
> : would I use P6 to parse such a language?
> I can think of two other approaches as well.  One would be to allow
> "pushback" on the queued input so that when we hit a line transition,
> we can immediately analyze the leading whitespace and replace it
> conceptually with the appropriate number of indent/unindent objects.
> It's not yet clear whether that is a good approach.  It might be
> rather inefficient to splice faked up objects into the middle of the
> input stream.  On the other hand, we don't actually have to splice
> the input, only pretend that we did.  And certainly, the Perl 5 lexer
> makes heavy use of this kind of we'll-fake-the-next-N-tokens queueing
> (though I actually botched the Perl 5 implementation of it by making
> it a stack instead of a queue).
> My final idea is that you can treat it as a fancy kind of lookbehind
> assertion, provided you have some landmark that will stop the
> normal analysis from running over the newline boundary.  With the
> other approaches, you have a precomputed positive unindent token
> to function as a "stopper", but with this approach, the only thing
> you can depend on is the newline itself.  So when you first hit a
> newline, you don't progress beyond it, but instead look ahead at the
> indentation of the following line and queue up the right number of
> indent/unindent objects in your own data structure (as well as
> pushing
> or popping your stack of current indents appropriately so that the
> new indent is on top).  Then as long as there are queued up objects,
> the newline doesn't report itself as a newline, but as the next
> object,
> until you run out, and then the newline allows itself to be skipped,
> along with the subsequent whitespace.  (The difference between this
> and the previous approach is that you're not relying on the rules
> engine to keep track of the queueing for you.)
> The very fact that I had to use a phrase like "positive unindent
> token"
> says a lot about why indentation as syntax is problematic in general.
> Larry

Gregory Woodhouse  <[EMAIL PROTECTED]>

"Without the requirement of mathematical aesthetics a great many discoveries 
would not have been made."

-- Albert Einstein

Reply via email to