[MyBNFGrammar.java ver1] #java

MyBNFGrammar01.java

 
/**
 *Created on Oct 21, 2009
 *http://www.java-forums.org/new-java/22195-help-bnf-grammar-program-using-recursive-descent-parsing.html
 */
 

/**
A ::= I "=" E
E ::= T "+" E | T "-" E | T
T ::= P "*" T | P "/" T | P
P ::= I | L | "("E")"
I ::= [a..z]
L ::= [0..9]

<program> ::= <stmts>
<stmts> ::= <stmt> | <stmt> ; <stmts> 
<stmt> ::= skip | var := <expr>
		| if \(<lexpr>\) then \(<stmts>\) else \(<stmts>\)
		| while \(<lexpr>\) do \(<stmts>\) 
<expr> ::= <term> <exprs> | <term>
<exprs> ::= <addop> <term> <exprs> | <addop> <term> 
<term> ::= <factor> <terms> | <factor>
<terms> ::= \* <factor> <terms> | \* <factor>
<factor> ::= integer | var | \( <expr> \)
<lexpr> ::= <lterm> <lexprs> | <lterm> 
<lexprs> ::= and <lterm> <lexprs> | and <lterm> 
<lterm> ::= not <lfactor> | <lfactor>
<lfactor> ::= true | false | <expr> <relop> <expr>
<relop> ::= <= | =
<addop> ::= \+ | \-
<EOF> ::= #
*/
import java.util.Scanner;

public class MyBNFGrammar {
  Scanner reader;
   
  public MyBNFGrammar(String in) {
	 // System.out.println("String in is " + in + "\n");
    this.reader = new Scanner(in); // .useDelimiter("#"); // End of Feed
    //System.out.println("reader intialized with " + reader.hasNext() + "\n");
  }
    
  public Token getNextToken() {
    Token t = null;
   
    try {
    if (reader.hasNext()){
    String value = reader.next();
    if (value == "#") { value = null; }
    System.out.println("value is " + value);
    t = new Token(value);
    System.out.println("Made t.value: " + t.value);
    	}
    }
    catch (Exception e) {System.out.println("Got an error assigning next token\n"); };
    return t;
  }
   
  /**
   * <stmts> ::= <stmt> | <stmt> ; <stmts>
   * @return
   */
  protected boolean stmts() {  
	  System.out.println("MADE IT TO STMTS");
    if (!stmt()) {
      return false;
    }
    Token t = getNextToken();
    
    if (t == null) {
      return true;
    }
    if (!TokenType.PUNCT_SEMIC.equals(t.type)) {
    	if (!stmts()){
    		return false;
    	}
    	return true;
     }
     return true;
    
  }
   
  /**
   * stmt ::= skip | var := <expr>
   *		| if \( <lexpr> \) then \( <stmts> \) else \( <stmts> \)
   * 		| while \( <lexpr> \) do \( <stmts> \)
   * @return
   */
  protected boolean stmt() {
	System.out.println("MADE IT TO stmt");
    if (!chr()) {
      return false;
    }
    
    Token t = getNextToken();
    
    if (t == null) {
      return true;   //no more input done
    }
    
    if (!TokenType.OP_EQUALS.equals(t.type) ) {
    		return false;
    }
   
    Token t2 = getNextToken();
    
    if (t2 == null){
    	return false;
    }
    System.out.println("MADE IT TO stmt2");
    if(!stmt()){
    	return false;
    }
    
     return true;
  }
  
 /**
  * <expr> ::= <term> <exprs> | <term> 
  * @return
  */
   
  protected boolean expr() {
	  if (!term()) {
	      return false;
	    }
	  
	    Token t = getNextToken();
	    if (t == null) {
	      return true;
	    }
	    
	    if (! exprs()){
	    	return false;
	    }
	  return true;  
  	}
  
  /**
   *  <term> := <factor> <term> | <factor>
   * @return
   */
  protected boolean term() {
	  if (!factor()) {
	      return false;
	    }
	  Token t = getNextToken();
	    if (t == null) {
	      return true;
	    }
	    
	    if (! term()){
	    	return false;
	    }
	  return true;
}

  /**
   * <terms> ::= \* <factor> <terms> | \* <factor>
   * @return
   */
  protected boolean terms() {
    if (!factor()) {
      return false;
    }
    Token t = getNextToken();
    if (t == null) {
      return true;
    }
 
    if (TokenType.OP_MULTIPLY.equals(t.type) || TokenType.OP_DIVIDE.equals(t.type) ) {
      if (!terms()) {
        return false;
      }
      return true;
    }
     
    return true;
  }
   
protected boolean exprs() {
	
	return true;
}


  /**
   * P ::= INT | CHAR | "("E")"
   * <factor> ::= integer | var | \( <expr> \)
   */
  protected boolean factor() {
    // because we don't have the push back ability we would have in an LALR parser,
    // we don't invoke the I, L functions recursively.
    Token t = getNextToken();
    if (t == null) {
      return false;
    }
    switch (t.type) {
      case CHR:
        return true;
         
      case INTEGER:
        return true;
         
      case PUNCT_LEFTPAREN:
        if (!stmt()) {
          return false;
        }
        Token t2 = getNextToken();
        if (t2 == null) {
          return false;
        }
        if (!TokenType.PUNCT_RIGHTPAREN.equals(t2.type)) {
          return false;
        }
        return true;
        
      default:
        return false;
    } // switch
  }
   
  /**
   * CHR ::= [a..z]
   * @return
   */
  protected boolean chr() {
	
    Token t = getNextToken();
    if (t == null) {
        return false;
      }
   
    if (t.value.equals("#")){
    	 System.out.println("MADE IT TO EOF");
    	return TokenType.EOF.equals(t.type);
    }
    
    System.out.println("MADE IT TO chr");
    return TokenType.CHR.equals(t.type);
  }
   
  /**
   * INTEGER ::= [0..9]
   * @return
   */
  protected boolean integer() {
    Token t = getNextToken();
    if (t == null) {
      return false;
    }
    return TokenType.INTEGER.equals(t.type);
  }
   
  /**
   * Invokes the parser. Expects the standard input to be the string to validate.
   * @param args
   */
  public static void main(String[] args) {
//      Scanner scan = new Scanner(System.in);
//      String str = scan.nextLine();
	  String str = "a = b #";
	  String str2 = "1 #";
      MyBNFGrammar g = new MyBNFGrammar(str);
      boolean result = g.stmts();
      System.out.println("The string \"" + str + "\" is " + (result ? "" : "not ") + "in the language.");
//      scan.close();  
      }
      
   
	
}