MCS-287 Lab 3 (Spring 2014)

Due April 25, 2014

Assignment

You are to write and turn in a Java program that meets the following specification. You do not need to turn in any evidence of testing if the program works correctly. However, if the program fails in some way to meet its specification, you are expected to turn in a statement regarding the shortcoming. If you fail to do so, your grade will be reduced both for your failure to document the error as well as for the error itself. If there is any aspect of the specification that isn't clear to you, please ask about it. You can submit your program the same way as in the prior lab.

The file Analyzer.zip contains the Eclipse project that you can import as your starting point. It contains Analyzer, which is where you will provide the overall functionality, and ScopedMap, which you need to fill in with the data structure described below that is the largest portion of the assignment. The project also includes a JUnit test class for each, AnalyzerTest and ScopedMapTest.

The test cases in AnalyzerTest and ScopedMapTest are both based on the example that is given below. I would suggest adding other tests of your own. For example, my test doesn't contain any syntax errors, so it wouldn't exercise that portion of your program. The Analyzer class I provided passes the example test but wouldn't pass any other test because it ignores its input and always blindly produces the example output. Your will replace this "dummy" output code with a real version. Your first priority, however, should be to get the ScopedMapTest to pass.

Input

Your analyzer should receive an input string that constitutes a block, as described by the following BNF grammar:

<blck> ::= begin <stmts> end

<stmts> ::= <empty>
          | <stmt> <stmts>

<stmt> ::= pass
         | declare <name>
         | use <name>
         | <blck>

A <name> is a token that consists of any non-whitespace characters; as such, you can readily use the java.util.Scanner class. At least one whitespace character must separate each pair of consecutive tokens. Additional whitespace may freely occur before the first token, after the last token, or between tokens.

If the input does not conform to this specification, your program should throw an IllegalArgumentException. This handling of syntactically illegal inputs will count for 20% of the grade of the assignment. In order for the input to be syntactically legal, it must consist of a single block and nothing more.

Output

Your analyzer should return a string similar to the input but with two changes. First, although the whitespace in the input is largely irrelevant, the output should be formatted to show its structure by breaking it into lines ending with the newline character ("\n"). Each line should include exactly one begin, end, pass, declare or use. The indentation of the lines should correspond to the block structure: two spaces of indentation per enclosing block. The second change your program should make in the output (as compared to the input) is that each declaration statement or use statement should be followed by an annotation as in the following example:

begin
  pass
  declare x {declaration 1}
  use y {illegal undeclared use}
  declare y {declaration 2}
  begin
    use x {references declaration 1}
    declare x {declaration 3}
    use x {references declaration 3}
    declare x {illegal redeclaration}
    use x {references declaration 3}
    declare y {declaration 4}
  end
  use x {references declaration 1}
end

Notice that each legal declaration receives a number one higher than the previous one. These numbers are stored for later reference in the use statements. An illegal redeclaration does not advance the number by one.

Data Structure

Your program should use a generic class, ScopedMap, which you must write. That class should conform to the documentation that I am linking to this assignment. This class will count for 70% of the grade of the assignment.

Your job will be easier if you use some of the predefined generic types in the Java API. Moreover, if you fail to do so, but rather build the ScopedMap class from scratch, you will not get full credit.

There are multiple plausible ways to store this data structure. Some are more efficient than others. You will receive extra credit if your ScopedMap can process each legal sequence of n operations in time that is essentially proportional to n.