We use regular expressions to describe regular languages. Regular expressions are themselves strings over an alphabet including regular characters and special characters such as parentheses,".","I", and **". The string"*(1.1.1..1).*" is a valid regular expression while the string "((101) (" is not. This language turns out not be regular (because it includes strings with arbitrarily deeply nested sets of parentheses). Let us assume we have already constructed a scanner that identifies the tokens regular expressions are composed of. The tokens we are allowed to build regular expressions from are ? char where char denotes any valid character of the underlying alphabet. You don't have to worry about recognizing 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 S. Make sure the grammar represents the semantic structure of regular expressions. For example, the partial grammar Echar E-EE EEE would allow us to parse the regular expression "ablc to be composed of two regular expressions "a" and "ble", which is semantically incorrect. The correct parse is a regular expression composed of two regular expressions "ab" (which in turn is composed of smaller regular expressions) and "c". Review how we ensured arithmetic expressions are parsed in a way that reflects operator precedence to get an idea how you can ensure that the parse tree corresponding to a regular expression correctly reflects its structure. (b) Provide the parse tree used to generate the string".*(1.111..1).*" using your grammar. () Verify that your grammar is LL(1). (If it is not, modify the grammar to make it LL(1).) In particular, provide FIRST, FOLLOW, and PREDICT sets for characters and productions and explain why they prove that the language is LL(1). (d) (Bonus: 25%) Provide the pseudo-code for a recursive descent parser for regular expressions based on your grammar. We use regular expressions to describe regular languages. Regular expressions are themselves strings over an alphabet including regular characters and special characters such as parentheses,".","I", and **". The string"*(1.1.1..1).*" is a valid regular expression while the string "((101) (" is not. This language turns out not be regular (because it includes strings with arbitrarily deeply nested sets of parentheses). Let us assume we have already constructed a scanner that identifies the tokens regular expressions are composed of. The tokens we are allowed to build regular expressions from are ? char where char denotes any valid character of the underlying alphabet. You don't have to worry about recognizing 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 S. Make sure the grammar represents the semantic structure of regular expressions. For example, the partial grammar Echar E-EE EEE would allow us to parse the regular expression "ablc to be composed of two regular expressions "a" and "ble", which is semantically incorrect. The correct parse is a regular expression composed of two regular expressions "ab" (which in turn is composed of smaller regular expressions) and "c". Review how we ensured arithmetic expressions are parsed in a way that reflects operator precedence to get an idea how you can ensure that the parse tree corresponding to a regular expression correctly reflects its structure. (b) Provide the parse tree used to generate the string".*(1.111..1).*" using your grammar. () Verify that your grammar is LL(1). (If it is not, modify the grammar to make it LL(1).) In particular, provide FIRST, FOLLOW, and PREDICT sets for characters and productions and explain why they prove that the language is LL(1). (d) (Bonus: 25%) Provide the pseudo-code for a recursive descent parser for regular expressions based on your grammar
