Anatomy of a Small CompilerCOMS W4115Prof. Stephen A. EdwardsFall 2003Columbia UniversityDepartment of Computer ScienceMxMxA Programming Langauge for Scientific ComputationResembles Matlab, Octave, Mathematica, etc.Project from Spring 2003Authors:Tiantian ZhouHanhua FengYong Man RaChang Woo LeeExamplePlotting the Lorenz equationsdy0dt= α(y1− y0)dy1dt= y0(r − y2) − y1dy2dt= y0y1− by2Mx source part 1/* Lorenz equation parameters */a = 10;b = 8/3.0;r = 28;/* Two-argument function returning a vector */func Lorenz ( y, t ) = [ a*(y[1]-y[0]);-y[0]*y[2] + r*y[0] - y[1];y[0]*y[1] - b*y[2] ];/* Runge-Kutta numerical integration procedure */func RungeKutta( f, y, t, h ) {k1 = h * f( y, t );k2 = h * f( y+0.5*k1, t+0.5*h );k3 = h * f( y+0.5*k2, t+0.5*h );k4 = h * f( y+k3, t+h );return y + (k1+k4)/6.0 + (k2+k3)/3.0;}Mx source part 2/* Parameters for the procedure */N = 20000;p = zeros(N+1,3);t = 0.0;h = 0.001;x = [ 10; 0; 10 ];p[0,:] = x’; /* matrix transpose */for ( i = 1:N ) {x = RungeKutta( Lorenz, x, t, h );p[i,:] = x’;t += h;}colormap(3);plot(p);return 0;Resultfile lines roleScanner and Parser: Builds the treegrammar.g 314 Lexer/Parser (ANTLR source)Interpreter: Walks the tree, invokes objects’ methodswalker.g 170 Tree Walker (ANTLR source)MxInterpreter.java 359 Function invocation, etc.MxSymbolTable.java 109 Name-to-object mappingTop-level: Invokes the interpreterMxMain.java 153 Command-line interfaceMxException.java 13 Error reportingRuntime system: Represents data, performs operationsMxDataType.java 169 Base classMxBool.java 63 BooleansMxInt.java 152 IntegersMxDouble.java 142 Floating-pointMxString.java 47 StringMxVariable.java 26 Undefined variableMxFunction.java 81 User-defined functionsMxInternalFunction.m4 410 sin, cos, etc. (macro processed)jamaica/Matrix.java 1387 MatricesMxMatrix.java 354 Wrapperjamaica/Range.java 163 e.g., 1:10MxRange.java 67 Wrapperjamaica/BitArray.java 226 Matrix masksMxBitArray.java 47 Wrapperjamaica/Painter.java 339 Bitmapsjamaica/Plotter.java 580 2-D plottingtotal 5371The Scannerclass MxAntlrLexer extends Lexer;options {k = 2;charVocabulary = ’\3’..’\377’;testLiterals = false;exportVocab = MxAntlr;}protected ALPHA : ’a’..’z’ | ’A’..’Z’ | ’_’;protected DIGIT : ’0’..’9’;WS : (’ ’ | ’\t’)+ { $setType(Token.SKIP); } ;NL : (’\n’ | (’\r’ ’\n’) => ’\r’ ’\n’ | ’\r’){ $setType(Token.SKIP); newline(); } ;The ScannerCOMMENT : ( "/*" ( options {greedy=false;} :NL| ˜( ’\n’ | ’\r’ ))* "*/"| "//" (˜( ’\n’ | ’\r’ ))* NL) { $setType(Token.SKIP); } ;LDV_LDVEQ : "/’" ((’=’) => ’=’ { $setType(LDVEQ); }| { $setType(LDV); });The ScannerLPAREN : ’(’;RPAREN : ’)’;/* ... */TRSP : ’\’’;COLON : ’:’;DCOLON : "::";ID options { testLiterals = true; }: ALPHA (ALPHA|DIGIT)* ;NUMBER : (DIGIT)+ (’.’ (DIGIT)*)?((’E’|’e’) (’+’|’-’)? (DIGIT)+)? ;STRING : ’"’!( ˜(’"’ | ’\n’) | (’"’! ’"’) )*’"’! ;The Parser: Top-levelclass MxAntlrParser extends Parser;options {k = 2;buildAST = true;exportVocab = MxAntlr;}tokens {STATEMENT;FOR_CON;/* ... */}program : ( statement | func_def )* EOF!{ #program = #([STATEMENT,"PROG"], program); };The Parser: Statementsstatement: for_stmt| if_stmt| loop_stmt| break_stmt| continue_stmt| return_stmt| load_stmt| assignment| func_call_stmt| LBRACE! (statement)* RBRACE!{#statement = #([STATEMENT,"STATEMENT"], statement); };The Parser: Statements 1for_stmt : "for"ˆ LPAREN! for_con RPAREN! statement ;for_con : ID ASGN! range (COMMA! ID ASGN! range)*{ #for_con = #([FOR_CON,"FOR_CON"], for_con); };if_stmt : "if"ˆ LPAREN! expression RPAREN! statement(options {greedy = true;}: "else"! statement )?;loop_stmt! : "loop" ( LPAREN! id:ID RPAREN! )? stmt:statement{ if ( null == #id )#loop_stmt = #([LOOP,"loop"], #stmt);else#loop_stmt = #([LOOP,"loop"], #stmt, #id);} ;The Parser: Statements 2break_stmt : "break"ˆ (ID)? SEMI! ;continue_stmt : "continue"ˆ (ID)? SEMI! ;return_stmt : "return"ˆ (expression)? SEMI! ;load_stmt : "include"ˆ STRING SEMI! ;assignment: l_value ( ASGNˆ | PLUSEQˆ | MINUSEQˆ | MULTEQˆ| LDVEQˆ | MODEQˆ | RDVEQˆ) expression SEMI!;func_call_stmt : func_call SEMI! ;func_call: ID LPAREN! expr_list RPAREN!{ #func_call = #([FUNC_CALL,"FUNC_CALL"], func_call); };The Parser: Function Definitionsfunc_def: "func"ˆ ID LPAREN! var_list RPAREN! func_body;var_list: ID ( COMMA! ID )*{ #var_list = #([VAR_LIST,"VAR_LIST"], var_list); }| { #var_list = #([VAR_LIST,"VAR_LIST"], var_list); };func_body: ASGN! a:expression SEMI!{ #func_body = #a; }| LBRACE! (statement)* RBRACE!{ #func_body = #([STATEMENT,"FUNC_BODY"], func_body); };The Parser: Expressionsexpression : logic_term ( "or"ˆ logic_term )* ;logic_term : logic_factor ( "and"ˆ logic_factor )* ;logic_factor : ("not"ˆ)? relat_expr ;relat_expr : arith_expr ( (GEˆ | LEˆ | GTˆ| LTˆ | EQˆ | NEQˆ) arith_expr )? ;arith_expr : arith_term ( (PLUSˆ | MINUSˆ) arith_term )* ;arith_term : arith_factor( (MULTˆ | LDVˆ | MODˆ | RDVˆ) arith_factor )* ;arith_factor: PLUS! r_value{ #arith_factor = #([UPLUS,"UPLUS"], arith_factor); }| MINUS! r_value{ #arith_factor = #([UMINUS,"UMINUS"], arith_factor); }| r_value (TRSPˆ)*;r_value: l_value | func_call | NUMBER | STRING | "true" | "false"| array | LPAREN! expression RPAREN! ;l_value : IDˆ ( LBRK! index RBRK! )* ;The Walker: Top-level{import java.io.*;import java.util.*;}class MxAntlrWalker extends TreeParser;options{importVocab = MxAntlr;}{static MxDataType null_data = new MxDataType( "<NULL>" );MxInterpreter ipt = new MxInterpreter();}The Walker: Expressionsexpr returns [ MxDataType r ]{MxDataType a, b;Vector v;MxDataType[] x;String s = null;String[] sx;r = null_data;}: #("or" a=expr right_or:.){ if ( a instanceof MxBool )r = ( ((MxBool)a).var ? a : expr(#right_or) );elser = a.or( expr(#right_or) );}| #("and" a=expr right_and:.){ if ( a instanceof MxBool )r = ( ((MxBool)a).var ? expr(#right_and) : a );elser = a.and( expr(#right_and) );}The Walker: Simple operators| #("not" a=expr) { r = a.not(); }| #(GE a=expr b=expr) { r = a.ge( b ); }| #(LE a=expr b=expr) { r = a.le( b ); }| #(GT a=expr b=expr) { r = a.gt( b ); }| #(LT a=expr b=expr) { r = a.lt( b ); }| #(EQ a=expr b=expr) { r = a.eq( b ); }| #(NEQ a=expr b=expr) { r = a.ne( b ); }| #(PLUS a=expr b=expr) { r = a.plus( b ); }| #(MINUS a=expr b=expr) { r = a.minus( b ); }| #(MULT a=expr b=expr) { r = a.times( b ); }| #(LDV a=expr b=expr) { r =
View Full Document
Unlocking...