컨텍스트 프리 - 문법을 구문 분석합니다

Question

나는 왼쪽 재귀적인 문법을 받아 들일 수 있기 때문에 상향식 파서가 하향식 파서보다 낫다는 것을 알고 있음을 알고 있습니다. 상향식 파싱을 선호하는 다른 이유는 무엇을 하향식 파싱을 통해 구문 분석을 선호 할 수 있습니까?

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.