CMSC 430, Section 101

CMSC 430: Theory of Language Translation

Basic Information

Time: Tuesday & Thursday 11:00-12:15
Location: CSI 1121

Text: "Compilers: Principles, Techniques & Tools" by Aho, Lam, Sethi and Ullman, Pearson Education Inc., 2007, ISBN - 0-321-48681-1

Name Office Office Hours Email
Marvin Zelkowitz AVW 4121 Mon 10am-11 & Wed 1pm-2pm Note change mvz@cs.umd.edu
In general whenever my door is open - Usually in the mornings. It is best to email first to make sure I am around.

Course News

April 5 - Because I didn't set up submit server correctly for project 3, deadline is now midnight Friday, April 6. ALso Project 5 is cancelled and project 4 is due May 3, 2007.
March 29 - Note that effective April 3, Wednesday office hours will be 1-2pm and Dr. Zelkowitz will not be in his office Wednesday morning.
February 21 - Do the following assignment and turn in results (hardcopy) in class on March 1: Output Postfix on a recursive descent parser
February 21 - All project due dates are listed below. The parser specifications are given.
February 15 - 5 test files of NIP programs are on the grace cluster as ~mvz/test0.nip through test4.nip. These programs can be used for each phase of the project. test0.nip and test4.nip are the most informative tests.

Lectures

Date	Lecture Topic	Slides	*Textbook (-Not yet updated to new text)**
1/25-30	Introduction & Overview; Review of CMSC 330	M01	Ch 1 (1-38) Ch 2 (39-107)
2/1-6	Scanner Construction	M04, LEX example	Ch 3 (109-189)
2/8-13	Top-down Parsers	M08	Ch 4.1-4.4 (191-231)
2/15-20	Bottom-up Parsers	M09 (new-2/21/07)
2/22-27	LR Parsers	M10, LR(1) example, LALR example	Ch 4.5-4.9 (233-300)
3/1	Intermediate forms	M11 quad example (Note: This is for a different language, but does show how quads are produced.)	Ch 6.1-6.2 (357-370)
3/6, 3/8	Context Sensitive Analysis	M12	Ch 5.1-5.4.3 (303-328) 6.5 (386-398)
3/13	Symbol tables	M13	85-91
3/15	Arrays, records	M14	Ch. 6.4 (380-386)
3/20, 3/22	Spring Break
3/27	Runtime environments and scope	M15 (Revised 4/5/07)	Ch 7 (427-502)
3/29	Mid term
4/3, 4/5, 4/10	Runtime environments	Java Bytecodes
4/12, 4/17	Code Generation (basic exprs, control flow)	M19 Code Gen notes	Ch. 8.1-8.3 (505-525) 8.6-8.7 (542-553)
4/19	Code shape	M21 M20
4/21	Optimization Overview	M25	360-362, Ch 8.4-8.5 (525-542)
4/26	Data-flow Analysis	M22	Ch 9.1-9.2 (583-617)
5/1	Instruction scheduling		Ch 8.9 (557-567)
5/3	Register allocation	M23 Lec20	Ch 8.8 (553-556)
5/8	RISC architectures	M24
5/10	Final Review
Saturday 5/12	Final	8-10am	CSI 1121

Old Exams

Practice problems using grammars

Homework 1 - Only do problems 1-6 now. Around February 12 a solution set will be posted for these. The remaining problems will be assigned later. Note that these problems will not be collected and graded, so you are not required to do them. But experience has shown that if you do not try them, you will not do well on the midterm and final.
Answers to problems 1-6
Homework 2 - from the above "Homework 1" pdf file, do problems 7(a), 8, 9, 10 and 14. (10 and 14 after March 8.) In addition, from the textbook, the following are representative problems: Page 258 (4.6.5, 4.6.6) and Page 278 (4.7.4 and 4.7.5). Solutions posted around March 12.
Answers to problems 7-14. Unfortunately I do not have printed solutions to the problems in the textbook.

Projects

NIP Compiler
1. The language you will be writing a compiler for is called NIP. The specifications for the language as well as the target machine language (HAC430) are now available at nip/NIP.project.2007-v2.pdf (Modified 03/13/2007). For now, look at only the syntax of the language. You can ignore the HAC430 machine language for several weeks. This language is different from versions used in the past. It may become necessary to issue revisions to this specification if defects in it become apparent.
2. NIP Scanner - Version 3 - Minor revision February 15, 8pm - Program due 11:59pm on February 20, 2007.
3. NIP parser - Version 1 - Program due 11:59pm on March 13, 2007.
4. NIP symbol table - Version 1 - Program due 11:59pm on April 5, 2007.
5. NIP Code generator - Version 1 - Program due 11:59pm on May 3, 2007.
6. All programs must be submitted no later than 11:59pm, May 10, 2007.

Class Resources

Class description: required textbooks, course objectives, grading policies, etc.
Syllabus: Defined by this web page.
This is a 400-level course and by now you are expected to know how to program. The choice of programming language is partially up to you. Your task this semester (among other tasks) is to build a compiler. You may write your compilers in Java, C or C++. In terms of grading, the compilers will be considered to be "black boxes." A set of input/output specifications will be given for each assignment and the programs will be tested to see if they meet those specifications. (My advice is to program in C or C++. Most CMSC courses use Java, which is not the dominant language in industry. Most of you could use more experience with C or C++.)
Grace cluster. You will use the grace machines (grace.umd.edu). All registered students who have glue accounts now have grace machine access. You may use your own machine to develop programs if you wish, but it is your responsibility to acces the grace cluster to obtain any project information placed there.
Submit program:
You will turn in your assignment using the submit server: submit.cs.umd.edu. More information on using it will be forthcoming.
The submit server will accept multiple submissions up to the submission deadline, overwriting previous submissions. Feel free to submit your project as many time as you desire before the deadline.
Grades will be made available on the grades server: grades.cs.umd.edu
Java information:
Java sources:
- Java JDK 6
- Java scanner generator: Jlex (JLex Manual) ( download java source)
- Java parser generator: CUP (Cup Manual) ( download zip archive)
C parsers and scanners
- Bison information
- Flex information

Name	Office	Office Hours	Email
Marvin Zelkowitz	AVW 4121	Mon 10am-11 & Wed 1pm-2pm Note change	mvz@cs.umd.edu
		In general whenever my door is open - Usually in the mornings. It is best to email first to make sure I am around.