parser.java

解释器是用于分析简单的算术运算, 适用于初学者开发自己的智能系统.

/* 
   This module contains the recursive descent
   parser that does not use variables.
   */
 
 import java.io.*;

// Exception class for parser errors.
class ParserException extends Exception {
  String errStr; // describes the error
  
  public ParserException(String str) {
    errStr = str;
  }
  
  public String toString() {
    return errStr;
  }
}

class Parser{
  // These are the token types
  final int NONE = 0;
  final int DELIMITER = 1;
  final int VARIABLE = 2;
  final int NUMBER = 3;
  
  // These are the types of syntax errors.
  final int SYNTAX = 0;
  final int UNBALPARENS = 1;
  final int NOEXP = 2;
  final int DIVBYZERO = 3;
  
  // This token indicates end-of-expression.
  final String EOE = "\0";
  
  private String exp;   // refers to expression string
  private int expIdx;   // current index into the expression
  private String token; // holds current token
  private int tokType;  // holds token's type
  
  // Parser entry point.
  public double evaluate(String expstr) throws ParserException
  {
  	double result;
  	exp = expstr;
  	expIdx = 0;
  	
  	getToken();
//    System.out.println("Get token: " + token);
  	
  	if(token.equals(EOE))
  	  handleErr(NOEXP); // no expression present
  // Parse and evaluate the expression.
    result = evalExp2();
    
    if(!token.equals(EOE)) // last token must be EOE
      handleErr(SYNTAX);
      
    return result;
      	  
  }
  
  // Add or subtract two terms.
  private double evalExp2() throws ParserException
  {
  	char op;
  	double result;
  	double partialResult;
  	
  	result = evalExp3();
  	
  	while((op = token.charAt(0)) == '+' || op == '-' )
  	{
  		getToken();
  		partialResult = evalExp3();
  		switch(op)
  		{
  			case '-':
  			  result = result - partialResult;
  			break;
  			case '+':
  			  result = result + partialResult;
  			break;
  			
  		}
  	}
  	return result;
  	
  }
  
  // Multiply or divide two factors.
  private double evalExp3() throws ParserException
  {
  	char op;
  	double result;
  	double partialResult;
  	
  	result = evalExp4();
  	
  	while((op = token.charAt(0)) == '*' || op == '/' || op == '%')
  	{
  		getToken();
  		partialResult = evalExp4();
  		switch(op)
  		{
  			case '*':
  			  result = result * partialResult;
  			break;
  			case '/':
  			  if(partialResult == 0.0)
  			    handleErr(DIVBYZERO);
  			  result = result / partialResult;
  			break;
  			case '%':
    System.out.println("%:  " + token);

  			  if(partialResult == 0.0)
  			    handleErr(DIVBYZERO);
  			  result = result % partialResult;
  			break;
  		}
  	}
  	return result;
  }
  
  // Process an exponent.
  private double evalExp4() throws ParserException
  {
  	double result;
  	double partialResult;
  	double ex;
  	int t;
  	
  	result = evalExp5();
  	
  	if(token.equals("^"))
  	{
  		getToken();
  		partialResult = evalExp4();
  		ex = result;
  		if(partialResult == 0.0)
  		{
  			result = 1.0;
  		} 
  		else
  		{
  			for(t = (int)partialResult - 1; t>0 ; t--)
  			  result = result * ex;
  	    }
  	}
  	return result;
  	
  }
  // Evaluate a unary + or -.
  private double evalExp5() throws ParserException
  {
  	double result;
  	String op;
  	
  	op = "";
  	if((tokType == DELIMITER) && 
  	    token.equals("+") || token.equals("-"))
  	{
  		op = token;
  		getToken();
  	}
  	result = evalExp6();
  	
  	if(op.equals("-"))
  	   result =- result;
  	
  	return result;
  }
  
  // Process a parenthesized expression.
  private double evalExp6() throws ParserException
  {
  	double result;
  	if(token.equals("("))
  	{
  		getToken();
  		result = evalExp2();
  		if(!token.equals(")"))
  		  handleErr(UNBALPARENS);
  		getToken();
  	}
  	else
  	{
  		result = atom();
  	}
  	return result;
  }
  // Get the value of a number.
  private double atom() throws ParserException
  {
  	double result = 0.0;
  	
  	switch(tokType)
  	{
  		case NUMBER:
  		  try{
  		    result = Double.parseDouble(token);
  		}catch(NumberFormatException exc){
  			handleErr(SYNTAX);
  		}
  		getToken();
  		break;
  		default:
  		  handleErr(SYNTAX);
  		break;
  	}
  	return result;
  }

  // Handle an error.
  private void handleErr(int error) throws ParserException
  {
  	String[] err = {
  		"Syntax Error",
  		"Unbalanced Parentheses",
  		"No Expression Present",
  		"Division by Zero"
  	};
  	
  	throw new ParserException(err[error]);
  	
  }

  // Obtain the next token.
  private void getToken()
  {
  	tokType = NONE;
  	token = "";
  // Check for end of expression
//    System.out.println("Expression length " + exp.length());
    if(expIdx == exp.length())
    {
    	token = EOE;
    	return;
    }
    
  // Skip over white space.
    while(expIdx < exp.length() && Character.isWhitespace(exp.charAt(expIdx))) ++ expIdx;
  
//    System.out.println("Skip over white space: " + token);
  // Trailing white space ends expression.
    if(expIdx == exp.length())
    {
    	token = EOE;
    	return;
    }
//    System.out.println("Trailing ending white space: " + token);
    
    if(isDelim(exp.charAt(expIdx)))
    {
    	token += exp.charAt(expIdx);
    	expIdx ++;
    	tokType = DELIMITER;
    }
    else if(Character.isLetter(exp.charAt(expIdx)))
    {
    	while(!isDelim(exp.charAt(expIdx)))
    	{
    		token += exp.charAt(expIdx);
    		expIdx ++;
    		if(expIdx >= exp.length())break;
    		
    	}
    	tokType = VARIABLE;
    }
    else if(Character.isDigit(exp.charAt(expIdx)))
    {
    	while(!isDelim(exp.charAt(expIdx)))
    	{
    		token += exp.charAt(expIdx);
    		expIdx ++;
    		if(expIdx >= exp.length())
    		    break;
    	}
    	tokType = NUMBER;
    	
    }
    else
    {
    	token = EOE;
    	return;
    }
  }

  
  // Return true if c is a delimiter.
  private boolean isDelim(char c)
  {
  	if((" +-/*^=()".indexOf(c) != -1))
  	  return true;
  	return false;
  }

  
}