Actually, there are a *lot* of languages with support for sophisticated parsing built in -- Icon, Haskell, Ocaml, and Bigloo Scheme all come immediately to mind. I'm not wholly convinced that this will be a successful experiment, though. A quick look at the Apocalypse suggests that Perl 6 grammaras are going to implement a recursive-descent-with-backtracking parsing engine. This is pretty nice, but has the downside that writing rules with left-recursion can cause a loop and stack overflow. That's a real annoyance because eliminating all left-recursion can make a grammar much less natural to read. Haskell parser combinators and Ocaml's stream parsers are also LL(1), so this is obviously not a critical weakness. However, Bigloo's define-grammar form calculates an LALR(1) parser, and that makes writing grammars much easier.

I also didn't see much about error handling and reporting. This is a shame, because the great strength of recursive-descent is that it makes error reporting relatively easy to do. In fact, it is nearly the only parsing technique for which I would rather write an error reporting routine than have rabid werewolves rip out and devour my brains. Perl6 could definitely use a little bit of extra semantics for rules that lets you chain and build error messages, so that you can report something like.

    Parse error at line 50, column 6
    in rule tlf, in rule method, in rule expr, in rule phrase, in rule if.
    Found token "{", when expecting token "else".

(This is an example from the parser of the language I'm writing.) It's not impossible to roll your own, but it would be nice if there were some preexisting machinery to hook into.

Cool. Here's why I think that some compiler support is helpful.

In Ocaml, a parser is just a function defined with a slightly funny syntax, so I can use the normal exception-handling system to build errors, like so:

exception Parse_error of string list 

let rec if' = 
  try parser 
      [<'Kwd "if"; test = expr;
\t'Kwd "then"; cons = expr;
\t'Kwd "else"; alt = expr;
\t'Kwd "endif" >] -> If(test, cons, alt)
  with
    Parse_error msgs -> raise (Parse_error ("in rule if" :: msgs))
and ... (* code for parsing expressions here, etc. *)

Most of the time (like in this example), this works fine. It has one down side, though. Namely, if you call a parser for a subexpression in tail position, you should be able to match the stream without growing the stack (this is *exactly* why regular grammars only permit nonterminals in the rightmost position). However, the addition of the 'try...with' code ruins the tail recursion (because you need to push an exception handler onto the stack), and this means that you get linear stack growth.

Changing the space complexity of an algorithm to add error reporting is not a win. :( Fixing this means dropping the use of exceptions, converting the parser to a continuation-passing style, and doing all of the error-handling work manually by passing around failure continuations everywhere. OR -- the compiler writer can do a little bit of hackery that exploits the fact that he knows this is a grammar. Everything looks and smells the same to the user, except that it's all magically efficient. :)

It looks like my post last night didn't work, so I'll try again. You can email me at <neelk@alum.mit.edu>.

I don't know if I'll be able to come in July. I quit my job so I could spend some time hacking and preparing for a grad school application in the fall. As a result, I'm trying to cut back on my expenses to maximize my "hang time", so to speak. I'll check Amtrak, and post whether I can come to Philly on the Open Forum.