CIS 461/561 (Introduction to Compilers)

General Information

Homeworks and Grades

Getting Help

• Monday: 2-4
• Wednesday: 11-12

Course Organization

I will provide working versions of early homeworks in case you need them to test the later ones. It is important that you keep going even if you miss an early homework. The due dates for the assignments are firm: there will be no extensions. Your grade will be calculated as follows:

1. in-class midterm exam: 30%
2. quizzes: 20%
3. programming assignments and final project: 50%

References

A. Appel, Modern Compiler Implementation in Java. (Errata.)

Some book about Java. Pick your favorite.

The Java Core API

The JLex documentation

The CUP documentation

Notes on the SPARC assembly language

Sample Tiger Programs

The "dragon book" is the classical reference about lexical analysis and parsing: Compilers---Principles, Techniques, and Tools, A. Aho and R. Sethi and J. Ullman, Addison-Wesley, Reading, Mass., 1985.

What is this Course About?

A industrial strength compiler is a major effort (in the order of 100K lines of code and 5 man/years). Few of you will write such compilers. Most of you, however, will write compilers that process "little languages." For example, you may be writing scripts that read an input from an HTML form, parse it, check it for consistency, and generate HTML code as output.

This course will present the general principles, algorithms, and techniques that are helpful for (big and small) compilers. In addition, the course should provide you with:

1. a concrete understanding of programming language concepts that complements the more mathematical understanding you get from a course in semantics; this should ultimately make you a better programmer,
2. understanding the cost of programming language constructs; understanding what can be implemented reasonably and what can be expected to be optimized by a typical compiler, etc,
3. writing a large program using an advanced programming language; managing the complexity of having multiple programmers; use modules and interfaces effectively,
4. a great case study for applying the software engineering concepts you were introduced to in other classes. This may be as close as you will get to "real" programming in a course.

let var x : int := 2     /* silly comment */
    var y : int := 7
in x+y  
end

[ Let,
  Var,
  Id "x", 
  Colon,
  Id "int",
  Assign,
  Intliteral 2,
  Var,
  Id "y",
  Colon,
  Id "int",
  Assign,
  Intliteral 7,
  In,
  Id "x",
  Plus,
  Id "y",
  End
] 

LetExp { decs = [ VarDec { init = IntExp 2,
                           typ = SOME (-,15),
                           var = { escape = ref true,
                                   name = -
                                 }
                           pos = 7,
                         },
                  VarDec { init = IntExp 7,
                           pos = 28,
                           typ = SOME (-,36),
                           var = { escape = ref true,
                                   name = -
                                 }
                         }
                ],
         body = SeqExp [ (OpExp { left = VarExp (SimpleVar (-,48)),
                                  oper = PlusOp,
                                  pos = 48,
                                  right = VarExp (SimpleVar (-,50))
                                 },
                          48)
                       ],

         pos=3
       }

MOVE(TEMP T101,
     ESEQ(SEQ(MOVE(MEM[4](BINOP(PLUS,TEMP T100,CONST -4)),
                   CONST 2),
              MOVE(MEM[4]( BINOP(PLUS,TEMP T100,CONST -8)),
                   CONST 7)),
              BINOP(PLUS,
                    MEM[4](BINOP(PLUS,TEMP T100,CONST -4)),
                    MEM[4](BINOP(PLUS,TEMP T100,CONST -8)))))

LABEL L19
MOVE(MEM[4](BINOP(PLUS,TEMP T100,CONST -4)),
     CONST 2)
MOVE(MEM[4](BINOP(PLUS,TEMP T100,CONST -8)),
     CONST 7)
MOVE(TEMP T101, 
     BINOP(PLUS,
           MEM[4](BINOP(PLUS,TEMP T100,CONST -4)),
	   MEM[4](BINOP(PLUS,TEMP T100,CONST -8))))
JUMP(NAME L18)
LABEL L18

.global toymain
.section ".text"
toymain:
save %sp, -136,%sp
L19:
mov 2 , %g2
st %g2, [%fp-16]
ld [%fp-16] , %g3
st %g3, [%fp+-4]
mov 7 , %g2
st %g2, [%fp-24]
ld [%fp-24] , %g3
st %g3, [%fp+-8]
ld [%fp+-4], %g2
st %g2, [%fp-32]
ld [%fp+-8], %g2
st %g2, [%fp-36]
ld [%fp-32], %g2
ld [%fp-36], %g3
add %g2, %g3, %g2
st %g2, [%fp-28]
ld [%fp-28], %i0
ba L18
nop
L18:
jmp %i7+8
restore

Lecture Topics