Analysieren der kontextfreien Grammatik

Question

Ich weiß, dass ein Bottom-up-Parser besser ist als ein Top-Down-Parser, da er die linke rekursive Grammatik akzeptieren kann, was andere Gründe dafür sein kann, dass wir das Bottom-up-Analysieren über Top-Down-Parsing bevorzugen?

Answer 1

Theoretically speaking, the LL(k) grammars are always strict subsets of the LR(k) grammars for any k, so deterministic predictive bottom-up parsers can accept a strictly greater set of grammars than than deterministic predictive top-down parsers. This also means that any LL(k) grammar is also LR(k).

Also, a tricky proof shows that any deterministic CFL (a CFL accepted by a deterministic push down automaton) has an LR(1) grammar, which means that LR grammars correspond precisely to those languages that have efficient stack-based parsing algorithms.

That said, if you allow for more general parsing algorithms like Unger's algorithm, Earley's algorithm, or the CYK algorithm, then top-down and bottom-up methods exist for parsing arbitrary CFGs. These algorithms can be much slower than the predictive methods, though, so they typically aren't used for programming languages.

Hope this helps!

Answer 2

We have bottom-up parsers generators like byson. Using them is much simpler then writing parsers manually.
Also, recursive descent parsers make all operations right-associative by default, which is incorrect for arithmetics. Turning them back to left-associative requires additional steps in parsing.