Skip to content

Instantly share code, notes, and snippets.

@vectorijk

vectorijk/AstParser.jj

Last active August 29, 2015 14:14
Show Gist options
  • Save vectorijk/2cb07843b8e8bcbd764b to your computer and use it in GitHub Desktop.
Save vectorijk/2cb07843b8e8bcbd764b to your computer and use it in GitHub Desktop.
Download ZIP
Compiler Homework CS321
Raw
AstParser.jj
// (For CS321 Assignment 3. Winter'15)
//
// miniJava AST parser (starter version).
//
// Kai Jiang (at jiangkai (dot gmail com))
// Feb 2015
PARSER_BEGIN(AstParser)
import java.util.*;
import java.io.*;
import ast.*;
public class AstParser {
public static void main(String [] args) throws Exception {
if (args.length == 1) {
FileInputStream stream = new FileInputStream(args[0]);
Ast.Program p = new AstParser(stream).Program();
stream.close();
System.out.print(p);
} else {
System.out.println("Need one file name as command-line argument.");
}
}
}
PARSER_END(AstParser)
SKIP:
{
" " | "\t" | "\n" | "\r" | "\f"
}
SKIP : /* Comments -- multi-line form and error detection not included */
{
<"#" (~["\n","\r"])* ("\n"|"\r"|"\r\n")>
}
// Keyword definitions
TOKEN :
{
<IF : "If" >
| <VOID : "void" >
| <ELSE : "Else" >
| <CALL : "Call" >
| <UNOP : "Unop" >
| <THIS : "This" >
| <FIELD : "Field" >
| <WHILE : "While" >
| <BINOP : "Binop" >
| <PARAM : "Param" >
| <PRINT : "Print" >
| <NEWOBJ : "NewObj" >
| <ASSIGN : "Assign" >
| <RETURN : "Return" >
| <INTTYPE : "IntType" >
| <OBJTYPE : "ObjType" >
| <VARDECL : "VarDecl" >
| <BOOLTYPE : "BoolType" >
| <ARRAYELM : "ArrayElm" >
| <CALLSTMT : "CallStmt" >
| <NEWARRAY : "NewArray" >
| <ARRAYTYPE : "ArrayType" >
| <CLASSDECL : "ClassDecl" >
| <METHODDECL : "MethodDecl" >
}
// Token definitions
TOKEN :
{
<IntLit: (["0"-"9"])+>
| <BoolLit: "true"|"false">
| <StrLit: "\"" (~["\"","\n"])* "\"">
| <Id: (["A"-"Z"]|["a"-"z"]|"_") (["A"-"Z"]|["a"-"z"]|"_"|["0"-"9"])*>
}
String ID():
{ Token tkn; }
{
tkn=<Id> { return tkn.image; }
}
int IntLit():
{ Token tkn; }
{
tkn=<IntLit> { return Integer.parseInt(tkn.image); }
}
boolean BoolLit():
{ Token tkn; }
{
tkn=<BoolLit> { return Boolean.parseBoolean(tkn.image); }
}
String StrLit():
{ Token tkn; }
{
tkn=<StrLit> { int len = tkn.image.length(); return tkn.image.substring(1,len-1); }
}
// Parsing routines
// Program -> {ClassDecl}
Ast.Program Program():
{ List<Ast.ClassDecl> classList = new ArrayList<Ast.ClassDecl>();
Ast.ClassDecl c; }
{
( c = ClassDecl() { classList.add(c); } )* <EOF>
{ return new Ast.Program(classList); }
}
// ClassDecl -> "ClassDecl" <Id> [<Id>] {VarDecl} {MethodDecl}
Ast.ClassDecl ClassDecl():
{ List<Ast.VarDecl> varList = new ArrayList<Ast.VarDecl>();
Ast.VarDecl v;
List<Ast.MethodDecl> methodList = new ArrayList<Ast.MethodDecl>();
Ast.MethodDecl m;
String className;
String parentName = null; }
{
"ClassDecl" className = ID() [ parentName = ID() ]
( v = VarDecl() { varList.add(v); } )*
( m = MethodDecl() { methodList.add(m); } )*
{ return new Ast.ClassDecl(className, parentName, varList, methodList); }
}
// MethodDecl -> "MethodDecl" Type <Id> "(" {Param} ")" {VarDecl} {Stmt}
Ast.MethodDecl MethodDecl():
{ Ast.Type t;
String methodName = null;
List<Ast.Param> paramList = new ArrayList<Ast.Param>();
Ast.Param p;
List<Ast.VarDecl> varList = new ArrayList<Ast.VarDecl>();
Ast.VarDecl v;
List<Ast.Stmt> stmtList = new ArrayList<Ast.Stmt>();
Ast.Stmt s; }
{
"MethodDecl" t = Type() methodName = ID() "(" ( p = Param() { paramList.add(p); } )*
")"
( v = VarDecl() { varList.add(v); } )*
( s = Stmt() { stmtList.add(s); } )*
{ return new Ast.MethodDecl(t, methodName, paramList, varList, stmtList); }
}
//VarDecl -> "VarDecl" Type <Id> Exp
Ast.VarDecl VarDecl():
{ Ast.Type t;
String varName;
Ast.Exp expr; }
{
"VarDecl" t = Type() varName = ID() expr = Exp()
{ return new Ast.VarDecl(t, varName, expr); }
}
//Param -> "(" "Param" Type <Id> ")"
Ast.Param Param():
{ Ast.Param p = null;
Ast.Type t = null;
String parameterName = null; }
{
"(" "Param" t = Type() parameterName = ID() ")"
{ return new Ast.Param(t, parameterName); }
}
//Type -> "void"
// | "IntType"
// | "BoolType"
// | "(" "ObjType" <Id> ")"
// | "(" "ArrayType" Type ")"
Ast.Type Type():
{
Ast.Type t = null;
Ast.Type array = null;
String id = null;
}
{
"void" { return null; }
| "IntType" { return Ast.IntType; }
| "BoolType" { return Ast.BoolType; }
| "(" ("ObjType" id = ID() { t = new Ast.ObjType(id); }
|"ArrayType" array = Type() { t = new Ast.ArrayType(array); }
) ")" { return t; }
}
//Stmt -> "{" {Stmt} "}"
// | "Assign" Exp Exp
// | "CallStmt" Exp <Id> "(" {Exp} ")"
// | "If" Exp Stmt [ "Else" Stmt ]
// | "While" Exp Stmt
// | "Print" (Exp | <StrLit>)
// | "Return" Exp
Ast.Stmt Stmt():
{
Ast.Stmt s;
Ast.Stmt s1 = null;
List<Ast.Stmt> stmtList = new ArrayList<Ast.Stmt>();
Ast.Exp e1;
Ast.Exp e2;
String nm = null;
String parg = null;
List<Ast.Exp> expList = new ArrayList<Ast.Exp>();
}
{
"{" ( s = Stmt() { stmtList.add(s); } )* "}" { return new Ast.Block(stmtList); }
| "Assign" e1 = Exp() e2 = Exp() { return new Ast.Assign(e1, e2); }
| "CallStmt" e1 = Exp() nm = ID() "(" ( e2 = Exp() { expList.add(e2); } )* ")" { return new Ast.CallStmt(e1, nm, expList); }
| "If" e1 = Exp() s = Stmt() [ LOOKAHEAD(2) "Else" s1 = Stmt() ] { return new Ast.If(e1, s, s1); }
| "While" e1 = Exp() s = Stmt() { return new Ast.While(e1, s); }
| "Print" ( e1 = Exp() { return new Ast.Print(e1); } | parg = StrLit() { return new Ast.Print(new Ast.StrLit(parg)); } )
| "Return" e1 = Exp() { return new Ast.Return(e1); }
}
//Exp -> "(" ")"
// | "(" "Binop" BOP Exp Exp ")"
// | "(" "Unop" UOP Exp ")"
// | "(" "Call" Exp <Id> "(" {Exp} ")" ")"
// | "(" "NewObj" <Id> ")"
// | "(" "Field" Exp <Id> ")"
// | "(" "NewArray" Type <IntLit> ")"
// | "(" "ArrayElm" Exp Exp ")"
// | "This"
// | <Id>
// | <IntLit>
// | <BoolLit>
Ast.Exp Exp():
{
Ast.Exp e = null;
Ast.BOP bop;
Ast.UOP uop;
Ast.Exp e1 = null;
Ast.Exp e2 = null;
String nm = null; // method name
String cn = null; // class name
String fn = null; // field name
Ast.Type t;
int len; int intlit;
boolean b;
List<Ast.Exp> expList = new ArrayList<Ast.Exp>();
}
{
"(" [ "Binop" bop = BOP() e1 = Exp() e2 = Exp() { e = new Ast.Binop(bop, e1, e2); }
| "Unop" uop = UOP() e1 = Exp() { e = new Ast.Unop(uop, e1); }
| "Call" e1 = Exp() nm = ID() "(" ( e2 = Exp() { expList.add(e2); } )* ")" { e = new Ast.Call(e1, nm, expList); }
| "NewObj" cn = ID() { e = new Ast.NewObj(cn); }
| "Field" e1 = Exp() fn = ID() { e = new Ast.Field(e1, fn); }
| "NewArray" t = Type() len = IntLit() { e = new Ast.NewArray(t, len); }
| "ArrayElm" e1 = Exp() e2 = Exp() { e = new Ast.ArrayElm(e1, e2); }
] ")" { return e; }
| "This" { return Ast.This; }
| nm = ID() { return new Ast.Id(nm); }
| intlit = IntLit() { return new Ast.IntLit(intlit); }
| b = BoolLit() { return new Ast.BoolLit(b); }
}
//BOP -> "+" | "-" | "*" | "/" | "&&" | "||"
// | "==" | "!=" | "<" | "<=" | ">" | ">="
Ast.BOP BOP(): {}
{
"+" { return Ast.BOP.ADD; }
| "-" { return Ast.BOP.SUB; }
| "*" { return Ast.BOP.MUL; }
| "/" { return Ast.BOP.DIV; }
| "&&" { return Ast.BOP.AND; }
| "||" { return Ast.BOP.OR; }
| "==" { return Ast.BOP.EQ; }
| "!=" { return Ast.BOP.NE; }
| "<" { return Ast.BOP.LT; }
| "<=" { return Ast.BOP.LE; }
| ">" { return Ast.BOP.GT; }
| ">=" { return Ast.BOP.GE; }
}
//UOP -> "-" | "!"
Ast.UOP UOP(): {}
{
"-" { return Ast.UOP.NEG; }
| "!" { return Ast.UOP.NOT; }
}
Raw
Checker.java
// This is supporting software for CS322 Compilers and Language Design II
// Copyright (c) Portland State University
//
// Static analysis for miniJava (W15) ((A starter version.)
// 1. Type-checking
// 2. Detecting missing return statement
// 3. (Optional) Detecting uninitialized variables
//
// (For CS321 Winter 2015 - Jingke Li)
//
// Name: Kai Jiang
// Email: jiangkai@gmail.com
import java.util.*;
import java.io.*;
import ast.*;
public class Checker {
static class TypeException extends Exception {
public TypeException(String msg) {
super(msg);
}
}
//------------------------------------------------------------------------------
// ClassInfo
//----------
// For easy access to class hierarchies (i.e. finding parent's info).
//
static class ClassInfo {
Ast.ClassDecl cdecl; // classDecl AST
ClassInfo parent; // pointer to parent
ClassInfo(Ast.ClassDecl cdecl, ClassInfo parent) {
this.cdecl = cdecl;
this.parent = parent;
}
// Return the name of this class
//
String className() {
return cdecl.nm;
}
// Given a method name, return the method's declaration
// - if the method is not found in the current class, recursively
// search ancestor classes; return null if all fail
//
Ast.MethodDecl findMethodDecl(String mname) {
for (Ast.MethodDecl mdecl : cdecl.mthds)
if (mdecl.nm.equals(mname))
return mdecl;
if (parent != null)
return parent.findMethodDecl(mname);
return null;
}
// Given a field name, return the field's declaration
// - if the field is not found in the current class, recursively
// search ancestor classes; return null if all fail
//
Ast.VarDecl findFieldDecl(String fname) {
for (Ast.VarDecl fdecl : cdecl.flds) {
if (fdecl.nm.equals(fname))
return fdecl;
}
if (parent != null)
return parent.findFieldDecl(fname);
return null;
}
}
//------------------------------------------------------------------------------
// Global Variables
// ----------------
// For type-checking:
// classEnv - an environment (a className-classInfo mapping) for class declarations
// typeEnv - an environment (a var-type mapping) for a method's params and local vars
// thisCInfo - points to the current class's ClassInfo
// thisMDecl - points to the current method's MethodDecl
//
// For other analyses:
// (Define as you need.)
//
private static HashMap<String, ClassInfo> classEnv = new HashMap<String, ClassInfo>();
private static HashMap<String, Ast.Type> typeEnv = new HashMap<String, Ast.Type>();
private static ClassInfo thisCInfo = null;
private static Ast.MethodDecl thisMDecl = null;
//------------------------------------------------------------------------------
// Type Compatibility Routines
// ---------------------------
// Returns true if tsrc is assignable to tdst.
//
// Pseudo code:
// if tdst==tsrc or both are the same basic type
// return true
// else if both are ArrayType // structure equivalence
// return assignable result on their element types
// else if both are ObjType // name equivalence
// if (their class names match, or
// tdst's class name matches an tsrc ancestor's class name)
// return true
// else
// return false
//
private static boolean assignable(Ast.Type tdst, Ast.Type tsrc) throws Exception {
if (tdst == tsrc
|| (tdst instanceof Ast.IntType) && (tsrc instanceof Ast.IntType)
|| (tdst instanceof Ast.BoolType) && (tsrc instanceof Ast.BoolType)) {
return true;
} else if ((tdst instanceof Ast.ArrayType) && (tsrc instanceof Ast.ArrayType)) {
return assignable((Ast.ArrayType) tdst, (Ast.ArrayType) tsrc);
} else if ((tdst instanceof Ast.ObjType) && (tsrc instanceof Ast.ArrayType)) {
if (((Ast.ObjType) tdst).nm.equals(((Ast.ObjType) tsrc).nm)) {
return true;
} else {
Ast.ClassDecl srcAncestor = classEnv.get(((Ast.ObjType) tsrc).nm).cdecl;
while (srcAncestor.pnm != null) {
if (srcAncestor.pnm.equals(((Ast.ObjType) tdst).nm)) {
return true;
} else {
srcAncestor = classEnv.get(srcAncestor.pnm).cdecl;
}
}
return false;
}
} else {
return false;
}
}
// Returns true if t1 and t2 can be compared with "==" or "!=".
//
private static boolean comparable(Ast.Type t1, Ast.Type t2) throws Exception {
return assignable(t1, t2) || assignable(t2, t1);
}
//------------------------------------------------------------------------------
// The Main Routine
//-----------------
//
public static void main(String[] args) throws Exception {
try {
if (args.length == 1) {
FileInputStream stream = new FileInputStream(args[0]);
Ast.Program p = new astParser(stream).Program();
stream.close();
check(p);
} else {
System.out.println("Need a file name as command-line argument.");
}
} catch (TypeException e) {
System.err.print(e + "\n");
} catch (Exception e) {
System.err.print(e + "\n");
}
}
//------------------------------------------------------------------------------
// Checker Routines for Individual AST Nodes
//------------------------------------------
// Program ---
// ClassDecl[] classes;
//
// 1. Sort ClassDecls, so parent will be visited before children.
// 2. For each ClassDecl, create an ClassInfo (with link to parent if exists),
// and add to classEnv.
// 3. Actual type-checking traversal over ClassDecls.
//
static void check(Ast.Program n) throws Exception {
Ast.ClassDecl[] classes = topoSort(n.classes);
for (Ast.ClassDecl c : classes) {
ClassInfo pcinfo = (c.pnm == null) ? null : classEnv.get(c.pnm);
classEnv.put(c.nm, new ClassInfo(c, pcinfo));
}
for (Ast.ClassDecl c : classes)
check(c);
}
// Utility routine
// - Sort ClassDecls based on parent-chidren relationship.
//
private static Ast.ClassDecl[] topoSort(Ast.ClassDecl[] classes) {
List<Ast.ClassDecl> cl = new ArrayList<Ast.ClassDecl>();
Vector<String> done = new Vector<String>();
int cnt = classes.length;
while (cnt > 0) {
for (Ast.ClassDecl cd : classes) {
if (!done.contains(cd.nm)
&& ((cd.pnm == null) || done.contains(cd.pnm))) {
cl.add(cd);
done.add(cd.nm);
cnt--;
}
}
}
return cl.toArray(new Ast.ClassDecl[0]);
}
// ClassDecl ---
// String nm, pnm;
// VarDecl[] flds;
// MethodDecl[] mthds;
//
// 1. Set thisCInfo pointer to this class's ClassInfo, and reset
// typeEnv to empty.
// 2. Recursively check n.flds and n.mthds.
//
static void check(Ast.ClassDecl n) throws Exception {
thisCInfo = classEnv.get(n.nm);
typeEnv.clear();
for (Ast.VarDecl var : n.flds) {
typeEnv.put(var.nm, var.t);
check(var);
}
for (Ast.MethodDecl method : n.mthds) {
typeEnv.put(method.nm, method.t);
check(method);
}
}
// MethodDecl ---
// Type t;
// String nm;
// Param[] params;
// VarDecl[] vars;
// Stmt[] stmts;
//
// 1. Set thisMDecl pointer and reset typeEnv to empty.
// 2. Recursively check n.params, n.vars, and n.stmts.
// 3. For each VarDecl, add a new name-type binding to typeEnv.
//
static void check(Ast.MethodDecl n) throws Exception {
thisMDecl = n;
typeEnv.clear();
for (Ast.Param param : n.params) {
typeEnv.put(param.nm, param.t);
check(param);
}
for (Ast.VarDecl var : n.vars) {
typeEnv.put(var.nm, var.t);
check(var);
}
//TODO
// if(n.t != null){
// boolean success = verifyReturns();
// if(!success){
// throw new TypeException("(In MethodDecl) Missing return statement");
// }
// }
}
// Param ---
// Type t;
// String nm;
//
// If n.t is ObjType, make sure its corresponding class exists.
//
static void check(Ast.Param n) throws Exception {
if (n.t instanceof Ast.ObjType) {
Ast.ObjType classnm = (Ast.ObjType) n.t;
if (!classEnv.containsKey(classnm.nm)) {
throw new TypeException("(In Param) Can't find class " + classnm.nm);
}
}
}
// VarDecl ---
// Type t;
// String nm;
// Exp init;
//
// 1. If n.t is ObjType, make sure its corresponding class exists.
// 2. If n.init exists, make sure it is assignable to the var.
//
static void check(Ast.VarDecl n) throws Exception {
}
// STATEMENTS
// Dispatch a generic check call to a specific check routine
//
static void check(Ast.Stmt n) throws Exception {
if (n instanceof Ast.Block) check((Ast.Block) n);
else if (n instanceof Ast.Assign) check((Ast.Assign) n);
else if (n instanceof Ast.CallStmt) check((Ast.CallStmt) n);
else if (n instanceof Ast.If) check((Ast.If) n);
else if (n instanceof Ast.While) check((Ast.While) n);
else if (n instanceof Ast.Print) check((Ast.Print) n);
else if (n instanceof Ast.Return) check((Ast.Return) n);
else
throw new TypeException("Illegal Ast Stmt: " + n);
}
// Block ---
// Stmt[] stmts;
//
static void check(Ast.Block n) throws Exception {
for (Ast.Stmt stmt : n.stmts) {
check(stmt);
}
}
// Assign ---
// Exp lhs;
// Exp rhs;
//
// Make sure n.rhs is assignable to n.lhs.
//
static void check(Ast.Assign n) throws Exception {
// ... need code ...
}
// CallStmt ---
// Exp obj;
// String nm;
// Exp[] args;
//
// 1. Check that n.obj is ObjType and the corresponding class exists.
// 2. Check that the method n.nm exists.
// 3. Check that the count and types of the actual arguments match those of
// the formal parameters.
//
static void check(Ast.CallStmt n) throws Exception {
// ... need code ...
}
// If ---
// Exp cond;
// Stmt s1, s2;
//
// Make sure n.cond is boolean.
//
static void check(Ast.If n) throws Exception {
Ast.Type condType = check(n.cond);
if (!(condType instanceof Ast.BoolType)) {
throw new TypeException("(In If) Cond exp type is boolean: " + condType);
}
}
// While ---
// Exp cond;
// Stmt s;
//
// Make sure n.cond is boolean.
//
static void check(Ast.While n) throws Exception {
Ast.Type condType = check(n.cond);
if (!(condType instanceof Ast.BoolType)) {
throw new TypeException("(In While) Cond exp type is boolean: " + condType);
}
}
// Print ---
// PrArg arg;
//
// Make sure n.arg is integer, boolean, or string.
//
static void check(Ast.Print n) throws Exception {
Ast.Type argType = check((Ast.Exp) n.arg);
if (n.arg == null) {
return;
}
if (!(n.arg instanceof Ast.IntType
|| n.arg instanceof Ast.StrLit
|| n.arg instanceof Ast.BoolType)) {
throw new TypeException("(In Print) Arg type is not int, boolean, or string: " + argType);
}
}
// Return ---
// Exp val;
//
// If n.val exists, make sure it matches the expected return type.
//
static void check(Ast.Return n) throws Exception {
// ... need code ...
}
// EXPRESSIONS
// Dispatch a generic check call to a specific check routine
//
static Ast.Type check(Ast.Exp n) throws Exception {
if (n instanceof Ast.Binop) return check((Ast.Binop) n);
if (n instanceof Ast.Unop) return check((Ast.Unop) n);
if (n instanceof Ast.Call) return check((Ast.Call) n);
if (n instanceof Ast.NewArray) return check((Ast.NewArray) n);
if (n instanceof Ast.ArrayElm) return check((Ast.ArrayElm) n);
if (n instanceof Ast.NewObj) return check((Ast.NewObj) n);
if (n instanceof Ast.Field) return check((Ast.Field) n);
if (n instanceof Ast.Id) return check((Ast.Id) n);
if (n instanceof Ast.This) return check((Ast.This) n);
if (n instanceof Ast.IntLit) return check((Ast.IntLit) n);
if (n instanceof Ast.BoolLit) return check((Ast.BoolLit) n);
throw new TypeException("Exp node not recognized: " + n);
}
// Binop ---
// BOP op;
// Exp e1,e2;
//
// Make sure n.e1's and n.e2's types are legal with respect to n.op.
//
static Ast.Type check(Ast.Binop n) throws Exception {
Ast.Type t1 = check(n.e1);
Ast.Type t2 = check(n.e2);
if (comparable(t1, t2)) {
switch (n.op) {
case ADD:
case SUB:
case MUL:
case DIV:
if (t1 instanceof Ast.IntType) {
return new Ast.IntType();
} else {
throw new TypeException("(In Binop) Wrong operand type: " + t1 + " with " + n.op);
}
case AND:
case OR:
if (t1 instanceof Ast.IntType)
throw new TypeException("(In Binop) Wrong operand type: " + t1 + " with " + n.op);
default:
return new Ast.BoolType();
}
} else {
throw new TypeException("(In Binop) Operand types don't match: " + t1 + " " + n.op + " " + t2);
}
}
// Unop ---
// UOP op;
// Exp e;
//
// Make sure n.e's type is legal with respect to n.op.
//
static Ast.Type check(Ast.Unop n) throws Exception {
if(!(n.e instanceof Ast.IntLit || n.e instanceof Ast.BoolLit)){
Ast.Type type = check(n.e);
if (type instanceof Ast.IntType){
if (n.op.equals(Ast.UOP.NEG)){
return new Ast.IntType ();
} else{
throw new TypeException("(In Unop) Bad operand type: " + n.op + " IntType");
}
} else if (type instanceof Ast.BoolType){
if (n.op.equals(Ast.UOP.NOT)){
return new Ast.BoolType();
} else{
throw new TypeException("(In Unop) Bad operand type: " + n.op + " BoolType" );
}
}
} else if (n.e instanceof Ast.IntLit){
if(n.op.equals(Ast.UOP.NEG)){
return new Ast.IntType ();
} else{
throw new TypeException("(In Unop) Bad operand type: " + n.op + " IntType");
}
} else {
if (n.op.equals(Ast.UOP.NOT)){
return new Ast.BoolType();
} else{
throw new TypeException("(In Unop) Bad operand type: " + n.op + " BoolType");
}
}
throw new TypeException("(In Unop) Type is not integer or boolean");
}
// Call ---
// Exp obj;
// String nm;
// Exp[] args;
//
// (See the hints in CallStmt.)
// In addition, this routine needs to return the method's return type.
//
static Ast.Type check(Ast.Call n) throws Exception {
// ... need code ...
}
// NewArray ---
// Type et;
// int len;
//
// 1. Verify that n.et is either integer or boolean.
// 2. Varify that n.len is non-negative.
// (Note: While the AST representation allows these cases to happen, our
// miniJava parser does not, so these checks are not very meaningful.)
//
static Ast.Type check(Ast.NewArray n) throws Exception {
if (n.et instanceof Ast.IntType || n.et instanceof Ast.BoolType) {
if (n.len >= 0) {
return new Ast.ArrayType(n.et);
} else {
throw new TypeException("(In NewArray) Index cannot be negative");
}
} else {
throw new TypeException("(In NewArray) Type should be either integer or boolean");
}
}
// ArrayElm ---
// Exp ar, idx;
//
// Varify that n.ar is array and n.idx is integer.
//
static Ast.Type check(Ast.ArrayElm n) throws Exception {
// ... need code ...
}
// NewObj ---
// String nm;
//
// Verify that the corresponding class exists.
//
static Ast.Type check(Ast.NewObj n) throws Exception {
if (classEnv.containsKey(n.nm)) {
return new Ast.ObjType(n.nm);
} else {
throw new TypeException("(In NewObj) Can't find class " + n.nm);
}
}
// Field ---
// Exp obj;
// String nm;
//
// 1. Verify that n.onj is ObjType, and its corresponding class exists.
// 2. Verify that n.nm is a valid field in the object.
//
static Ast.Type check(Ast.Field n) throws Exception {
// ... need code ...
}
// Id ---
// String nm;
//
// 1. Check if n.nm is in typeEnv. If so, the Id is a param or a local var.
// Obtain and return its type.
// 2. Otherwise, the Id is a field variable. Find and return its type (through
// the current ClassInfo).
//
static Ast.Type check(Ast.Id n) throws Exception {
if (typeEnv.containsKey(n.nm)) {
return typeEnv.get(n.nm);
} else {
Ast.VarDecl r = thisCInfo.findFieldDecl(n.nm);
if (r == null) {
throw new TypeException("(In Id) Can't find variable " + n.nm);
}
return r.t;
}
}
// This ---
//
// Find and return an ObjType that corresponds to the current class
// (through the current ClassInfo).
//
static Ast.Type check(Ast.This n) {
return typeEnv.get(thisCInfo.className());
}
// Literals
//
public static Ast.Type check(Ast.IntLit n) {
return Ast.IntType;
}
public static Ast.Type check(Ast.BoolLit n) {
return Ast.BoolType;
}
public static void check(Ast.StrLit n) {
// nothing to check or return
}
}
Raw
mjLexer.java
//----------------------------------------------------------------------
// A starting version of miniJava (W15) lexer.
//
// (For CS321 Winter 2015)
//----------------------------------------------------------------------
// Date: Jan 2015
// author: Kai Jiang
// email: jiangkai@pdx.edu
import java.io.FileReader;
import java.io.PushbackReader;
import java.util.HashMap;
public class mjLexer implements mjTokenConstants {
// Line and column numbers
static int currLine, currColumn, beginLine, beginColumn;
static FileReader reader = null;
static PushbackReader pbReader = null;
static class LexError extends Exception {
public LexError(int line, int column, String msg) {
super("at (" + line + "," + column + ") " + msg);
}
}
// Token object
//
static class Token {
int code; // token code
String lexeme; // lexeme string
int line; // line number of token's first char
int column; // column number of token's first char
public Token(int code, String lexeme, int line, int column) {
this.code = code;
this.lexeme = lexeme;
this.line = line;
this.column = column;
}
public String toString() {
return "(" + line + "," + column + ") " + code + " " + lexeme;
}
}
// The main method
//
public static void main(String[] args) {
try {
if (args.length == 1) {
Token tkn;
int tknCnt = 0;
currLine = 1;
currColumn = 0;
// reader = new FileReader("error/error02.in");
reader = new FileReader(args[0]);
pbReader = new PushbackReader(reader);
while ((tkn = nextToken()) != null) {
System.out.print("(" + tkn.line + "," + tkn.column + ")\t");
switch (tkn.code) {
case ID:
System.out.println("ID(" + tkn.lexeme + ")");
break;
case INTLIT:
System.out.println("INTLIT(" + tkn.lexeme + ")");
break;
case DBLLIT:
System.out.println("DBLLIT(" + tkn.lexeme + ")");
break;
case STRLIT:
System.out.println("STRLIT(" + tkn.lexeme + ")");
break;
//reserved keywords
case TRUE:
case FALSE:
case CLASS:
case EXTENDS:
case STATIC:
case PUBLIC:
case VOID:
case MAIN:
case INT:
case DOUBLE:
case STRING:
case BOOLEAN:
case NEW:
case THIS:
case IF:
case ELSE:
case SYSTEM:
case OUT:
case PRINTLN:
case WHILE:
case RETURN:
case EQ:
case NEQ:
case LE:
case GE:
case AND:
case OR:
case '+':
case '-':
case '*':
case '/':
case '!':
case '<':
case '>':
case '=':
case ';':
case ',':
case '.':
case '(':
case ')':
case ']':
case '[':
case '{':
case '}':
default:
System.out.println(tkn.lexeme);
}
tknCnt++;
}
// int tmp;
// while( (tmp = nextChar() ) != -1 ){
// System.out.print((char)tmp);
// }
System.out.println("Total: " + tknCnt + " tokens");
reader.close();
pbReader.close();
} else {
System.err.println("Need a file name as command-line argument.");
}
} catch (LexError e) {
System.err.println(e);
} catch (Exception e) {
System.err.println(e);
}
}
private static int peek() throws Exception {
int next = pbReader.read();
pbReader.unread(next);
return next;
}
private static int nextChar() throws Exception {
//fixme windows '\r\n'
int c = pbReader.read();
if (c == '\n') {
currLine++;
currColumn = 0;
} else {
currColumn++;
}
return c;
}
// Return the next token
//
private static Token nextToken() throws Exception {
for (; ; ) {
int c = nextChar();
//skip while space trick (windows newline carriage return '\r')
while (isWhiteSpace(c)) {
c = peek();
if (!isWhiteSpace(c)) {
if (c == -1) {
return null;
} else {
c = nextChar();
break;
}
} else {
c = nextChar();
}
}
//init begin mark of column and line
beginColumn = currColumn;
beginLine = currLine;
switch (c) {
//EOF
case ((char) -1):
case -1:
return null;
// single-character operators/delimiters
case '+':
return new Token('+', "+", beginLine, beginColumn);
case '-':
return new Token('-', "-", beginLine, beginColumn);
case '*':
return new Token('*', "*", beginLine, beginColumn);
case '!':
if (peek() == '=') {
nextChar();
return new Token(NEQ, "!=", beginLine, beginColumn);
} else {
return new Token('!', "!", beginLine, beginColumn);
}
case '<':
if (peek() == '=') {
nextChar();
return new Token(LE, "<=", beginLine, beginColumn);
} else {
return new Token('<', "<", beginLine, beginColumn);
}
case '>':
if (peek() == '=') {
nextChar();
return new Token(LE, ">=", beginLine, beginColumn);
} else {
return new Token('>', ">", beginLine, beginColumn);
}
case '=':
if (peek() == '=') {
nextChar();
return new Token(EQ, "==", beginLine, beginColumn);
} else {
return new Token('=', "=", beginLine, beginColumn);
}
case ';':
return new Token(';', ";", beginLine, beginColumn);
case ',':
return new Token(',', ",", beginLine, beginColumn);
case '.':
//Double number without prefix( integer part )
//char after '.' is Digit, return double literal (Example Pattern : (.123) = (0.123) )
if (isDigit(peek())) {
StringBuilder buffer = new StringBuilder();
buffer.append('.');
buffer.append((char) nextChar());
while (isDigit(peek())) {
buffer.append((char) nextChar());
}
return new Token(DBLLIT, Double.toString(Double.parseDouble(buffer.toString())), beginLine, beginColumn);
} else {
return new Token('.', ".", beginLine, beginColumn);
}
case '(':
return new Token('(', "(", beginLine, beginColumn);
case ')':
return new Token(')', ")", beginLine, beginColumn);
case '[':
return new Token('[', "[", beginLine, beginColumn);
case ']':
return new Token(']', "]", beginLine, beginColumn);
case '{':
return new Token('{', "{", beginLine, beginColumn);
case '}':
return new Token('}', "}", beginLine, beginColumn);
case '&':
if (peek() == '&') {
nextChar();
return new Token(AND, "&&", beginLine, beginColumn);
} else {
throw new LexError(currLine, currColumn, "Illegal char: &");
}
case '|':
if (peek() == '|') {
nextChar();
return new Token(OR, "||", beginLine, beginColumn);
} else {
throw new LexError(currLine, currColumn, "Illegal char: |");
}
case '/':
if (peek() == '/') { // single line comment
int tmp;
nextChar(); //eat second '/'
while ((tmp = peek()) != '\n') {
if (tmp == -1) { // handle with last line followed with EOF
return null;
}
nextChar();
} //eat before newline '\n'
nextChar(); //eat '\n'
continue;
} else if (peek() == '*') { // bracket comment
nextChar();
for (; ; ) {
if (peek() == '*') {
nextChar();
while (peek() == '*') {
nextChar();
}
if (peek() == '/') {
nextChar();
break;
}
} else if (peek() == (char) -1) {
throw new LexError(beginLine, beginColumn, "unterminated multi-line comments");
} else {
nextChar();
}
}
continue;
} else { // single '/' sign
return new Token('/', "/", beginLine, beginColumn);
}
default:
//ID and keywords
if (isLetter(c)) {
StringBuilder buffer = new StringBuilder();
buffer.append((char) c);
while (isLetterOrDigit(peek())) { //id: first char must be letter, following char can be letter or number
buffer.append((char) nextChar());
}
if (reserved.containsKey(buffer.toString())) {
//if buffer is in the reserved keywords
return new Token(reserved.get(buffer.toString()), buffer.toString(), beginLine, beginColumn);
} else {
return new Token(ID, buffer.toString(), beginLine, beginColumn);
}
}
//number literal
//fixme double
if (isDigit(c)) {
StringBuilder buffer = new StringBuilder();
//legal numbers:
//Oct 0000123 01234
//Hex 0x12af3 0x000123
if (c == '0') {
int tmp = peek(); //closest char after first number 0
if (tmp == 'x' || tmp == 'X') {
nextChar(); //eat 'x'
while (isHex(peek())) {
buffer.append((char) nextChar());
}
if (buffer.toString().length() == 0) {
throw new LexError(beginLine, beginColumn, "ill-formed hexadecimal integers");
}
Long t;
t = Long.parseLong(buffer.toString(), 16);
if (t > Integer.MAX_VALUE) {
throw new LexError(beginLine, beginColumn, "integer overflow " + buffer.toString());
} else {
return new Token(INTLIT, Integer.toString(Integer.parseInt(buffer.toString(), 16)), beginLine, beginColumn);
}
} else if (isOctal(tmp)) {
//treat 008 as two tokens
buffer.append((char) nextChar()); //insert next number after first number 0 into buffer
while (isOctal(peek())) {
buffer.append((char) nextChar());
}
// read until not digit then judge whether is Octal , if not throw exception
// while (isDigit(peek())) {
// buffer.append((char) nextChar());
// }
// boolean flag = false;
// String BUFFER = buffer.toString();
// for (int i = 0; i < BUFFER.length(); i++){
// if (!isOctal(BUFFER.charAt(i))){
// flag = true;
// break;
// }
// }
// if (flag == true ){
// throw new LexError(beginLine, beginColumn, "ill-formed octal integers " + BUFFER);
// } else {
Long t;
t = Long.parseLong(buffer.toString(), 8);
if (t > Integer.MAX_VALUE) {
throw new LexError(beginLine, beginColumn, "integer overflow " + buffer.toString());
} else {
return new Token(INTLIT, Integer.toString(Integer.parseInt(buffer.toString(), 8)), beginLine, beginColumn);
}
// }
} else if (isDot(tmp)) { // Double number (0.nnnnnnn)
nextChar(); // eat '.'
buffer.append('0');
buffer.append('.');
while (isDigit(peek())) {
buffer.append((char) nextChar());
}
return new Token(DBLLIT, Double.toString(Double.parseDouble(buffer.toString())), beginLine, beginColumn);
} else { //handle single zero
buffer.append((char) c);
return new Token(INTLIT, buffer.toString(), beginLine, beginColumn);
}
} else {
//normal number and Double number with integer part
// flag used to mark there is only one point among double literal
// flag equals false that means number literal without point
// flag equals true that means there has exists one point among number literal,
// afterwards we must move on and only recognize digits and treat point followed as another point.
boolean flag = false;
int tmp;
buffer.append((char) c);
tmp = peek();
for (; ; ) {
if (isDigitOrDot(tmp)) {
//has accept one point must jump out for loop
if (isDot(tmp) && (flag == true)) {
break;
} else if (isDot(tmp) && (flag == false)) {
flag = true;
buffer.append((char) nextChar());
tmp = peek();
continue;
} else if (isDigit(tmp)) {
buffer.append((char) nextChar());
tmp = peek();
continue;
}
} else {
break;
}
}
// for(;;){
// tmp = peek();
// if ( isDot(tmp) ){
// nextChar(); //eat '.'
// flag = true;
// buffer.append('.');
//
// while( isDigit(peek() ) ){
// buffer.append((char) nextChar());
// }
// break;
// } else if ( isDigit(tmp) ){
// nextChar();
// buffer.append((char) tmp);
// while( isDigit(peek() ) ){
// buffer.append((char) nextChar());
// }
// break;
// } else {
// break;
// }
// }
if (flag == false) {
Long t;
t = Long.parseLong(buffer.toString());
if (t > Integer.MAX_VALUE) {
throw new LexError(beginLine, beginColumn, "integer overflow " + buffer.toString());
} else {
return new Token(INTLIT, Integer.toString(Integer.parseInt(buffer.toString())), beginLine, beginColumn);
}
} else {
return new Token(DBLLIT, Double.toString(Double.parseDouble(buffer.toString())), beginLine, beginColumn);
}
}
}
//string literal
if (isQuotationMark(c)) {
StringBuilder buffer = new StringBuilder();
buffer.append((char) c);
int tmp;
tmp = peek();
while (!isQuotationMark(tmp)) {
if (tmp == (char) -1 || tmp == -1) { //confront EOF unterminated strings
throw new LexError(currLine, currColumn, "unterminated strings");
}
buffer.append((char) nextChar());
tmp = peek();
}
buffer.append((char) nextChar());
return new Token(STRLIT, buffer.toString(), beginLine, beginColumn);
}
throw new LexError(currLine, currColumn, "Illegal char: " + (char) c);
}
}
}
private static HashMap<String, Integer> reserved;
//reserved keywords
static {
reserved = new HashMap<String, Integer>();
reserved.put("true", TRUE);
reserved.put("false", FALSE);
reserved.put("class", CLASS);
reserved.put("extends", EXTENDS);
reserved.put("static", STATIC);
reserved.put("public", PUBLIC);
reserved.put("void", VOID);
reserved.put("main", MAIN);
reserved.put("int", INT);
reserved.put("double", DOUBLE);
reserved.put("String", STRING);
reserved.put("boolean", BOOLEAN);
reserved.put("new", NEW);
reserved.put("this", THIS);
reserved.put("if", IF);
reserved.put("else", ELSE);
reserved.put("System", SYSTEM);
reserved.put("out", OUT);
reserved.put("println", PRINTLN);
reserved.put("while", WHILE);
reserved.put("return", RETURN);
}
// Utility routines
//
private static boolean isLetter(int c) {
return (('A' <= c) && (c <= 'Z')
|| ('a' <= c) && (c <= 'z'));
}
private static boolean isDigit(int c) {
return ('0' <= c) && (c <= '9');
}
private static boolean isDot(int c) {
return (c == '.');
}
//for Double number
private static boolean isDigitOrDot(int c) {
return isDigit(c) || isDot(c);
}
private static boolean isLetterOrDigit(int c) {
return isLetter(c) || isDigit(c);
}
private static boolean isQuotationMark(int c) {
return c == '"';
}
private static boolean isOctal(int c) {
return ('0' <= c) && (c <= '7');
}
private static boolean isHex(int c) {
return ('0' <= c) && (c <= '9')
|| ('A' <= c) && (c <= 'F')
|| ('a' <= c) && (c <= 'f');
}
private static boolean isWhiteSpace(int c) {
return (c == ' ') || (c == '\t') || (c == '\f') || (c == '\n') || (c == '\r');
}
}
Raw
mjLLGrammar.jj
// This is supporting software for CS321 Compilers and Language Design I
// Copyright (c) Portland State University
//
//----------------------------------------------------------------------
// miniJava Raw Grammar (JavaCC Specification)
//
// (For CS321 Winter 2015 - Jingke Li)
//----------------------------------------------------------------------
//
// Name: Kai Jiang
// Email: jiangkai@pdx.edu
// options { DEBUG_PARSER=true; } /* Show debugging info */
PARSER_BEGIN(mjLLGrammar)
import java.io.*;
public class mjLLGrammar {
public static void main(String [] args) {
try {
if (args.length == 1) {
FileInputStream stream = new FileInputStream(args[0]);
new mjLLGrammar(stream).Program();
stream.close();
} else {
System.out.println("Need a file name as command-line argument.");
}
} catch (TokenMgrError e) {
System.err.println(e);
} catch (Exception e) {
System.err.println(e);
}
}
}
PARSER_END(mjLLGrammar)
//
// LEXER SECTION ---------------------------------------------------------------
//
SKIP : /* White space */
{
" " | "\t" | "\n" | "\r" | "\f"
}
SKIP : /* Comments -- multi-line form and error detection not included */
{
<"//" (~["\n","\r"])* ("\n"|"\r"|"\r\n")>
}
TOKEN : /* Keywords */
{
"class" | "extends" | "static" | "public" | "void" | "int" | "double"
| "boolean" | "new" | "this" | "if" | "else" | "while" | "return" | "main"
| "true" | "false" | "String" | "System" | "out" | "println"
}
TOKEN : /* Internal tokens */
{
<#DIGIT: ["0"-"9"]>
| <#LETTER: (["A"-"Z"]|["a"-"z"])>
}
TOKEN : /* Integer literals */
{
<INTLIT: (<DIGIT>)+>
{ try {
Integer.parseInt(matchedToken.image);
} catch (Exception e) {
throw new TokenMgrError("Lexical error at line " + matchedToken.beginLine +
", column " + matchedToken.beginColumn +
". Integer overflow: " + matchedToken.image, 0);
}
}
}
TOKEN : /* Double literals */
{
<DBLLIT: (<DIGIT>)+"."(<DIGIT>)*|(<DIGIT>)*"."(<DIGIT>)+>
{ try {
Double.parseDouble(matchedToken.image);
} catch (Exception e) {
throw new TokenMgrError("Lexical error at line " + matchedToken.beginLine +
", column " + matchedToken.beginColumn +
". Malformed double: " + matchedToken.image, 0);
}
}
}
TOKEN : /* String literals */
{
<STRLIT: ("\"" (~["\"","\n"])* "\"")>
}
TOKEN : /* Identifiers */
{
<ID: <LETTER> (<LETTER>|<DIGIT>)*>
}
TOKEN : /* Operators and delimiters */
{
"+" | "-" | "*" | "/" | "&&" | "||" | "!"
| "==" | "!=" | "<" | "<=" | ">" | ">="
| "=" | ";" | "," | "." | "(" | ")" | "[" | "]" | "{" | "}"
}
//
// PARSER SECTION ---------------------------------------------------------------
//
// Program -> {ClassDecl}
//
void Program(): {}
{
(ClassDecl())* <EOF>
}
// ClassDecl -> "class" <ID> ["extends" <ID>] "{" {VarDecl} {MethodDecl} "}"
//
void ClassDecl(): {}
{
"class" <ID> ["extends" <ID>] "{" (VarDecl())* (MethodDecl())* "}"
}
//MethodDecl -> "public" MethodDeclPrime
// "{" {VarDecl} {Stmt} "}"
void MethodDecl(): {}
{
"public" MethodDeclPrime() "{" ( LOOKAHEAD(2) VarDecl())* (Stmt())* "}"
}
//MethodDeclPrime -> ExtType <ID> "(" [Param {"," Param}] ")"
// | "static" "void" "main" "(" "String" "[" "]" <ID> ")"
void MethodDeclPrime(): {}
{
ExtType() <ID> "(" [Param() ("," Param())*] ")"
| "static" "void" "main" "(" "String" "[" "]" <ID> ")"
}
// Param -> Type <ID>
//
void Param(): {}
{
Type() <ID>
}
// VarDecl -> Type <ID> ["=" InitExpr] ";"
//
void VarDecl(): {}
{
Type() <ID> ["=" InitExpr()] ";"
}
// ExtType -> Type | "void"
//
void ExtType(): {}
{
Type() | "void"
}
// Type -> BasicType
// | BasicType "[" "]"
// | <ID>
void Type(): {}
{
BasicType() TypePrime()
| <ID>
}
// TypePrime -> epsilon
// | "[" "]"
void TypePrime(): {}
{
[ "[" "]" ]
}
// BasicType -> "int" | "double" | "boolean"
//
void BasicType(): {}
{
"int" | "double" | "boolean"
}
// Stmt -> "{" {Stmt} "}"
// | ExtId StmtPrime ";"
// | "if" "(" Expr ")" Stmt ["else" Stmt]
// | "while" "(" Expr ")" Stmt
// | "System" "." "out" "." "println" "(" [PrArg] ")" ";"
// | "return" [Expr] ";"
//
void Stmt(): {}
{
"{" (Stmt())* "}"
| ExtId() StmtPrime() ";"
| "if" "(" Expr() ")" Stmt() ["else" Stmt()]
| "while" "(" Expr() ")" Stmt()
| "System" "." "out" "." "println" "(" [ PrArg() ] ")" ";"
| "return" [Expr()] ";"
}
//StmtPrime -> "(" [Args] ")"
// | [ "[" Expr "]" ] "=" InitExpr
//
void StmtPrime(): {}
{
"(" [Args()] ")"
| [ "[" Expr() "]" ] "=" InitExpr()
}
// Args -> Expr {"," Expr}
//
void Args(): {}
{
Expr() ("," Expr())*
}
// PrArg -> Expr | <STRLIT>
//
void PrArg(): {}
{
Expr() | <STRLIT>
}
// InitExpr -> "new" InitExprPrime
// | Expr
void InitExpr(): {}
{
"new" InitExprPrime()
| Expr()
}
// InitExprPrime -> BasicType "[" <INTLIT> "]"
// | <ID> "(" ")"
void InitExprPrime(): {}
{
BasicType() "[" <INTLIT> "]"
| <ID> "(" ")"
}
//Expr -> Expr1 { "||" Expr1 }
void Expr(): {}
{
Expr1() ( "||" Expr1() )*
}
//Expr1 -> Expr2 { "&&" Expr2 }
void Expr1(): {}
{
Expr2() ( "&&" Expr2() )*
}
//Expr2 -> Expr3 {CompareOp Expr3}
//
void Expr2(): {}
{
Expr3() (CompareOp() Expr3() )*
}
//Expr3 -> Expr4 { ("+"|"-") Expr4 }
void Expr3(): {}
{
Expr4() ( ("+"|"-") Expr4() )*
}
//Expr4 -> Expr5 { ("*"|"/") Expr5 }
void Expr4(): {}
{
Expr5() ( ("*"|"/") Expr5() )*
}
//Expr5 -> {UnOp} Expr6
void Expr5(): {}
{
(UnOp() )* Expr6()
}
// Expr6 -> "(" Expr ")"
// | ExtId ["(" [Args()] ")" | "[" Expr "]" ]
// | Literal
void Expr6(): {}
{
"(" Expr() ")"
| ExtId() ["(" [Args()] ")" | "[" Expr() "]" ]
| Literal()
}
// Lvalue -> ExtId() LvaluePrime()
// LvaluePrime -> "[" Expr "]"
// | epsilon
void Lvalue(): {}
{
ExtId() LvaluePrime()
}
void LvaluePrime(): {}
{
[ "[" Expr() "]" ]
}
// ExtId -> ["this" "."] <ID> {"." <ID>}
//
void ExtId(): {}
{
["this" "."] <ID> ("." <ID>)*
}
// Literal -> <INTLIT> | <DBLLIT> | "true" | "false"
//
void Literal(): {}
{
<INTLIT> | <DBLLIT> | "true" | "false"
}
// CompareOp -> "==" | "!=" | "<=" | ">=" | "<" | ">"
void CompareOp(): {}
{
"==" | "!=" | "<=" | ">=" | ">" | "<"
}
// UnOp -> "-" | "!"
//
void UnOp(): {}
{
"-" | "!"
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment