CIT 594 Previous Announcements
Spring 2009, David Matuszek

Date Announcements
April 13, 2009 Here are some "Logo" programs that I've written. You may find them useful for testing your Interpreter.
Tries out most features of our mini-Logo language, not including procedures.
Uses a procedure, but does not use parameters.
Uses procedures, parameters, and local and global variables. If you handle variables correctly, you should get two rows each of blue, green, and red figures.
Uses a recursive procedure to draw a familiar picture.
Some of these do a great deal of drawing, so if you don't have a speed control, you may want to change the hard-wired delay in your program.
April 6, 2009 Some corrections for the Interpreter, mostly pretty minor (Thanks, Adam!):
  • The nestedStars.logo program is missing a set y 10 command right near the top.
  • In the table in the Interpreter assignment, fourth row, it should say pendown instead of penup.
  • My Tree class is in a package named tree, but yours is (or was) in a package named support. Since you will be handing in your Tree class along with your Interpreter, it doesn't matter what you call this package.
  • The Big Picture page refers to an assignment you never did.
Parse trees can get pretty long, and you are supposed to display one in a message dialog. Here's some code that can help:
     * Embeds a GUI component inside a JScrollPane.
     * @param component The JComponent to be made scrollable.
     * @return A scrollable pane containing the given JComponent.
    private JScrollPane makeScrollable(JComponent component) {        
        // Make a panel containing the component
        JPanel panel = new JPanel();
        panel.setLayout(new BorderLayout());
        panel.add(component, BorderLayout.CENTER);
        return new JScrollPane(panel);
My code had a ComponentListener with a // TODO Make this work flag in it, that I didn't clean out before giving you the code (the actual fix was elsewhere). You can ignore or discard that listener.
April 2, 2009

I forgot to say that I added two methods to my Tree class, and you should do the same.

public Tree<Token> getChild(i)
Returns the ith child of this Tree. Same as children().get(i).
public String toMultilineString()

Returns a String representation of this Tree which, if printed, would give the same result as the print() method.

The best way to do this is to take your print() method (and any methods it calls), and change it to build up a string, rather than printing as it goes. Then, to follow the DRY principle, you can replace your original print() method with one that simply prints the result of calling toMultilineString().

BTW, the way I used toMultilineString() in the starter code I gave you is not the way it should be used. It should be displayed in a message dialog, not in the main GUI area.

March 27, 2009

Because the definition of the color() method was ambiguous, I replaced all calls to recognizer.color() with calls to recognizer.command() (and never call your Recognizer's color() method).

I forgot to do the equivalent in

You can download the fixed version, or just make the changes yourself (five in testColor, and one more in testBadColorCommand).

March 25, 2009

A define node should have exactly two children: A header and a block. The header also has two children, a <name> and a list. The example pictures showed two different structures; I've now made them consistent.

Also, not new but should be made explicit: Wherever a block or a list is expected, it should be present, even if it has no children.

March 25, 2009

I have made some corrections to the examples on the Parser assignment. The only significant change is the replacement of a <procedures> node with a <list> node.

As you know, it was a bad design decision to have both an EOI token and a hasNext() method. So that this does not continue to be a problem, please use only the EOI token, not the hasNext() method, in your Parser. If you can easily remove the hasNext() method from your Tokenizer ("easily" means it isn't too difficult to make the necessary changes to your Recognizer and JUnit tests), please do so.

Poor choice of method name: The listOfCommands() method should create a Tree with block, not a list, as the root. Keep the name, but make sure it does the right thing.

March 17, 2009 Some of you have asked why it is necessary to create a new Recognizer object for every string we want to try to recognize. The answer is, there is no good reason. I suggest (but don't require) that you add the method public void recognize(String input) to your Recognizer.
March 17, 2009

Grades on Midterm Exam

Midterm Exam Grades

Average (mean), 74.90

Median, 75.5

St. dev., 12.44

March 13, 2009 I've posted my
March 11, 2009

In response to a couple of questions about the Recognizer assignment, please provide these constructors:
    public Recognizer(String input) // For testing purposes
and either or both of
    public Recognizer(File inputFile) // For recognizing a <program> on a file
    public Recognizer(Reader reader) // For any use
In accordance with the DRY principle, only one of these should do the actual work (most easily, the one that takes a Reader as a parameter), and the others should just call that one with the appropriate parameter.

What your tests should do is just call the Recognizer with various strings, for example,

    Recognizer r = new Recognizer("if x<y { \n penup \n } \n");
    r = new Recognizer("if x<y { \n penup \n } \n");
March 3, 2009 Here's a long list of CIT 594 Exam Questions. Most of the questions on the midterm will be drawn from this list.
February 25, 2009

As mentioned in class, please change the method
    private static boolean isNonterminal(String s) {
        return s.startsWith("<");

    public static boolean isNonterminal(String s) {
        return s.startsWith("<") && s.endsWith(">") && s.length() > 2;

I've been asked whether the public void read(Reader reader) of the Grammar class should throw an IOException. Yes, it probably should.

So that I can test your Grammar class (and to simplify your own testing), please add the following method to Grammar:

    public Map<String, Definitions> getRules() {
        return grammar;

The Random Program Generator assignment is now due Monday, March 2. On Tuesday I will give out the next assignment, to be due sometime after Spring Break.

February 22, 2009

According to the assignment:

"As a special case, the two-character sequence \n is returned as a terminal whose value is the newline character."

I forgot to test for this special case. Here's the needed test:

    public void testNext_BackslashN_Terminal() {
        Token x = new Token(TokenType.TERMINAL, "x");
        Token eol = new Token(TokenType.EOL, "\n");
        Token eolAsTerminal = new Token(TokenType.TERMINAL, "\n");
        use("x \\n x \n x");

To make this a little simpler, you can assume that \n in your input BNF is not adjacent to any other printable character. That is, you don't have to deal with things like ;\n or one\ntwo. In general, you can assume that tokens are seperated by whitespace (or are at the beginning or end of the line.).

February 18, 2009 There are already some minor corrections to the Random Program Generator. frowny Doin' my best here.
February 18, 2009 I've been preaching TDD (Test Driven Design) for a long time, but I don't know how many of you have actually tried it. Now's your chance! and
February 17, 2009 In response to emailed questions, here are corrections to the Tokenizer assignment.
  • When I said that a NUMBER was only digits, I was only thinking about integers, and what I intended was: don't include a sign. So 123-45 would be three tokens, not two. I did not mean to disallow floating-point numbers such as 123.45; please accept StreamTokenizer's definition of numbers.
  • Also, contrary to what I told some students earlier, the sval of a number is null, so just use tokenizer.nval.toString() as the value of your NUMBER Tokens.
  • An underscore, _, can always be part of a NAME, even as the first character. It's too much of a problem otherwise. Just use tokenizer.wordChars('_', '_');.
In light of these corrections, the assignment is now due Wednesday by midnight (instead of Tuesday). Also, here's a freebie: tokenizer.ordinaryChars(10,13);. Try assorted Java statements, including numbers, names, and comments, to figure out what other "ordinary characters" you need.
February 9, 2009

In the Timing Methods assignment, my intent was that your subset methods would work directly with the sorted or unsorted arrays, as specified for that particular method. I did not expect you to sort the arrays as part of the algorithm. However, since I failed to make that explicit, you can sort or not sort--it's up to you. If you sort, you can use Arrays.sort, or implement your own sort.

Methods should not have side effects. That is, a method should do the one thing it is supposed to do, and not change anything else in the process. If you sort the array as part of the membership test, that is a side effect, and normally would be considered Very Bad Style. In this case, however, "unsorted" really means that the order is unknown or unimportant, so it's okay.

If you sort as part of the subset tests, then the sorting is part of the algorithm, and must be included in the timing of the algorithm. It is important to remember that sorting an already sorted array may (depending on the algorithm) have very different timing characteristics than sorting a random array. Hence, you should randomize between runs of the subset method. But since randomizing the array is not part of the subset algorithm, you will need to time this separately, and subtract out the time required for randomization.

Finally, a request. In the assignment, I said "This file should include an analysis of each method, giving both your Big-O formula and a brief explanation of how you arrived at this formula." So that we can understand your analysis, please include a sentence or two describing your algorithm.

February 8, 2009

If the code I provide for the Timing Methods assignment (or any other assignment) appears incomplete or messed up, please (1) let me know exactly what browser you are using, and (2) use a different browser to access the page.

It appears that IE7 under Windows XP ignores the <pre> tag when there is a <code> tag inside it. Since these tags have been around as long as HTML has existed, that's a pretty egregious problem.

In any case, I've posted a slightly modified page for this assignment; the only change is in the HTML markup, which should now work for any halfway decent browser (not including IE)

February 6, 2009

For testing your Tree API, I used

I also tested your unit tests with my own Tree API (which I am not posting!), with three deliberate errors in it: equals not correctly handling a null value in a node, addChild not checking for a cycle, and contains checking no deeper than the children of the root.

January 30, 2009 No new assignment yet. I'll post a new assignment after next Tuesday's class.
January 28, 2009 I have posted some Required Eclipse settings. Please use these settings for all future assignments (the third assignment and beyond).
January 22, 2009

I seem to have had real trouble with generics in this assignment.

Almost everywhere that a variable is declared to be of type Tree, it should be Tree<V> instead. The exceptions are in the constructor, which (for some reason) must be just Tree, and the parse method, which should return a Tree<String>.

Also, the children method should return, not just a List, but a List<Tree<V>>.

Thanks to all the people who have pointed out these problems to me.

January 20, 2009 I see that my example of output from toString() was inconsistent:
     one (two three(four five(six seven eight)))
with a space after one but no space after three or five. Since my example was inconsistent, you can include or not include a space before an open parenthesis, as you choose.

Obviously the parse(String s) method requires a space between, for example, two and three (otherwise it would get twothree as a single token, but it should be able to accept and ignore any and all extra spaces.
January 20, 2009 Correction: As someone pointed out in class, the parse method should return a Tree<String>, not a Tree<V>. Also, I noticed that this method really should be static; so,
     public static Tree<String> parse(String s)
January 20, 2009 Correction: The method addChild(V value) creates a brand new node, hence adding this node to a tree cannot possibly create a loop in the tree, hence it can never throw an IllegalArgumentException. Just omit the throws IllegalArgumentException part.
January 19, 2009 Correction: The constructor for the Tree class should be public Tree(V value), not public Tree<V>(V value).