parser.java

TINY Parser——TINY语言的自顶向下的预测分析器

/**
 *Author:chmkeily
 *
 *Date:2007-6
 */
 
 

/**
 * TINY语言语法分析器
 * parser类
 */
public class parser
{	
	//lookahead
	private Token lookahead = null;
	//retrack flag
	private boolean retrack = false;
	
	//lexer
	private Lexer scanner;
	
	//parser constructor
	public parser(String filename) throws Exception
	{
		scanner = new Lexer(filename);
		retrack = false;
	}
	
	/*------------------------------------------------------*/
	//functions
	//每一个非终结符号对应一个函数
	
	/**
	 *getToken (get next-token)
	 */
	private void getToken() throws Exception
	{
		if(retrack==true) retrack = false;
		else lookahead = scanner.nextToken();
	}
	
	/**
	 *判断是否是词法错
	 */
	private boolean isLexicalError()
	{
		return lookahead.type==Sym.Error_Character
			||lookahead.type==Sym.Error_Identifier
			||lookahead.type==Sym.Error_Number;			
	}
	
	/**
	 *factor
	 */
	private int factor() throws Exception
	{		
		getToken();
		
		if( lookahead.type==Sym.LPAREN )
		{
			int m1 = expr();
			if( m1<0 ) return m1;
			
			getToken();		
			if( lookahead.type!=Sym.RPAREN )
			{
				//Lexical Errors
				if(isLexicalError()==true) return -1;
				
				System.out.println("[syntax  error] Row " + scanner.row + ":\t\')\' is wanted");
				return -1;
			}
			
			return m1;
		}
		
		if( lookahead.type==Sym.IDENTIFIER || lookahead.type==Sym.NUMBER )
		{			
			return 0;
		}
		
		//errors
		
		//Lexical Errors
		if(isLexicalError()==true) return -1;
		
		// no identifier, numer ,or expression
		System.out.println("[syntax  error] Row "+scanner.row+":\tidentifier, number or (expression) is wanted");		
		retrack = true;	//
		return -1;
	}
	
	/**
	 *termx
	 */
	private int termx() throws Exception
	{
		getToken();
		
		if(lookahead.type==Sym.MULTIPLY || lookahead.type==Sym.DIVIDE)
		{
			int m1 = factor();
			if( m1<0 ) return -1;
			
			int m2 = termx();
			if( m2<0 ) return -1;
			
			return 3+m1+m2;
		}
		
		//epsilon
		retrack = true;	//
		return 0;
	}
	
	/**
	 *term
	 */
	private int term() throws Exception
	{
		int m1 = factor();
		if( m1<0 ) return -1;
		
		int m2 = termx();
		if( m2<0 ) return -1;
		
		return m1+m2;
	}
	
	/**
	 *simple-exprx
	 */	
	private int simple_exprx() throws Exception
	{
		getToken();
		
		if(lookahead.type==Sym.ADD || lookahead.type==Sym.MINUS)
		{
			int m1 = term();
			if(m1<0) return -1;
			
			int m2 = simple_exprx();
			if(m2<0) return -1;
			
			return 2+m1+m2;
		}
		
		//epsilon
		retrack = true;	//
		return 0;		
	}
	
	/**
	 *simple-expr
	 */
	private int simple_expr() throws Exception
	{
		int m1 = term();
		if(m1<0) return -1;
		
		int m2 = simple_exprx();
		if(m2<0) return -1;
		
		return m1+m2;
	}
	
	/**
	 *exprx
	 */
	private int exprx() throws Exception
	{
		getToken();
		
		if(lookahead.type==Sym.SMALLER || lookahead.type==Sym.EQUAL)
		{
			int m = simple_expr();
			
			if( m<0 ) return -1;			
			else return 1+m;
		}
		
		//epsilon
		retrack = true;	//
		return 0;
	}
	
	/**
	 *expr
	 */	
	private int expr() throws Exception
	{
		int m1 = simple_expr();
		if(m1<0) return -1;
		
		int m2 = exprx();		
		if(m2<0) return -1;
		
		return m1+m2;
	}
	
	/**
	 *if-stmtx
	 */
	private int if_stmtx(int w) throws Exception
	{
		getToken();
		
		if(lookahead.type==Sym.END)
		{
			return 4*w;
		}
		
		if(lookahead.type==Sym.ELSE)
		{
			int m = stmt_sequence();
			if(m<0) return -1;
			
			getToken();
			if(lookahead.type==Sym.END)
			{
				return 6*(w+m);
			}
		}
		
		//Lexical Errors
		if(isLexicalError()==true) return -1;
		
		System.out.println("[syntax  error] Row "+scanner.row+":\t\'end\' is wanted");
		return -1;
	}

	/**
	 *statement
	 */
	private int statement() throws Exception
	{
		getToken();
		
		if(lookahead.type==Sym.EOF)
		{
			System.out.println("[syntax  error] Row "+scanner.row+":\tUnexpected semicolon \';\'");
			return -1;
		}
		
		if(lookahead.type==Sym.IF)
		{
			int m1 = expr();
			if(m1<0) return -1;
			
			getToken();
						
			if(lookahead.type!=Sym.THEN)
			{
				//Lexical Errors
				if(isLexicalError()==true) return -1;
				
				System.out.println("[syntax  error] Row "+scanner.row+":\t\'then\' is wanted");				
				return -1;
			}
			
			int m2 = stmt_sequence();
			if(m2<0) return -1;
			
			int m3 = if_stmtx(m1+m2);
			if(m2<0) return -1;
			
			return m3;	/////
		}
		
		if(lookahead.type==Sym.REPEAT)
		{
			int m1 = stmt_sequence();
			if(m1<0) return -1;
			
			getToken();
			if(lookahead.type!=Sym.UNTIL)
			{
				//Lexical Errors
				if(isLexicalError()==true) return -1;
				
				System.out.println("[syntax  error] Row "+scanner.row+":\t\'until\' is wanted");
				return -1;
			}
			
			int m2 = expr();
			if(m2<0) return -1;
			
			return 10*(m1+m2);
		}
		
		if(lookahead.type==Sym.IDENTIFIER)
		{
			getToken();
			if(lookahead.type!=Sym.ASSIGN)
			{
				//Lexical Errors
				if(isLexicalError()==true) return -1;
				
				System.out.println("[syntax  error] Row "+scanner.row+":\t\':=\' is wanted");
				return -1;
			}
			
			int m = expr();
			if(m<0) return -1;
			
			return 2*m;
		}
		
		if(lookahead.type==Sym.READ)
		{
			getToken();
			if(lookahead.type!=Sym.IDENTIFIER)
			{
				//Lexical Errors
				if(isLexicalError()==true) return -1;
				
				System.out.println("[syntax  error] Row "+scanner.row+":\tidentifier is wanted");
				return -1;
			}
			
			return 4;
		}
		
		if(lookahead.type==Sym.WRITE)
		{
			int m = expr();
			if(m<0) return -1;
			
			return 4+m;
		}
		
		return -1;
	}
		
	/**
	 *stmt-sequencex
	 */
	private int stmt_sequencex(int w) throws Exception
	{
		getToken();
		
		if(lookahead.type==Sym.SEMICOLON)
		{
			int m1 = statement();
			if( m1<0 ) return -1;
			
			int m2 = stmt_sequencex(2*(w+m1));
			if( m2<0 ) return -1;
			
			return m2;
		}
		
		//epsilon
		retrack = true;	//
		return w;	//		
	}
	
	/**
	 *stmt-sequence
	 */
	private int stmt_sequence() throws Exception
	{
		int m1 = statement();
		if(m1<0) return -1;
		
		int m2 = stmt_sequencex(m1);
		if(m2<0) return -1;
		
		return m2;
	}
	
	/**
	 *program
	 */
	private int program() throws Exception	//
	{
		int m = stmt_sequence();		
		if( m<0 ) return -1;
		
		if( lookahead.type==Sym.EOF ) return m;
		else
		{
			System.out.println("[syntax  error] Row "+scanner.row+":\t\';\' is wanted");
			return -1;
		}
	}
	
	/*--------------------------------------------------*/
	
	/**
	 *parse
	 *
	 * 对给定的TINY源文件(程序)进行语法分析，
	 * 并且，对完全正确的TINY源程序输出其复杂度，对含有错误的源程序则估计其错误类型并输出错误信息
	 */
	public void parse() throws Exception
	{
		int m = program();
		if(m>=0)
		{
			System.out.println("M="+m);
		}
	}
	
}