predict.java

语法分析器

/**
 * according to expression number, deal with suitable stack
 * 
 * @author shirly
 * @version:1.2
 */

public class Predict {
	/**
	 * @param n
	 *            is the expression number according to number deal with the
	 *            four stack
	 */
	public void predict(int n) {
		AST currentAST;
		switch (n) {
		case 1:
			// Program==ProgramHead ProgramBody
			Parse.signStack.push(Type.ProgramBody);
			Parse.signStack.push(Type.ProgramHead);
			break;
		case 2:
			// ProgramHead= Class ID
			Parse.signStack.push(Type.ID);
			Parse.signStack.push(Type.CLASS);
			Parse.treeStack.peek().setType(Type.ID);
			Parse.treeStack.peek().isLeaf = false;
			break;
		case 3:
			// ProgramBody=={Stmt-Sequence}
			Parse.signStack.push(Type.RIGHTBig);
			Parse.signStack.push(Type.Stmt_Sequence);
			Parse.signStack.push(Type.LEFTBig);
			break;
		case 4:
			// Stmt-Sequence== e
			break;
		case 5:
			// Stmt_Sequence== stmt SemiOp Stmt_Sequence
			Parse.signStack.push(Type.Stmt_Sequence);
			Parse.signStack.push(Type.SemiOp);
			Parse.signStack.push(Type.Stmt);
			break;
		case 6:
			// stmt==e
			Parse.treeStack.push(null);
			break;
		case 7:
			// stmt==if_stmt
			Parse.signStack.push(Type.if_stmt);
			AST ifNode = new AST();
			Parse.treeStack.peek().addChild(ifNode);
			Parse.treeStack.push(ifNode);
			break;
		case 8:
			// stmt== while_stmt
			Parse.signStack.push(Type.while_stmt);
			break;
		case 9:
			// stmt== assign-stmt
			Parse.signStack.push(Type.assign_stmt);
			break;
		case 10:
			// stmt== read-stmt
			Parse.signStack.push(Type.read_stmt);
			break;
		case 11:
			// stmt== write_stmt
			Parse.signStack.push(Type.write_stmt);
			break;
		case 12:
			// stmt==varDec_stmt
			Parse.signStack.push(Type.varDec_stmt);
			break;
		case 13:
			// varDec_stmt == TypeDef varIdList
			Parse.signStack.push(Type.varIdList);
			Parse.signStack.push(Type.TypeDef);
			break;
		case 14:
			// TypeDef==BaseType TypeMore
			Parse.signStack.push(Type.TypeMore);
			Parse.signStack.push(Type.BaseType);
			break;
		case 15:
			// BaseType== int
			Parse.signStack.push(Type.INT);
			currentAST = Parse.treeStack.peek();
			AST intNode = new AST(Type.INT);
			intNode.isLeaf = false;
			currentAST.addChild(intNode);
			Parse.treeStack.push(intNode);
			break;
		case 16:
			// BaseType== real
			Parse.signStack.push(Type.REAL);
			currentAST = Parse.treeStack.peek();
			AST realNode = new AST(Type.REAL);
			realNode.isLeaf = false;
			currentAST.addChild(realNode);
			Parse.treeStack.push(realNode);
			break;
		case 17:
			// TypeMore==e
			break;
		case 18:
			// TypeMore== [Exp]
			// tableLL[Type.TypeMore][-Type.LEFTMid] = 18;
			Parse.signStack.push(Type.RIGHTMid);
			Parse.signStack.push(Type.Exp);
			Parse.signStack.push(Type.LEFTMid);
			Parse.opStack.push(new AST(Type.END));
			break;
		case 19:
			// varIdList== ID varListMore
			// tableLL[Type.varIdList][-Type.ID] = 19;
			Parse.signStack.push(Type.varListMore);
			Parse.signStack.push(Type.ID);
			currentAST = Parse.treeStack.peek();
			AST id = new AST(Type.ID);
			id.info = ": ID";
			currentAST.addChild(id);
			Parse.treeStack.push(id);
			break;
		case 20:
			// varListMore == e
			break;
		case 21:
			// varListMore == , varIdList
			Parse.signStack.push(Type.varIdList);
			Parse.signStack.push(Type.COMMA);
			break;
		case 22:
			// read_stmt=read variable;
			Parse.signStack.push(Type.variable);
			Parse.signStack.push(Type.READ);
			currentAST = Parse.treeStack.peek();
			AST read = new AST(Type.READ);
			read.isLeaf = false;
			currentAST.addChild(read);
			Parse.treeStack.push(read);
			Parse.opStack.push(new AST(Type.END));
			break;
		case 23:
			// write_stmt==write (Exp)
			Parse.signStack.push(Type.RIGHTSmall);
			Parse.signStack.push(Type.Exp);
			Parse.signStack.push(Type.LEFTSmall);
			Parse.signStack.push(Type.WRITE);
			currentAST = Parse.treeStack.peek();
			AST write = new AST(Type.WRITE);
			write.isLeaf = false;
			currentAST.addChild(write);
			Parse.opStack.push(new AST(Type.END));
			Parse.treeStack.push(write);
			break;
		case 24:
			// assign_stmt == variable AssignOp Exp
			Parse.signStack.push(Type.Exp);
			Parse.signStack.push(Type.AssignOp);
			Parse.signStack.push(Type.variable);
			break;
		case 25:
			// variable = ID variMore
			Parse.signStack.push(Type.variMore);
			Parse.signStack.push(Type.ID);
			AST idType = new AST(Type.ID);
			idType.isLeaf = false;
			Parse.treeStack.push(idType);
			Parse.numStack.push(idType);
			break;
		case 26:
			// variMore==e
			AST idNode = Parse.treeStack.pop();
			if (Parse.treeStack.peek().getType() == Type.MINUSUNI
					|| Parse.treeStack.peek().getType() == Type.READ) {
				Parse.treeStack.peek().addChild(idNode);
				Parse.opStack.pop();
				Parse.numStack.pop();
				if (Parse.treeStack.peek().getType() == Type.MINUSUNI)
					Parse.treeStack.pop();
			}
			break;
		case 27:
			// variMore= [Exp]
			Parse.treeStack.peek().isLeaf = true;
			Parse.signStack.push(Type.RIGHTMid);
			Parse.signStack.push(Type.Exp);
			Parse.signStack.push(Type.LEFTMid);
			Parse.opStack.push(new AST(Type.END));
			break;
		case 28:
			// if-stmt==if(TestExp){Stmt-sequence}ifMore
			Parse.signStack.push(Type.ifMore);
			Parse.signStack.push(Type.RIGHTBig);
			Parse.signStack.push(Type.Stmt_Sequence);
			Parse.signStack.push(Type.LEFTBig);
			Parse.signStack.push(Type.RIGHTSmall);
			Parse.signStack.push(Type.TestExp);
			Parse.signStack.push(Type.LEFTSmall);
			Parse.signStack.push(Type.IF);
			Parse.treeStack.peek().isLeaf = false;
			Parse.treeStack.peek().setType(Type.IF);
			Parse.opStack.push(null);
			break;
		case 29:
			// ifMore == e
			break;
		case 30:
			// ifMore == else elseMore
			Parse.signStack.push(Type.elseMore);
			Parse.signStack.push(Type.ELSE);
			AST elseNode = new AST(Type.ELSE);
			elseNode.isLeaf = false;
			Parse.treeStack.pop().setRight(elseNode);
			Parse.treeStack.push(elseNode);
			break;
		case 31:
			// elseMore== if-stmt
			Parse.signStack.push(Type.if_stmt);
			AST ifNode2 = new AST();
			Parse.treeStack.pop().addChild(ifNode2);
			Parse.treeStack.push(ifNode2);
			break;
		case 32:
			// elseMore=={stmt-sequence}
			Parse.signStack.push(Type.RIGHTBig);
			Parse.signStack.push(Type.Stmt_Sequence);
			Parse.signStack.push(Type.LEFTBig);
			break;
		case 33:
			// while-stmt==while(TestExp){stmt-sequence}
			Parse.signStack.push(Type.RIGHTBig);
			Parse.signStack.push(Type.Stmt_Sequence);
			Parse.signStack.push(Type.LEFTBig);
			Parse.signStack.push(Type.RIGHTSmall);
			Parse.signStack.push(Type.TestExp);
			Parse.signStack.push(Type.LEFTSmall);
			Parse.signStack.push(Type.WHILE);
			AST whileNode = new AST(Type.WHILE);
			whileNode.isLeaf = false;
			Parse.treeStack.peek().addChild(whileNode);
			Parse.treeStack.push(whileNode);
			Parse.opStack.push(null);
			break;
		case 34:
			// Exp==Term otherTerm
			Parse.signStack.push(Type.otherTerm);
			Parse.signStack.push(Type.Term);
			break;
		case 35:
			int i = priosity(Parse.opStack.peek());
			A: while (!Parse.opStack.isEmpty()) {
				switch (i) {
				case -1:// null
					Parse.opStack.pop();
					break A;
				case 0:// Type.End
					if (Parse.opStack.peek() != null)
						if (Parse.numStack.peek().getType() != Type.END) {
							if (Parse.opStack.peek().getType() == Type.END) {
								Parse.treeStack.peek().addChild(
										Parse.numStack.pop());
								if (Parse.treeStack.peek().getType() == Type.INT
										|| Parse.treeStack.peek().getType() == Type.REAL)
									Parse.treeStack.peek().getDown().setType(
											Type.Exp);
								if (Parse.treeStack.peek().isLeaf
										|| Parse.treeStack.peek().getType() == Type.MINUSUNI)
									Parse.treeStack.pop();
								Parse.opStack.pop();
								i = 0;
								continue A;
							} else {
								if (Parse.opStack.peek().getType() == Type.MINUSUNI) {
									i = 5;
									break;
								}
							}
						} 
							break A;
				case 2:// Type.LEFTSmall
					Parse.opStack.pop();
					if (Parse.opStack.peek() != null)
						if (Parse.opStack.peek().getType() == Type.MINUSUNI) {
							i = 5;
							break;
						}
					break A;
				case 5:// Type.MINUSUNI
					Parse.treeStack.pop().addChild(Parse.numStack.pop());
					Parse.opStack.pop();
					break A;
				default:
					AST right = Parse.numStack.pop();
					AST priNode = Parse.opStack.pop();
					priNode.addChild(Parse.numStack.pop());
					priNode.addChild(right);
					Parse.numStack.push(priNode);
					i = priosity(Parse.opStack.peek());
					break;
				}
			}
			break;
		case 36:
			// otherTerm == AddOp Exp
			Parse.signStack.push(Type.Exp);
			Parse.signStack.push(Type.AddOp);
			AST addOp = new AST(Type.AddOp);
			exp(addOp);
			Parse.treeStack.push(addOp);
			break;
		case 37:
			// Term == Factor otherFactor
			Parse.signStack.push(Type.otherFactor);
			Parse.signStack.push(Type.Factor);
			break;
		case 38:
			// 38. otherFactor == e
			break;
		case 39:
			// 39. otherFactor== MultiOp Term
			Parse.signStack.push(Type.Term);
			Parse.signStack.push(Type.MultiOp);
			AST multiOp = new AST(Type.MultiOp);
			exp(multiOp);
			Parse.treeStack.push(multiOp);
			break;
		case 40:
			// 40. Factor == Sign factorMore
			Parse.signStack.push(Type.factorMore);
			Parse.signStack.push(Type.Sign);
			break;
		case 41:
			// 41. Factor == Num
			Parse.signStack.push(Type.NUM);
			AST num = new AST(Type.NUM);
			Parse.numStack.push(num);
			Parse.treeStack.push(num);
			break;
		case 42:
			// 42. factorMore== (Exp)
			Parse.signStack.push(Type.RIGHTSmall);
			Parse.signStack.push(Type.Exp);
			Parse.signStack.push(Type.LEFTSmall);
			Parse.opStack.push(new AST(Type.LEFTSmall));
			break;
		case 43:
			// 43. factorMore == variable
			Parse.signStack.push(Type.variable);
			break;
		case 44:
			// 44. Sign== e
			break;
		case 45:
			// 45. Sign == MINUSUNI
			Parse.signStack.push(Type.MINUSUNI);
			AST minusuni = new AST(Type.MINUSUNI);
			Parse.treeStack.push(minusuni);
			minusuni.isLeaf = false;
			minusuni.info = "";
			Parse.numStack.push(minusuni);
			Parse.opStack.push(new AST(Type.MINUSUNI));
			break;
		case 46:
			// 46. TestExp == Exp otherExp
			Parse.signStack.push(Type.otherExp);
			Parse.signStack.push(Type.Exp);
			break;
		case 47:
			// 47. otherExp == CmpOp Exp
			Parse.signStack.push(Type.Exp);
			Parse.signStack.push(Type.CmpOp);
			AST cmpOp = new AST(Type.CmpOp);
			Parse.opStack.push(new AST(Type.END));
			exp(cmpOp);
			Parse.treeStack.push(cmpOp);
			break;
		case 48:
			// 48. AddOp == +
			Parse.signStack.push(Type.ADD);
			Parse.treeStack.peek().setType(Type.ADD);
			break;
		case 49:
			// 49. AddOp== MINUSBI
			Parse.signStack.push(Type.MINUSBI);
			Parse.treeStack.peek().setType(Type.MINUSBI);
			break;
		case 50:
			// 50. MultiOp == *
			Parse.signStack.push(Type.MULTI);
			Parse.treeStack.peek().setType(Type.MULTI);
			break;
		case 51:
			// 51. MultiOp== /
			Parse.signStack.push(Type.DIVID);
			Parse.treeStack.peek().setType(Type.DIVID);
			break;
		case 52:
			// 52. CmpOp == <
			Parse.signStack.push(Type.LESS);
			Parse.treeStack.peek().setType(Type.LESS);
			break;
		case 53:
			// 53. CmpOp == >
			Parse.signStack.push(Type.BIGGER);
			Parse.treeStack.peek().setType(Type.BIGGER);
			break;
		case 54:
			// 54. CmpOp == <>
			Parse.signStack.push(Type.NOTEQUAL);
			Parse.treeStack.peek().setType(Type.NOTEQUAL);
			break;
		case 55:
			// 55. CmpOp == ==
			Parse.signStack.push(Type.EQUAL);
			Parse.treeStack.peek().setType(Type.EQUAL);
			break;
		case 56:
			// 56 AssignOp == =
			Parse.signStack.push(Type.ASSIGN);
			AST assign = new AST(Type.ASSIGN);
			assign.isLeaf = false;
			assign.info = ": assign-stmt";
			assign.addChild(Parse.numStack.pop());
			Parse.treeStack.peek().addChild(assign);
			Parse.treeStack.push(assign);
			Parse.opStack.push(new AST(Type.END));
			break;
		case 57:
			// 57:SemiOp == ;
			Parse.signStack.push(Type.SEMI);
			Parse.treeStack.pop();
		default:
			break;
		}
	}

	/**
	 * @param node
	 * @according to the type of the node, return the priosity of the node
	 */
	private int priosity(AST node) {
		if (node == null)
			return -1;
		switch (node.getType()) {
		case Type.END:
			return 0;
		case Type.LESS:
		case Type.BIGGER:
		case Type.NOTEQUAL:
		case Type.EQUAL:
		case Type.CmpOp:
			return 1;
		case Type.LEFTSmall:
			return 2;
		case Type.ADD:
		case Type.MINUSBI:
		case Type.AddOp:
			return 3;
		case Type.MULTI:
		case Type.DIVID:
		case Type.MultiOp:
			return 4;
		case Type.MINUSUNI:
			return 5;
		default:
			return -1;
		}
	}

	/**
	 * if parameter2 > =parameter1,return false; if parameter2<parameter1,return
	 * true;
	 */
	private boolean comparePri(AST node1, AST node2) {
		if (priosity(node1) > priosity(node2)) {
			return true;
		} else
			return false;
	}

	/**
	 * @param node
	 *            if the priosity of the node is bigger than the top node of the
	 *            treeStack,push it to the Stack! else pop the top two node from
	 *            the numStack, and let the two node as the child of the top
	 *            node of the opStack
	 */
	private void exp(AST node) {
		if (comparePri(node, Parse.opStack.peek())) {
			Parse.opStack.push(node);
		} else {
			while (!comparePri(node, Parse.opStack.peek())) {
				AST right = Parse.numStack.pop();
				AST priNode = Parse.opStack.pop();
				priNode.addChild(Parse.numStack.pop());
				priNode.addChild(right);
				Parse.numStack.push(priNode);
			}
			Parse.opStack.push(node);
		}
	}
}