On Thu, May 13, 2004 at 10:26:32AM -0500, Abhijit A. Mahabal wrote: : : On Wed, 12 May 2004, Larry Wall wrote: : : > 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, : : I see a terminology issue looming here. Er, what is recdescent? The dragon : book and Parse::RecDescent do not seem to use the same defn. According to : aho/ullman "A parser that uses a set of recursive procedures to recognize : its input with no backtracking is called a recursive descent parser". (p : 180). Parse::RecDescent does not shy away from backtracking, and in : Aho/Ullman's eyes it would be a top-down parser, but not recdescent.
Well, I think the dragon book does violence to the language here. In plain terms, a top-down parser "descends" by definition, and typically uses recursion to do so, even if that recursion is emulated. Whether it also supports backtracking is somewhat orthogonal. <sermon> As with many CS offerings from the Modern era, the dragon book unconsciously tends to try to classify implementations into "pure" and "impure", so one feels discouraged from using techniques like backtracking or hybrid compilers. In this Postmodern era, we tend to value whatever tickles our fancy, and it happens that computers are getting fast enough that parsing doesn't always have to be optimized to death for speed. Instead, we can occasionally optimize for other things like fun and flexibility. And that's what Perl 6 is aiming for. </sermon> : As usual, I may have missed something. I am not sure which of the two you : mean, but I feel it is the Parse::RecDescent sense because it is powerful : and easier for users (and does not require recomputing the parsing table), : but it is also (much?) slower. We mean it in the more general sense. Whether a grammar can be parsed with or without backtracking depends on how you write the grammar, unless you happen to have a language with no "dangling syntax". We try to avoid dangling syntax in Perl, but don't always succeed. Nevertheless, if the grammar *usually* doesn't need to backtrack, it can effectively be just about as fast as a non-backtracking grammar. Plus there are tricks you can do short of analyzing all the rules into a state diagram. For instance, the design of Perl 6 rules allows you to pass in a parameter that could supply a list of "stoppers" to a subrule so it knows where to stop, just as you might do in a standard recursive descent parser. : Or, of course, you may mean both. When a program uses a lot of evals then : it may be worthwhile when compiling the program to calculate the : parse-tables and other no-backtracking book-keeping so that the eval's : happen faster at runtime. Hmm, well, there's something to be said for discouraging people from using C<eval> by making it slow. :-) Larry
