Clarification (this is in the assignment, just not as explicitly as it could be):

Your NFA should accept its input if and only if it is in a final state at the end of the input. It isn't enough to "pass through" a final state.

This implies that, for the purpose of the backtracking algorithm, a final state is not the same as a goal node. You have reached a goal node if you are in a final state and there is no more input. Your test for a goal node must test both these conditions.

A search path will fail in one of two ways: either (1) there is no transition out of the current state for the current input symbol, or (2) there is no more input and the current state is not a final state.

It doesn't matter how many ways there are to fail to accept the input; an NFA accepts the input if there is any way to reach a goal node. Hence, each failure causes backtracking (and going back over the input). The input is rejected if all possible paths have been explored, and all have failed.

In response to a very common question, to print a graph, just produce an ASCII listing of it. Don't try to create a "picture"--that's very, very difficult.

You should print out everything about the graph, so that someone with a pencil and paper could make a complete drawing of it, if they wanted to.

Extra day. Mostly in order to give people a chance to ask more questions, the Graph assignment will be due Tuesday by midnight. The final project will be made available on Tuesday.

In response to a number of questions about what is possible on a graph, here is an example graph that you should be able to create:
Note that the ASCII labels in the above are just values; nothing prevents you from using the same value in more than one place. Also, remember that you are creating "plain" graphs, not hypergraphs.

There's an inconsistency in the assignment that only two people have noticed so far (thanks, Warren and Michael!). I said that Edges would have a Graph as their container, but a Graph would have only Nodes as its contents. This violates Plex validity.

You should resolve the inconsistency by either (1) making the container of Edges empty, or (2) making the contents of a Graph hold Edges along with Nodes. I think you will find the former more convenient, but it's your choice.

• There were some errors in my TurtleTest.java, for reasons I'll discuss in class. The link now points to the new version.
  
  
• protected void store(String name, int value): Using the name as a key, look in the topmost hash table on the stack, then in the next one down, then the next one down, etc., until you either find name or you run out of hash tables. If you find name, replace its value with the new value; but if you don't find name, store it in the topmost hash table (thus making it a "local" variable, more or less) with the new value. (Thanks, Ivy!)
  
  
• In TurtleCanvas, paint and addCommand must be synchronized. If they are not, you will sometimes get a ConcurrentModificationException from the ArrayList. (Thanks, Saajan!)
  
  
• Correction to my LogoGui: In addition to doing interpreter.setTerminated(true), it should also do interpreter.setPaused(false). (I haven't posted a new version; it's easier just to add this line yourself.)
  
  
• The Stop button in LogoGui must terminate the Interpreter thread. It calls interpreter.setTerminated(true), which sets a flag in the interpreter, but this isn't enough by itself. You stop the interpreter Thread. To do this, be sure that your run() method exits (returns) when this flag gets set. (Thanks, Gang and Saajan!)

Signature change:
In Part I, I said that one of the required methods was:
protected void callProcedure(String name, Tree<Token> actualParameters)
but I am changing that to:
protected void callProcedure(Tree callStatement)
where the parameter is the node containing the call token.
Reason for change: The actual parameters don't form a tree. The revised method will be much simpler to implement.

Modifications (mostly minor) to recently posted code:

• LogoGui.java -- Fixed erroneous message on Stop button.
• LogoTokenizer.java -- Added some missing Javadoc
• LogoTokenizerTest.java -- Important fix. Replaced some platform-specific characters with Unicode escape characters.
• Recognizer.java -- Added some missing Javadoc

By popular demand!

Pizza bash, Wed. Mar. 22, 6 pm in Levine 315.

Trivial correction: In my sample Parser code for expression(), I inserted a missing '}'.

Clarification: Every procedure node should have a parameters child and a block child, even if there are no parameters or statements.

Late programs: As noted, there will be no extensions given on this assignment. However, late penalties will not be applied during Spring Break. See the Parser Assignment page for details.

Testing: For your last-minute testing pleasure , I'm posting DavesParserTest.java. Please note:

• While I've tried not to make any assumptions about your program (other than those in the assignment), a few often slip through. If my tests are incompatible with your parser, and you think the problem is in the tests, please let Gang and me know.
• Note that my AssertStackIs method checks both that the top of the stack is as expected and that it is the only thing on the stack.

Correction: On the Parser Assignment page, in the <block> example, <block>'s children were in one order in the sample code but a different order in the picture. It's now been corrected to show the same order for both.

Another correction: In the <program> example, there were three commands in the sample code (before the define) but only two in the picture. Now corrected.

I have posted my (noisy) version of RecognizerTest.java. Since your Parser should be built around your Recognizer, you may wish to use this test file to make sure you have a good starting point.

Note: In general, JUnit tests should not print anything. This is a modified version of my JUnit test class that prints out where you are using false but should be throwing an Exception.

Sajaan is the first to point out that java.util.Map defines put as returning the "previous value associated with specified key, or null if there was no mapping for key. A null return can also indicate that the map previously associated null with the specified key, if the implementation supports null values."

In order to implement our put method in a reasonable manner, therefore, the List.add method should also return the old value or null. So in the assignment, please change
     public void add(Pair pair)
to
    public Object add(Pair pair)
where the returned result is the old value or null. (Adjust your JUnit tests accordingly.)

Also, note that I did not specify whether null keys and values were allowed, so it's your choice.

Yet another correction : In my Grammar I forgot to change
     <EOL> ::= end of string
to
     <EOL> ::= "\n"
     <END_OF_INPUT> ::= end of string

Changes in Grammar (you knew it had to happen, right?):

• Change
  <logicalExpression> ::= <comparison> | "(" <condition> ")"
  to just
  <logicalFactor> ::= <comparison>
  
  
• Change
  <conjunct> ::= [ "not" ] <logicalExpression>
  to
  <conjunct> ::= [ "not" ] <logicalFactor>

Deleting the parentheses in the rule for <logicalExpression> is necessary to avoid a parsing problem: If a line starts with "if (2", you can't tell whether the "(2" starts an arithmetic expression or a logical expression.

Changing "<logicalExpression>" to "<logicalFactor>" is just to correct the terminology.

Since my Recognizer now passes all my tests, I don't think I'll neeed to make any more changes in the grammar.

I've made some changes in the third assignment, as marked in this red color. I've added a method that I had mistakenly omitted (nodesOf), but I also simplified what you have to do about Exceptions.

As promised, I have posted the (brief) Style Rules that are required in this and all subsequent assignments.

No office hours tonight!

Sorry, my schedule is still in a state of chaos.

Clarification: null is not a legal Tree, and you should not allow it to be added as a child--throw an IllegalArgumentException if this is tried.

The methods firstChild() and lastChild() return null when called from a Tree node that has no children.

Change in Tokenizer assignment:
You are not required to use a Stack in your Tokenizer. (Depending on your implementation, a Stack may be a good way to push back tokens, or a terrible way.)

\n should be counted as whitespace. The EOL token is meant to denote the end of the string, not a newline character.

Also: If you are getting messages such as
   junit.framework.AssertionFailedError: expected:<NAME:foo> but was:<NAME:foo>
then the problem is with your public boolean equals(Object o) method, which is called by assertEquals. Two objects can be unequal but still look the same when they are printed,