Compiler Design – Significance of Bottom Up Parsing

A bottom-up parser creates the parse tree for a given input string starting from leaves towards the root. A bottom-up parser tries to find the right-most derivation of the given input string in the reverse order. Bottom-up parsing is also known as shift-reduce parsing. Bottom-up parsing is the process of “reducing” a string ‘w’ to the start symbol of the grammar. At each reduction step, a particular substring matching the right-side of a production is replaced by the symbol on the left-side of the production. If the substring is chosen correctly, a right most derivation is traced out in reverse. A general style of bottom-up syntax analysis, known as shift-reduce parsing. Two types of bottom-up parsing: Operator-Precedence parsing – an easy to implement form of shift reduce parsing. LR parsing – a much more general form of Shift Reduce Parsing. LR parsing is used in a number of automatic parser generators. Informally a Handle of a string ‘w’ is a substring that matches the RHS of some production and whose reduction to the non-terminal on the LHS of the production represents one step along the reverse of a rightmost derivation. But not every substring that matches the right side of a production rule is handle. A rightmost derivation in reverse can be obtained by “handle-pruning.”