Compiler Design

Compiler Design



Course Information

Instructor:Rich Maclin


Text:Aho, Lam, Sethi, and Ullman, Compilers: Principles, Techniques, and Tools, 2nd Ed., Addison-Wesley, ISBN 0-321-48681-1


Click here to download the files:-

Useful software:

Class Materials (previous offerings)

Project Parts:

  1. Project Part 1: A String Table
  2. Project Part 2: Two Scanners
  3. Project Part 3: The Parser
  4. Project Part 4: Symbol Table, Type Checking and Interpreter

Homework Assignments:

  1. Homework 1
  2. Homework 2
  3. Homework 3
  4. Homework 4
  5. Homework 5

Sample Exam Questions:

Compiler Design Notes

Compiler Design Notes

Topics Covered
1 Introduction to Compiling
2 Lexical Analysis
3 Lexical Analysis
4 Syntax Analysis -- Context Free Grammars
5 Syntax Analysis -- Top-Down Parsing
6 Syntax Analysis -- LL Parsing
7 Syntax Analysis -- Bottom-Up Parsing
8 Syntax Analysis -- LR Parsing
Midterm
9 Syntax-Directed Translation -- Attribute Definitions
10 Syntax-Directed Translation -- Evaluation of Attribute Definitions
11 Semantic Analysis, Type Checking
12 Run-Time Organization
13 Intermediate Code Generation
14 Intermediate Code Generation
Final

Lecture Notes:

lec00-outline.PPT
lec01-lexicalanalyzer.PPT
lec02-parserCFG.PPT
lec03-topdownparser.PPT
lec04-bottomupparser.PPT
lec05-syntaxdirected.PPT
lec06-typechecking.PPT
lec07-intermediatecg.PPT
lec08-memoryorg.PPT

Compiler Design and Construction PDF

Compiler Design and Construction PDF

Compiler Design and Construction I

Instructor : T. K. Prasad 

Text Book Required :Compiler Construction: Principles and Practice, Kenneth C. Louden, PWS Publishing Company, 1997. 

Download Lectures here

Topic Readings
Introduction to Compilers Chapter 1
Introduction to COOL CoolAid
Lexical Analysis Chapter 2
Implementing Lexer
FLEX Chapters 1-2, 6   lex & yacc
Context-free Grammars Chapter 3
Ambiguity; Abstract Syntax Trees Attribute Grammars

Top-down Parsing Chapter 4
(continue)
Bottom-up Parsing Chapter 5
 Bottom-up Parsing : Basics (ppt)
Bottom-up Parsing : Algorithms
(continue)
LR Parsing
(continue) (ppt)
Overview of Semantic Analysis Chapter 6
Type Checking and Inference
(WRAP-UP)

Compiler Design 5

Compiler Design

Compiler Design

Spring 1998

Meets 12-1:20 pm in Sage 2707


CS 66-648 Compiler Design:

Syllabus Spring 1998


Instructor: M. S. Krishnamoorthy (moorthy)

Prerequisites:

CS 66-431 Systems Programming You must be familiar with a high level block-structured language. If you are not proficient in C or C++ then you must be prepared to learn it quickly. You should understand general programming concepts (recursion, parameter passing). You should have experience using data structures such as pointers, linked lists, trees, hash tables, and stacks.Text:
  1. Compilers: Principles, Techniques and Tools, Aho, Sethi, and Ullman, Addison-Wesley, 1986.
Extra references:
  1. A Retargetable C Compiler: Design and Implementation Fraser and Hansen, Benjamin-Cummings, 1995.
  2. Advanced Compiler Design and Implementation, Muchnick, Morgan and Kaufmann, 1998.
  3. Crafting a Compiler, Fischer and LeBlanc, Benjamin-Cummings, 1988.
  4. Introduction to Compiler Construction with UNIX, Schreiner and Friedman, Prentice-Hall, 1985. (on reserve)
  5. Compiler Design in C, Holub, Prentice-Hall, 1990.
  6. Recent Research Papers.
Grading:
Projects (3) 75%Test(1) 25%
If you cannot do the projects, because of accessability to a computer with utilities, such as lex, yacc, then there will be around 5 homeworks. 90-100 is an A, 80-89 is a B, 70-79 is a C, 60-69 is a D, <>
Topics:
  1. The Structure of a Compiler ( 1 lecture)
  2. Lexical Analyzer, LEX, Design of Lex ( 3 lectures)
  3. Top down Parsing, LL(1) Parsers ( 3 lectures)
  4. Bootom up Parsing, YACC, LR parsers ( 3 lectures)
  5. Syntax Directed Translation ( 2 lectures)
  6. Types and Type Checking ( 2 lectures)
  7. Run-Time Storage Administration and Symbol Table Management ( 2 lectures)
  8. Intermediate Code and Code Generation ( 4 lectures)
  9. Data-Flow Analysis ( 3 lectures)
  10. Code Optimizations ( 2 lectures)
  11. Architcure and recent development on compilers ( 2 lectures)
Compiler Project:You will do the projects on either the unix worlstations or on PC's it is your responsibility to ensure that your program works correctly on it. All programming is done in C or C++. A number of tools will be used, i.e. Lex, Yacc, Make.
Late Assignments:
Unless you make prior arrangements with the instructor or have a medical excuse:
  1. Programming projects are submitted electronically and are due at midnight (23:59:59) on the due date. If you have your Makefile set up correctly, this will simply consist of the command make submit.
  2. Programs may be submitted late for a penalty of 10% per day for up to 4 school days.
Dishonesty Policy:On written homework assignments, you may discuss problems with other students, but the writeup must be your own. Merely copying answers is not permitted.
On programming projects, you may discuss problems and help one another find program bugs. You are not to write code together. All programming code must be your own.
The penalty for cheating on homework, programming projects, quizzes, and exams will be failure for the class.
Save all graded homework until the end of the semester just in case something is lost or recorded incorrectly.

Projects 3 and 4 are out. project34
Project 2 is out. project2
Test tables Example1 and Example2 latex tables.
Project 1 is out. project1
Java Programming Language Reference Manual
Example Directory Some programs contain some lex programs for testing leap years and converting latex enumerated lists.
Contains another Java compiler (for a subset of Java) - Written in C++ by Gor and Jonathan .
Java compiler for a subset of java is here. This was written in 1996 by Hongshi Guo as a part of a class project.
powerpoint viewer from microsoft to enable viewing slides across versions.

Lectures

lecture1.ppt 13-Jan-1998 09:52 43K 

[   ] lecture2.ppt            13-Jan-1998 09:52   47K  
 [   ] lecture3.ppt            21-Jan-1998 09:10   48K  
 [   ] lecture4.ppt            26-Jan-1998 08:09   51K  
 [   ] lecture5.ppt            26-Jan-1998 08:09   67K  
 [   ] lecture5supp.ppt        26-Jan-1998 08:09   50K  
 [   ] lecture6.ppt            02-Feb-1998 09:00   67K  
 [   ] lecture7.ppt            02-Feb-1998 09:01   71K  
 [   ] lecture8.ppt            09-Feb-1998 08:57   57K  
 [   ] lecture9.ppt            18-Feb-1998 09:30   60K   
[   ] lecture11.ppt           25-Feb-1998 09:25   48K  
 [   ] lecture12.ppt           25-Feb-1998 09:26   61K  
 [   ] lecture13.ppt           23-Mar-1998 08:45   61K  
 [   ] lecture14.ppt           23-Mar-1998 08:45   62K  
 [   ] lecture15.ppt           23-Mar-1998 08:45   62K  
 [   ] lecture16.ppt           23-Mar-1998 08:45   59K  
 [   ] lecture17.ppt           30-Mar-1998 10:19   69K

Lectures In PS  

[   ] lec1.ps                 13-Jan-1998 09:52  127K 
[   ] lec2.ps                 13-Jan-1998 09:52  174K 
[   ] lec3.ps                 21-Jan-1998 09:10  154K 
[   ] lec4.ps                 26-Jan-1998 08:08  147K  

[   ] lec5.ps                 26-Jan-1998 08:08  161K 
[   ] lec5supp.ps             26-Jan-1998 08:08   92K 
[   ] lec6.ps                 02-Feb-1998 09:01  174K 
[   ] lec7.ps                 02-Feb-1998 09:00  195K 
[   ] lec8.ps                 09-Feb-1998 08:54  170K 
[   ] lec9.prn                18-Feb-1998 09:30  133K 
[   ] lec11.ps                25-Feb-1998 09:25  123K 
[   ] lec12.ps                25-Feb-1998 09:25  160K 
[   ] lec13.ps                23-Mar-1998 08:46  176K 
[   ] lec14.ps                23-Mar-1998 08:47  182K 
[   ] lec15.ps                23-Mar-1998 08:47  216K 
[   ] lec16.ps                23-Mar-1998 08:47  136K 
[   ] lec17.ps                30-Mar-1998 10:19  171K 
[   ] lec19.ps                10-Apr-1998 12:00  153K 
[   ] lec20.ps                10-Apr-1998 12:01  168K

Compiler Design 4

Compiler Design PPT

Compiler Design

Text Book :-
1. Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman, "Compilers: Principles, Techniques, and Tools", 2nd Edition, Addison-Wesley, 2007.

Course Outline:
WeekNo Topics Covered
1 Introduction to Compiling
2 Lexical Analysis
3 Lexical Analysis
4 Syntax Analysis -- Context Free Grammars
5 Syntax Analysis -- Top-Down Parsing
6 Syntax Analysis -- LL Parsing
7 Syntax Analysis -- Bottom-Up Parsing
8 Syntax Analysis -- LR Parsing
Midterm
9 Syntax-Directed Translation -- Attribute Definitions
10 Syntax-Directed Translation -- Evaluation of Attribute Definitions
11 Semantic Analysis, Type Checking
12 Run-Time Organization
13 Intermediate Code Generation
14 Intermediate Code Generation
Click here to download the files:-
Lecture Notes:

Compiler Design 3

Compiler Design PPT

COMPILER DESIGN LECTURES SLIDES

 Slides:
Download Notes:-
 
Lectures
 
[ ]01. Introduction.ppt02-Oct-2007 09:09181K
[ ]02. Chapter 3 - Lexical Analysis.ppt02-Oct-2007 09:091.0M
[ ]Chapter 4 - Syntax Analysis.ppt04-Nov-2007 09:301.9M
[ ]Chapter 5 - Syntax Directed Translation.ppt29-Nov-2007 18:22537K
[ ]Chapter 6 - Intermediate code generation.ppt05-Jan-2008 11:271.7M
[ ]Chapter 7 - RUN_TIME ENVIRONMENT.ppt05-Jan-2008 11:271.7M
[ ]Chapter 8 - Code Generation.ppt

Compiler Design 2

Advanced Compiler Design PDF

Advanced Compiler Design



Objectives
Compilers and interpreters are very widely used. Every programmer uses these tools to execute programs written in high level languages. It is hence essential for a computer scientist to understand the process by which programs written in high-level languages are translated and executed. The main objective of this course is to gain an in depth understanding of the above process. Most complex software systems are not monolithic; they are programmable using special purpose languages. An understanding of the language translation process thus plays an important role in the design of real life systems.

Overview

In the class, we will discuss the theoretical aspects of designing a compiler. In the projects, you will then apply the theory you have learned in the class to develop a complete compiler for a high level language. The problem of language translation is traditionally decomposed into many phases. Most common are:
  • Lexical analysis (analogous to recognizing words in a sentence),
  • Parsing (analogous to grouping words into phrases, sentences, paragraphs etc.)
  • Semantic Analysis (e.g., type checking), and
  • Code generation
All phases use a symbol table to keep track of the properties (types, number of parameters etc.) of each symbol (variables, procedures etc.). In the end, code is generated for an abstract machine which may be interpreted (as in Java), or may be translated further into machine instructions (as in C). We will cover each of these topics in detail.
The compiler will be written in Java. Advanced topics such as program optimization, machine code generation and storage management will be discussed in the lectures.

Reading

The course will use the following textbooks:
  • Compilers: Principles, Techniques, and Tools, by Aho, Sethi, and Ullman, Addison-Wesley, 1988, 796pp. ISBN 0-201-10088-6.
Slides will be posted as links in the tentative schedule below. Following books are recommended for additional reading:
  • Modern Compiler Implementation in Java, by Andrew Appel.
  • The Java Programming Language Second Edition by Ken Arnold and James Gosling.
Click here to download the files:-

Date
Topic
Chapter
Projects
1.
Jan 27
Organization. Overview of Compilation. l1
1, 2

2.
Jan 29
Lexical Analysis: Regular Expression & Definitions l3, l4
3.1-3.3

3.
Feb 03
Lexical Analysis: RE<->NFA<->DFA l4, l5, Javacc 1 2 3 4 5 6 7 8 9 10
3.4-3.6

4.
Feb 05
Grammars, Recursive Descent Parsing. l6, l7
4.4
P1 Out
5.
Feb 10
LL Parsing. l8, l9
4.4

6.
Feb 12
Bottom-up Parsing, l10
4.5

7.
Feb 17
LR Parsers, l11
4.7
P1 due, P2 out
8.
Feb 19
Item set construction, 1 2 3 4 SLR, LR, LALR, l12
4.7

9.
Feb 24
Attributes, l16, l17
4.9

10.
Feb 26
Syntax-Directed Translation, l15, att
5.1

11.
Mar 02
Symbol Tables, l13, st
7.6

12.
Mar 04
Name Resolution, l14, l15

P2 due,P3 out
13.
Mar 09
Abstract Syntax Trees l18, ast
5.2

14.
Mar 11
Review for Mid-Term Exam


15.
Mar 16
Mid-Term Exam. Previous: 00e, 00a; 98e, 98a; 97e, 97a, 02


16.
Mar 18
Types: type checking expressions and operations l19
6.1, 6.2

17.
Mar 23
Types & Equivalences l20 TypeChecking.ppt
6.3, 6.4
P3 due, P4 out
18.
Mar 25
Types in OO-languages: method resolution l21
6.5

19.
Mar 30
Intermediate code generation: languages, expressions l22, l24
8.1-8.4

20.
Apr 01
Runtime storage organization l23, pCall
7.2, 7.3











21.
Apr 13
Intermediate code generation: statements. Optimizations l25, l26
8.4-8.7, 9.4
P4 due, P5 out
22.
Apr 15
Control-Flow Analysis CFA): blocks, flow-graphs, loops l27.5-9.ppt,
9.4,10.1,10.4

23.
Apr 22
CFA: l28.15-24.ppt


24.
Apr 27
Data-Flow Analysis (DFA): l29.25-34.ppt


25.
Apr 29
DFA: dags, bbOpt. Global DFA:paths, reaching defs, struct Progs, l p35-47.ppt


26.
May 04
DFA: iterative solution, structure-based solution, l31


Compiler Design

AUTOMATA THEORY

Lecture notes will be available in either postscript or pdf format.
  • For files that are in postscript format, you need a postscript previewer. You should be able to view them on the SparcStations. If you want to print them, while viewing them, select "save" and save as a file with a ".ps" extension, for example: lect1.psYou can then send the file to the printer by typing: lpr lect1.ps
  • To read PDF files you can download the free Adobe Acrobat Reader.
Lecture Notes

Compilers Design PDF

Programming Languages
and Compilers

Download :


Class
Topic
Lecture slides (pdf)
1
Introduction to course; intro to OCaml
lecture 1 (ann) ,lecture1.ml
2
Ocaml - tuples and lists
lecture 2(lecture 2 (ann)) (Supplementary notes for lecture 2)
3
OCaml - type definitions, abstract syntax
lecture 3(lecture 3 (ann))
4
Language implementation overview
lecture 4 (v. 2)(supplementary notes)
5
Lexical analysis
lecture 5(lecture 5 with annotations from today and 2/6)
6
Regular expressions, Ocamllex
lecture 6(lecture 6 annotated)
7
Parsing - context-free grammars, recursive descent parsing
lecture 7(lecture 7 ann) (Code from lecture: 1, 2, 3,1b, 2b, 3b, 3c)
8
Top-down parsing
lecture 8 (ann)(lecture 8 addendum)
9
Bottom-up (shift/reduce) parsing
lecture 9(lecture 9 ann)
10
LR parsing - conflict resolution
lecture 10(lecture 10 ann) (supplement to lecture 10) (The LR theorem)

Review for midterm 1 (optional)
Review questions(solutions)

Midterm 1 - 180 Bevier Hall, 7-8:30PM
exam solution
11
Code generation
lecture 11
12
Code generation (cont.)
lecture 12(lecture 12 ann)
13
Garbage collection; run-time systems for dynamic languages
lecture 13 (6up)
14
History of programming languages
lecture 14(lecture 14 ann)
15
APL
lecture 15(lecture 15 ann)
16
Functional programming: higher-order functions
lecture 16 (ann)
17
More higher-order functions
lecture 17(lecture 17 ann) (supp. notes on dynamic scope)

Spring break
18
Even more higher-order functions
lecture 18(lecture 18 ann)
19
Functional programming in o-o languages
lecture 19
20
Review for midterm 2 (optional)
sample questions(solutions) (12:30 review notes) (2:00 review notes)

Midterm 2 - 151 Everitt Lab, 7-8:30PM
Midterm solutions
21
Inference systems; formalizing operational semantics
lecture 21(lecture 21 ann)
22
Type systems
lecture 22 (ignore pages 18-22) (proof trees for examples)
23
Operational semantics
lecture 23 (2-up) (6-up) (Two examples) (handout) (yet another example)
24
Hoare logic for imperative languages
lecture 24(lecture 24 ann)
25
Hoare logic for imperative languages
lecture 25 (ann), fibonacci number example
26
Advanced topics: Lazy evaluation; lambda-calculus
lecture 26(lecture 26 ann)
27
Advanced topics: functional programming for parallelism
lecture 27
28
Wrap-up; review for final; preview of follow-up courses
For review:sp08-final.pdf(solution) - see below.
And Spring 08 sample questions(solutions) - see below.
And slides fromvideotaped problem session
Subscribe to: Posts (Atom)