Why is bottom-up parsing more common than top-down parsing?

If you choose a powerful parser generator, you can code your grammar without worrying about peculiar properties. (LA)LR means you don’t have to worry about left recursion, one less headache. GLR means you don’t have to worry about local ambiguity or lookahead.

And the bottom-up parsers tend to be pretty efficient. So, once you’ve paid the price of a bit of complicated machinery, it is easier to write grammars and the parsers perform well.

You should expect to see this kind of choice wherever there is some programming construct that commonly occurs: if it is easier to specify, and it performs pretty well, even if the machinery is complicated, complex machinery will win. As another example, the database world has gone to relational tools, in spite of the fact that you can hand-build an indexed file yourself. It’s easier to write the data schemas, it’s easier to specify the indexes, and with complicated enough machinery behind (you don’t have to look at the gears, you just use them), they can be pretty fast with almost no effort. Same reasons.

Leave a Comment