CMSC 435: Assignment 5

Overview

Write a predictive, recursive descent (RD) parser for the C- language defined in Appendix A.2 of the text.

In a comment above every parsing method that represents a non-terminal, show the rewritten grammar rule that it parses. Use DESCRIPTIVE non-terminal and function names. Use the STANDARD techniques we studied to remove LEFT RECURSION and perform LEFT FACTORING (use EBNF and avoid adding unnecessary non-terminals). Aim to avoid ad-hoc techniques, and IF you use them, write DETAILED comments explaining your logic. Ensure your entire parser is well-commented.

Use your Lexer class from a previous assignment to obtain tokens.

Use my Parser template. Do NOT modify the public interface.

Input Specification

Take the name of a C- program as a command-line argument. If no argument is specified read from standard input (this is NECESSARY for the grading scripts). Use .cm as the extension for C- source files. You may add zero or more optional flags.

> ./CMinus [ --flags ]* [ <Program.cm> ]

Output Specification

Output “Valid!” if program is a valid sentence in C-.

> ./CMinus Gcd.cm
Valid!

Output an appropriate error if the program is invalid. Start line and column numbers with 1. Use the exact format below.

> ./CMinus Errors.cm
Compilation Error
  Parse Error [Line x, Col y]
    Expected { 'a', 'b', 'c' } but got 'd'

Here’s a concrete error message.

> ./CMinus Errors.cm
Compilation Error
  Parse Error [Line 12, Col 5]
    Expected { '(', 'Id', 'Num' } but got '+'

You are NOT required to do error recovery. Thrown an exception object and handle it in your driver (CMinus.cc).

Submission

Submit ALL necessary source files and a Makefile. ENSURE your Makefile is named Makefile, properly builds your program, and that make clean removes all generated files.

Hints

Parsing an expression requires some care. I recommend you take the approach below.

• If the expression does not start with an Id, parse a simple expression.

• If it does start with an Id, match the Id, then look for a subscript or args expression.

• If the current token is Assign, match it and parse an expression. Otherwise, it is a simple-expression in which the first factor has been consumed.

See the CMinusProgram directory for some test cases.

Gary M. Zoppetti, Ph.D.