Recursive Descent Parsing Consider the following BNF grammar: Using the techniqu

Question

Recursive Descent Parsing

Consider the following BNF grammar:

Using the technique described in class implement a recursive descent parser that recognizes strings in this language. Input should be from a file called input.txt and output should be to the console. An example session might look like this:

You must implement the project in C++! Implementations that do not include a solution in both languages will, at best, receive half credit. To simplify things you will not have to handle whitespace when parsing the string, i.e. " " and similiar are illegal characters in this language.

Explanation / Answer

That was certainly all a bit abstract and theoretical for many readers. Now we are ready to put some meat on these abstract concepts and implement the parser based on that grammar.

We first add to our class Token that holds the information about the tokens in the input.

In short, this class defines a number of static constants for the different types of tokens and a couple of fields that hold the data for the individual token. Note how we made the fields public final. This makes it immediately clear that we are dealing with an immutable object and there is no need for a multitude of getters in the class.

Next we write class called Parser which does the actual parsing of the expression. The tokens are stored in a List of Token objects and one Token object is stored as the lookahead.

The parser we are about to write will not do much except throwing an excpetion if the expression is invalid. If the parser runs without an exception being thrown we know that the expression is valid. In one of the future posts we will add to this parser and construct an internal representation of the expression that can be used for calculations.

The main method of the parser is called parse and takes the tokens as parameter.

In the parse method we first create a shallow copy of the token list because we will be taking elements out of the list and we don

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.