chrushed

Top-down parsing starts with the input and works its way down to the start symbol, while bottom-up parsing starts with the input and works its way up to the start symbol. Top-down parsing uses predictive parsing techniques, such as LL and recursive descent, while bottom-up parsing uses shift-reduce or LR parsing algorithms.

Stacks are not only the preferred data structure for bottom up parsing, they are the only data structure suitable for bottom up parsing.

Bottom-up parsing is usually referred to as depth-first search. Top-down parsing is referred to as breadth-first search. The two are exactly the same in terms of implementation, the difference is only in the structure used to store information collated from the previous iterations. With top-down parsing you use a queue, pushing to the back and popping from the front. With bottom-up parsing you use a stack, pushing to and popping from the back.

Seppo Sippu has written:

'Parsing theory' -- subject(s): Formal languages, Parsing (Computer grammar)