Programming Languages: Concepts and Implementation

3.5 Bottom-up, Shift-Reduce Parsing and Parser Generators

We engage in bottom-up parsing when we parse a string using the shift-reduce method (as we demonstrated in Section 2.7). The bottom-up nature refers to starting the parse with the terminals of the string and working backward (or bottom-up) toward the start symbol of the grammar. In other words, a bottom-up parse of a string attempts to construct a rightmost derivation of the string in reverse (i.e., bottom-up). While parsing a string in this bottom-up fashion, we can also construct a parse tree for the sentence, if desired, by allocating nodes of the tree as we shift and setting pointers to pre-allocated nodes in the newly created internal nodes as we reduce. (We need not always build ...