On Tue, May 11, 2004 at 10:48:22AM -0400, Dan Sugalski wrote: : >Certainly some things won't be recursive-descent anyway (operator : >precedence). : : Oh, don't be too sure of that. :)
Oh, I think Allison can be quite sure of that. :-) In fact, I'd go so far as to say that it's almost impossible to do recursive descent when you allow for defining new operator precedence levels on the fly as Perl 6 does. : Operator precedence can be done in : a recdescent grammar straightforwardly enough. It's a bit longwinded, : but doable. Yes, of course, it *can* be done that way. The point is you don't *want* to do that part in recursive descent, because that's where most of the overhead goes, plunging down 24 or so levels of recursion on *every* term because of all the precedence levels. In contrast, operator precedence is an easily implemented bottom-up technique that works quite well for expressions. And you'll note that operator syntax is precisely where Perl 6 abandons rules and lets people define operators with precedence. So what we're aiming for is parsing the gross structure of the program down to the expression level by recursive descent, then switching to operator precedence for as long as it makes sense. It's pretty easy for operator precedence to tell when it should give up and return to the outer top-down parser. And, of course, terms that include blocks may end up recursing down into the top-down parser again. (As might macros with peculiar is_parsed rules.) : The difference in speeds between top-down and bottom-up : parsers run in the orders of magnitude, and there's not too much we : can do to make that faster. Certainly, which is why I've been advocating a hybrid approach from the getgo. We don't have to fall into the either/or fallacy here. Intentionally building in an operator precedence engine will take most of the performance pressure off of the recursive descent engine, and will naturally optimize between bottom-up and top-down without the programmer having to throw in cargo-cultish pragmas. Larry
