parser.java

java语言开发的基于tiny语言的编译器

package jeex.tiny;

import java.io.*;
import java.util.*;
import jeex.tiny.Tree.*;
/**
 * A class for building the abstract syntax tree.
 */
class Parser implements Tokens {
	Scanner S;
	
	Parser(Scanner s) {
		this.S = s;
	}
	/**
	 * Main entry.
	 * Program -> StmtSeq
	 */
	Tree Program() {
		Tree tree = StmtSeq();
		return tree;
	}
	/**
	 * StmtSeq -> Statement { ";" Statement }
	 */
	Tree StmtSeq() {
		Vector v = new Vector();
		v.add(Statement());
		while(true) {
			while(S.token == SEMI) {
				accept(SEMI);
				v.add(Statement());
				if (S.token == ELSE || S.token == UNTIL || S.token == END || S.token == EOF)
					break;
			}
			if (S.token == ELSE || S.token == UNTIL 
					|| S.token == END || S.token == EOF) { // end of statement sequence
				break;
			}
			//must be syntax error, and continue to parse
			if (S.token != SEMI) {
				syntaxErrorNoSkip("Expect: " + TokenUtil.tokenToString(SEMI));
				v.add(Statement());
			}
		}
		// if there exists only a statement, return the statement and do not create StmtSeq.
		if (v.size() == 1) {
			return (Tree)v.get(0);
		} else {
			return new StmtSeq(v);
		}
	}
	/**
	 * Statement -> IfStmt | RepeatStmt | AssignStmt | ReadStmt | WriteStmt
	 */
	Tree Statement() {
		Tree tree;
		switch(S.token) {
			case IF: tree = IfStmt(); break;
			case REPEAT: tree = RepeatStmt(); break;
			case READ: tree = ReadStmt(); break;
			case WRITE: tree = WriteStmt(); break;
			case IDENT:	tree = AssignStmt(); break;
			default:
				syntaxError("No such statement begin with " + TokenUtil.tokenToString(S.token));
				tree = new ErrorTree();
		}
		return tree;
	}
	/**
	 * IfStmt -> "IF" Expr "THEN" StmtSeq [ "ELSE" StmtSeq ] "END"
	 */
	Tree IfStmt() {
		accept(IF);
		Tree cond = Expr();
		accept(THEN);
		Tree thenPart = StmtSeq();
		Tree elsePart = null;
		if (S.token == ELSE) {
			S.nextToken();
			elsePart = StmtSeq();
		}
		accept(END);
		return new IfStmt(cond,thenPart,elsePart);
	}
	/**
	 * RepeatStmt -> "REPEAT" StmtSeq "UNTIL" Expr
	 */
	Tree RepeatStmt() {
		accept(REPEAT);
		Tree statements = StmtSeq();
		accept(UNTIL);
		Tree cond = Expr();
		return new RepeatStmt(cond,statements);
	}
	/**
	 * WriteStmt -> "WRITE" Expr
	 */
	Tree WriteStmt() {
		accept(WRITE);
		return new WriteStmt(Expr());
	}
	/**
	 * ReadStmt -> "READ" "IDENT"
	 */
	Tree ReadStmt() {
		accept(READ);
		Tree tree ;
		if(S.token != IDENT) {
			syntaxError("Read statement must be follow an identifier");
			tree = new ErrorTree();
		} else {
			S.nextToken();
			tree = new ReadStmt(new Ident(S.identName));
		}
		return tree;
	}
	/**
	 * AssignStmt -> "IDENT" ":=" Expr
	 */
	Tree AssignStmt() {
		accept(IDENT);
		String ident = S.identName;
		accept(ASSIGN);
		Tree expr = Expr();
		return new AssignStmt(new Ident(ident),expr);
	}
	/**
	 * Expr -> SimpleExpr [Comparisonop SimpleExpr ]
	 * Comparisonop -> "<" | "="
	 */
	Tree Expr() {
		Tree tree = SimpleExpr();
		Tree second = null;
		int op = 0;
		if(S.token == LT || S.token == EQ) {
			op = S.token;
			S.nextToken();
			second = SimpleExpr();
			tree = new Expr(tree,op,second);
		}
		return tree;
	}
	/**
	 * SimpleExpr -> Term { Addop Term }
	 * Addop -> "+" | "-"
	 */
	Tree SimpleExpr() {
		Tree tree = Term();
		while(S.token == PLUS || S.token == MINUS) {
			int op = S.token;
			S.nextToken();
			Tree right = Term();
			Tree left = tree;
			tree = new Operation(op,left,right);
		}		
		return tree;
	}
	/**
	 * Term -> Factor { Mulop Factor }
	 * Mulop -> "*" | "/"
	 */
	Tree Term() {
		Tree tree = Factor();
		while(S.token == MUL || S.token == DIV) {
			int op = S.token;
			S.nextToken();
			Tree right = Factor();
			Tree left = tree;
			tree = new Operation(op,left,right);
		}
		return tree;
	}
	/**
	 * Factor -> "(" Expr ")" | "NUMBER" | "IDENT"
	 */
	Tree Factor() {
		Tree tree = null;
		switch(S.token) {
			case LPAREN: {
				S.nextToken();
				tree = new ParExpr(Expr());
				accept(RPAREN);
				break;
			}
			case NUMBER: {
				tree = new Literal(Integer.parseInt((String)S.literalValue));
				S.nextToken();
				break;
			}
			case IDENT: {
				tree = new Ident(S.identName);
				S.nextToken();
				break;
			}
			default:
				tree = new ErrorTree();
				syntaxError("Error factor");
		}
		return tree;
	}
	
	private void accept(int token) {
		if (S.token == token) {
			S.nextToken();
		} else {
			syntaxError("Expect " + TokenUtil.tokenToString(token));
		}
	}
	
	void syntaxError(String msg) {
		syntaxErrorNoSkip(msg);
		while(S.token != SEMI && S.token != EOF) {
			S.nextToken();
		}
	}
	
	void syntaxErrorNoSkip(String msg) {
		Log.error("Syntax error at line " + S.line + " : " + msg);		
	}
}