All~
If I recall my dragon book correctly, shift reduce parsers (which are what most compilers use) can actually parse a larger class of grammars then recursive descent parsers which can only parse LL(k) grammars. So that is another good reason to have it. Perhaps Perl 6 grammars should provide an is parsed trait that allows one to specify which type of parsing to use, then we could dictate that the default behavior for parsing or perl itself is shift reduce parsing rather than recursive descent.
At least this way people know when they are making a trade off between, speed and other things.
Matt
Dan Sugalski wrote:
At 1:24 PM -0500 5/10/04, Allison Randal wrote:
Dan Sugalski wrote:
I'm not so sure about that. (Not that it won't be replaced, but that it needs the grammar engine) I'm pretty sure that grammars as Larry's defined 'em are recursive-descent, and if that's true then I've this really nasty feeling we're going to find it insufficiently fast to parse perl. Could be wrong, but even if we pick up two orders of magnitude in speed over Parse::RecDescent things'll still be significantly more sluggish than the current perl 5 parser.
(OTOH, if the grammar engine's not required to be recursive-descent that makes things rather faster, which is fine with me :)
That's a question with multiple layers of answers. :)
The abstraction we need to meet is: a) everything that can be done in the parser that ships with Perl 6 can be done in Perl 6; and b) it is possible to change the way Perl 6 is parsed within Perl 6 code (by loading a custom grammar module, for example).
Right, that bit I get. :)
But, there's some flexibility in how we satisfy that abstraction. It might be reasonable to have "fast parsing" that merely comes close to simulating recursive-descent, as long as we also provide a (slower) full recursive-descent parser that produces the same PIR output.
The problem there is that if we do this then the first time someone overrides a parser rule they'll go from millisecond parse times to second parse times.
Recdescent parsers do an extraordinary amount of work for what you get. It's a massively brute-force way of parsing, which is part of the problem--that brute-force path is mandated by the parsing algorithm. The grammar you build a recdescent parser out of, as Damian has pointed out to me, isn't inherently different than the one you'd build a bottom-up parser from, it's the behavior of the built parser that's the issue. There are constructs that aren't valid in recdescent parsers (that whole left-recursive thing mainly) but that's true of all the different parser types.
I suppose I could go try convince Larry to lift the guarantees of behaviour for the grammar engine (well, besides correctness, at least) for this. Dunno that it'll be too successful without abysmal benchmarks to show with it, though. :)
Certainly some things won't be recursive-descent anyway (operator precedence).
Oh, don't be too sure of that. :) Operator precedence can be done in a recdescent grammar straightforwardly enough. It's a bit longwinded, but doable.
Also, it may be a little too early to decide that one method of parsing will be fast or slow. IIRC we nearly ditched CPS because it was too slow, then found a way to speed it up.
Nope, CPS was originally not an option because of brain-cramp issues, not speed. 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.
