$($Please make all files, and make sure the code compiles and produces teh given output.$)------$Implement the RE$2$DFA algorithm using the PLY package. The context$-$free grammar for the language of regular expressions is shown below.

re : re PLUS term

re : term

term : term factor

term : factor

factor : factor STAR

factor : niggle

niggle : LETTER

niggle : LPAREN re RPAREN

Since the expression tree nodes have various attributes associated with them, such as nullable, firstpos, lastpos, etc., this problem can benefit from building a traditional tree data structure with nodes and pointers to children nodes. I am providing a skeletal file, RENode.py$,$ below, which you should use to construct the tree data structure in REParser.py and also use in the main program to compute the various functions such as nullable, firstpos, and lastpos. For this assignment, we will assume that there are no $\backslash$epsi or $\backslash$phi regular expressions.

class RENode:

def $\_\_$init$\_\_($self$)$:

self.operator $=\text{'}\text{'}$ # $\text{'}*\text{'},\text{'}.\text{'},\text{'}+\text{'},$ 'leaf'

self.symbol $=\text{'}\text{'}$ # only for leaf nodes

self.position $=0$ # only for leaf nodes

self.lchild $=$ None

self.rchild $=$ None # only for $.$ and $+$

self.nullable $=$ False

self.firstpos $=$ set$()$

self.lastpos $=$ set$()$

# Your methods go here

def to$\_$string$($self$,$n$)$:

result $=\text{'}\text{'}*$n

if self.operator $==$ 'leaf':

result $+=$ 'SYMBOL: $\text{'}+$self.symbol

result $+=\text{'}$ NULLABLE$=\text{'}+$str$($self$.$nullable$)$

result $+=\text{'}$ FIRSTPOS$=\text{'}+$str$($self$.$firstpos$)$

result $+=\text{'}$ LASTPOS$=\text{'}+$str$($self$.$lastpos$)+\text{'}$

$\text{'}$

elif self.operator $==\text{'}*\text{'}$:

result $+=$ 'OPERATOR: STAR'

result $+=\text{'}$ NULLABLE$=\text{'}+$str$($self$.$nullable$)$

result $+=\text{'}$ FIRSTPOS$=\text{'}+$str$($self$.$firstpos$)$

result $+=\text{'}$ LASTPOS$=\text{'}+$str$($self$.$lastpos$)+\text{'}$

$\text{'}$

result $+=$ self.lchild.to$\_$string$($n$+2)$

elif self.operator $==\text{'}.\text{'}$:

result $+=$ 'OPERATOR: DOT'

result $+=\text{'}$ NULLABLE$=\text{'}+$str$($self$.$nullable$)$

result $+=\text{'}$ FIRSTPOS$=\text{'}+$str$($self$.$firstpos$)$

result $+=\text{'}$ LASTPOS$=\text{'}+$str$($self$.$lastpos$)+\text{'}$

$\text{'}$

result $+=$ self.lchild.to$\_$string$($n$+2)$

result $+=$ self.rchild.to$\_$string$($n$+2)$

elif self.operator $==\text{'}+\text{'}$:

result $+=$ 'OPERATOR: PLUS'

result $+=\text{'}$ NULLABLE$=\text{'}+$str$($self$.$nullable$)$

result $+=\text{'}$ FIRSTPOS$=\text{'}+$str$($self$.$firstpos$)$

result $+=\text{'}$ LASTPOS$=\text{'}+$str$($self$.$lastpos$)+\text{'}$

$\text{'}$

result $+=$ self.lchild.to$\_$string$($n$+2)$

result $+=$ self.rchild.to$\_$string$($n$+2)$

else:

result $+=$ 'SOMETHING WENT WRONG'

return result

def $\_\_$str$\_\_($self$)$:

return self.to$\_$string$(0)$

Submit RE$.$py$,$ RELexer.py$,$ REParser.py$,$ RENode.py$,$ and DFA.py$.$ A sample run is shown below:

$ python$3$ RE$2$DFA.py $($aa$+$bb$)*$aaa

start $1\_3\_5$

final $8\_2\_6$

$1\_3\_5$:a:$2\_6$

$1\_3\_5$:b:$4$

$2\_6$:a:$1\_3\_5\_7$

$2\_6$:b:EMPTY

$4$:a:EMPTY

$4$:b:$1\_3\_5$

$1\_3\_5\_7$:a:$8\_2\_6$

$1\_3\_5\_7$:b:$4$

$2\_6\_8$:a:$1\_3\_5\_7$

$2\_6\_8$:b:EMPTY

EMPTY:a:EMPTY

EMPTY:b:EMPTY