colored_squares.logo

Tries out most features of our mini-Logo language, not including procedures.

wheel.logo

Uses a procedure, but does not use parameters.

figures.logo

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.

recursive_squares.logo

Uses a recursive procedure to draw a familiar picture.

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

    /**
     * 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);
    }

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 i^th 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.

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

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

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.

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.

Grades on Midterm Exam

Average (mean), 74.90 Median, 75.5 St. dev., 12.44

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");
    assertTrue(r.command());
    r = new Recognizer("if x<y { \n penup \n } \n");
    assertFalse(r.expression());

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

    }
to
    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:

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.

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:

    @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");
        assertEquals(x, t.next());
        assertEquals(eolAsTerminal, t.next());
        assertEquals(x, t.next());
        assertEquals(eol, t.next());
        assertEquals(x, t.next());
        assertFalse(t.hasNext());
    }

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

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

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)

For testing your Tree API, I used DavesTreeTest.java.

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.

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.