Top-down and bottom-up are not mutually exclusive. At least not completely. But self-modifying parsers are *much* easier to do with top-down than bottom-up, because the whole point of bottom-up is that you can analyze the grammar at "compile" (parser generation) time, and propagate the knowledge throughout the rule engine.
A simple example is /fish|job|petunia/. Rather than trying to match /fish/ and upon failure, trying /job/, and as a last resort /petunia/, you could do a dispatch table on the first letter and never have to fall back to anything. In the case of /fish|job|<petunia>/, however, you can't guarantee that FIRST(<petunia>) will always be "p". You could generate both parsers and then use a notification or dependency system to pick which to use, but done naively you end up with an exponential number of parsers and the logic is likely to be both slow and a bug magnet. You could compile the parser assuming everything is final and then at runtime regenerate the entire parser if anything changes. Which wouldn't work for long, but perhaps you could break the grammar down into components that are individually compiled bottom-up, but coordinated top-down. Then you could limit the scope of recompiles in the bottom-up components, and not need recompiles in the top-down structure. The decisions of where to break things down would be quite similar to a regular compiler's inlining decisions. It may be that grammars are just too recursive for this to help much, though. I suspect a slight variant of the above may work best. Rather than doing a full-out LALR(1) parser for the bottom-up components, you'd do a somewhat more naive but still table-driven (shift/reduce) parser, carefully limiting what it is assuming about the FIRST() etc. of the rules within it. That should limit the impact of changes, and simplify the logic of what needs to be done differently when a change is detected. On May-11, Matt Fowles wrote: > > 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. Optimization hints could also be very helpful, or we could even default to a total recursive-descent parser and only attempt bottom-up precomputation if the grammar author specifically says it's ok. The main problem being that people will say lots of things if it makes their code faster, without having any idea what it actually means.
