CS326 - Assignment 5

Due Date: Friday, April 13, in class.

1. Start reading chapter 4.

2. Problem 4.3, p. 267.

3. Problem 4.14, p. 270.

Special instructions for 4.14:

Rewrite the grammar so that it is unambiguous, left-factored, and does not contain any left-recursion.
Compute the entries of the predictive parsing table for the grammar using algorithm 4.4 on pg. 190.
Your final answer should be the predictive parsing table in a format similar to that in Figure 4.17 (p. 191).

4. Graduate (Due at 11:59 p.m.).

Write a short Python program boolparse.py that accepts as input, a boolean expression string and parses it using the predictive parsing table you created in problem 3. Your program should work as follows:

% python boolparse.py "not ( true or false )"
Accepted
% python boolparse.py "true true and true"
Syntax error

Note: your program only needs to print a message "Accepted" if the string is valid syntax. Otherwise, print "Syntax error".

Note: To tokenize the input string for this problem, just assume that all tokens are separated by whitespace and use the Python split() function. For example:

import sys
tokens = sys.argv[1].split()  

# example: tokens = [ 'not', '(', 'true', 'or', 'false', ')' ]

Hand-in your solution by creating a tar-file

% tar -cf yourname.tar boolparse.py

and copying it to /stage/classes/current/CS326/handin/assign5