List Processor Machines

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 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.

identifier

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.

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

Here's a session with our interpreter:

tucotuco.cs.indiana.edu% 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.
tucotuco.cs.indiana.edu% 

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

class List {
  String value;
  List nextElement; 
}