CMSC 435: Assignment 4

Overview

Write a PREDICTIVE (no backtracking), recursive descent parser for the grammar below. EBNF is used, so be careful to note whether a symbol is a metasymbol or not. The six valid metasymbols are the following: {, }, [, ], (, and ). A symbol is NOT a metasymbol if it is in single quotes (e.g., ‘[’ and ‘}’). All the tokens are single characters, so the scanner is trivial. NAME your scanner function getToken (see Required Functions below).

In a comment above EVERY parsing method, show the rewritten GRAMMAR RULE that it parses. Use the STANDARD techniques we studied to remove left recursion and perform left factoring.

M  →   { S } '$'

S  →   I | W | A | P | C | G

I  →   '[' E ? { S } : { S } ']' | '[' E ? { S } ']'

W  →   '{' E ? { S } '}'

A  →   id = E ;

P  →   < E ;

C  →   < ( 'B' | 'T' | 'N' ) ;

G  →   > id ;

E  →   E + T | E - T | T

T  →   T * U | T / U | T % U | U

U  →   F ^ U | F

F  →   '(' E ')' | id | num

id   →   a | b | ... | z
num  →   0 | 1 | ... | 9

Grammar Key

Terminals B, T, and N, stand for blank, tab, and newline, respectively. An identifier (id) must be a SINGLE LOWERCASE letter. A number (num) must be a SINGLE DIGIT. A valid program must end in $.

Input Specification

Input a string from the user (one character at a time). Use whitespace (space, tab, carriage return, or newline) as a delimiter.

Output Specification

Indicate whether the sentence is valid or not. Detect an error and output an error message indicating ALL of the following:

- function in which the error occurred,
- the line number,
- expected token, and
- current token.

Use the following error format:

Error in "<function>" on line <lineNum>:
  expected '<expectedToken>' but got '<currentToken>'. 

If the string is valid output “Valid!”.

Sample Session 1

[ a ?
    b  = 5 ;
]  $

Valid!

Sample Session 2

> x;
> y;

< (x * y)
    + 3
    % (y ^ 2);

{ x &
    x = x - 1;
}
$
  
Error in "W" on line 8:
  expected '?' but got '&'. 

Required Functions

// Read and return a character token.
// Skip whitespace and keep track of line number. 
char
getToken ();
  
// Check if the current token matches `expectedToken`.
// If so, update the current token.
// If not, call the `error` function. 
// `function` is the function which called `match`.
void
match (std::string_view function, char expectedToken);

// Output an error message using the appropriate format.
// `function` is the function in which the error occurred. 
void
error (std::string_view function, std::string_view expected);

Submission

Submit your single parser file Parser.cc.

Hints

The part of the grammar involving “{ S }” means “zero or more statements”. In handling such a construct, you need to know when to stop calling function S, the one that handles a statement. There are two methods to do this: call S as long as the next token is one that can start a statement. The other (equivalent) method is to keep calling S until the next token is one that may end a sequence of statements.

See the RecursiveDescent directory for examples and some test cases.

Extra Credit

Use the code below to generate tokens.

// Token representation holding the character and its one-based source line
struct Token
{
  char value;
  int line;
};

// Use a C++23 std::generator and coroutine
std::generator<Token>
tokenize ()
{
  char ch;
  int line = 1;
  while (std::cin >> std::noskipws >> ch)
    if (ch == '\n')
      ++line;
    else if (not std::isspace (static_cast<unsigned char> (ch)))
      co_yield Token { ch, line };
  co_yield Token { '$', line };
}

Gary M. Zoppetti, Ph.D.