parser.java

编译器

package compiler;

import java.util.Stack;

public class Parser 
{
	/*private static final String GRAMMAR[] = {
	//非终极符: P(程序),S(分程序),D(变量定义),E(表达式),
	//终极符: int(变量说明符),=(赋值号),A(变量),C(常数),
	//　　　　 if else then(条件语句符),while do(循环语句符),
	//　　　　　+　-　*　/(算数运算符),;(语句结束符)
		A 0.P =>S
		B 1.S =>D ; S
		C 2.S =>A = E ;
        D 3.S =>if E then { S } S
		E 4.S =>if E then { S } else { S } S
		F 5.S =>while E do { S } S
		G 6.S =>null 
		H 7.D =>int A
		I 8.D =>int A = E
		J 9.E =>E + F
        K 10.E =>E - F
        L 11.E =>F
		M 12.F =>F * H
        N 13.F =>F / H
        O 14.F =>H
		P 15.H =>( E )
		Q 16.H =>A
		R 17.H =>C
	
    //非终极符的机内定义：
    public Token P = new Token(24,"P");
	public Token S = new Token(19,"S");
	public Token D = new Token(23,"D");
	public Token Y = new Token(22,"E");
	public Token A = new Token(20,"F");
	public Token C = new Token(21,"H");
	
	//终极符的机内定义:
	//关键字
	public Token int = new Token(0,"int");
	public Token if = new Token(1,"if");
	public Token then = new Token(2,"then");
    public Token else = new Token(3,"else");
	public Token while = new Token(4,"while");
	public Token do = new Token(17,"do");
	//常量变量
	public Token A = new Token(15,"A");
	public Token C = new Token(16,"C");
	//操作符与界限符
	public Token { = new Token(7,"{");
	public Token } = new Token(8,"}");
	public Token ( = new Token(5,"(");
	public Token ) = new Token(6,")");
	public Token + = new Token(9,"+");
	public Token - = new Token(10,"-");
	public Token * = new Token(11,"*");
	public Token / = new Token(12,"/");
	public Token = = new Token(14,"=");
	public Token ; = new Token(13,";");
	public Token SPACE = new Token(25," ");
	public Token END = new Token(18,"#");*/
	
	
	//自定义类:
	public Scanner scanner;								//生成扫描器对象
	public Token token;									//生成属性字对象
	public ErrorHandle errorhandle;						//生成错误处理对象
	public MakeAnalyzeTable makeAnalyzeTable;			//生成分析表生成器对象
	public SymbolTable symbolTable;						//生成符号表对象
	public Generator generator;							//生成中间代码生成器对象
	public TreeNode parent;
	
	//int型标记量
	public int gotostate;								//标记规约后状态栈应移进的下一状态
	public int rule;									//标记规约时用到的规则号
	public int operation;								//标记根据slr分析表得到的操作号
	public int analyzetable[][];						//slr分析表
	public int symbolTableIndex;						//标记符号表的索引号
	public int grammar1[] = {1,3,4,7,11,7,0,2,4,
							 3,3,1,3,3,1,3,1,1};			//标记每条规则右侧的文法符号的数目
	public int grammar2[] = {24,19,19,19,19,19,19,23,23,
			                 22,22,22,20,20,20,21,21,21};	//标记每条规则左侧的非终极符代号
	public String grammar3[] = {"P","S","S","S","S","S","S",
								"D","D","E","E","E","F","F",
								"F","H","H","H"};			//标记每条规则左侧的非终极符
	public int children_num_of_parent[] = {0,0,3,3,4,3,0,0,0,3,3,1,3,3,1,1,1,1};//标记规约时每个规则左侧的非终极符对应的孩子数
	
	boolean the_val_or_con_is_already_in_symbolTable;//相同的变量在符号表中只出现一次
	boolean lex_and_grammar_analyzing_successfully;
	
	//分析栈
	public Stack<TreeNode> symbolStack;	//符号栈
	public Stack<Integer> stateStack;	//状态栈
	public Stack<TreeNode> tempStack;	//临时栈
	
	//构造函数
	public Parser()
	{
		scanner = new Scanner();
		token = new Token();
		errorhandle = new ErrorHandle();
		makeAnalyzeTable = new MakeAnalyzeTable();
		symbolTable = new SymbolTable();
		generator = new Generator();
		
		//int型标记量
		gotostate = 0;
		rule = 0;
		operation = 0;
		analyzetable = new int[47][24];
		symbolTableIndex = 0;
		
		the_val_or_con_is_already_in_symbolTable = false;
		lex_and_grammar_analyzing_successfully = true;
		
		//分析栈
		symbolStack = new Stack<TreeNode>();
		stateStack = new Stack<Integer>();
		tempStack = new Stack<TreeNode>();
	}
	
	//主方法
/*	public static void main(String[] args) 
	{
		//String source = new String("int i = 1 ; int j ; while 4+2 do { j = i + 1 ;}#");
		String source = new String("int i= 3 ; if 1 then { if 1 then {while 1 do{i = 2;} i = i - 1;}else {i = i + 1 ;}} else {i = i - 3;}#");
//		A 0.P =>S
//		B 1.S =>D ; S
//		C 2.S =>A = E ;
//      D 3.S =>if E then { S } S
//		E 4.S =>if E then { S } else { S } S
//		F 5.S =>while E do { S } S
//		G 6.S =>null 
//		H 7.D =>int A
//		I 8.D =>int A = E
//		J 9.E =>E + F
//      K 10.E =>E - F
//      L 11.E =>F
//		M 12.F =>F * H
//      N 13.F =>F / H
//      O 14.F =>H
//		P 15.H =>( E )
//		Q 16.H =>A
//		R 17.H =>C
		//String source = new String("int i = 3 ; i = 5 + 6;#");
		Parser parser = new Parser();
		parser.grammarAnalyze(source);
	}*/
	
	//判断规约时弹出的节点需不需要加入语法树的方法
	public boolean includeThisNode(int v)
	{
		if(v>=9&&v<=12 || v>=14&&v<=16 || v>=19&&v<=23)
			return true;
		else 
			return false;
	}
	
	//判断规约时是否需要建父结点(某些规则时不用建)
	public boolean makeingParent(int r)
	{
		if(r>=1&&r<=6 || r>=7&&r<=17)
			return true;
		else 
			return false;
	}
	
	//语法分析方法
	public void grammarAnalyze(String source)
	{
		stateStack.push(0);
		symbolStack.push(new TreeNode(0,18,"#"));
		
		//生成slr分析表
		makeAnalyzeTable.makeAnalyzetable(analyzetable);
		
        //调用扫描器，识别第一个单词，并返回一个属性字
		Scanner.index = 0;
		token = scanner.lexAnalyze(source , symbolTable);
		
		//999表示程序已读完
		while(token.getType() != 999)
		{
            System.out.println(token.name + token.type);//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
			
            //遇到分界符，空格、回车或tab键不做任何操作//////////////////////////////////////////////////////////////////////
			if(token.getType() == 25)
			{
				token = scanner.lexAnalyze(source , symbolTable);
			}
			
			//词法分析遇到错误///////////////////////////////////////////////////////////////////////////////////////////
			else if(token.getType() == 400)
			{
				errorhandle.showError(1);
				lex_and_grammar_analyzing_successfully = false;
				break;
			}
			
			//否则根据分析表进行分析
			else
			{
				//对符号表的操作：///////////////////////////////////////////////////////////////////////////////////////
				//如果识别出的单词是变量,先判断是否有初值,若有侧初值添加,否则初值赋0
				if(token.getType() == 15)
				{
					//如果符号表中不包含该变量则添加，否则不添加
					if(!symbolTable.contains(token.name))
					{
						if(Scanner.if_variable_assigned_value = true)
						{
							symbolTable.addItem(symbolTableIndex++ , "val" ,
									            token.getName() , Scanner.variable_value);
						}
						else
						{
							symbolTable.addItem(symbolTableIndex++ , "val" ,
						                        token.getName() , 0);
						}
					}	
				}
				
				//如果识别出的单词是常数,直接添加到符号表中
				else if(token.getType() == 16)
				{
					symbolTable.addItem(symbolTableIndex++ , "const" , token.getName() ,
							            Integer.parseInt(token.getName()));
				}
				
				
				//根据分析栈栈顶元素和下一个读入的单词得出当前操作operation////////////////////////////////////////////////////
				/*其中操作的机内表示(operation值的含义)：1~45表示移进操作，且对应状态入状态栈
	              									50~67表示规约操作，且用该数减去50为规则号,表示规约时所用的规则
	              									对于分析表中GOTO的操作,operation就代表规约后状态栈栈顶的状态号*/
				operation = analyzetable[stateStack.peek()][token.getType()];
	            				
				//分析成功/////////////////////////////////////////////////////////////////////////////////////////////
				if(operation == 200)
                {
                	System.out.println("Analyzing successfully!");//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
					break;
                }
				
				//语法分析错误//////////////////////////////////////////////////////////////////////////////////////////
				else if(operation == 0)
				{
					errorhandle.showError(2);
					lex_and_grammar_analyzing_successfully = false;
					break;
				}
				
				//进行移进操作//////////////////////////////////////////////////////////////////////////////////////////
				else if(operation >= 1 && operation <= 45)
				{
					//生成语法树节点,并将生成节点入栈,为以后语法树的生成做准备
					TreeNode newnode = new TreeNode(0 , token.getType() , token.getName());
					
					//符号入栈
					symbolStack.push(newnode);
					//状态入栈
					stateStack.push(operation);
                    
					//调用扫描器，继续识别下一个单词
					token = scanner.lexAnalyze(source , symbolTable);
				}
				
				//进行规约操作//////////////////////////////////////////////////////////////////////////////////////////
				else if(operation >= 50 && operation <= 67)
				{
					//规约时用到的规则号
					rule = operation - 50;
					
                    //当规约规则满足建树条件时，建树且出栈
					if(makeingParent(rule))
					{
						//建父结点
						parent = new TreeNode(rule , grammar2[rule] , grammar3[rule]);
						
						//出栈并将出栈的符号入临时栈
						for(int i = 0 ; i < grammar1[rule] ; i ++)
						{
							tempStack.push(symbolStack.pop());
							stateStack.pop();
						}	
							
						for(int i = 0 ; i < grammar1[rule] ; i ++)
						{
							//只当出栈的节点值为S,A,=,E,F,H,C,+,-,*,/时才把节点加入树中
							if(includeThisNode(tempStack.peek().type))
							{
								//将孩子结点与父结点相连
								tempStack.peek().parent = parent;
								//将父结点与孩子结点相连								
								parent.children.add(tempStack.pop());
							}
							
							//当出栈的节点值非S,A,=,E,F,H,C,+,-,*,/时不把节点加入语法树中
							else
							{
								tempStack.pop();
							}
						}
						
						//规则左侧文法符号进符号栈
						symbolStack.push(parent);
						
                        //规约后状态栈的goto操作,即状态栈应移进哪个状态
						gotostate = analyzetable[stateStack.peek()][symbolStack.peek().type];
						stateStack.push(gotostate);
					}
                    
					//当规约规则的左侧非终极符号为D时，不建树直接出栈
					else
					{
						for(int i = 0 ; i < grammar1[rule] ; i ++)
						{
							symbolStack.pop();
							stateStack.pop();
						}
						
						//规则左侧文法符号进符号栈
						symbolStack.push(new TreeNode(rule , grammar2[rule] , grammar3[rule]));
						
						//规约后状态栈的goto操作,即状态栈应移进哪个状态
						gotostate = analyzetable[stateStack.peek()][symbolStack.peek().type];
						stateStack.push(gotostate);
					}
				}//进行规约操作
			}//否则根据分析表进行分析
		}//while(token.getType() != 999)
		
		if(lex_and_grammar_analyzing_successfully)
		{
			generator.generateMediumCode(parent , symbolTable);
		}
		
		for(int i = 0 ; i < symbolTableIndex ; i ++)
		{
			System.out.println(i + "     " + symbolTable.type.get(i) + "    " +
					            symbolTable.name.get(i) + "   " +
					            symbolTable.value.get(i));
		}
		
		//System.out.println(parent.children.elementAt(1).children.elementAt(2).name);
		//System.out.println(parent.rule);
		//System.out.println(parent.children.elementAt(1).rule);
		//System.out.println(parent.name);
		//System.out.println(parent.children.elementAt(1).children.elementAt(1).children.elementAt(0).name);
	}
}