about recursive descent parsing on Wikipedia: https://en.wikipedia.org/wiki/Recu

ID: 3531273 • Letter: A

Question

about recursive descent parsing on Wikipedia: https://en.wikipedia.org/wiki/Recursive_descent_parser. Your assignment is to define a grammar for a language, and then implement a recursive descent parser for this language. When it comes time to write your recursive descent parser, follow the approach discussed in the lecture notes, baesd on nextchar(), match(), and the throwing of exceptions. You may program in C++ or Java. The exercise is meant to be a fun diversion from our usual paper-and-pencil homework; you are required to work individually. The assignment is to write a recursive descent parser for regular expressions. The alphabet of the regular expressions is {'a', 'b', 'c', 'd', '|', '*', '(',')'}. Union is denoted by '|', and kleene star by '*'. Concatenation is denoted by placing two sub-expressions next to each other. Assume 1 line of input - i.e. a single string - and no spaces, much like the parser shown in class. Here are examples of valid regular expressions: a (a|bc)* a*|b* abcd abc* a|b|c|d(a|b)c* a|b abc*** (((a)*)|((b)*))b ab|bc|c|d a*bc*d (a)(b)(c)|(d)* For this assignment, the EMPTY STRING is *not* a valid regular expression. You should correctly capture the precedence of the operators in your parser, which from lowest to highest is union, concatenation, and kleene. For example, the regular expression ab*c|d is really this when precedence is taken into account: (a(b*)c)|(d) Your first order of business is to write the grammar for the language of regular expression. For a hint on how to get started, see example 2.4 on page 105 of the Sipser text. Your grammar must be written in the form of a comment at the top of your main program file. If your grammar contains left recursion, i.e. rules of the form