Programming Languages: Concepts and Implementation

3.7 Top-down Vis-à-Vis Bottom-up Parsing

A hierarchy of parsers can be developed based on properties of grammars used in them (Table 3.5). Top-down and bottom-up parsers are classified as LL and LR parsers, respectively. The first L indicates that both read the input string from Left-to-right. The second character indicates the type of derivation the parser constructs: Top-down parsers construct a Leftmost derivation, while bottom-up parsers construct a Rightmost derivation. Use of a parsing table in table-driven parsers, which can be top-down or bottom-up, often requires looking one token ahead in the input string without consuming it. These types of parsers are classified by prepending LA (for Look Ahead) before the first two characters and ...