To be done in groups of two. Pick your partner!This is a continuation of the previous assignment. Now, we are going to generate an abstract syntax tree of the input, and evaluate the tree to compute a value for the expression. We can consider the abstract syntax tree as the meaning of the expression that was parsed.An abstract syntax tree is like a parse tree, except at the nodes we have operators, rather than non$-$terminals. For example, the abstract syntax tree for $(3+4)*5$ is given below. Note that there is no need for parenthesis in the tree.$*/\backslash +5/\backslash 34$Our original grammar remains unchanged.G$1$:GEE E $+$ T $|$ E $-$ T $|$T T T $*$ F $|$T $/$ F $|$ F F $($ E $)|$ M$|$ NM a $|$ b $|$ c$|$ dN $0|1|2|3$This grammar is not suitable for top down recursive descent parsing because of left recursion.Removing left recursion, we get the grammar G$2$:G$2$: GEE TRR $+$ T R$|-$T R $|$ T FSS $*$ FS $|/$ F S $|$ F $($ E $)|$ M$|$ NM a $|$ b $|$ c$|$ dN $0|1|2|3""$ means the empty production, i$.$e$.$ if T $,$ then T can derive the empty string.Now, we can write recursive functions for parsing according to G$2,$ generating an abstract syntax tree as a result of parsing, and evaluating the returned abstract syntax tree to compute the value of the expression. We shall assume that a is a constant with value $10,$ b is a constant with value $20,$ c is a constant with value $30$ and d is a constant with value $40.$Below is the pseudo$-$code of the parser, tree printer and evaluator. We shall need a way to represent trees, hence the class Node.Class Node$\{$char symbol; $//$ either an operator, or one of $0,1,2,3,$a$,$b$,$c$,$d Node leftChild; $//$ will be NULL if node is a leafNode rightChild; $//$ will be NULL if node is a leaf$\}$Bool error $=$ FALSE; char next$\_$token $=\text{'}\%\text{'}$;void main$()\{$Node theTree;$/*$ open file for reading $*/......$theTree $=$ G$()$; if $($not error$)\{$printTree$($theTree$)$;value $=$ evaluate$($theTree$)$; print The value is$,$ value;$\}$else print input not parsed correctly$\}/*$ G $->$ E $*/$Node G$()\{$ Node tree;lex$()$;print $("$G $->$ E$")$;tree $=$ E$()$;if $($next$\_$token$==\text{'}$$$\text{'}$ and $!($error$))\{$print "success"; return tree;$\}$ else $\{$return NULL; $\}\}/*$ E $->$ T R $*/$ Node E$()\{$Node temp;if $($error$)$ return NULL; print $("$E $->$ T R$")$;temp $=$ T$()$;return R$($temp$)$; $\}/*$ R $->+$ T R $|-$ T R $|$ e $*/$ Node R$($Node tree$)\{$Node temp$1,$ temp$2$;if $($error$)$ return NULL;if $($next$\_$token$==\text{'}+\text{'})\{$ print $("$R $->+$ T R$")$; lex$()$;print $("$failure: unconsumed input$=\%$s$",$ unconsumed$\_$input$())$;temp$1=$ T$()$;temp$2=$ R$($temp$1)$;return new Node$(+,$ tree, temp$2)$;$\}$else if $($next$\_$token$==\text{'}-\text{'})\{$print $("$R $->-$ T R$")$;lex$()$;temp$1=$T$()$;temp$2=$R$($temp$1)$;return new Node$(-,$ tree, temp$2)$;$\}$ else $\{$print $("$R$->$e$")$;return$($tree$)$; $\}\}/*$ T $->$ F S $*/$ Node T$()\{$Node temp;if $($error$)$ return; print $("$ T $->$ F S$")$; temp $=$ F$()$;return S$($temp$)$;$\}$S $->*$ F S $|/$ F S $|$ e $*/$ Node temp$1,$ temp$2$;if $($error$)$ return;if $($next$\_$token$==\text{'}*\text{'})\{$ print $("$S $->*$ F S$")$;lex$()$;temp$1=$F$()$;temp$2=$S$($temp$1)$;return new Node$(*,$ tree, temp$2)$;$\}$else if $($next$\_$token$==\text{'}/\text{'})\{/*$Node S$($Node tree$)\{$print $"$S $->/$ F S$"$lex$()$;temp$1=$F$()$;temp$2=$S$($temp$1)$;return new Node$(/,$tree,temp$2)$;$\}$ else $\{$print $"$S $->$ e$"$;return$($tree$)$; $\}\}/*$ F $->($ E $)|$ N $|$ M $*/$ Node F$()\{$Node temp;if $($error$)$ return NULL;if $($next$\_$token$==\text{'}(\text{'})\{$ print $"$F$->($ E $)"$; lex$()$;temp$=$E$()$;if $($next$\_$token $==\text{'})\text{'})\{$ lex$()$;return$($temp$)$; $\}$else $\{$ error$=$TRUE;print$("$error: unexptected token $",$ next$\_$token$)$; print$("$unconsumed$\_$input $",$ unconusmed$\_$input$())$; return NULL;$\}\}$else if $($next$\_$token is one of $\text{'}$a$\text{'}$ or $\text{'}$b$\text{'}$ or $\text{'}$c$\text{'}$ or $\text{'}$d$\text{'})\{$ print $("$F$->$M$")$;return $($M$())$;$\}$else if $($next$\_$token is one of $\text{'}0\text{'}$ or $\text{'}1\text{'}$ or $\text{'}2\text{'}$ or $\text{'}3\text{'})\{$print $("$F$->$N$")$;return$($N$())$; $\}$else $\{$ error$=$TRUE;print$("$error: unexptected token $",$ next$\_$token$)$;print$("$unconsumed$\_$input $",$ unconusmed$\_$input$())$; return$($NULL$)$;$\}\}/*$ M a $|$ b $|$ c $|$ d $*/$ Node M$()\{$char prev$\_$token $=$ next$\_$token;if $($error$)$ return NULL;if $($next$\_$token is one of $\text{'}$a$\text{'}$ or $\text{'}$b$\text{'}$ or $\text{'}$c$\text{'}$ or $\text{'}$d$\text{'})\{$print $("$M$->",$ next$\_$token$)$;lex$()$;return new Node$($prev$\_$token, NULL,NULL$)$;$\}$ else $\{$ error$=$TRUE;print$("$error: unexptected token $",$ next$\_$token$)$; print$("$unconsumed$\_$input $",$ unconusmed$\_$input$())$; return$($NULL$)$;$\}\}/*$ N $0|1|2|3*/$ Node N$()\{$char prev$\_$token $=$ next$\_$token;if $($error$)$ return NULL;if $($next$\_$token is one of $\text{'}0\text{'}$ or $\text{'}1\text{'}$ or $\text{'}2\text{'}$ or $\text{'}3\text{'})\{$ print $("$N$->",$ next$\_$token$)$;lex$()$;return new Node$($prev$\_$token, NULL,NULL$)$;$\}$ else $\{$ error$=$TRUE;print$("$error: unexptected token $",$ next$\_$token$)$; print$("$unconsumed$\_$input $",$ unconusmed$\_$input$())$; return$($NULL$)\}\}//$ print tree in postfix notation void printTree$($Node tree$)\{$if $($tree$==$NULL$)$ return; printTree$($tree$.$leftChild$)$; printTree$($tree$.$rightChild$)$; print$($tree$.$symbol$)$;$\}//$ compute the value of the expression int evaluate$($Node tree$)\{$if $($tree$==$NULL$)$ return $-1$;if $($tree$.$symbol$=$a$)$ return $10$;if $($tree$.$symbol$=$b$)$ return $20$;if $($tree$.$symbol$=$c$)$ return $30$;if $($tree$.$symbol$=$d$)$ return $40$;if $($tree$.$symbol$=$ one of $0,1,2,3)$ return the value of tree.symbol;if $($tree$.$symbol$=+)$ return $($evaluate$($tree$.$leftChild$)+$ evaluate$($tree$.$rightChild$))$; if $($tree$.$symbol$=-)$ return $($evaluate$($tree$.$leftChild$)-$ evaluate$($tree$.$rightChild$))$; if $($tree$.$symbol$=*)$ return $($evaluate$($tree$.$leftChild$)*$ evaluate$($tree$.$rightChild$))$; if $($tree$.$symbol$=/)$ return $($evaluate$($tree$.$leftChild$)/$ evaluate$($tree$.$rightChild$))$;$\}$OK$,$ now that the parser is mostly written for you, here is what you will do:Write a Python program $($based on the pseudo$-$code given above$)$ to parse expressions as defined by the grammar above, print the abstract syntax tree and compute its value. The input should be in a file. You should have global variables error $($of type Boolean$),$ and next$\_$token $($of type char$).$ Define a function lex$()$ that gets the next character from the file and places it inside next$\_$token. lex$()$ should skip any white spaces, such as newlines or the space character. The function unconusmed$\_$input$()$ should return the remaining input in the file. The last character in the file should always be $$.$ Define functions $($hint: class methods$)$ G$(),$ E$(),$ R$(),$ T$(),$ F$()$ and N$().$ Inside ma