grammaranalysis.java

编译原理的课程设计

package source;
import java.util.Queue;
import java.util.Stack;
import java.util.Vector;
//语法分析类
public class GrammarAnalysis
{
	//中间变量的后缀
	private static int mdIndex = 0;
	//中间变量表
	private static Stack<String> mdStack = new Stack<String>();
	//赋值操作符
	private final static String[] ASSIGNOP = new String[]{"=", "+=", "-=", "*=", "/="};
	//双目逻辑运算符
	private final static String[] DOULOGOP = new String[]{"&&", "||"};
	//关系运算符
	private final static String[] RELESHOP = new String[]{">", "<", "==", "!=", ">=", "<="};
	//简单双目算术运算符
	private final static String[] ARISASOP = new String[]{"+", "-"};
	//复杂双目算术运算符
	private final static String[] ARISMDOP = new String[]{"*", "/", "**", "%", "|", "&", "^", ">>", "<<"};
	//单目运算符
	private final static String[] SINGLEOP = new String[]{"!", "++", "--"};
	//符号表
	private final static Vector<String> SIGNS = new Vector<String>();
	//文法
	private final static String[] SENTENCE = new String[]
		{
			"A->B",
			"B->ifCthenC",
			"B->ifCthenCelseB",
			"B->C",
			"C->MasiopD",
			"C->D",
			"D->E",
			"E->EdolopF",
			"E->F",
			"F->G",
			"G->GrelopH",
			"G->H",
			"H->I",
			"I->IarsopJ",
			"I->J",
			"J->K",
			"K->KarcopL",
			"K->L",
			"L->lsiopM",
			"L->M",
			"M->(C)",
			"M->{A}",
			"M->id"
		};
	private final static byte[][] priTable = new byte[][]
	{  //0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 2},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 3},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 0, 0, 0, 0, 0, 0, 0, 2, 0, 3, 0, 3},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 0, 0, 0, 0, 0, 0, 0, 3, 0, 3, 0, 3},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 0, 2, 0, 0, 0, 0, 0, 3, 0, 3, 0, 3},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 0, 3, 0, 0, 0, 0, 0, 3, 0, 3, 0, 3},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 0, 3, 2, 0, 0, 0, 0, 3, 0, 3, 0, 3},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 0, 3, 3, 0, 0, 0, 0, 3, 0, 3, 0, 3},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 0, 3, 3, 2, 0, 0, 0, 3, 0, 3, 0, 3},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 0, 3, 3, 3, 0, 0, 0, 3, 0, 3, 0, 3},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 0, 3, 3, 3, 2, 0, 0, 3, 0, 3, 0, 3},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 0, 3, 3, 3, 3, 0, 0, 3, 0, 3, 0, 3},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 2, 3, 3, 3, 3, 0, 0, 3, 0, 3, 0, 3},
		{0, 0, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0},
		{0, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0},
		{0, 0, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0},
		{0, 0, 0, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0},
		{0, 0, 0, 0, 0, 2, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0},
		{0, 0, 0, 0, 0, 0, 0, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0},
		{0, 0, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 3, 3, 3, 3, 3, 0, 0, 3, 0, 3, 0, 3},
		{2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 3, 3, 3, 3, 3, 0, 0, 3, 0, 3, 0, 3},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 3, 3, 3, 3, 3, 0, 0, 3, 0, 3, 0, 3},
		{2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0}
	};
	//私有变量声明
	public Stack<Word> opStack = new Stack<Word>();
	//构造语法分析器
	public GrammarAnalysis()
	{
		SIGNS.add("A");
		SIGNS.add("B");
		SIGNS.add("C");
		SIGNS.add("D");
		SIGNS.add("E");
		SIGNS.add("F");
		SIGNS.add("G");
		SIGNS.add("H");
		SIGNS.add("I");
		SIGNS.add("J");
		SIGNS.add("K");
		SIGNS.add("L");
		SIGNS.add("M");
		SIGNS.add("if");
		SIGNS.add("else");
		SIGNS.add("then");
		SIGNS.add("asiop");
		SIGNS.add("dolop");
		SIGNS.add("relop");
		SIGNS.add("arsop");
		SIGNS.add("arcop");
		SIGNS.add("lsiop");
		SIGNS.add("(");
		SIGNS.add(")");
		SIGNS.add("{");
		SIGNS.add("}");
		SIGNS.add("id");
		SIGNS.add("#");
		opStack.push(new Word("#", 27));
	}
	//语法分析
	public int grammar_analysis(Queue<Word> opQueue)
	{
		int debug = 0;
		Word srcWrd = null;          //从栈中取串
		Word aimWrd = null;          //从队列中取串 
		//简单优先语法制导翻译
		while(!opQueue.isEmpty())
		{
			Stack<Word> tpStack = new Stack<Word>();
			boolean isGen = false;
			srcWrd = opQueue.peek();
			aimWrd = opStack.peek();
			byte prty = priTable[aimWrd.Code][srcWrd.Code];
			//出错处理
			if(prty == 0)
			{
				System.out.println(aimWrd.Value + " 与 " + srcWrd.Value + "不能匹配！");
				return -1;
			}
			//小于等于关系处理
			else if(prty == 1 || prty == 2)
			{
				opQueue.remove();
				opStack.push(srcWrd);
			}
			//大于关系处理
			else
			{
				tpStack.push(opStack.pop());
				srcWrd = opStack.peek();
				aimWrd = tpStack.peek();
				prty = priTable[srcWrd.Code][aimWrd.Code];
				while(prty == 2)
				{
					isGen = true;
					tpStack.push(opStack.pop());
					srcWrd = opStack.peek();
					aimWrd = tpStack.peek();
					prty = priTable[srcWrd.Code][aimWrd.Code];
				}
				StringBuffer sbuf1 = new StringBuffer();
				StringBuffer sbuf2 = new StringBuffer();
				Word wrd = null;
				while(!tpStack.isEmpty())
				{
					wrd = tpStack.pop();
					sbuf1.append(wrd.Value + " ");
					sbuf2.append(SIGNS.elementAt(wrd.Code));
				}
				if(isGen)
				{//产生中间变量的规约
					System.out.println("T" + (++mdIndex) + " := " + sbuf1.toString());
					for(String index : SENTENCE)
					{
						String subs = index.substring(3);
						if(subs.equals(sbuf2.toString()))
						{
							subs = index.substring(0, 1);
							opStack.push(new Word("T"+mdIndex, SIGNS.indexOf(subs)));
						}
					} 
				}
				else
				{//不产生中间变量的规约
					for(String index : SENTENCE)
					{
						String subs = index.substring(3, index.length());
						if(subs.equals(sbuf2.toString()))
						{
							subs = index.substring(0, 1);
							opStack.push(new Word(wrd.Value, SIGNS.indexOf(subs)));
						}
					} 
				}
			}
		}
		//分析完成
		if(opStack.peek().Code == 27) return 0;
		//分析未完成
		return 1;
	}
}