Parser, Grammar

S’ -> Seof {Pop S’; Push Seof}
S -> [] {Pop S; Push []; Pop []}
S -> [T] {Pop S; Begin Subtree; Push T; Consume T; Push [ to second tree; Back up Subtree}
S -> SS {Pop S; Push SS}

T -> Atom {Pop T; Push Atom}
T -> TT {Pop T; Push TT}
T -> S {Pop T; Push S}

Atom -> integer | float | string | variable/name | operator {Pop Atom: Push on Level of Tree }

Example

S' = [+ 1 [+ 7 2]]eof

Pop, Push [+1 [+ 7 2]]eof

S->[T] Pop, Begin SubTree , will Push and then Consume T, Push [ to 2nd and find ]

T->TT First T is +, Second T is rest

T-> Atom; Atom-> Operator, + is actually placed on Tree at Level Implied by Brackets

Tree:

+

T->TT First T is 1, Second T is rest

T-> Atom; Atom-> Operator, 1 is actually placed on Tree at Level Implied by Brackets

Tree:

+

1

T->S; S->[T] Pop, Begin SubTree , will Push and then Consume T, Push [ to 2nd and find ]

Operations are repeated for T-> TT and T->Atom for +, 7, 2

] found, Pop off 2nd stack, Return to Parent Tree

] found, Pop off 2nd stack, Return to Parent Tree

Tree:

+

1

   +

   7

   2

S consumed, pop eof

Error Case: The same but with only one ] at the end.

Same operations up to eof, 2nd stack isn’t empty, throw incorrect number of brackets error.