$[05]$ Using the Bottom$-$UP parsing $($syntactical analysis$)$ algorithm, trace the first $5$ iterations of the parser given the input: $"(a+b)**(c+d)$$ $"$ Show only the contents of the STACK each iteration.

$(S_0,a_{1}dots{a}_{n}S)//$ The parser at initial configuration $=($stack$,$ input$)$

state# $=0,$ action $=-,$ stack $=[0]$

while$($ action $$ "accept" & action $$ error $)$

$3\mathrm{.}1$ state# $=$ stack right, nextToken $=$ input left

Grammar

$3\mathrm{.}2$ Find action

$3\mathrm{.}2\mathrm{.}1$ action $=$ ActionTable$[$ row$=$state#$,$ cohmnn$=$nextToken $]$

$3\mathrm{.}2\mathrm{.}2$ state #$=$ the index part of the action e$.$g$.$ if action ${?}_T=R3=>$ state #$=3$

$EE+T$

$ET$

$3\mathrm{.}3$ if action $=S)$

$//$ Shift

$3\mathrm{.}3\mathrm{.}1$ Push nextToken and state"

else

$//$ Reduce

$TT**F$

$TF$

$3\mathrm{.}3\mathrm{.}2$ Remove top of the stack token and its state#

$F(E)$

$3\mathrm{.}3\mathrm{.}3$ Exposed state, $x$ State ${?}^E=$ current stack right statel" after $3\mathrm{.}3\mathrm{.}2$

$F$ id

$3\mathrm{.}3\mathrm{.}4$ Push the LHS nonterminal of the rule of the removed token in $33\mathrm{.}2$

$3\mathrm{.}3\mathrm{.}5$ state $=$ GOTOTable$[$ xStae# in $3\mathrm{.}3\mathrm{.}3.$ LHS in $3\mathrm{.}3\mathrm{.}4]$

$3\mathrm{.}3\mathrm{.}5$ Push the state

endIF

$//$ If action $==$ void cell $$ error

$3\mathrm{.}4$ if $($any error detected $)$

$3\mathrm{.}4\mathrm{.}1$ handleError$($ errorType $)$

$3\mathrm{.}4\mathrm{.}2$ error $=$ TRUE

endIF

$\backslash$table$[[$Sute$,$Terminals,Non$-$Terminals$],[$Action$,$Coto$],[$ld$,*,-,1,),s,$E$,T,$r$],[0,$ss$,,,$SA$,,,1,2,3],[1,,$$$6,,,,$sccept,,,$],[2,,R,57,,122,R2,,,],[3,,$RA$,$RA$,,$R$4,$R$4,,,],[4,$ss$,,,$s$4,,,8,2,3],[5,,$RS$,126,,$R$6,$RS$,,,],[6,$ss$,,,$SA$,,,,9,3],[7,$SS$,,,$si$,,,,,10],[8,,56,,,511,,,,]]$