generator.java

编译器

package compiler;

import java.util.Stack;
import java.util.Vector;

public class Generator 
{
	public Vector<TreeNode> expression;
	public Vector<Quaternion> quaternionList;
	public Stack<TreeNode> expressionStack;
	public int index_of_temp_variable;
	public int index_of_quaternion;
		
	public static StringBuffer ourPutOnConsole;
	
	//构造函数
	public Generator()
	{
		expression = new Vector<TreeNode>();
		quaternionList = new Vector<Quaternion>();
		expressionStack = new Stack<TreeNode>();
		index_of_temp_variable = 0;
		index_of_quaternion = 0;
		ourPutOnConsole = new StringBuffer();
	}
	
	//用来判断逆波兰式中的元素是否为操作符
	public boolean isOperator(TreeNode node)
	{
		if(node.name == "+" || node.name == "-" || 
	       node.name == "*" || node.name == "/")
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	
	//生成中间代码
	public void generateMediumCode(TreeNode root , SymbolTable symbolTable)
	{
		index_of_quaternion = generateQuaternionList(root , quaternionList , index_of_quaternion , symbolTable);
		
		Quaternion q = new Quaternion();
		for(int i = 0 ; i < quaternionList.size() ; i ++)
		{
			q = quaternionList.elementAt(i);
			if(q.operator.equals("jnz") || q.operator.equals("j"))
			{
				int num = q.number + q.leapnum;
				q.targetOperand = "" + num;
			}
			
			
			Generator.ourPutOnConsole.append(q.number + ":" + "(" + q.operator + "," +
			           q.sourceOperand1 + "," + q.sourceOperand2 + "," +
			           q.targetOperand + ")" + "\n");
		
			
			System.out.println(q.number + ":" + "(" + q.operator + "," +
					           q.sourceOperand1 + "," + q.sourceOperand2 + "," +
					           q.targetOperand + ")");
			//System.out.println("!!!!!!" + q.leapnum);
		}
		System.out.println(index_of_quaternion + ":" + "END");
	}
	
	public int generateQuaternionList(TreeNode node , Vector<Quaternion> quaternionList , int index , SymbolTable symbolTable)
	{
		expression.clear();
		
		if(node.name == "S" || node.name == "D")
		{
			//规则是S =>D ; S
			if(node.rule == 1)
			{
				index = generateQuaternionList(node.children.elementAt(0) , quaternionList , index , symbolTable);
				index = generateQuaternionList(node.children.elementAt(1) , quaternionList , index , symbolTable);
			}
			
			//规则是S =>A = E
			else if(node.rule == 2)
			{
				generateExpression(expression , node.children.elementAt(2));//对E(表达式)生成逆波兰式
				index = generateQuaternion(expression , quaternionList , index);//把逆波兰式生成四元式,然后将四元式插入四元式链
				
				//生成赋值四元式：(:=,中间变量,_,目标变量)插入到四元式链
				quaternionList.add(new Quaternion(index++ , ":=" , quaternionList.lastElement().targetOperand ,
						                          "_" , node.children.get(0).name));
			}
			
			//规则是S =>if E then { S } S
			else if(node.rule == 3)
			{
				generateExpression(expression , node.children.get(0));//对E(表达式)生成逆波兰式
				index = generateQuaternion(expression , quaternionList , index);//把逆波兰式生成四元式,然后将四元式插入四元式链
				
				Vector<Quaternion> quaternionList1 = new Vector<Quaternion>();
				Vector<Quaternion> quaternionList2 = new Vector<Quaternion>();
				//分别对S =>if E then { S } S的后两个S生成四元式向量
				generateQuaternionList(node.children.get(1) , quaternionList1 , 0 , symbolTable);
				generateQuaternionList(node.children.get(2) , quaternionList2 , 0 , symbolTable);
				
				//生成四元式：(jnz,i,_,跳转号)插入到四元式链
				quaternionList.add(new Quaternion(index++ , "jnz" , quaternionList.lastElement().targetOperand ,
						                            "_" , "" + (index-1+2) , 2));
				
				//生成四元式：(j,_,_,跳转号)
				quaternionList.add(new Quaternion(index++ , "j" , "_" , "_" , 
						                          "" + (index-1+quaternionList1.size()+1) , quaternionList1.size()+1));
				
				//把递归生成的quaternionList1加入到quaternionList
				for(int i = 0 ; i < quaternionList1.size() ; i ++)
				{
					quaternionList1.elementAt(i).number = index++;
					quaternionList.add(quaternionList1.elementAt(i));
				}
				
				//把递归生成的quaternionList2加入到quaternionList
				for(int i = 0 ; i < quaternionList2.size() ; i ++)
				{
					quaternionList2.elementAt(i).number = index++;
					quaternionList.add(quaternionList2.elementAt(i));
				}
				
				//清空quaternionList1、quaternionList2以便下一次使用
				//quaternionList1.clear();
				//quaternionList2.clear();
			}
			
			//规则是S =>if E then { S } else { S } S
			else if(node.rule == 4)
			{
				generateExpression(expression , node.children.get(0));//对E(表达式)生成逆波兰式
				index = generateQuaternion(expression , quaternionList , index);//把逆波兰式生成四元式,然后将四元式插入四元式链
				
				Vector<Quaternion> quaternionList1 = new Vector<Quaternion>();
				Vector<Quaternion> quaternionList2 = new Vector<Quaternion>();
				Vector<Quaternion> quaternionList3 = new Vector<Quaternion>();
				
				//分别对S =>if E then { S } else { S } S的后三个S生成四元式向量
				generateQuaternionList(node.children.get(1) , quaternionList1 , 0 , symbolTable);
				generateQuaternionList(node.children.get(2) , quaternionList2 , 0 , symbolTable);
				generateQuaternionList(node.children.get(3) , quaternionList3 , 0 , symbolTable);
				
				//生成四元式：(jnz,i,_,跳转号)插入到四元式链
				quaternionList.add(new Quaternion(index++ , "jnz" , quaternionList.lastElement().targetOperand ,
						                            "_" , "" + (index-1+2) , 2));
				
				//生成四元式：(j,_,_,跳转号)
				quaternionList.add(new Quaternion(index++ , "j" , "_" , "_" , 
						                          "" + (index-1+quaternionList1.size()+2) , quaternionList1.size()+2));
				
				//把递归生成的quaternionList1加入到quaternionList
				for(int i = 0 ; i < quaternionList1.size() ; i ++)
				{
					quaternionList1.elementAt(i).number = index++;
					quaternionList.add(quaternionList1.elementAt(i));
				}
				
				//生成四元式：(j,_,_,跳转号)
				quaternionList.add(new Quaternion(index++ , "j" , "_" , "_" , 
						                          "" + (index-1+quaternionList2.size()+1) , quaternionList2.size()+1));
				
				//把递归生成的quaternionList2加入到quaternionList
				for(int i = 0 ; i < quaternionList2.size() ; i ++)
				{
					quaternionList2.elementAt(i).number = index++;
					quaternionList.add(quaternionList2.elementAt(i));
				}
				
				//把递归生成的quaternionList3加入到quaternionList
				for(int i = 0 ; i < quaternionList3.size() ; i ++)
				{
					quaternionList3.elementAt(i).number = index++;
					quaternionList.add(quaternionList3.elementAt(i));
				}
				
				//清空quaternionList1、quaternionList2、quaternionList3以便下一次使用
				//quaternionList1.clear();
				//quaternionList2.clear();
				//quaternionList3.clear();
			}
			
			//规则是while E do { S } S
			else if(node.rule == 5)
			{
				generateExpression(expression , node.children.get(0));//对E(表达式)生成逆波兰式
				index = generateQuaternion(expression , quaternionList , index);//把逆波兰式生成四元式,然后将四元式插入四元式链
				
				
				
				Vector<Quaternion> quaternionList1 = new Vector<Quaternion>();
				Vector<Quaternion> quaternionList2 = new Vector<Quaternion>();
				//分别对while E do { S } S的后两个S生成四元式向量
				generateQuaternionList(node.children.get(1) , quaternionList1 , 0 , symbolTable);
				generateQuaternionList(node.children.get(2) , quaternionList2 , 0 , symbolTable);
				
				//生成四元式：(jnz,i,_,跳转号)插入到四元式链
				quaternionList.add(new Quaternion(index++ , "jnz" , quaternionList.lastElement().targetOperand ,
						                            "_" , "" + (index-1+2) , 2));
				int indexbuffer = index - 1;
				
				//生成四元式：(j,_,_,跳转号)
				quaternionList.add(new Quaternion(index++ , "j" , "_" , "_" , 
						                          "" + (index-1+quaternionList1.size()+2) , quaternionList1.size()+2));
				
				//把递归生成的quaternionList1加入到quaternionList
				for(int i = 0 ; i < quaternionList1.size() ; i ++)
				{
					quaternionList1.elementAt(i).number = index++;
					quaternionList.add(quaternionList1.elementAt(i));
				}
				
				//生成四元式返回循环条件：(j,_,_,跳转号)
				quaternionList.add(new Quaternion(index++ , "j" , "_" , "_" , 
                        "" + indexbuffer , -(index-1-indexbuffer)));
				
				//把递归生成的quaternionList2加入到quaternionList
				for(int i = 0 ; i < quaternionList2.size() ; i ++)
				{
					quaternionList2.elementAt(i).number = index++;
					quaternionList.add(quaternionList2.elementAt(i));
				}
				
				//清空quaternionList1、quaternionList2以便下一次使用
				//quaternionList1.clear();
				//quaternionList2.clear();
			}
			
			//规则是D =>int A
			else if(node.rule == 7)
			{
				quaternionList.add(new Quaternion(index++ , "val" , "_" , "_" , node.children.elementAt(0).name));
			}
			
			//规则是D =>int A = E
			else if(node.rule == 8)
			{
				quaternionList.add(new Quaternion(index++ , "val" , "" + symbolTable.findValueByName(node.children.elementAt(0).name) , "_" , node.children.elementAt(0).name));
			}
			
			//规则是S =>null
			else if(node.rule == 6)
			{
			}
		}
		return index;
	}
	
	//根据逆波兰表达式求相应四元式
	public int generateQuaternion(Vector<TreeNode> expression , Vector<Quaternion> quaternionList , int index)
	{
		expressionStack.clear();
		
		if(expression.size() == 1)
		{
			Quaternion newquaternion = new Quaternion();
			newquaternion.number = index++;
			newquaternion.operator = ":=";
			newquaternion.sourceOperand2 = "_";
			newquaternion.sourceOperand1 = expression.elementAt(0).name;
			newquaternion.targetOperand = "T" + index_of_temp_variable++;
			
			quaternionList.add(newquaternion);
		}
		else
		{
			for(int i = 0 ; i < expression.size() ; i ++)
			{
				//如果不是操作符，即操作对象入栈
				if(!isOperator(expression.elementAt(i)))
				{
					expressionStack.push(expression.elementAt(i));
				}
				
				//如果是操作符，则产生一个四元式，且填入操作符和操作对象
				else
				{
					//产生一个四元式，且填入操作符和操作对象
					Quaternion newquaternion = new Quaternion();
					newquaternion.number = index++;
					newquaternion.operator = expression.elementAt(i).name;
					newquaternion.sourceOperand2 = expressionStack.pop().name;
					newquaternion.sourceOperand1 = expressionStack.pop().name;
					newquaternion.targetOperand = "T" + index_of_temp_variable++;
					expressionStack.push(new TreeNode(newquaternion.targetOperand));//将临时变量入栈
					
					quaternionList.add(newquaternion);
				}
			}
		}
		return index;
	}
	
	
	//生成逆波兰式的方法
	public void generateExpression(Vector<TreeNode> expression , TreeNode node)
	{
		if(node.children.size() == 0)
		{
			expression.add(node);
		}
		else
		{
			//因为是对表达式求逆波兰式,所以只可能是:该节点有三个孩子节点或只有一个孩子节点
			if(node.children.size() == 3)
			{
				generateExpression(expression , node.children.elementAt(0));
				generateExpression(expression , node.children.elementAt(2));
				generateExpression(expression , node.children.elementAt(1));
			}
			else
			{
				generateExpression(expression , node.children.elementAt(0));
			}
		}
	}
}