An Introduction to Formal Languages and Automata, 7th Edition

15.2 TOP-DOWN VS. BOTTOM-UP PARSING

There are different approaches to parsing algorithms. The exhaustive search algorithm (Section 5.2) is a form of top-down parsing. In top-down parsing, the parser begins with the grammar’s start symbol and replaces the left-most variable in each step of the derivation until the input string is derived. A derivation tree for top-down parsing produces derivation trees like we saw in Section 5.1. With exhaustive search parsing, if a variable A has more than one rule, the parser tries all possible rules in each step, an inefficient approach. LL parsing is another type of top-down parsing. With LL parsing, if a variable A has more than one rule, the algorithm inspects the symbols in the input string from left to ...