We use regular expressions to describe regular languages. Regular expressions are themselves stringsover an alphabet including regular characters and special characters such as parentheses, ., |, and*. The string .*(1.1|1..1).* is a valid regular expression while the string ((10|)( is not.This language turns out not be regular (because it includes strings with arbitrarily deeply nested sets ofparentheses). Let us assume we have already constructed a scanner that identifies the tokens regularexpressions are composed of.1 The tokens we are allowed to build regular expressions from are( ) | . * + ? charwhere char denotes any valid character of the underlying alphabet. You dont have to worry aboutrecognizing valid characters; we assume the scanner takes care of this for us.
(a) Provide a context-free grammar that defines the language of regular expressions. As is customary,assume that each input string is terminated by a special end-of-string marker $. Make surethe grammar represents the semantic structure of regular expressions. For example, the partialgrammar
E ? char
E ? EE
E ? E|E
would allow us to parse the regular expression ab|c to be composed of two regular expressionsa and b|c, which is semantically incorrect. The correct parse is a regular expression composedof two regular expressions ab (which in turn is composed of smaller regular expressions) andc. Review how we ensured arithmetic expressions are parsed in a way that reflects operatorprecedence to get an idea how you can ensure that the parse tree corresponding to a regularexpression correctly reflects its structure.
(b) Provide the parse tree used to generate the string .*(1.1|1..1).* using your grammar.
(c) Verify that your grammar is LL(1). (If it is not, modify the grammar to make it LL(1).) Inparticular, provide FIRST, FOLLOW, and PREDICT sets for characters and productions and explainwhy they prove that the language is LL(1).
d) (Bonus: 25%) Provide the pseudo-code for a recursive descent parser for regular expressionsbased on your grammar.
"Place your order now for a similar assignment and have exceptional work written by our team of experts, guaranteeing you A results."