Build and validate a parser for the WML language within Scala. Your code should follow a pure functional programming style, and using Scala. All data types must be immutable, and data may not be modified once assigned.

The goal is to be able to successfully parse the WML language, and presented as an explicit grammar in the accompanying grammar.txt file.

Below is the content of grammar.txt file:

TSTART = "{{" TEND = "}}" VSTART = "{{{" VEND = "}}}" DSTART = "{'" DEND = "'}" PIPE = "|" PIPES = "||" OUTERTEXT = anything, except for TSTART, or DSTART INNERITEXT = anything, except for TSTART, DSTART, VSTART, PIPE(s), TEND INNERDTEXT = anything, except for TSTART, DSTART, VSTART, PIPE(s), DEND BODYTEXT = anything, except TSTART, DSTART, VSTART, DEND VNAME = anything, except for PIPE(s), VEND

::= (OUTERTEXT | | )* ::= TSTART TEND ::= (PIPE ?)* ::= (INNERITEXT | | | )* ::= VSTART VNAME (PIPE )? VEND

::= DSTART PIPES DEND ::= (INNERDTEXT | | | )* ::= (PIPE )* ::= (INNERDTEXT | | | )+ ::= (BODYTEXT | | | )*

Your parser will need to be able to construct an AST. Define an appropriate class hierarchy for represent- ing your nodes. Your class hierarchy should be rooted at an abstract class, ASTNode, and it should be designed to capture all the non-terminals and non-constant/parametric terminals. Include toString functions for each of your definitions that emit the corresponding name of the termi- nal token. For non-terminals, the string emitted should start with the terminal name, an opening bracket, and then the entire substructure, all single-space separated, terminated by a closing bracket. Do not print out optional elements that are absent or null. For example, invoking tostring on the instantiated root of your tree based on parsing "abc def {{ xxx | bar uuuu }}" should return the string "PROGRAM ( OUTERTEXT INVOKE ( ITEXT (INNERITEXT ) TARGS ( ITEXT (INNERITEXT ) ) ) )" Provide a file q2.scala with the hierarchy definition. Your parser will need to be able to construct an AST. Define an appropriate class hierarchy for represent- ing your nodes. Your class hierarchy should be rooted at an abstract class, ASTNode, and it should be designed to capture all the non-terminals and non-constant/parametric terminals. Include toString functions for each of your definitions that emit the corresponding name of the termi- nal token. For non-terminals, the string emitted should start with the terminal name, an opening bracket, and then the entire substructure, all single-space separated, terminated by a closing bracket. Do not print out optional elements that are absent or null. For example, invoking tostring on the instantiated root of your tree based on parsing "abc def {{ xxx | bar uuuu }}" should return the string "PROGRAM ( OUTERTEXT INVOKE ( ITEXT (INNERITEXT ) TARGS ( ITEXT (INNERITEXT ) ) ) )" Provide a file q2.scala with the hierarchy definition