Name:

SE550 midterm exam: Winter 2000-2001

Answer all questions.

Time allowed: 2 hours

Total number of points: 100

Messaging service

Some questions will refer to MessageServer, MessagePutClient and MessageRequestParser classes. They are defined here.

public class MessageServer implements Runnable {

    public static void main (final String[] args) throws IOException {        
        final ServerSocket sSocket = new ServerSocket (2000);
        while (true) {
            final Socket socket = sSocket.accept ();
            final MessageServer server = new MessageServer (socket);
            server.start ();
        }
    }

    protected final static Hashtable table = new Hashtable ();

    protected final Socket socket;
    protected final PrintWriter out;
    protected final BufferedReader in;
    protected final Thread thread;

    protected MessageServer (final Socket socket) throws IOException {
        this.socket = socket;
        this.out = new PrintWriter (socket.getOutputStream (), true);
        this.in = new BufferedReader (new InputStreamReader (socket.getInputStream ()));
        this.thread = new Thread (this);
    }

    public void start () { 
        thread.start (); 
    }

    public void run () {
        try {
            String line = in.readLine (); 
            while (line != null && !line.equals ("QUIT")) {
                if (line.startsWith ("PUT ")) {
                    put (line.substring (4));
                } else if (line.startsWith ("GET ")) {
                    get (line.substring (4));
                } else {
                    error ();
                }
                line = in.readLine ();
            }
        } catch (final IOException ex) {
        } finally {
            try {
                out.close ();
                in.close ();
                socket.close ();
            } catch (final IOException ex) {
            }
        }
    }

Messaging service continued

    protected Vector messages (final String userid) {
        Vector messages = (Vector)(table.get (userid));
        if (messages == null) { 
            messages = new Vector (); 
            table.put (userid, messages); 
        }
        return messages;
    }

    protected void put (final String userid) throws IOException {
        messages (userid).add (in.readLine ());
        out.println ("OK");
    }

    protected void get (final String userid) throws IOException {
        final Vector messages = messages (userid);
        out.println ("FOR " + userid);
        while (messages.size () > 0) {
            try {
                out.println ("GOT " + messages.remove (0));
            } catch (final ArrayIndexOutOfBoundsException ex) {
            }
        }
        out.println ("OK");
    }

    protected void error () throws IOException {
        out.println ("ERROR");
    }

}

Messaging service continued

public class MessagePutClient {

    public static void main (final String[] args) {

        try {
            final Socket socket = new Socket (args[0], 2000);
            final PrintWriter out = new PrintWriter (socket.getOutputStream (), true);
            final BufferedReader in = new BufferedReader (new InputStreamReader (socket.getInputStream ()));
            for (int i=2; i < args.length; i++) {
                out.println ("PUT " + args[1]);
                out.println (args[i]);
                if (!(in.readLine ().equals ("OK"))) {
                    System.err.println ("Putting message " + args[i] + " failed");
                    System.exit (1);
                }            
            }
            out.println ("QUIT");
            out.close ();
            in.close ();
            socket.close ();
        } catch (final IOException ex) {
            System.err.println ("Network error: " + ex);
            System.exit (1);
        }
    }

}

Messaging service continued

public grammar class MessageRequestParser {

  public void handleQuitRequest () { code for handling a quit request }

  public void handleGetRequest (String userid) { code for handling a get request }

  public void handlePutRequest (String userid, String message) { code found handling a put request }

  token {
    <QUIT: "QUIT">
  | <PUT: "PUT">
  | <GET: "GET">
  | <CRLF: "\n" | "\r" | "\n\r">
  | <SPACE: " ">
  | <ID: (<IDCHAR>)+>
  | <IDCHAR: ['a'-'z'] | ['A'-'Z'] | ['0'-'9']>
  }

  public production void request () {
    quitRequest () | putRequest () | getRequest ()
  }

  production void quitRequest () {
    ( <QUIT> <CRLF> ) | <eof>
    { handleQuitRequest (); }
  }

  production void putRequest () {
    { String userid; String message; }
    <PUT> <SPACE> userid=id () <SPACE> message=message () <CRLF>
    { handlePutRequest (userid, message); }
  }

  production void getRequest () {
    { String userid; }
    <GET> <SPACE> userid=id () <CRLF>
    { handleGetRequest (userid); }
  }

  production String message () {
    { StringBuffer result = new StringBuffer (); String tmp; }
    ( 
      tmp = id () { result.append (tmp); }
    | <SPACE> { result.append (" "); }
    )*
    { return result.toString (); }
  }

  production String id () {
    { Token t; }
    t = <ID>
    { return t.image; }
  }

}

Question 1 (10 points)

a) What is a lossy protocol?

b) What is an unordered protocol?

c) What is a packet-based protocol?

d) Is IP lossy, unordered, and packet-based?

e) Is TCP lossy, unordered, and packet-based?

Question 2 (15 points)

Assume that on machine server the following command is run:

  java MessageServer

and that on machine client the following command is run:

  java MessagePutClient server fred hello world
  java MessagePutClient server wilma foo

a) What messages are sent between the client and the server (assuming no network problems)?

b) What is the contents of MessageServer.table after the messages are sent.

Question 3 (10 points)

If a client sends the following requests to the MessageServer, what responses will be returned?

  PUT barney
  a message






  PUT barney
  another message






  PUT betty
  yet another message






  GET barney






  GET barney






  GET betty






  GET betty





  QUIT

Question 4 (15 points)

The client code only allows messages to be sent, not read. Write a client which gets messages from the server. For example, running:

  java MessageGetClient server fred

could produce the result:

  Message 1 for fred: hello
  Message 2 for fred: world
  There were 2 messages for fred.

The command line arguments to the program are the name of the server, and the userid to fetch messages for.

public class MessageGetClient {

    public static void main (final String[] args) {
        try {
            final Socket socket = new Socket (args[0], 2000);
            final String userid = args[1];
            final PrintWriter out = new PrintWriter (socket.getOutputStream (), true);
            final BufferedReader in = new BufferedReader (new InputStreamReader (socket.getInputStream ()));
            // your code goes here

Question 4 continued

Question 5 (15 points)

Give two grammars for the protocol which is used by the MessageGetClient, MessagePutClient and MessageServer programs.

(For purposes of this question, you can assume that userids can only contain alphanumeric characters, and messages can only contain alphanumeric characters and spaces.)

a) Your first grammar should define a nonterminal <request>, which defines the language of requests sent by the clients.

Question 5 continued

b) Your second grammar should define a nonterminal <response>, which defines the language of responses sent by the server.

Question 6 (15 points)

The mparse parser MessageRequestParser gives a parser for name requests. Write a parser for message responses.

public grammar class MessageResponseParser {

  public void handleOKResponse () { code for handling an OK response
  }

  public void handleForResponse (final String userid) { code for handling a FOR userid response }

  public void handleGotResponse (final String message) { code for handling a GOT message response }

  public void handleErrorResponse () { code for handling an ERROR response }

  token {
    <OK: "OK">
  | <FOR: "FOR">
  | <GOT: "GOT">
  | <ERROR: "ERROR">
  | <CRLF: "\n" | "\r" | "\n\r">
  | <SPACE: " ">
  | <ID: (<IDCHAR>)+>
  | <IDCHAR: ['a'-'z'] | ['A'-'Z'] | ['0'-'9']>
  }

  production String message () {
    { StringBuffer result = new StringBuffer (); String tmp; }
    ( 
      tmp = id () { result.append (tmp); }
    | <SPACE> { result.append (" "); }
    )*
    { return result.toString (); }
  }

  production String id () {
    { Token t; }
    t = <ID>
    { return t.image; }
  }

  // your code goes here

Question 6 continued

Question 7 (10 points)

Consider the following class definitions:

interface BinaryTree {
}
class Leaf implements BinaryTree {
}
class Node implements BinaryTree {
  final BinaryTree left;
  final Object root;
  final BinaryTree right;
  Node (final BinaryTree left, final Object root, final BinaryTree right) {
    this.left = left; this.root = root; this.right = right;
  }
}

a) Write the XML which is sent when the following code is executed:

  BinaryTree leaf = new Leaf ();
  BinaryTree foo = new Node (leaf, "fred", leaf);
  BinaryTree bar = new Node (leaf, "wilma", leaf);
  BinaryTree baz = new Node (foo, "barney", bar);
  xmlSerializer.writeObject (baz);

Question 7 continued

b) Write the Java code which could generate the following XML serialization:

  <Node id="1">
    <Node id="2">
      <Leaf id="3">
      </Leaf>
      <String>hello</String>
      <Leaf href="#3"/>
    </Node>
    <String>world</String>
    <Node href="#2"/>
  </Node>

Question 8 (10 points)

A good design rule for using object serialization is never serialize a mutable object.

Explain, with an example, why this is a good design rule.

Worksheet

You can use this sheet as scrap paper.

Worksheet

You can use this sheet as scrap paper.

Worksheet

You can use this sheet as scrap paper.

Worksheet

You can use this sheet as scrap paper.