CSC448: Lecture 1 (Introduction, Scanners)

Course: CSC448 (Compiler Design)

Instructor: James Riely

Course overview.

Administrative information.

Introduction to parsing and the CUP LALR parser generator.

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.

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
        

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.

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.

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

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

For the compiler writer:

• Scanning: from a stream of characters to a stream of tokens.
• Parsing: from a stream of tokens to an abstract syntax tree.

Scanner and parser generators exist and are normally used.

Based on formalisms including:

• regular expressions
• finite-state automata
• context-free grammars and BNF / EBNF
• pushdown-stack automata

A language is a set of strings over some alphabet.

Consider the following operations on languages over the same alphabet:

• The empty string: lambda
• A symbol from the alphabet: a
• Union: r | s
• Concatenation: r s
• Iteration: r*

Regular expressions are a syntax for describing these operations.

Build regular expressions for the following examples:

• The string "Dragon".
• The strings "Alice" or "Bob".
• Any non-empty string of digits.
• Any string of digits of length exactly 5 characters.
• Any non-empty string of digits of length less than or equal to 3 characters.
• Simple URLs of the form "http://fpl.cs.depaul.edu".
• The tokens of your favourite programming language (as long as it is Java).

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:

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:

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);
   }
}

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:

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