INSR TREE©

Number to tree builder (Version 1)

Dafydd Gibbon, 2008-11-16

X: Enter a sequence of numbers separated by spaces:

Schedule

Bottom-up (or shift-reduce) parsers work by shifting symbols onto a stack until the top of the stack contains a right-hand side of a production. The stack is then reduced by replacing the production's right-hand side by its left-hand side. This process continues until the string has been reduced to the start symbol of the grammar.

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):
S → W S
W → W S
W → w
S → s
S → w
However, whether a particular unit is s, w, S, W is calculated on the fly.

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

  1. Bottom-up: newlist01 = [] for item in numberlist: newlist01.append([item]) for rank in reverse(rankset): i == 0 newlist02 == [] for i in range(len(numberlist)-1): if newlist01[i][-1] = rank: newlist02 = newlist02.append([ newlist01[i], newlist01[i+1] newlist01=newlist02

Walkthrough:

1 -> 1 1 2 -> 1 2 3 1 -> [ 3, 1 ] 2 3 1 -> [ 2 [ 3, 1 ] ] 5 3 1 -> [ [ 5, 3] , 1 ] 3 2 3 1 -> [ [ 3, 2 ] , [ 3, 1 ] ] Algorithm: ( scan predict complete )* push(current) if first(stack) > next: replace(first(stack), [ current, next ] # maybe also next as top node. for i in range(len(stack)): # check reverse/reversed if rightmost(firststack(stack)) > rightmost(secondstack(stack)): temp = pop(firststack) replace(first(stack), [ first(stack), temp ] else: break