//////////////////////////////////////////////////////////////////////////////// // Author: Julie Petrusa (991339) // // Due date: October 30, 2001 // // This program accepts as input a "stmt" as a string of characters to be // // parsed. If it is syntactically correct this program outputs its parse // // tree, otherwise an indication of where the error occurred and a brief // // error message are displayed. // // Known bugs: none // //////////////////////////////////////////////////////////////////////////////// import java.io.*; // needed in order to do I/O import java.util.StringTokenizer; // needed in order to get tokens class LexicalAnalyser { //--------------------------------------------------------------------------- // fields // -st will hold the StringTokenizer // -delimiters will hold the string of delimiters for the StringTokenizer // -returnLexemes is set to true so that StringTokenizer will return the // delimiters as lexemes // -the numbers from 0 to 10 will hold all the possible tokens // -the number 11 indicates that there are no more tokens private StringTokenizer st; final String delimiters = "\t\n\r' ':=<"; final boolean returnLexemes = true; final int colon_ = 0; final int equals_ = 1; final int ID_ = 2; final int integer_ = 3; final int if_ = 4; final int then_ = 5; final int endif_ = 6; final int while_ = 7; final int do_ = 8; final int endwhile_ = 9; final int lessthan_ = 10; final int error_ = 11; //--------------------------------------------------------------------------- // constructor // -creates the StringTokenizer with the input statement public LexicalAnalyser(String statement) { st = new StringTokenizer(statement, delimiters, returnLexemes); } //--------------------------------------------------------------------------- // method Tokens // -if there are more lexemes in the input statement, returns the token // corresponding to the next lexeme as long as it is not a space // -returns an indication that there are no more tokens otherwise public int Tokens() { String nextToken; if (st.hasMoreTokens()) { nextToken = st.nextToken(); if ((nextToken.charAt(0) == 32) && (st.hasMoreTokens())) nextToken = st.nextToken(); return Lexemes(nextToken); } else return error_; } //--------------------------------------------------------------------------- // method Lexemes // -returns the token corresponding to each lexeme public int Lexemes(String nextToken) { for (int j=48; j<58; j++) if (nextToken.charAt(0) == j) return integer_; if (nextToken.charAt(0) == 58) return colon_; else if (nextToken.charAt(0) == 61) return equals_; else if (nextToken.charAt(0) == 105 && nextToken.charAt(1) == 102) return if_; else if (nextToken.charAt(0) == 116 && nextToken.charAt(1) == 104 && nextToken.charAt(2) == 101 && nextToken.charAt(3) == 110) return then_; else if (nextToken.charAt(0) == 101 && nextToken.charAt(1) == 110 && nextToken.charAt(2) == 100 && nextToken.charAt(3) == 105 && nextToken.charAt(4) == 102) return endif_; else if (nextToken.charAt(0) == 119 && nextToken.charAt(1) == 104 && nextToken.charAt(2) == 105 && nextToken.charAt(3) == 108 && nextToken.charAt(4) == 101) return while_; else if (nextToken.charAt(0) == 100 && nextToken.charAt(1) == 111) return do_; else if (nextToken.charAt(0) == 101 && nextToken.charAt(1) == 110 && nextToken.charAt(2) == 100 && nextToken.charAt(3) == 119 && nextToken.charAt(4) == 104 && nextToken.charAt(5) == 105 && nextToken.charAt(6) == 108 && nextToken.charAt(7) == 101) return endwhile_; else if (nextToken.charAt(0) == 60) return lessthan_; else return ID_; } //--------------------------------------------------------------------------- } // end LexicalAnalyser class Parse { //--------------------------------------------------------------------------- // fields // -la will hold the LexicalAnalyser // -tree will be used to build the parse tree // -token will hold the current input token // -the numbers from 0 to 10 will hold all the possible tokens // -the number 11 indicates that there are no more tokens private LexicalAnalyser la; private TheStringStack tree; private int token; final int colon_ = 0; final int equals_ = 1; final int ID_ = 2; final int integer_ = 3; final int if_ = 4; final int then_ = 5; final int endif_ = 6; final int while_ = 7; final int do_ = 8; final int endwhile_ = 9; final int lessthan_ = 10; final int error_ = 11; //--------------------------------------------------------------------------- // constructor // -creates the LexicalAnalyser with the input statement // -creates TheStringStack with the length of the input statement // -gets the next token // -displays a message saying whether or not the statement is in the language // -displays the parse tree if the statement is in the language public Parse(String statement) { la = new LexicalAnalyser(statement); tree = new TheStringStack(statement.length()); token = la.Tokens(); if (stmt()) { System.out.println(); System.out.println(); System.out.println("The statement is in the language:"); System.out.println(); System.out.println(); System.out.println(""); System.out.println(" |"); String treepop; while (!tree.isEmpty()) { treepop = tree.pop(); if (treepop == "") { System.out.println(""); System.out.println(" |"); System.out.println("if then endif"); System.out.println(" | |"); System.out.println(" "); System.out.println(" | | |"); System.out.println(); } if (treepop == "") { System.out.println(""); System.out.println(" |"); System.out.println("while do endwhile"); System.out.println(" | |"); System.out.println(" "); System.out.println(" | | |"); System.out.println(); } if (treepop == "") { System.out.println(""); System.out.println(" |"); System.out.println(" := "); System.out.println(" | |"); System.out.println(); } } System.out.println(statement); } else { System.out.println(); System.out.println(); System.out.println("The statement is NOT in the language!!!"); } } //--------------------------------------------------------------------------- // method stmt // -returns true if ::= | | // -returns false otherwise public boolean stmt() { return (IFstmt() || WHILEstmt() || ASGNstmt()); } //--------------------------------------------------------------------------- // method IFstmt // -returns true if ::= if then endif // -returns false otherwise public boolean IFstmt() { if (match(if_) && condition() && match(then_) && stmt() && match(endif_)) { tree.push(""); return true; } else return false; } //--------------------------------------------------------------------------- // method WHILEstmt // -returns true if ::= while do endwhile // -returns false otherwise public boolean WHILEstmt() { if (match(while_) && condition() && match(do_) && stmt() && match(endwhile_)) { tree.push(""); return true; } else return false; } //--------------------------------------------------------------------------- // method ASGNstmt // -returns true if ::= := // -returns false otherwise public boolean ASGNstmt() { if (match(ID_) && match(colon_) && match(equals_) && match(integer_)) { tree.push(""); return true; } else return false; } //--------------------------------------------------------------------------- // method condition // -returns true if ::= // -returns false otherwise public boolean condition() { return (match(ID_) && relop() && match(ID_)); } //--------------------------------------------------------------------------- // method relop // -returns true if ::= '=' | '<' // -returns false otherwise public boolean relop() { return (match(equals_) || match(lessthan_)); } //--------------------------------------------------------------------------- // method match // -returns true if the input token matches the expected token // -returns false otherwise public boolean match(int tok) { if (token == tok) { token = la.Tokens(); return true; } else return false; } //--------------------------------------------------------------------------- } // end parse class TheStringStack { //--------------------------------------------------------------------------- // fields private int maxSize; // maximum size of stack array private String[] stringStack; // stack array private int top; // top of stack //--------------------------------------------------------------------------- // constructor public TheStringStack(int s) { maxSize = s; // set maximum size of array stringStack = new String[maxSize]; // create array top = -1; // no items yet } //--------------------------------------------------------------------------- /* method push -puts an item on the top of the stack -precondition: -stack is not full -postcondition: -if stack not full, item is pushed on top of stack -if stack full, throws IllegalStateException -return: -void */ public void push(String j) throws IllegalStateException { if(isFull()) // if stack full, throw exception throw new IllegalStateException("Stack is full!"); else // not full, stringStack[++top] = j; // increment top, insert item } //--------------------------------------------------------------------------- /* method pop -takes an item from the top of the stack -precondition: -stack is not empty -postcondition: -if stack not empty, item is popped off top of stack -if stack empty, throws IllegalStateException -return: -the popped item */ public String pop() throws IllegalStateException { if(isEmpty()) // if stack empty, throw exception throw new IllegalStateException("Stack is empty!"); else // not empty, return stringStack[top--]; // access item, decrement top } //--------------------------------------------------------------------------- /* method peek -peeks at the top of the stack -precondition: -none -postcondition: -the item at the top of the stack is returned -return: -the item at the top of the stack */ public String peek() { return stringStack[top]; // return the item at the top of the stack } //--------------------------------------------------------------------------- /* method isEmpty -returns true if stack is empty, false otherwise -precondition: -none -postcondition: -if stack empty, true is returned -if stack not empty, false is returned -return: -true if stack is empty, false otherwise */ public boolean isEmpty() { return (top == -1); // return true if stack empty, false otherwise } //--------------------------------------------------------------------------- /* method isFull -returns true if stack is full, false otherwise -precondition: -none -postcondition: -if stack full, true is returned -if stack not full, false is returned -return: -true if stack is full, false otherwise */ public boolean isFull() { return (top == maxSize-1); // return true if stack full, } // false otherwise //--------------------------------------------------------------------------- } // end class TheStringStack class Parser { //--------------------------------------------------------------------------- // main method // -tests the above classes public static void main(String[] args) throws IOException { try { System.out.println(""); // display banner System.out.println(""); System.out.println("Author: Julie Petrusa (991339)"); System.out.println("Due date: October 30, 2001"); System.out.print("This program accepts as input a 'stmt' as "); System.out.println("a string of characters to be parsed."); System.out.print("If it is syntactically correct this program "); System.out.println("outputs its parse tree, otherwise"); System.out.print("an indication of where the error occurred "); System.out.println("and a brief error message are"); System.out.println("displayed."); boolean value = true; do { System.out.println(""); // display options for the user System.out.println(""); System.out.println("Choose one of the following options:"); System.out.println(" 1 --> Parse a statement"); System.out.println(" 2 --> Exit the program"); System.out.print("Answer: "); // prompt user for answer System.out.flush(); int answer = getInt(); // read in the user's answer switch (answer) // do what the user wants { case 1: System.out.println(""); System.out.println(""); System.out.print("Statement: "); // prompt for statement System.out.flush(); String statement = getString(); // read in statement Parse parse = new Parse(statement); // create Parse break; case 2: value = false; // to end do-while loop break; default: // invalid answer, display error message System.out.println(""); System.out.println("Invalid answer!"); break; } // end switch } while (value != false); System.in.read(); // to view console } // end try catch (IOException e) { System.out.println("IOException"); } // end catch } //--------------------------------------------------------------------------- /* method getString -reads in a string -precondition: -the user has typed in a valid string -postcondition: -if valid string, string is read in -if not valid string, throws IOException -return: -static */ public static String getString() throws IOException { InputStreamReader isr = new InputStreamReader(System.in); BufferedReader br = new BufferedReader(isr); String s = br.readLine(); return s; } //--------------------------------------------------------------------------- /* method getInt -reads in an integer -precondition: -the user has typed in a valid integer -postcondition: -if valid integer, integer is read in -if not valid integer, throws IOException -return: -static */ public static int getInt() throws IOException { String s = getString(); return Integer.parseInt(s); } //--------------------------------------------------------------------------- } // end class Parser