// ==========================================================================
// Author: Yee Hsu
// Date: 3/10/2007
// File: parser.java
//
// Desc: Java compiler/debugger parser
// ==========================================================================
package parser;
import lexer.*;
import ast.*;
import java.util.*;
/**
* The Parser class performs recursive-descent parsing; as a
* by-product it will build the <b>Abstract Syntax Tree</b> representation
* for the source program<br>
* Following is the Grammar we are using:<br>
* <pre>
* PROGRAM -> program BLOCK ==> program
*
* BLOCK -> { D* S* } ==> block
*
* D -> TYPE NAME ==> decl
* -> TYPE NAME FUNHEAD BLOCK ==> functionDecl
*
* TYPE -> int
* -> boolean
* -> float
*
* FUNHEAD -> '(' (D list ',')? ')' ==> formals
*
* S -> if E then BLOCK else BLOCK ==> if
* -> while E BLOCK ==> while
* -> return E ==> return
* -> BLOCK
* -> NAME = E ==> assign
* -> repeat BLOCK while E ==> repeat
*
* E -> SE
* -> SE == SE ==> =
* -> SE != SE ==> !=
* -> SE < SE ==> <
* -> SE <= SE ==> <=
*
* SE -> T
* -> SE + T ==> +
* -> SE - T ==> -
* -> SE | T ==> or
*
* T -> F
* -> T * F ==> *
* -> T / F ==> /
* -> T & F ==> and
*
* F -> (E)
* -> NAME
* -> <int>
* -> NAME '(' (E list ',')? ')' ==> call
* -> <float>
*
* NAME -> <id>
* </pre>
*/
public class Parser {
private Token currentToken;
private Lexer lex;
/**
* Construct a new Parser;
* @param sourceProgram - source file name
* @exception Exception - thrown for any problems at startup (e.g. I/O)
*/
public Parser(String sourceProgram) throws Exception {
try {
lex = new Lexer(sourceProgram);
scan();
}
catch (Exception e) {
System.out.println("********exception*******"+e.toString());
throw e;
};
}
public Lexer getLex() { return lex; }
/**
* Execute the parse command
* @return the AST for the source program
* @exception Exception - pass on any type of exception raised
*/
public AST execute() throws Exception {
try {
return rProgram();
}catch (SyntaxError e) {
e.print();
throw e;
}
}
/** <pre>
* program -> 'program' block ==> program
* </pre>
* @return the program tree
* @exception SyntaxError - thrown for any syntax error
*/
public AST rProgram() throws SyntaxError {
AST t = new ProgramTree();
expect(Sym.Program);
t.addKid(rBlock());
return t;
}
/** <pre>
* block -> '{' d* s* '}' ==> block
* </pre>
* @return block tree
* @exception SyntaxError - thrown for any syntax error
* e.g. an expected left brace isn't found
*/
public AST rBlock() throws SyntaxError {
expect(Sym.LeftBrace);
AST t = new BlockTree();
while (true) { // get decls
try {
t.addKid(rDecl());
} catch (SyntaxError e) { break; }
}
while (true) { // get statements
try {
t.addKid(rStatement());
} catch (SyntaxError e) { break; }
}
expect(Sym.RightBrace);
return t;
}
/** <pre>
* d -> type name ==> decl
* -> type name funcHead block ==> functionDecl
* </pre>
* @return either the decl tree or the functionDecl tree
* @exception SyntaxError - thrown for any syntax error
*/
public AST rDecl() throws SyntaxError {
AST t,t1;
t = rType();
t1 = rName();
if (isNextTok(Sym.LeftParen)) { // function
t = (new FunctionDeclTree()).addKid(t).addKid(t1);
t.addKid(rFunHead());
t.addKid(rBlock());
return t;
}
t = (new DeclTree()).addKid(t).addKid(t1);
return t;
}
/** <pre>
* type -> intType
* type -> floatType
* type -> boolType
* </pre>
* @return either the intType, floatType or boolType tree
* @exception SyntaxError - thrown for any syntax error
*/
public AST rType() throws SyntaxError {
AST t;
if (isNextTok(Sym.Int)) {
t = new IntTypeTree();
scan();
} else if (isNextTok(Sym.Float)) {
t = new FloatTypeTree();
scan();
} else
{
expect(Sym.BOOLean);
t = new BoolTypeTree();
}
return t;
}
/** <pre>
* funHead -> ( (decl list ',')? ) ==> formals
* note a funhead is a list of zero or more decl's
* separated by commas, all in parens
* </pre>
* @return the formals tree describing this list of formals
* @exception SyntaxError - thrown for any syntax error
*/
public AST rFunHead() throws SyntaxError {
AST t = new FormalsTree();
expect(Sym.LeftParen);
if (!isNextTok(Sym.RightParen)) {
do {
t.addKid(rDecl());
if (isNextTok(Sym.Comma)) {
scan();
} else {
break;
}
} while (true);
}
expect(Sym.RightParen);
return t;
}
/** <pre>
* S -> if e then block else block ==> if
* -> while e block ==> while
* -> return e ==> return
* -> block
* -> name = e ==> assign
* -> repeat BLOCK while E ==> repeat
* </pre>
* @return the tree corresponding to the statement found
* @exception SyntaxError - thrown for any syntax error
*/
public AST rStatement() throws SyntaxError {
AST t;
if (isNextTok(Sym.If)) {
scan();
t = new IfTree();
t.addKid(rExpr());
expect(Sym.Then);
t.addKid(rBlock());
expect(Sym.Else);
t.addKid(rBlock());
return t;
}
if (isNextTok(Sym.While)) {
scan();
t = new WhileTree();
t.addKid(rExpr());
t.addKid(rBlock());
return t;
}
if (isNextTok(Sym.Return)) {
scan();
t = new ReturnTree();
t.addKid(rExpr());
return t;
}
if (isNextTok(Sym.LeftBrace)) {
return rBlock();
}
if (isNextTok(Sym.Repeat)) {
scan();
t = new RepeatTree();
t.addKid(rBlock());
expect(Sym.While);
t.addKid(rExpr());
return t;
}
t = rName();
t = (new AssignTree()).addKid(t);
expect(Sym.Assign);
t.addKid(rExpr());
return t;
}
/** <pre>
* e -> se
* -> se == se ==> =
* -> se != se ==> !=
* -> se < se ==> <
* -> se <= se ==> <=
* </pre>
* @return the tree corresponding to the expression
* @exception SyntaxError - thrown for any syntax error
*/
public AST rExpr() throws SyntaxError {
AST t, kid = rSimpleExpr();
t = getRelationTree();
if (t == null) {
return kid;
}
t.addKid(kid);
t.addKid(rSimpleExpr());
return t;
}
/** <pre>
* se -> t
* -> se + t ==> +
* -> se - t ==> -
* -> se | t ==> or
* This rule indicates we should pick up as many <i>t</i>'s as
* possible; the <i>t</i>'s will be left associative
* </pre>
* @return the tree corresponding to the adding expression
* @exception SyntaxError - thrown for any syntax error
*/
public AST rSimpleExpr() throws SyntaxError {
AST t, kid = rTerm();
while ( (t = getAddOperTree()) != null) {
t.addKid(kid);
t.addKid(rTerm());
kid = t;
}
return kid;
}
/** <pre>
* t -> f
* -> t * f ==> *
* -> t / f ==> /
* -> t & f ==> and
* This rule indicates we should pick up as many <i>f</i>'s as
* possible; the <i>f</i>'s will be left associative
* </pre>
* @return the tree corresponding to the multiplying expression
* @exception SyntaxError - thrown for any syntax error
*/
public AST rTerm() throws SyntaxError {
AST t, kid = rFactor();
while ( (t = getMultOperTree()) != null) {
t.addKid(kid);
t.addKid(rFactor());
kid = t;
}
return kid;
}
/** <pre>
* f -> (e)
* -> name
* -> <int>
* -> name '(' (e list ',')? ) ==> call
* -> <float>
* </pre>
* @return the tree corresponding to the factor expression
* @exception SyntaxError - thrown for any syntax error
*/
public AST rFactor() throws SyntaxError {
AST t;
if (isNextTok(Sym.LeftParen)) { // -> (e)
scan();
t = rExpr();
expect(Sym.RightParen);
return t;
}
if (isNextTok(Sym.INTeger)) { // -> <int>
t = new IntTree(currentToken);
scan();
return t;
}
if (isNextTok(Sym.FLoat)) { // -> <float>
t = new FloatTree(currentToken);
scan();
return t;
}
t = rName();
if (!isNextTok(Sym.LeftParen)) { // -> name
return t;
}
scan(); // -> name '(' (e list ',')? ) ==> call
t = (new CallTree()).addKid(t);
if (!isNextTok(Sym.RightParen)) {
do {
t.addKid(rExpr());
if (isNextTok(Sym.Comma)) {
scan();
} else {
break;
}
} while (true);
}
expect(Sym.RightParen);
return t;
}
/** <pre>
* name -> <id>
* </pre>
* @return the id tree
* @exception SyntaxError - thrown for any syntax error
*/
public AST rName() throws SyntaxError {
AST t;
if (isNextTok(Sym.Identifier)) {
t = new IdTree(currentToken);
scan();
return t;
}
throw new SyntaxError(currentToken,Sym.Identifier);
}
AST getRelationTree() { // build tree with current token's relation
int kind = currentToken.getKind();
switch (kind) {
case Sym.Equal:
case Sym.NotEqual:
case Sym.Less:
case Sym.LessEqual:AST t = new RelOpTree(currentToken);
scan(); return t;
}
return null;
}
private AST getAddOperTree() {
int kind = currentToken.getKind();
switch (kind) {
case Sym.Plus:
case Sym.Minus:
case Sym.Or: AST t = new AddOpTree(currentToken);
scan(); return t;
}
return null;
}
private AST getMultOperTree() {
int kind = currentToken.getKind();
switch (kind) {
case Sym.Multiply:
case Sym.Divide:
case Sym.And: AST t = new MultOpTree(currentToken);
scan(); return t;
}
return null;
}
private boolean isNextTok(int kind) {
if ((currentToken == null) || (currentToken.getKind() != kind)) {
return false;
}
return true;
}
private void expect(int kind) throws SyntaxError {
if (isNextTok(kind)) {
scan();
return;
}
throw new SyntaxError(currentToken,kind);
}
private void scan() {
currentToken = lex.nextToken();
//if (currentToken != null) {currentToken.print();} //debug
return;
}
}
class SyntaxError extends Exception {
private Token tokenFound;
private int kindExpected;
/**
* record the syntax error just encountered
* @param tokenFound is the token just found by the parser
* @param kindExpected is the token we expected to find based on
* the current context
*/
public SyntaxError(Token tokenFound, int kindExpected) {
this.tokenFound = tokenFound;
this.kindExpected = kindExpected;
}
void print() {
System.out.println("Expected: " +
TokenType.tokens[kindExpected].toString());
return;
}
}