|
[ Lectures
| Course Description | Course
Outline | Homework and Project Information | Class Schedule ]
|
|
Lectures and Other Course Materials(back to top)
|
Course announcements and assignments will be posted on T-Square.
|
|
CourseDescription (back to top)
|
|
A language is a certain class of strings that can be recognized by a
corresponding machine. The objective of this course is to learn these
abstract languages and the computations of their corresponding machines.
Scanners and parsers of compilers will illustrate the practical applications
of these theories. Notion of the Turing machines, decidability, and
reducibility will also be discussed. The key objectives of this course are
the following:
- in-depth understanding
of computational powers of regular languages, context-free languages and
Turing machines;
- understanding of
practical applications of regular and context-free languages in
compilers;
- problem solving by
combining the two in pattern matching languages
|
|
Course
Outline (back to top)
|
|
Required Textbooks
Bundle ISBN# 1418879746, including
Outline
- Lexical analysis,
scanners, pattern matching
- Regular expressions,
DFAs, NFAs and automata
- Limits on regular
expressions, pumping lemma
- Practical parsing, LL
and LR parsing
- Context-free
languages, grammars, Chomsky Hierarchy
- Pushdown automata,
deterministic vs. non-deterministic
- Attribute grammars,
type inferencing
- Context-free vs.
context-sensitive grammars
- Decidable vs.
Undecidable problems, Turing Machines, Halting Problem
- Complexity of computation,
classes of languages P/NP, space and time completeness
Grading
- Homeworks: 25%
- Midterm : 30%
- Final: 30%
- Mini-project : 15%
|
|
Homework
and Project Information (back to top)
|
Georgia Tech and College of Computing academic Honor Code applies. Homeworks are announced in class and are posted on the class web page. You are allowed to discuss course materials, homework problems, and
assignments in small groups, but limited to discussion of general
ideas only. You must write your solutions completely independently,
and must report the names of your collaborators with whom you discussed
the assignments. Under no circumstances may you copy solutions from any
source, including but not limited to other students solutions, official
solutions distributed in past terms, and solutions from courses taught at
other universities. Violation of these rules may result in disciplinary
actions. Homework solutions should be turned in in class, stapled, before the lecture starts, on a due day. If you are unable to attend a lecture when a homework is due, you can email me (and cc the TAs) a postscript or a PDF file with your solutions before the time of the class. No late homeworks will be accepted.The exams are closed book. One cheet sheet may be allowed. The details about the project will be posted later.
|
|
Class
Schedule (back to top)
|
|
- In the reading list, L
stands for the textbook by Louden and S by Sipser.
- A very tentative
schedule
|
Week
|
Date
|
Topic
|
Reading
|
|
1
|
Tuesday, January 11
|
Course Introduction/Logistics/Compiler concepts
|
|
|
|
Thursday, January 13
|
Introduction to compiler concepts
|
L1
|
|
2
|
Tuesday, January 18
|
Regular expressions; Deterministic finite automata (DFA)
|
L2.1-3, S1.1
|
|
|
Thursday, January 20
|
Nondeterministic finite automota; RegExp=regular
languages
|
L2.4,S1.2-3
|
|
3
|
Tuesday, January 25
|
Topic contd.
|
|
|
|
Thursday, January 27
|
Topic contd.
|
|
|
4
|
Tuesday, February 1
|
Topic contd.
|
|
|
|
Thursday, February 3
|
Pumping lemma
|
S1.4
|
|
5
|
Tuesday, February 8
|
Pumping lemma
|
|
|
|
Thursday, February 10
|
Lexical analysis; Context-free grammar |
L2.3,S2.1 |
|
6
|
Tuesday, February 15
|
Lexical analysis; Context-free grammar
|
|
|
|
Thursday, February 17
|
Ambiguity; Chomsky normal form
|
L3.1-5
|
|
7
|
Tuesday, February 22
|
Non-context-free languages
|
S2.3 |
|
|
Thursday, February 24
|
Pushdown Automata |
S2.2 |
|
8
|
Tuesday, March 1
|
Recursive descent; LL(1) parsing |
L4.1-2
|
|
|
Thursday, March 3
|
LL(1) parsing; First and follow sets
|
L4.2-3
|
|
9
|
Tuesday, March 8
|
LL parsing contd.
|
|
|
|
Thursday, March 10
|
Review for Midterm
|
|
|
10
|
Tuesday, March 15
|
Midterm Examination
|
|
|
|
Thursday, March 17
|
Overview of bottom-up parsing; LR(0); Simple LR(1)
|
L5.1-3
|
|
11
|
Tuesday, March 22
|
Spring Break
|
|
|
|
Thursday, March 24
|
Spring Break
|
|
|
12
|
Tuesday, March 29
|
Overview of bottom-up parsing; LR(0); Simple LR(1)
|
L5.1-3
|
|
|
Thursday, March 31
|
Overview of bottom-up parsing; LR(0); Simple LR(1)
|
L5.1-3
|
|
13
|
Tuesday, April 5
|
Overview of bottom-up parsing; LR(0); Simple LR(1)
|
L5.1-3
|
|
|
Thursday, April 7
|
LALR(1), Error Recovery etc.
|
L5.5-7
|
|
14
|
Tuesday, April 12
|
|
|
|
|
Thursday, April 14
|
|
S3.1
|
|
15
|
Tuesday, April 19
|
Turing Machines
|
S3.1
|
|
|
Thursday, April 21
|
Turing machines
|
S3.1
|
|
16
|
Tuesday, April 26
|
Turing Machines
|
S3.1
|
|
|
Thursday, April 28
|
Review for final
|
|
|
|
May 2 - May 6
|
Finals Week
|
|
|