Assignment 11 - Due Wednesday April 14 Friday April 16 23:59 by e-mail

List Processor Machines

Write the code for an interpreter that processes lists as detailed below.

Your interpreter receives statements from the user, parses them and then executes them. It then prints back the results. Here is a grammar for the kind of commands your interpreter should be able to understand:

 1. statement  := assignment
 2.            := expression 
 3.            := identifier               // value 

 4. assignment := identifier = expression  // OK

 5. expression := remove string from list  // list 
 6.            := reverse list             // list 

 7. list       := string       // list of one  
 8.            := string list  // one cell followed by list 
The syntactic categories in blue are called terminals. They must appear as such. The interpreter only understands statements made out of terminals.

The syntactic categories in italics are not detailed. They are what you expected them to be, alphanumeric strings of characters that start with an alphabetic character for identifiers. We underline them because we treat them as terminals.

All the other syntactic categories are called non-terminals.

Non-terminals describe a statement or part of a statement that is in the making.

Essentially our interpreter should understand the following 5 types of commands:

identifier = remove string from list

The identifier is set to the value of the list out of which occurrences of the specified string have been removed.

identifier = reverse list

The identifier is set to the value of the reversed list.


The value of the identifier is returned, if the identifier has one. Otherwise undefined is returned.

remove string from list

A list is returned, after the occurrences of the specified string have been removed. If the list is empty the value returned is null.

reverse list

The reversed list is returned.

The lists processed are only lists of strings of characters.

This grammar does not allow the user to specify empty lists.

Here's a session with our interpreter: java Homework11    
Welcome to the List Processor Machine. 
input> a = remove 1 from 1 2 1 3 1 4
input> b = reverse 1 2 3 4 5 6
input> a
2 3 4
input> b
6 5 4 3 2 1
input> remove 1 from 1 1 1 2 1 3 
2 3
input> reverse 1 2 3
3 2 1
input> reverse test a is this 
this is a test
input> quit
Thanks for visiting. Good-bye. 
The processor's answers are in blue.

Your interpreter must use internally a one-way List representation similar to the one below:

class List {
  String value;
  List nextElement; 
You may add more methods to it (and you should) but not more instance variables.