CS 524 - Compiler Construction
Spring 2008 - San Diego State

2-3:15pm P-149

Dr. Kris Stewart, Professor, stewart@sdsu.edu
Computer Science Department, San Diego State University
Office : CG535 Office Hours: Mon noon-1:45pm, Wed 1-1:45pm or by appointment

This URL https://stewart.sdsu.edu/cs524/spr08/index.html; Upd: 24Dec2023
html misc Mathematical, Greek and Symbolic characters for HTML:
Email
TEXT Compilers: Principles, Techniques and Tools by Aho, Lam, Sethi and Ullman, Addison Wesley Publisher, 2006 [Dragon Book].


Sample test for Procs These are the first 4 files for my Procedures tests
Midterm 2 will be returned Wednesday 07May08
Phase 5 will be scored and e-returned Tuesday 06May08
Instructor will be checking Phases within a few days for remaining semester.
**Upd** Completed Project no longer due on date of Final: Monday, May 12 but now at end of Final Week May 17 Midnight; Grades due 23May08.
Discuss Project and trouble shoot - 05-07 May 2008
Midterm Two - Runtime Mechanisms - 30 April 08
Midterm Review - 28 April 08
Distribute Practice Midterm2, Hints for Booleans (Phase 4 postponed) - 23April08
Hints for Procedures (Phase 6) - 21April08
Run Time Environment [07 April 2008} 09apr Upd 16Apr08

IfThenElsifElse
Control Structures 1 of 2 [24March08] As a Group of 3 (or 2) Control Structures 2 of 2 [26March08] as a group of 3 (or 2)

Instructor providing a working version of Phase 3 to assist everyone. 24March08
mkdir Phase3
cd Phase3
cp ~stewart/cs524/simpleP3/* .
Integer Declarations [17Mar08] Due 29March08 ** CANCELLED **

Chapter 6 Intermediate Code Generation

Practice Midterm [12March08, discussed 27feb08] Practice Midterm1 solutions [Lecture Wed]

Using SLRgen [13Feb08} to generate the Simple-LR parser tables
Expected results for Comments
Strings-FrontEnd Strings-BackEnd ** Upd ** 25Feb08 with Strings Sample simple.lex for Phase 2 simple.lr for Phase 2 ** 10march08 **
Readings and Problems for Compile-Time Structures - Part 1 [*upd* 27Feb08]
Ch 4.5 Bottom-Up Parsing
InfoLab [discussion] 07Feb08
Ch4 Syntax Analysis [05Feb08]
Ch3 Lexical Analysis 28Jan08
Project [30Jan08 - GMCS 425 lab]
Project Structures
Resources **Upd26march08**
Calendar [project deadlines and mid terms] **Upd25feb08**

NOTE: We meet in GMCS 425 next Wednesday (30Jan08) to logon to the Rohan Solaris/UNIX system and start to examine our Compiler Project in detail.
General Introduction 23Jan08

Introduction

Compilers are fundamental to modern computing. Compiler construction unifies many of the subjects that comprise Computer Science since a compiler is one LARGE example of: Come join me in a one-on-one encounter with a tool you have been using for years and see how the fundamental concepts above are actually used to get an important job done - automatically translating Higher Level Languages into the assembly code for the hardware to actual work with.

PUT YOUR COMPUTER SCIENCE KNOWLEDGE TO WORK FOR YOU!

Prerequisites

CS320 Programming Languages, CS310 Data Structures, and CS237 Assembler Language provide the background for this course, although much of the material needed to apply this knowledge in this course is quickly reviewed in lecture to provide a compiler-centric view of the particular concepts and precisely how they are employed to produce a compiler.

An example of the beginning point of your project is given by the source code:

                beta :=2;
                readln(gamma);
                alpha := 2 + beta * gamma;
                if beta = 2 then
                        beta := beta + gamma * alpha + alpha;
                        writeln(beta);
                end if;


A result from the compiler is to recognize the language structures and represent them in an
Abstract Syntax Tree, displayed as

  :=stmt       readln         :=stmt                  ifstmt
   /  \        |              /   \                   /     \
beta    2       \list      alpha    +                |       |
                 gamma            /   \              |       |
                                 2     *            ==     thenlist
                                     /   \         /  \     | writeln
                                  beta  gamma    beta  2    | := stmt

The next step is to generate the SPIM assembly language.

For example, the assignment statement, :=stmt, above corresponds to:

# Generate Assignment Statement 
# 
        lw      $t0,4($t8)
        lw      $t1,8($t8)
        mul     $t0,$t0,$t1
        add     $t0,$t0,2
        sw      $t0,0($t8)
where we load the values of beta and gamma from memory into their own registers (t0 and t1, above), multiply the values together and store in t0, add the constant 2 to register t0 and store the result back to the memory location of alpha.

Course Grade

50% 2 Midterm Examinations
50% Compiler Project

The project extends a working compiler in incremental stages over the semester. This involves effort, but is a good way to clarify the concepts covered in course lectures. We use UNIX and the C language to make effective use of the language tools lex (for lexical analysis) and yacc (for parsing) on Rohan. The working compiler already has the capabilities to process arithmetic statements, has a working symbol table, has a way to display internal workings of the compiler and generate assembly code for a machine named SPIM.

A significant software project, such as the one which is the basis of this course, should be approached from a Team point of view. The initial phases of your project will be done as an individual student, but later phases will be done as a member of a team. Students should be considering who they wish to partner with later in the semester for this 3-person activity.

SPIM is based on the MIPS R2000/R3000 emulator by James R. Larus, now with Microsoft Research, and featured in the text: Computer Organization and Design: The Hardware/Software Interface by Patterson and Hennessy, Morgan Kaufmann Pub. The file: www.cs.wisc.edu/~larus/HP_AppA.pdf local pdf file from Larus. Morgan-Kaufmann has generously allowed Larus to make available an electronic copy in PDF of Appendix A: Assemblers, Linkers, and the SPIM Simulator the text: Computer Organization and Design: The Hardware/Software Interface by Patterson and Hennessy, Morgan Kaufmann Publishers.

These are examples based on the prerequisites of the course. If they look somewhat familiar to you, then you are ready for this adventure. Join us Spring 2008!