Write a Python program using PLY to compute a Relational Algebra expression corresponding to an atomic formula in Datalog. Here are some sample atomic formulas from Datalog:

employee$("$jones$",20,$x$,$y$,$"john",x$,$y$,$x$,$x$,$z$)$ p$($x$,$x$,$x$,$x$,$x$)$ p$($x$,20,$x$,$y$,$"john",x$,$y$)$ student$($x$,$y$,$z$)$

As can be seen, an atomic formula in Datalog begins with a NAME token followed by a left parenthesis $($LPAREN$),$ followed by a list or arguments and ends with a right parenthesis $($RPAREN$).$ The list of arguments is COMMA separated and each of argument can be either a NUMBER constant $($assume positive integers$)$ or a STRING constant, or a NAME corresponding to a variable.

A sample run of the final program on a Terminal is shown below $($user input is shown in RED$)$:

macbook$-$pro:dlog raj$ python$3$ DLOG.py DLG: employee$("$jones$",20,$x$,$y$,$"john",x$,$y$,$x$,$x$,$z$)$ rename$[$x$,$y$,$z$]($project$[$x$\_2,$x$\_3,$x$\_9]($select$[$x$\_0=$"jones" and x$\_1=20$ and x$\_4=$"john" and x$\_2=$x$\_5$ and x$\_5=$x$\_7$ and x$\_7=$x$\_8$ and x$\_3=$x$\_6]($rename$[$x$\_0,$x$\_1,$x$\_2,$x$\_3,$x$\_4,$x$\_5,$x$\_6,$x$\_7,$x$\_8,$x$\_9]($employee$))))$ DLG: p$($x$,$x$,$x$,$x$,$x$)$ rename$[$x$]($project$[$x$\_0]($select$[$x$\_0=$x$\_1$ and x$\_1=$x$\_2$ and x$\_2=$x$\_3$ and x$\_3=$x$\_4]($rename$[$x$\_0,$x$\_1,$x$\_2,$x$\_3,$x$\_4]($p$))))$ DLG: p$($x$,20,$x$,$y$,$"john",x$,$y$)$ rename$[$x$,$y$]($project$[$x$\_0,$x$\_3]($select$[$x$\_1=20$ and x$\_4=$"john" and x$\_0=$x$\_2$ and x$\_2=$x$\_5$ and x$\_3=$x$\_6]($rename$[$x$\_0,$x$\_1,$x$\_2,$x$\_3,$x$\_4,$x$\_5,$x$\_6]($p$))))$ DLG: student$($x$,$y$,$z$)$ rename$[$x$,$y$,$z$]($student$)$ DLG: exit

Some notes:

STEP $1$: Identify all tokens and define the lexical specifications in DLOGLexer.py$.$ This has already been done for you above!

STEP $2$: Write a grammar specification for the Datalog atom. Then, write the Parser specification in DLOGParser.py$.$

STEP $3$: Write the main program $($DLOG$.$py$)$ that prompts the user, reads a Datalog atom from the keyboard, calls the parser which returns a data structure containing the details of the atom. While debugging, you may print this data structure to verify that the lexical analysis and parsing steps work.

STEP $4$: Finally, write the code in DLOG.py to process the data structure and generate the Relational Algebra string. Print this string to terminal.

The conversion from Datalog atom to Relational Algebra string works as follows $($described in an inside$-$out manner, with p$($x$,20,$x$,$y$,$"john",x$,$y$)$ as an example$)$:

First produce a list of variables, x$\_0,...,$ x$\_$n$-1,$ where n is the number of arguments in the Datalog atom and generate the following string:

rename$[$x$\_0,$x$\_1,$x$\_2,$x$\_3,$x$\_4,$x$\_5,$x$\_6]($p$)$

Next, generate the select conditions; There are two types of select conditions: one that correspond to the numeric or string constants in the Datalog atom and the other that correspond to repeated variable arguments in the Datalog atom. Combine all of the conditions with "and" and generate the following string:

select$[$x$\_1=20$ and x$\_4=$"john" and x$\_0=$x$\_2$ and x$\_2=$x$\_5$ and x$\_3=$x$\_6]($rename$[$x$\_0,$x$\_1,$x$\_2,$x$\_3,$x$\_4,$x$\_5,$x$\_6]($p$))$

As you can see, there are two conditions that correspond to the constant arguments of the atom, two conditions to ensure that the $3$ instances of variable x are equated and one condition to ensure that the $2$ instances of the variable y are equated. Notice that this string builds on the string generated in the previous step.Next, generate the project list; this list consists of the unique variables in the Datalog atom $($in this case the unique variables are x and y$)$; Generate the following string, again building on the previous string:

project$[$x$\_0,$x$\_3]($select$[$x$\_1=20$ and x$\_4=$"john" and x$\_0=$x$\_2$ and x$\_2=$x$\_5$ and x$\_3=$x$\_6]($rename$[$x$\_0,$x$\_1,$x$\_2,$x$\_3,$x$\_4,$x$\_5,$x$\_6]($p$)))$

In the final step, produce the rename list of unique variables from the original names of variables and generate the final string:

rename$[$x$,$y$]($project$[$x$\_0,$x$\_3]($select$[$x$\_1=20$ and x$\_4=$"john" and x$\_0=$x$\_2$ and x$\_2=$x$\_5$ and x$\_3=$x$\_6]($rename$[$x$\_0,$x$\_1,$x$\_2,$x$\_3,$x$\_4,$x$\_5,$x$\_6]($p$))))$

Notice that in the final example, student$($x$,$y$,$z$),$ there are no constant arguments and no repeated variables resulting in an empty select condition. In this case produce only the final rename part as shown in the sample run. This is a special case and can be handled at the end.

Submit the following files: DLOG.py$,$ DLOGLexer.py$,$ and DLOGParser.py$.$