CSC448: Lecture 1 (Introduction, Scanners)

Contents [0/22]

Are You In The Right Room? [1/22]
Overview of Today's Class [2/22]
Overview: Course Overview [3/22]
Overview: Why take this course? [4/22]
Admin: Course Homepage [5/22]
Admin: Contact Information [6/22]
Admin: Course Mailing List [7/22]
Admin: Attendance [8/22]
Admin: COL [9/22]
Admin: Assessment [10/22]
Admin: Plagiarism [11/22]
Admin: Textbooks [12/22]
Admin: Prerequisites [13/22]
Admin: Expectations [14/22]
Admin: Installing Eclipse [15/22]
Scanning/Parsing: Scanning and Parsing Overview [16/22]
Scanning/Parsing: Review of Regular Expressions [17/22]
Scanning/Parsing: Regular Expression Examples [18/22]
Scanning/Parsing: JFlex and CUP [19/22]
Scanning/Parsing: Homework [20/22]
Further examples: Arithmetic [21/22]
Further examples: Abstract Syntax Trees [22/22]

Are You In The Right Room? [1/22]

Course: CSC448 (Compiler Design)

Instructor: James Riely

Overview of Today's Class [2/22]

Course overview.

Administrative information.

Introduction to parsing and the CUP LALR parser generator.

Overview: Course Overview [3/22]

We will cover:

As homeworks, we will be doing some of the labs from the text. These use java, eclipse and some other tools:

If you prefer not to use eclipse, you can install apache ant and run ant directly from the command line.

Overview: Why take this course? [4/22]

By the end of this course, you will:

Admin: Course Homepage [5/22]

Course homepage: http://www.depaul.edu/~jriely/csc448winter2011

Lecture slides may not be available before the class.

Lecture slides may change after class.

Lecture slides are a supplement to lectures only. The slides are not intended to be read in lieu of listening to lecture and may be misleading if used this way.

Admin: Contact Information [6/22]

Instructor:James Riely
Home Page:http://www.depaul.edu/~jriely
Email:jriely@cs.depaul.edu
Phone:1.312.362.5251
Address: School of Computing, DePaul University
243 South Wabash Avenue
Chicago, IL 60604-2301
Office:CDM 846
Office Hours: Tue 3:00-4:00pm, Wed 1:00-2:00pm in CDM 846
Class Page:http://www.depaul.edu/~jriely/csc448winter2011
Class Hours: Wed 5:45-9:00pm in Lewis 1007 [Section 801]
Online, Anytime [Section 810]

I check email about twice a day. I do not often check voice-mail.

Please check that the email address on your CampusConnect record is correct.

Please include your name and the course in your emails:

From: fun_dude@yahoo.com
Subject: Homework

Prof,

Where's the homework???

--
fun_dude@yahoo.com
        

Admin: Course Mailing List [7/22]

Course mailing list: mailto:csc448winter2011@googlegroups.com

Unless your message is personal, send it to the course mailing list!

To subscribe to the list or unsubscribe from it, go to the link on the course homepage.

Last minute information will go to the mailing list.

If necessary, update your spam filter to accept messages from the mailing list.

Admin: Attendance [8/22]

You are required to attend/watch all of the lectures within 24 hours of class meeting.

You are responsible for all material discussed in class.

In-class students must attend the midterm exam.

Admin: COL [9/22]

Some of the materials for this course (homework submission, lecture recordings and grades) will be available to you through the Course OnLine web (COLweb) site at https://col.cdm.depaul.edu.

Every page in COLweb has built-in help and information available in an information box at the top right part of the page -- click the "+" to see the topics.

If you have any problems using the system, click the link titled "Having Trouble? Click Here" at the bottom of any page and your questions will be promptly answered by COLweb support staff.

Admin: Assessment [10/22]

Your final grade will be based on:

Assessment for homework assignments will be based on whether they achieve the set task and quality of the code.

You are expected to complete all of the homework assignments by the deadline. Late homework submissions will not be accepted. Homework assignments must be submitted through the online system. Email submissions will not be accepted.

Admin: Plagiarism [11/22]

See the academic integrity policy in the student handbook.

Homework assignments must be solved individually. You must not look at anyone else's solutions, and you must clearly acknowledge any code that you obtain from other sources (such as books, magazines, or the Internet). If you are in any doubt, contact the instructor for advice.

Your project work and report must consist of your own work. Use of material prepared by others must be minimal (check with the instructor if in any doubt) and clearly indicated by quoting and citation.

Admin: Textbooks [12/22]

Required Books

Crafting a Compiler [Amazon, AddAll]

by Charles N. Fischer, Ron K. Cytron, and Richard J. LeBlanc
Addison-Wesley, Copyright: 2009 or 2010

Admin: Prerequisites [13/22]

Prerequisites: CSC373 and CSC383.

You should be familiar with the following topics:

Admin: Expectations [14/22]

We will use several tools. I expect you to learn these without too much guidance from me.

The course requires that you actively engage the material on your own.

Admin: Installing Eclipse [15/22]

See here: http://www.cs.wustl.edu/~cytron/cacweb/HelpDocs/Install/

and here: http://www.cs.wustl.edu/~cytron/cacweb/HelpDocs/Studios/ant.html

Scanning/Parsing: Scanning and Parsing Overview [16/22]

For the compiler writer:

Scanner and parser generators exist and are normally used.

Based on formalisms including:

Scanning/Parsing: Review of Regular Expressions [17/22]

A language is a set of strings over some alphabet.

Consider the following operations on languages over the same alphabet:

Regular expressions are a syntax for describing these operations.

Scanning/Parsing: Regular Expression Examples [18/22]

Build regular expressions for the following examples:

Scanning/Parsing: JFlex and CUP [19/22]

Scanner and parser generators: lex, yacc, bison, JavaCC, ANTLR, CUP.

file:demo.flex [source]
00001: import java_cup.runtime.SymbolFactory;
00002: import java_cup.runtime.ComplexSymbolFactory;
00003: 
00004: %%
00005: 
00006: %class DemoLexer
00007: %public
00008: %{
00009:    private SymbolFactory sf = new ComplexSymbolFactory ();
00010:    public DemoLexer (java.io.InputStream r, SymbolFactory sf)
00011:    {
00012:      this (r);
00013:      this.sf = sf;
00014:    }
00015: %}
00016: %eofval{
00017:   return sf.newSymbol ("EOF", sym.EOF);
00018: %eofval}
00019: 
00020: %unicode
00021: 
00022: %cup
00023: %cupdebug
00024: 
00025: %char
00026: %column
00027: %line
00028: 
00029: 
00030: ALPHA=[A-Za-z_]
00031: DIGIT=[0-9]
00032: NONNEWLINE_WHITE_SPACE_CHAR=[\ \t\b\012]
00033: NEWLINE=\r|\n|\r\n
00034: IDENT={ALPHA}({ALPHA}|{DIGIT}|_)*
00035: 
00036: %% 
00037: 
00038: <YYINITIAL> {
00039:   "Dragon"
00040:     { return sf.newSymbol ("Dragon", sym.DRAGON); }
00041: 
00042:   "Alice"|"Bob"
00043:     { return sf.newSymbol ("AliceOrBob", sym.ALICEORBOB); }
00044:   
00045:   {DIGIT}{DIGIT}{DIGIT}{DIGIT}{DIGIT}
00046:     { return sf.newSymbol ("FiveDigits", sym.FIVEDIGITS); }
00047: 
00048:   {DIGIT}{1,3}
00049:     { return sf.newSymbol ("ShortDigits", sym.SHORTDIGITS); }
00050: 
00051:   {DIGIT}+
00052:     { return sf.newSymbol ("Digits", sym.DIGITS); }
00053: 
00054:   "http://" ({IDENT} ".")* {IDENT}
00055:     { return sf.newSymbol ("SimpleURL", sym.SIMPLEURL); }
00056: 
00057:   {NONNEWLINE_WHITE_SPACE_CHAR}+ { }
00058: 
00059:   {IDENT}
00060:     { return sf.newSymbol ("Identifier", sym.IDENTIFIER, yytext ()); }
00061: }
00062: 
00063: {NEWLINE} { }
00064: 
00065: . { System.out.println ("Illegal character: <" + yytext () + ">"); }
00066: 

file:demo.cup [source]
00001: import java_cup.runtime.*;
00002: 
00003: import java.util.ArrayList;
00004: import java.util.List;
00005: 
00006: /* TO PRINT LIST OF TOKENS DURING READ, UNCOMMENT FOLLOWING LINE */
00007: scan with {: return ((DemoLexer) getScanner ()).debug_next_token (); :}; 
00008: 
00009: terminal DRAGON, ALICEORBOB;
00010: terminal DIGITS, FIVEDIGITS, SHORTDIGITS;
00011: terminal SIMPLEURL;
00012: 
00013: terminal String IDENTIFIER; 
00014: 
00015: non terminal start_non_terminal;
00016: non terminal one_non_terminal;
00017: 
00018: 
00019: start_non_terminal
00020:  ::= one_non_terminal start_non_terminal
00021:    |
00022:    ;
00023: 
00024: one_non_terminal
00025:  ::= DRAGON
00026:    | ALICEORBOB
00027:    | DIGITS
00028:    | FIVEDIGITS
00029:    | SHORTDIGITS
00030:    | SIMPLEURL
00031:    | IDENTIFIER
00032:    ;
00033: 

file:Main.java [source] [doc-public] [doc-private]
00001: import java.io.FileInputStream;
00002: import java.util.List;
00003: import java.util.Map;
00004: 
00005: import java_cup.runtime.*;
00006: 
00007: 
00008: public class Main
00009: {
00010:   public static void main (String[] args) 
00011:     throws Exception
00012:   {
00013:     SymbolFactory sf = new ComplexSymbolFactory ();
00014:     DemoLexer lexer;
00015:     if (args.length == 0) {
00016:       lexer = new DemoLexer (System.in, sf);
00017:     } else {
00018:       lexer = new DemoLexer (new java.io.FileInputStream (args[0]), sf);
00019:     }
00020:     DemoParser parser = new DemoParser (lexer, sf);
00021: 
00022:     Symbol symbol;
00023:     symbol = parser.parse ();
00024:   }
00025: }
00026: 
00027: 

Scanning/Parsing: Homework [20/22]

We will do lab 3 from the CAC website. See the link on the course homepage.

I have posted a video on getting started with the homework.

The video implements this FSA:

lab3_simple_fsa

It uses the following code.

package lab3;

import java.util.Enumeration;

public class Fsa {
 static final int X = -1;

 static int GOTO[][] = {
/*     B    D    S    O    C    S    T    N    S    W    O */
/*     l    e    e    r    o    t    e    o    t    i    t */
/*     a    f    m         m    r    r    n    a    t    h */
/*     n    i    i         m         m         r    h    e */
/*     k    n              a         i         t         r */
/*          e                        n                     */
/*                                   a                     */
/*                                   l                     */
/*                                                         */
{      0,   X,   X,   X,   X,   X,   1,   0,   X,   X,   X} /* 0 */,
{      1,   X,   X,   X,   X,   2,   X,   X,   X,   X,   X} /* 1 */,
{      2,   X,   X,   X,   X,   3,   X,   X,   X,   X,   X} /* 2 */,
{      3,   X,   0,   X,   4,   X,   X,   X,   X,   X,   X} /* 3 */,
{      4,   X,   X,   X,   X,   3,   X,   X,   X,   X,   X} /* 4 */,
};

 static int ACTION[][] = {
/*     B    D    S    O    C    S    T    N    S    W    O */
/*     l    e    e    r    o    t    e    o    t    i    t */
/*     a    f    m         m    r    r    n    a    t    h */
/*     n    i    i         m         m         r    h    e */
/*     k    n              a         i         t         r */
/*          e                        n                     */
/*                                   a                     */
/*                                   l                     */
/*                                                         */
{      0,   X,   X,   X,   X,   X,   0,   0,   X,   X,   X} /* 0 */,
{      0,   X,   X,   X,   X,   0,   X,   X,   X,   X,   X} /* 1 */,
{      0,   X,   X,   X,   X,   2,   X,   X,   X,   X,   X} /* 2 */,
{      0,   X,   0,   X,   0,   X,   X,   X,   X,   X,   X} /* 3 */,
{      0,   X,   X,   X,   X,   2,   X,   X,   X,   X,   X} /* 4 */,
};

   public Fsa(Enumeration e) {
      // Uncomment the line below and each token processed will be echoed.
      //((TokenEnum)e).setDebug(true);

      SymbolTable symboltable = new SymbolTable();

      int state = 0;

      String 
         lhs     = "", 
         term    = "", 
         nonterm = "$FINAL$";

      while (e.hasMoreElements()) {
         Token t = (Token)e.nextElement();

         System.out.println("   Read token type " + t.type() + ": " + t);

         int action = ACTION[state][t.type()];
         int newstate = GOTO[state][t.type()];

         //System.out.println("State " + state + " Performing action " + action + " and going to " + newstate);

         switch (action) {
         case  X: /* error */
             System.out.println(" ABORT ");    
             System.exit(0);
         case  0: /* do nothing */
             break;    
         case  2: /* terminal */
       	     symboltable.enterTerminal(t.strValue());
       	     System.out.println("Found terminal " + t.strValue());
             break;
         }

         state = newstate;
      }
      if (state != 0) oops("End in bad state: " + state);
   }

   void oops(String s) {
      System.err.println("Error: " + s);
      System.out.println("ABORT");
      System.exit(-1);
   }
}

Further examples: Arithmetic [21/22]

EBNF/BNF for arithmetic expressions.

Precedence and associativity.

Ignore semantic actions (code in braces) for now.

file:arithmetic.flex [source]
00001: import java_cup.runtime.SymbolFactory;
00002: 
00003: %%
00004: 
00005: %class ArithmeticLexer
00006: %public
00007: %{
00008:    private SymbolFactory sf;
00009:    public ArithmeticLexer (java.io.InputStream r, SymbolFactory sf)
00010:    {
00011:      this (r);
00012:      this.sf = sf;
00013:    }
00014: %}
00015: %eofval{
00016:   return sf.newSymbol ("EOF", sym.EOF);
00017: %eofval}
00018: 
00019: %unicode
00020: 
00021: %cup
00022: %cupdebug
00023: 
00024: %char
00025: %column
00026: %line
00027: 
00028: 
00029: ALPHA=[A-Za-z_]
00030: DIGIT=[0-9]
00031: NONNEWLINE_WHITE_SPACE_CHAR=[\ \t\b\012]
00032: NEWLINE=\r|\n|\r\n
00033: IDENT={ALPHA}({ALPHA}|{DIGIT}|_)*
00034: 
00035: %% 
00036: 
00037: <YYINITIAL> {
00038:   "(" { return sf.newSymbol ("LeftParen", sym.LPAREN); }
00039:   ")" { return sf.newSymbol ("RightParen", sym.RPAREN); }
00040:   ";" { return sf.newSymbol ("Semicolon", sym.SEMI); }
00041:   "=" { return sf.newSymbol ("Equals", sym.EQUALS); }
00042:   "+" { return sf.newSymbol ("Plus", sym.PLUS); }
00043:   "-" { return sf.newSymbol ("Minus", sym.MINUS); }
00044:   "*" { return sf.newSymbol ("Times", sym.TIMES); }
00045:   "/" { return sf.newSymbol ("Divide", sym.DIVIDE); }
00046: 
00047:   {NONNEWLINE_WHITE_SPACE_CHAR}+ { }
00048: 
00049:   {IDENT}
00050:     { return sf.newSymbol ("Identifier", sym.IDENTIFIER, yytext ()); }
00051: 
00052:   {DIGIT}+
00053:     {
00054:       int i = Integer.parseInt (yytext ());
00055:       return sf.newSymbol ("IntegerConstant", sym.INTEGER_CONSTANT, new Integer (i));
00056:     }
00057: }
00058: 
00059: {NEWLINE} { }
00060: 
00061: . {
00062:   System.out.println ("Illegal character: <" + yytext () + ">");
00063: }
00064: 
00065: 

file:arithmetic.cup [source]
00001: import java_cup.runtime.*;
00002: 
00003: import java.util.ArrayList;
00004: import java.util.List;
00005: 
00006: 
00007: terminal           LPAREN, RPAREN;
00008: terminal           SEMI, EQUALS;
00009: terminal           PLUS, MINUS, TIMES, DIVIDE;
00010: 
00011: terminal String    IDENTIFIER; 
00012: terminal Integer   INTEGER_CONSTANT;
00013: 
00014: non terminal List<Decl>     decl_list;
00015: non terminal Decl           decl;
00016: non terminal Exp            expression;
00017: 
00018: precedence left PLUS, MINUS;
00019: precedence left TIMES, DIVIDE; 
00020: 
00021: 
00022: decl_list ::= decl_list:l decl:d
00023:               {: l.add (d); RESULT = l; :}
00024:               |
00025:               {: RESULT = new ArrayList<Decl> (); :}
00026:               ;
00027: 
00028: decl ::= IDENTIFIER:id EQUALS expression:e SEMI
00029:          {: RESULT = new Decl (id, e); :}
00030:          ;
00031: 
00032: expression ::= INTEGER_CONSTANT:i
00033:                {: RESULT = new ExpInt (i.intValue ()); :}
00034:                | IDENTIFIER:id 
00035:                {: RESULT = new ExpVar (id); :}
00036:                | expression:e1 PLUS expression:e2
00037:                {: RESULT = new ExpBinOp (ExpBinOp.BinOp.PLUS, e1, e2); :}
00038:                | expression:e1 MINUS expression:e2
00039:                {: RESULT = new ExpBinOp (ExpBinOp.BinOp.MINUS, e1, e2); :}
00040:                | expression:e1 TIMES expression:e2
00041:                {: RESULT = new ExpBinOp (ExpBinOp.BinOp.TIMES, e1, e2); :}
00042:                | expression:e1 DIVIDE expression:e2
00043:                {: RESULT = new ExpBinOp (ExpBinOp.BinOp.DIVIDE, e1, e2); :}
00044:                | LPAREN expression:e RPAREN
00045:                {: RESULT = e; :}
00046:                ;
00047: 
00048: 

Further examples: Abstract Syntax Trees [22/22]

Abstract syntax trees (ASTs) are distinct from parse trees.

Pretty printer for Arithmetic.

Building the AST during parsing with CUP.

file:arithmetic.flex [source]
00001: import java_cup.runtime.SymbolFactory;
00002: 
00003: %%
00004: 
00005: %class ArithmeticLexer
00006: %public
00007: %{
00008:    private SymbolFactory sf;
00009:    public ArithmeticLexer (java.io.InputStream r, SymbolFactory sf)
00010:    {
00011:      this (r);
00012:      this.sf = sf;
00013:    }
00014: %}
00015: %eofval{
00016:   return sf.newSymbol ("EOF", sym.EOF);
00017: %eofval}
00018: 
00019: %unicode
00020: 
00021: %cup
00022: %cupdebug
00023: 
00024: %char
00025: %column
00026: %line
00027: 
00028: 
00029: ALPHA=[A-Za-z_]
00030: DIGIT=[0-9]
00031: NONNEWLINE_WHITE_SPACE_CHAR=[\ \t\b\012]
00032: NEWLINE=\r|\n|\r\n
00033: IDENT={ALPHA}({ALPHA}|{DIGIT}|_)*
00034: 
00035: %% 
00036: 
00037: <YYINITIAL> {
00038:   "(" { return sf.newSymbol ("LeftParen", sym.LPAREN); }
00039:   ")" { return sf.newSymbol ("RightParen", sym.RPAREN); }
00040:   ";" { return sf.newSymbol ("Semicolon", sym.SEMI); }
00041:   "=" { return sf.newSymbol ("Equals", sym.EQUALS); }
00042:   "+" { return sf.newSymbol ("Plus", sym.PLUS); }
00043:   "-" { return sf.newSymbol ("Minus", sym.MINUS); }
00044:   "*" { return sf.newSymbol ("Times", sym.TIMES); }
00045:   "/" { return sf.newSymbol ("Divide", sym.DIVIDE); }
00046: 
00047:   {NONNEWLINE_WHITE_SPACE_CHAR}+ { }
00048: 
00049:   {IDENT}
00050:     { return sf.newSymbol ("Identifier", sym.IDENTIFIER, yytext ()); }
00051: 
00052:   {DIGIT}+
00053:     {
00054:       int i = Integer.parseInt (yytext ());
00055:       return sf.newSymbol ("IntegerConstant", sym.INTEGER_CONSTANT, new Integer (i));
00056:     }
00057: }
00058: 
00059: {NEWLINE} { }
00060: 
00061: . {
00062:   System.out.println ("Illegal character: <" + yytext () + ">");
00063: }
00064: 
00065: 

file:arithmetic.cup [source]
00001: import java_cup.runtime.*;
00002: 
00003: import java.util.ArrayList;
00004: import java.util.List;
00005: 
00006: 
00007: terminal           LPAREN, RPAREN;
00008: terminal           SEMI, EQUALS;
00009: terminal           PLUS, MINUS, TIMES, DIVIDE;
00010: 
00011: terminal String    IDENTIFIER; 
00012: terminal Integer   INTEGER_CONSTANT;
00013: 
00014: non terminal List<Decl>     decl_list;
00015: non terminal Decl           decl;
00016: non terminal Exp            expression;
00017: 
00018: precedence left PLUS, MINUS;
00019: precedence left TIMES, DIVIDE; 
00020: 
00021: 
00022: decl_list ::= decl_list:l decl:d
00023:               {: l.add (d); RESULT = l; :}
00024:               |
00025:               {: RESULT = new ArrayList<Decl> (); :}
00026:               ;
00027: 
00028: decl ::= IDENTIFIER:id EQUALS expression:e SEMI
00029:          {: RESULT = new Decl (id, e); :}
00030:          ;
00031: 
00032: expression ::= INTEGER_CONSTANT:i
00033:                {: RESULT = new ExpInt (i.intValue ()); :}
00034:                | IDENTIFIER:id 
00035:                {: RESULT = new ExpVar (id); :}
00036:                | expression:e1 PLUS expression:e2
00037:                {: RESULT = new ExpBinOp (ExpBinOp.BinOp.PLUS, e1, e2); :}
00038:                | expression:e1 MINUS expression:e2
00039:                {: RESULT = new ExpBinOp (ExpBinOp.BinOp.MINUS, e1, e2); :}
00040:                | expression:e1 TIMES expression:e2
00041:                {: RESULT = new ExpBinOp (ExpBinOp.BinOp.TIMES, e1, e2); :}
00042:                | expression:e1 DIVIDE expression:e2
00043:                {: RESULT = new ExpBinOp (ExpBinOp.BinOp.DIVIDE, e1, e2); :}
00044:                | LPAREN expression:e RPAREN
00045:                {: RESULT = e; :}
00046:                ;
00047: 
00048: 

file:Main.java [source] [doc-public] [doc-private]
00001: import java.io.FileInputStream;
00002: import java.util.List;
00003: import java.util.Map;
00004: 
00005: import java_cup.runtime.*;
00006: 
00007: 
00008: public class Main
00009: {
00010:   public static void main (String[] args) 
00011:     throws Exception
00012:   {
00013:     SymbolFactory sf = new ComplexSymbolFactory ();
00014:     ArithmeticLexer lexer;
00015:     if (args.length == 0) {
00016:       lexer = new ArithmeticLexer (System.in, sf);
00017:     } else {
00018:       lexer = new ArithmeticLexer (new java.io.FileInputStream (args[0]), sf);
00019:     }
00020:     ArithmeticParser parser = new ArithmeticParser (lexer, sf);
00021: 
00022:     Symbol symbol = parser.parse ();
00023: 
00024:     List<Decl> decls = (List<Decl>) symbol.value;
00025:     for (Decl decl : decls) {
00026:       System.out.println (decl);
00027:     }
00028: 
00029:     System.out.println ();
00030: 
00031:     Interpreter interpreter = new Interpreter ();
00032:     Map<String, Integer> bindings = interpreter.evaluateDecls (decls);
00033:     for (String var : bindings.keySet ()) {
00034:       System.out.println (var + " = " + bindings.get (var));
00035:     }
00036:   }
00037: }
00038: 
00039: 

file:Decl.java [source] [doc-public] [doc-private]
00001: public class Decl
00002: {
00003:   public final String var;
00004:   public final Exp exp;
00005: 
00006: 
00007:   public Decl (String var, Exp exp)
00008:   {
00009:     this.var = var;
00010:     this.exp = exp;
00011:   }
00012: 
00013: 
00014:   public String toString ()
00015:   {
00016:     return var + " = " + exp + ";";
00017:   }
00018: }
00019: 

file:Exp.java [source] [doc-public] [doc-private]
00001: public abstract class Exp
00002: {
00003: }
00004: 

file:ExpBinOp.java [source] [doc-public] [doc-private]
00001: public class ExpBinOp extends Exp
00002: {
00003:   public enum BinOp { 
00004:     PLUS ("+"),
00005:     MINUS ("-"),
00006:     TIMES ("*"),
00007:     DIVIDE ("/"),
00008:     ;
00009: 
00010:     final String string;
00011: 
00012:     BinOp (String string) 
00013:     {
00014:       this.string = string;
00015:     }
00016: 
00017:     public String toString ()
00018:     {
00019:       return string;
00020:     }
00021:   };
00022: 
00023: 
00024:   public final BinOp op;
00025:   public final Exp left;
00026:   public final Exp right;
00027: 
00028: 
00029:   ExpBinOp (BinOp op, Exp left, Exp right)
00030:   {
00031:     this.op = op;
00032:     this.left = left;
00033:     this.right = right;
00034:   }
00035: 
00036: 
00037:   public String toString ()
00038:   {
00039:     return "(" + left + " " + op + " " + right + ")";
00040:   }
00041: }
00042: 

file:ExpInt.java [source] [doc-public] [doc-private]
00001: public class ExpInt extends Exp
00002: {
00003:   public final int value;
00004: 
00005: 
00006:   public ExpInt (int value)
00007:   {
00008:     this.value = value;
00009:   }
00010: 
00011: 
00012:   public String toString ()
00013:   {
00014:     return Integer.toString (value);
00015:   }
00016: }
00017: 

file:ExpVar.java [source] [doc-public] [doc-private]
00001: public class ExpVar extends Exp
00002: {
00003:   public final String var;
00004: 
00005: 
00006:   public ExpVar (String var)
00007:   {
00008:     this.var = var;
00009:   }
00010: 
00011: 
00012:   public String toString ()
00013:   {
00014:     return var;
00015:   }
00016: }
00017: 

file:Interpreter.java [source] [doc-public] [doc-private]
00001: import java.util.List;
00002: import java.util.HashMap;
00003: import java.util.Map;
00004: 
00005: 
00006: public class Interpreter
00007: {
00008:   public Map<String, Integer> evaluateDecls (List<Decl> decls)
00009:   {
00010:     Map<String, Integer> bindings = new HashMap<String, Integer> ();
00011:     
00012:     for (Decl decl : decls) {
00013:       int value = evaluateExp (bindings, decl.exp);
00014:       bindings.put (decl.var, new Integer (value));
00015:     }
00016:     
00017:     return bindings;
00018:   }
00019: 
00020: 
00021:   int evaluateExp (Map<String, Integer> bindings, Exp exp) 
00022:   {
00023:     if (exp instanceof ExpInt) {
00024:       ExpInt expI = (ExpInt) exp;
00025:       return expI.value;
00026: 
00027:     } else if (exp instanceof ExpVar) {
00028:       ExpVar expV = (ExpVar) exp;
00029:       Integer value = bindings.get (expV.var);
00030:       if (value == null) {
00031:         throw new RuntimeException ("Variable " + expV.var + " not defined");
00032:       } else {
00033:         return value.intValue ();
00034:       }
00035: 
00036:     } else if (exp instanceof ExpBinOp) {
00037:       ExpBinOp expB = (ExpBinOp) exp;
00038:       int left = evaluateExp (bindings, expB.left);
00039:       int right = evaluateExp (bindings, expB.right);
00040:       if (expB.op.equals (ExpBinOp.BinOp.PLUS)) {
00041:         return left+right;
00042:       } else if (expB.op.equals (ExpBinOp.BinOp.MINUS)) {
00043:         return left-right;
00044:       } else if (expB.op.equals (ExpBinOp.BinOp.TIMES)) {
00045:         return left*right;
00046:       } else if (expB.op.equals (ExpBinOp.BinOp.DIVIDE)) {
00047:         return left/right;
00048:       } else {
00049:         throw new RuntimeException ("Missing case for BinOp " + expB.op);
00050:       }
00051: 
00052:     } else {
00053:       throw new RuntimeException ("Missing case for Exp " + exp);
00054:     }
00055:   }
00056: }
00057: 

Revised: 2008/09/03 15:33