We will implement a parser for the tree grammar that Gerves requested in class. The grammar is:

S $->$ N S

S $->$

N $->$ root $()$

N $->$ node $(,$ L $)$

L $->[]$

L $->[$ LL $]$

LL $->$

LL $->$ LL $,$

The tokens are root, node, $(,),[,],,$ and $($which stands for and string constant$).$ The non$-$terminals are S$,$ N$,$ L and LL$.$

Consider this subset of the tree grammar:

a$)$ L $->[]$

b$)$ L $->[$ LL $]$

c$)$ LL $->$

d$)$ LL $->$ LL $,$

Add a brand new starting non$-$terminal

S $->$ L $

Then:

a$)$ Define the states for the grammar.

b$)$ Make a table the grammar.

c$)$ Use your table to parse the expression:

$[$ "Hello" $,$ "there" $]$