parser.java

基于算符优先关心的

package parser;

import java.util.ArrayList;

import exceptions.DividedByZeroException;
import exceptions.EmptyExpressionException;
import exceptions.ExpressionException;
import exceptions.FunctionCallException;
import exceptions.LexicalException;
import exceptions.MissingLeftParenthesisException;
import exceptions.MissingOperandException;
import exceptions.MissingOperatorException;
import exceptions.MissingRightParenthesisException;
import exceptions.TrinaryOperationException;
import exceptions.TypeMismatchedException;
/**
 * main program of the Syntax Analysis
 * @author Yuanhang Yang
 *
 */
public class Parser {

	/**function: initial a parser with expression,and $ is pushed into stack prefix
	 * 
	 * @param expression
	 * @throws ExpressionException
	 * 
	 */
	public Parser(String expression) throws ExpressionException {
		token = new Token(expression.toLowerCase());
		prefix.push(new Terminal(TokenType.dollor, "$"));
	}

	Token token = null;

	Terminal curter = null;//record the current token

	Terminal topOper = null;//the most top Terminal

	SymbolStack prefix = new SymbolStack();//a stack stores the expression and $

	OppTable table = new OppTable();
/**function: get the next token 
 * 
 * @return		the next token
 * @throws LexicalException
 */
	public Terminal nextToken() throws LexicalException {
		return token.nexttoken();
	}
/**function:The most important function of the Syntax Analysis.when ty=0/-1,do the 
 * shift();when ty=1,do the reduce(),else error().
 * @return	the evaluation result 
 * @throws ExpressionException
 */
	public double parse() throws ExpressionException {
		curter = nextToken();

		if (curter.tokenType == TokenType.dollor)
			throw new EmptyExpressionException();

		while (true) {

			Terminal top = (Terminal) prefix.getFirstTerminal();
			if (top.tokenType == TokenType.dollor
					&& curter.tokenType == TokenType.dollor)
				break;

			int ty = table.get(top.tokenType, curter.tokenType);
			switch (ty) {
			case -1:
			case 0:
				shift();
				curter = nextToken();
				break;
			case 1:
				reduce();
				break;
			default:
				error(ty);
			}
		}

		if (prefix.peek().tokenType == TokenType.BoolExpr)
			throw new TypeMismatchedException();
		else if(prefix.peek().tokenType != TokenType.ArithExpr)
			throw new ExpressionException();
		return (Double) (((NonTerminal) prefix.peek()).v);
	}
/**function: deal with the syntax exceptions
 * 
 * @param t		the value of table[top][curter]
 * @throws ExpressionException
 */
	public void error(int t) throws ExpressionException {
		if (t == 2)
			throw new MissingOperatorException();
		else if (t == 3)
			throw new MissingOperandException();
		else if (t == 4) {
			throw new MissingLeftParenthesisException();
		} else if (t == 5) {
			throw new MissingRightParenthesisException();
		} else if (t == 6) {
			throw new FunctionCallException();
		} else if (t == 7) {
			throw new TrinaryOperationException();
		} else if (t == 8) {
			throw new TypeMismatchedException();
		} else
			throw new ExpressionException();
	}
/**function: the action of shift.push curter into the stack prefix
 *
 */
	public void shift() {
		prefix.push(curter);
	}
/**function:the action of reduce.
 * 
 * @throws ExpressionException
 */
	public void reduce() throws ExpressionException {

		ArrayList<Symbol> param = new ArrayList<Symbol>();
		Terminal curTer = null;
		Symbol temp = null;
		do {
			temp = prefix.pop();
			if (temp.tokenType <= TokenType.dollor)
				curTer = (Terminal) temp;
			param.add(0, temp);

			temp = prefix.peek();

			if (curTer != null && temp.tokenType <= TokenType.dollor
					&& table.get(temp.tokenType, curTer.tokenType) == -1)
				break;

		} while (true);

		reduce(param);

	}
/**function: reduce all kinds of productions according to the size of the production.
 * 
 * @param param
 * 			a vessel contain the tokens ready to be reduce
 * @throws ExpressionException
 */
	public void reduce(ArrayList<Symbol> param) throws ExpressionException {
		Symbol first = param.get(0);

		if (param.size() == 1) {
			if (first.tokenType == TokenType.number) { //
				double v = Double.parseDouble(((Terminal) first).str);
				prefix.push(new NonTerminal(TokenType.ArithExpr, v));
			} else if (first.tokenType == TokenType.bool) {
				boolean v = Boolean.parseBoolean(((Terminal) first).str);
				prefix.push(new NonTerminal(TokenType.BoolExpr, v));
			} else
				throw new MissingOperandException();
		}

		else if (param.size() == 2) {
			if (first.tokenType == TokenType.negative) {
				NonTerminal t = arithExpr(param.get(1));
				prefix.push(new NonTerminal(TokenType.ArithExpr,
						0 - (Double) (t.v)));
			} else if (first.tokenType == TokenType.not) {
				NonTerminal t = boolExpr(param.get(1));
				prefix.push(new NonTerminal(TokenType.BoolExpr,
						!(Boolean) (t.v)));
			} else
				throw new MissingOperandException();
		}

		else if (param.size() == 3) {
			if (first.tokenType == TokenType.leftbracket) {
				if (param.get(2).tokenType != TokenType.rightbracket)
					throw new MissingRightParenthesisException();
				Symbol s1 = param.get(1);
				if (s1.tokenType == TokenType.ArithExpr) {
					prefix.push(new NonTerminal(TokenType.ArithExpr,
							((NonTerminal) s1).v));
				} else if (s1.tokenType == TokenType.BoolExpr) {
					prefix.push(new NonTerminal(TokenType.BoolExpr,
							((NonTerminal) s1).v));
				} else
					throw new MissingOperandException();
			} else if (first.tokenType == TokenType.ArithExpr) {
				double v1 = (Double) ((NonTerminal) first).v;
				NonTerminal t = arithExpr(param.get(2));
				double v2 = (Double) t.v;
				Symbol s1 = param.get(1);
				if (s1.tokenType == TokenType.and
						| s1.tokenType == TokenType.or)
					throw new TypeMismatchedException();
				else if (s1.tokenType == TokenType.add_sub) {
					if (((Terminal) s1).str.equals("+"))
						prefix.push(new NonTerminal(TokenType.ArithExpr, v1
								+ v2));
					else
						prefix.push(new NonTerminal(TokenType.ArithExpr, v1
								- v2));
				} else if (s1.tokenType == TokenType.mult_div) {
					if (((Terminal) s1).str.equals("*"))
						prefix.push(new NonTerminal(TokenType.ArithExpr, v1
								* v2));
					else {
						if (v2 == 0.0)
							throw new DividedByZeroException();
						prefix.push(new NonTerminal(TokenType.ArithExpr, v1
								/ v2));
					}
				} else if (s1.tokenType == TokenType.power) {
					prefix.push(new NonTerminal(TokenType.ArithExpr, Math.pow(
							v1, v2)));
				} else if (s1.tokenType == TokenType.relop) {
					if (((Terminal) s1).str.equals(">"))
						prefix
								.push(new NonTerminal(TokenType.BoolExpr,
										v1 > v2));
					else if (((Terminal) s1).str.equals(">="))
						prefix.push(new NonTerminal(TokenType.BoolExpr,
								v1 >= v2));
					else if (((Terminal) s1).str.equals("<"))
						prefix
								.push(new NonTerminal(TokenType.BoolExpr,
										v1 < v2));
					else if (((Terminal) s1).str.equals("<="))
						prefix.push(new NonTerminal(TokenType.BoolExpr,
								v1 <= v2));
					else if (((Terminal) s1).str.equals("<>"))
						prefix.push(new NonTerminal(TokenType.BoolExpr,
								v1 != v2));
					else if (((Terminal) s1).str.equals("="))
						prefix.push(new NonTerminal(TokenType.BoolExpr,
								v1 == v2));
				} else
					throw new MissingOperandException();
			} else if (first.tokenType == TokenType.BoolExpr) {
				boolean v1 = (Boolean) ((NonTerminal) first).v;
				NonTerminal t = boolExpr(param.get(2));
				boolean v2 = (Boolean) t.v;
				Symbol s1 = param.get(1);
				if (s1.tokenType == TokenType.and) {
					prefix.push(new NonTerminal(TokenType.BoolExpr, v1 && v2));
				} else if (s1.tokenType == TokenType.or)
					prefix.push(new NonTerminal(TokenType.BoolExpr, v1 || v2));
				else
					throw new MissingOperandException();
			} else throw new MissingOperandException();
		}

		else if (param.size() == 4) {
			if (first.tokenType == TokenType.fun) {
				if (((Terminal) first).str.equals("min")
						|| ((Terminal) first).str.equals("max"))
					throw new MissingOperandException();
				if (param.get(1).tokenType != TokenType.leftbracket)
					throw new MissingLeftParenthesisException();
				else if (param.get(3).tokenType != TokenType.rightbracket)
					throw new MissingRightParenthesisException();
				NonTerminal s2 = arithExpr(param.get(2));
				if (((Terminal) first).str.equals("sin"))
					prefix.push(new NonTerminal(TokenType.ArithExpr, Math
							.sin((Double) s2.v)));
				else
					prefix.push(new NonTerminal(TokenType.ArithExpr, Math
							.cos((Double) s2.v)));
			} else if(first.tokenType == TokenType.question){
				throw new MissingOperandException();
			} else throw new MissingOperandException();
		}

		else if (param.size() == 5) {
			if (param.get(1).tokenType != TokenType.question
					|| param.get(3).tokenType != TokenType.colon)
				throw new MissingOperandException();
			NonTerminal s0 = boolExpr(param.get(0));
			NonTerminal s2 = arithExpr(param.get(2));
			NonTerminal s4 = arithExpr(param.get(4));

			double v = (Boolean) s0.v ? (Double) s2.v : (Double) s4.v;

			prefix.push(new NonTerminal(TokenType.ArithExpr, v));
		}

		else if (param.size() > 5) {
			if (first.tokenType == TokenType.fun) {
				if (((Terminal) first).str.equals("sin")
						|| ((Terminal) first).str.equals("cos"))
					throw new FunctionCallException();
				if (param.get(1).tokenType != TokenType.leftbracket)
					throw new MissingLeftParenthesisException();
				else if (param.get(param.size() - 1).tokenType != TokenType.rightbracket)
					throw new MissingRightParenthesisException();
				NonTerminal nt = null;
				ArrayList<Double> paralist = new ArrayList<Double>();
				for (int i = 2; i < param.size() - 1; i += 2) {
					nt = arithExpr(param.get(i));

					paralist.add((Double) nt.v);

					if (param.get(i + 1).tokenType != TokenType.comma) {
						if (i == param.size() - 2)
							break;
						throw new FunctionCallException();
					}

				}
				if (((Terminal) first).str.equals("max")) {
					double max = paralist.get(0);
					for (int i = 1; i < paralist.size(); ++i) {
						if (max < paralist.get(i))
							max = paralist.get(i);
					}
					prefix.push(new NonTerminal(TokenType.ArithExpr, max));
				} else {
					double min = paralist.get(0);
					for (int i = 1; i < paralist.size(); ++i) {
						if (min > paralist.get(i))
							min = paralist.get(i);
					}
					prefix.push(new NonTerminal(TokenType.ArithExpr, min));
				}
			} else
				throw new ExpressionException();
		}
	}
/**function：get a arithExpr NonTerminal
 * 
 * @param s		Symbol
 * @return		(NonTerminal) s
 * @throws ExpressionException
 */
	private NonTerminal arithExpr(Symbol s) throws ExpressionException {
		if (s.tokenType == TokenType.ArithExpr)
			return (NonTerminal) s;
		else if (s.tokenType == TokenType.BoolExpr)
			throw new TypeMismatchedException();
		else
			throw new MissingOperandException();
	}
/**function:get a boolExpr NOnTerminal
 * 
 * @param s		symbol
 * @return 	(NonTerminal) s
 * @throws ExpressionException
 */
	private NonTerminal boolExpr(Symbol s) throws ExpressionException {
		if (s.tokenType == TokenType.BoolExpr)
			return (NonTerminal) s;
		else if (s.tokenType == TokenType.ArithExpr)
			throw new TypeMismatchedException();
		else
			throw new MissingOperandException();
	}

}