constitutetree.java

用java写的语句级语法分析器。用于一些软件对输入的语句进行语法分析

package Expression;

import java.util.ArrayList;

public class ConstituteTree {
	private Expression expression;
	private String Command;
	private int Len,Order;
	private int IncreasPRI = 0;//优先级增量
	private ArrayList Paralist = new ArrayList();//值数组
	private ArrayList Operlist = new ArrayList();//运算符数组
	private ArrayList Bracketlist = new ArrayList();//括号数组
	private ArrayList Alllist = new ArrayList();
	private Expression[] para;
	
	public ConstituteTree(String command) {
		super();
		// TODO Auto-generated constructor stub
		Command = command.trim() + " ";
		Len = Command.length();
		expression = new Expression(2);
	}
	
	//下面的函数实现的了将表达式中的所有值，括号和运算符分类
	public void Gen(){
		String str = "";
		boolean IsKey = false,ISDoubleKey = false,IsKeyWords =false;
		char parameter ;
		Order=0;
		for(int i=0;i<Len;i++){
			parameter = Command.charAt(i);
			if (parameter =='('){
				Bracketlist.add(new Bracket(0,Order));
				Alllist.add(new Bracket(0,Order));
				Order++;
				IncreasPRI += 4;
				continue;
			}
			if (parameter ==')'){
				if (str!="") {
					Paralist.add(new Expression(-1,-1,Order,str));
					Alllist.add(new Expression(-1,-1,Order,str));
					Order++;
					str = "";
					IsKey = false;
				}
				Bracketlist.add(new Bracket(1,Order));
				Alllist.add(new Bracket(1,Order));
				Order++;
				IncreasPRI -= 4;
				continue;
			}
			else if(parameter =='\"'){
				if (str!="") {
					Paralist.add(new Expression(-1,-1,Order,str));
					Alllist.add(new Expression(-1,-1,Order,str));
					Order++;
					str = "";
					IsKey = false;
				}
				Bracketlist.add(new Bracket(2,Order));
				Alllist.add(new Bracket(2,Order));
				Order++;
				if (Command.indexOf("\"",i+1) != -1){
					Paralist.add(new Expression(-1,-1,Order,Command.substring(i+1,Command.indexOf("\"",i+1))));
					Alllist.add(new Expression(-1,-1,Order,Command.substring(i+1,Command.indexOf("\"",i+1))));
					Order++;
					Bracketlist.add(new Bracket(2,Order));
					Alllist.add(new Bracket(2,Order));
					Order++;
					i= Command.indexOf("\"",i+1);
				}
				continue;
			}
			for(int j = 0; j<OperConsts.AllChar.length;j++){
				if (parameter == OperConsts.AllChar[j])
					IsKey = true;
			}
			if (!IsKey){
				str +=  parameter;
			}			
			else{
				for(int j = 7; j<OperConsts.AllChar.length;j++){
					if (parameter == OperConsts.AllChar[j]){
						if (Command.charAt(i+1) == OperConsts.AllChar[6])
								ISDoubleKey = true;
					}
				}
				if (ISDoubleKey){
					if (str!="") {
						Paralist.add(new Expression(-1,-1,Order,str));
						Alllist.add(new Expression(-1,-1,Order,str));
						Order++;
						str = "";
						IsKey = false;
					}
					Operlist.add(new Expression(0,1+IncreasPRI,Order,Command.substring(i,i+2)));
					Alllist.add(new Expression(0,1+IncreasPRI,Order,Command.substring(i,i+2)));
					i++;
					Order++;
					ISDoubleKey = false;
					IsKey = false;
				}					
				else{
					if (parameter == ' ')
						IsKey = false;
					else if (parameter == '='){
						if (str!="") {
							Paralist.add(new Expression(-1,-1,Order,str));
							Alllist.add(new Expression(-1,-1,Order,str));
							Order++;
							str = "";
							IsKey = false;
						}
						Operlist.add(new Expression(0,1+IncreasPRI,Order,Command.substring(i,i+1)));
						Alllist.add(new Expression(0,1+IncreasPRI,Order,Command.substring(i,i+1)));
						Order++;
						IsKey = false;
					}
					else if (parameter == '+'||parameter == '-'){
						if (str!="") {
							Paralist.add(new Expression(-1,-1,Order,str));
							Alllist.add(new Expression(-1,-1,Order,str));
							Order++;
							str = "";
							IsKey = false;
						}
						Operlist.add(new Expression(0,2+IncreasPRI,Order,Command.substring(i,i+1)));
						Alllist.add(new Expression(0,2+IncreasPRI,Order,Command.substring(i,i+1)));
						Order++;
						IsKey = false;
					}
					else if (parameter == '*'||parameter == '/'||parameter == '%'){
						if (str!="") {
							Paralist.add(new Expression(-1,-1,Order,str));
							Alllist.add(new Expression(-1,-1,Order,str));
							Order++;
							str = "";
							IsKey = false;
						}
						Operlist.add(new Expression(0,3+IncreasPRI,Order,Command.substring(i,i+1)));
						Alllist.add(new Expression(0,3+IncreasPRI,Order,Command.substring(i,i+1)));
						Order++;
						IsKey = false;
					}
					else{
						if (str!="") {
							Paralist.add(new Expression(-1,-1,Order,str));
							Alllist.add(new Expression(-1,-1,Order,str));
							Order++;
							str = "";
							IsKey = false;
						}
						Operlist.add(new Expression(0,1+IncreasPRI,Order,Command.substring(i,i+1)));
						Alllist.add(new Expression(0,1+IncreasPRI,Order,Command.substring(i,i+1)));
						Order++;
						IsKey = false;
					}
				}
				for(int j = 0; j<OperConsts.Keywords.length;j++){
					if (str.equals(OperConsts.Keywords[j]))
						IsKeyWords = true;
				}
				if (IsKeyWords){
					Operlist.add(new Expression(0,0+IncreasPRI,Order,str));
					Alllist.add(new Expression(0,0+IncreasPRI,Order,str));
					Order++;
					str = "";
					IsKey = false;
					IsKeyWords = false;
				}
				else if (str!="") {
					Paralist.add(new Expression(-1,-1,Order,str));
					Alllist.add(new Expression(-1,-1,Order,str));
					Order++;
					str = "";
					IsKey = false;
				}
			}			
		}
		Analyse();
	}

	//分析并得到二叉树
	private void Analyse(){
		Expression[] oper= new Expression[Operlist.size()];
		Operlist.toArray(oper);
		for (int i = 0;i<oper.length; i++){
			if (i==0){
				expression.setRightExp(oper[i]);
				oper[i].setParent(expression);
			}
			else{
				Expression temp = new Expression();
				temp = oper[i-1];
				if (temp.getPRI() < oper[i].getPRI()){
					oper[i].setParent(temp);
					temp.setRightExp(oper[i]);
				}
				else{
					while(temp.getParent() != null){
						if (temp.getPRI() >= oper[i].getPRI() && temp.getParent().getPRI()<oper[i].getPRI()){
							temp.getParent().setRightExp(oper[i]);
							oper[i].setParent(temp.getParent());
							temp.setParent(oper[i]);
							oper[i].setLeftExp(temp);
							break;
						}
						temp = temp.getParent();
					}
				}
			}
		}
		para = new Expression[Paralist.size()];
		Paralist.toArray(para);
		AddPara(0,expression);
		Checkup(expression);
	}
	


	private void Checkup(Expression expression) {		
		for (int i=0;i< para.length;i++){
			char [] ch = new char [para[i].getParameter().length()];
			para[i].getParameter().getChars(0,para[i].getParameter().length(),ch,0);
			int m =0;
			if (ch[0] > '0'&& ch [0]< '9'){
				for (int j=1; j<para[i].getParameter().length();j++){
					if (ch[j] == '.' && m ==0) m++ ;
					else if (ch[j] < '0'||ch[j]>'9'){
						System.out.println("存在非法的标识符。");
						return;
					}
				}
			}
		}
		Expression[] oper= new Expression[Operlist.size()];
		Operlist.toArray(oper);
		Bracket[] brac = new Bracket[Bracketlist.size()];
		Bracketlist.toArray(brac);
		int left=0,right=0,semi=0;
		if (oper.length +1 != para.length){
			System.out.println("值与运算符不能对应。");
			return;
		}
		for (int i=0;i<Alllist.size();i++){
			if (Alllist.get(i) instanceof Bracket){
				if (((Bracket) Alllist.get(i)).getType() == 0 ){
					if (i+1 >= Alllist.size()||(Alllist.get(i+1) instanceof Expression && ((Expression) Alllist.get(i+1)).getType() == 0)){
						WrongOutput();
						return;
					}
					if (i-1 > 0){
						if ((Alllist.get(i-1) instanceof Expression && ((Expression) Alllist.get(i-1)).getType() == -1)){
							WrongOutput();
							return;
						}
					}
				}
				else if (((Bracket) Alllist.get(i)).getType() == 1){
					if (i-1 < 0||((Alllist.get(i-1) instanceof Expression && ((Expression) Alllist.get(i-1)).getType() == 0))){
						WrongOutput();
						return;
					}
					if (i+1 < Alllist.size()){
						if ((Alllist.get(i+1) instanceof Expression && ((Expression) Alllist.get(i+1)).getType() == -1)){
							WrongOutput();
							return;
						}
					}
				}
			}
		}
		
		for (int i= 0;i<brac.length;i++){
			if(i<brac.length && brac[i].getType() == 0){
				left ++;
			}
			if(i<brac.length && brac[i].getType() == 1){
				right ++;
			}
			if(i<brac.length && brac[i].getType() == 2){
				semi ++;
			}
		}
		if (left != right){
			System.out.println("括号不能对称。");
			return;
		}
		if (semi%2 != 0){
			System.out.println("双引号用法错误。");
			return;
		}
		for(int i=0 ;i<oper.length;i++){
			
			if (oper[i].getLeftExp() == null){
				System.out.println("缺少运算的值。");
				return;
			}
			else if(oper[i].getRightExp() == null){
				System.out.println("缺少运算的值。");
				return;
			}
			else if (oper[i].getParent() == null){
				System.out.println("最终的逻辑运算符不至一个。");
				return;
			}
			else if  (i+1 < oper.length ){
				if (oper[i].getPosition() + 1 == oper[i+1].getPosition()){
					System.out.println("两个运算符中间缺少运算值。");
					return;
				}
			}
			else if (i==oper.length-1){
				break;
			}
		}
		System.out.println("表达式语法正确");
	}

	private void WrongOutput() {
		System.out.println("表达式语法错误，请更正！");
	}

	private int AddPara(int i ,Expression expression){
		try {
			if (expression.getLeftExp()!= null ){
				if(expression.getLeftExp().getType() == 0){
					i = AddPara(i,expression.getLeftExp());
					if (i>para.length){
						WrongOutput();
						return i;
					}
				}
			}
			else{
				if (expression != this.expression){
					expression.setLeftExp(para[i]);
					i++;
				}
			}
			if (expression.getRightExp() != null && expression.getRightExp().getType() == 0){
				i = AddPara(i,expression.getRightExp());
				if (i>para.length){
					WrongOutput();
					return i;
				}
			}
			else{
				expression.setRightExp(para[i]);
				i++;
			}
		} catch (RuntimeException e) {
			// TODO Auto-generated catch block
			return i;
		}
		return i;
	}
}