Number to tree builder (Version 1)

Dafydd Gibbon, 2008-11-16

The string of symbols to be replaced at each stage is called a handle. Bottom-up parsers that proceed from left to right in the input string must always replace the leftmost handle and, in so doing, they effectively construct a rightmost derivation sequence in reverse order. For example, a rightmost derivation of the string abcde might be S → ACD → ACde → Acde → abcde

A bottom-up parser would construct this derivation in reverse, first reducing abcde to Acde, then to ACde, then to ACD, and finally to the start symbol S. The handle at each stage is respectively ab, c, de, and ACD.

The INSR parser effectively has a deterministic context-free grammar (S is start symbol):

The algorithm schedule can be either top-down or bottom up:

Walkthrough: