CS102 Spring 2008

Lab # 4

Recognizing Simple Languages using Grammars and Recursion

In this laboratory exercise you will write a program that implements and tests two simple language recognizer methods from Chapter 6 of the text: isId( ) and isAⁿBⁿ( ). The main() method, constructor, and test methods for this lab have been provided for you. You need only implement the recursive methods and helper methods. The algorithm for isId( ) appears on page 301 of the text, and isAⁿBⁿ( ) appears on page 304.

Launch NetBeans and Create Project

1. Launch NetBeans and create a new project named Lab4. Go to the File menu and select "NewProject", then specify "Java Application" -- or click on the third button from the left on the button bar.
   
   
2. Edit Main.java and put your name, date, and lab information in the file header comments.
   
   
3. Delete the static main method and constructor that was automatically generated by NetBeans.
   
   
4. Copy and paste the following methods into your Main class: 
   
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        new Main();
    }    

    /** Creates a new instance of Main */
    public Main() {
        this.runIsIdTests();
        this.runIsAnBnTests();
    }

    /**
     * Runs tests for isId()
     */
    private void runIsIdTests() {
        String[] goodIds = {
            "public", "static", "void", "main", "Main", "String",
            "a12345", "b_$", "__valid$$", "MAXNODES_"
        };

        String[] badIds = {
            "1var", "(parenID)", "%1", "42", "count#", "w's", "|abs|",
            "<letter>", "<digit>", "/tag"
        };

        System.out.println("\nTesting valid Java Identifiers:");
        for (String w : goodIds) {
            if (this.isId(w)) {
                System.out.println("PASSED: " +
                        "isId( " + w + " ) was true");
            }
            else {
                System.out.println("FAILED: " +
                        "isId( " + w + " ) was false");
            }
        }

        System.out.println("\nTesting invalid Java Identifiers:");
        for (String w : badIds) {
            if (!this.isId(w)) {
                System.out.println("PASSED: " +
                        "isId( " + w + " ) was false");
            }
            else {
                System.out.println("FAILED: " +
                        "isId( " + w + " ) was true");
            }
        }                
    }

    /**
     * Runs tests for isAnBn()
     */
    private void runIsAnBnTests() {
        String[] ofFormAnBn = {
            "", "AB", "AABB", "AAABBB", "AAAABBBB", "AAAAABBBBB"
        };

        String[] notOfFormAnBn = {
            "A", "B", "AA", "BB", "ABB", "AAB", "ABAB",
            "BABA", "AABBAABB", "ABC"
        };

        System.out.println("\nTesting valid strings of form A^nB^n:");
        for (String w : ofFormAnBn) {
            if (this.isAnBn(w)) {
                System.out.println("PASSED: " +
                        "isAnBn( " + w + " ) was true");
            }
            else {
                System.out.println("FAILED: " +
                        "isAnBn( " + w + " ) was false");
            }
        }

        System.out.println("\nTesting invalid strings of form A^nB^n:");
        for (String w : notOfFormAnBn) {
            if (!this.isAnBn(w)) {
                System.out.println("PASSED: " +
                        "isAnBn( " + w + " ) was false");
            }
            else {
                System.out.println("FAILED: " +
                        "isAnBn( " + w + " ) was true");
            }
        }                
    }


5. Now copy and paste the following empty-body methods into your Main class. These are the methods you will implement, following the recursive algorithms presented in the text. Remember, these algorithms are simple because they were derived from the simple grammars for these languages.
   
    /**
     * Returns true if w is a legal java identifier;
     * otherwise returns false.
     */
    public boolean isId(String w) {
        // implement this method
    }

    /**
     * Determines whether given character is a letter.
     * (helper method for isId)
     */
    private boolean isLetter(char c) {
        // implement this method
    }

    /**
     * Determines whether given character is a digit.
     * (helper method for isId)
     */
    private boolean isDigit(char c) {
        // implement this method
    }

    /**
     * Returns true if w is of the form A^nB^n;
     * otherwise returns false.
     */
    public boolean isAnBn(String w) {
        // implement this method
    }

   
6. Save and run your project. When it successfully produces the correct output (shown below), submit your lab.  Here is the sample output:
   
   init:
   deps-jar:
   Compiling 1 source file to /Users/mlsmith/Desktop/SimpleLanguages/build/classes
   compile:
   run:
   
   Testing valid Java Identifiers:
   PASSED: isId( public ) was true
   PASSED: isId( static ) was true
   PASSED: isId( void ) was true
   PASSED: isId( main ) was true
   PASSED: isId( Main ) was true
   PASSED: isId( String ) was true
   PASSED: isId( a12345 ) was true
   PASSED: isId( b_$ ) was true
   PASSED: isId( __valid$$ ) was true
   PASSED: isId( MAXNODES_ ) was true
   
   Testing invalid Java Identifiers:
   PASSED: isId( 1var ) was false
   PASSED: isId( (parenID) ) was false
   PASSED: isId( %1 ) was false
   PASSED: isId( 42 ) was false
   PASSED: isId( count# ) was false
   PASSED: isId( w's ) was false
   PASSED: isId( |abs| ) was false
   PASSED: isId( <letter> ) was false
   PASSED: isId( <digit> ) was false
   PASSED: isId( /tag ) was false
   
   Testing valid strings of form A^nB^n:
   PASSED: isAnBn(  ) was true
   PASSED: isAnBn( AB ) was true
   PASSED: isAnBn( AABB ) was true
   PASSED: isAnBn( AAABBB ) was true
   PASSED: isAnBn( AAAABBBB ) was true
   PASSED: isAnBn( AAAAABBBBB ) was true
   
   Testing invalid strings of form A^nB^n:
   PASSED: isAnBn( A ) was false
   PASSED: isAnBn( B ) was false
   PASSED: isAnBn( AA ) was false
   PASSED: isAnBn( BB ) was false
   PASSED: isAnBn( ABB ) was false
   PASSED: isAnBn( AAB ) was false
   PASSED: isAnBn( ABAB ) was false
   PASSED: isAnBn( BABA ) was false
   PASSED: isAnBn( AABBAABB ) was false
   PASSED: isAnBn( ABC ) was false
   BUILD SUCCESSFUL (total time: 0 seconds)
   

Submitting your work

From a terminal window, type the following commands:

 cd
 cd cs102
        submit102 Lab4

Log out

When you are done, close NetBeans, and then locate the logout button on the menu bar. Click on the logout button (red arrow pointing through an open door).  Choose "Logout..." and then click "Yes" when prompted.  Always remember to log out when you are done using the system, to ensure that no one else uses your account.