|
[
Announcements | Lectures
| Course Description | Course
Outline | Homework and Project Information | Class Schedule ]
|
|
Announcements (back to top)
|
|
|
|
|
|
Lectures (back to top)
|
|
|
|
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 language, 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 such as Perl.
|
|
Course
Outline (back to top)
|
|
Required Textbooks
Bundle ISBN# 1418879746, including
Both textbooks are also available on reserve in the library.
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
- Future topics: Quantum
Grading
- Homeworks: 25%
- Pop-quizzes : 5%
- Midterm : 25%
- Final: 30%
- Mini-project : 15%
|
|
Homework
and Project Information (back to top)
|
|
Collaboration Policy
You are allowed to discuss course materials, homework problems, and
programming 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 Guideline
No late homework or assignment is allowed without prior
approval of the instructor. All homeworks due in the class at the beginning.
- Homework
I (PDF), Due : January 27th 2009, Total points : 70
- Homework
II (PDF), Due : February 17th 2009, Total points : 100
- Homework
III (PDF), Due : February 26th 2009, Total points : 50
- PRACTICE
TEST (MIDTERM) (PDF)
- Homework
IV (PDF), Due : April 9th 2009, Total points : 100
- Homework
V (PDF), Due : April 17th 2009, Total points : 100
- SAMPLE
TEST FINAL (PDF)
|
|
Class
Schedule (back to top)
|
|
- In the reading list, L
stands for the textbook by Louden and S by Sipser.
- Check the newsgroup git.cc.class.cs3240
for class news.
- All schedules are
very tentative and are subject to change.
- A very tentative
schedule
|
Week
|
Date
|
Topic
|
Reading
|
|
1
|
Tuesday, January 6
|
Course Introduction/Logistics/Compiler concepts
|
|
|
|
Thursday, January 8
|
Introduction to compiler concepts
|
L1
|
|
2
|
Tuesday, January 13
|
Regular expressions; Deterministic finite automata (DFA)
|
L2.1-3, S1.1
|
|
|
Thursday, January 15
|
Nondeterministic finite automota; RegExp=regular
languages
|
L2.4,S1.2-3
|
|
3
|
Tuesday, January 20
|
Topic contd.
|
|
|
|
Thursday, January 22
|
Topic contd.
|
|
|
4
|
Tuesday, January 27
|
Topic contd.
|
|
|
|
Thursday, January 29
|
Topic contd.
|
|
|
5
|
Tuesday, February 3
|
Pumping lemma
|
S1.4
|
|
|
Thursday, February 5
|
Pumping lemma
|
S1.4
|
|
6
|
Tuesday, February 10
|
Lexical analysis; Context-free grammar
|
L2.3,S2.1
|
|
|
Thursday, February 12
|
Ambiguity; Chomsky normal form
|
L3.1-5
|
|
7
|
Tuesday, February 17
|
Contd.
|
|
|
|
Thursday, February 19
|
Contd.
|
|
|
8
|
Tuesday, February 24
|
Non-context-free languages; Recursive descent
|
S2.3; L4.1
|
|
|
Thursday, February 26
|
LL(1) parsing; First and follow sets
|
L4.2-3
|
|
9
|
Tuesday, March 3
|
LL parsing contd.
|
|
|
|
Thursday, March 5
|
Review for Midterm
|
|
|
10
|
Tuesday, March 10
|
Midterm Examination
|
|
|
|
Thursday, March 12
|
Overview of bottom-up parsing; LR(0); Simple LR(1)
|
L5.1-3
|
|
11
|
Tuesday, March 17
|
Spring Break
|
|
|
|
Thursday, March 19
|
Spring Break
|
|
|
12
|
Tuesday, March 24
|
Overview of bottom-up parsing; LR(0); Simple LR(1)
|
L5.1-3
|
|
|
Thursday, March 26
|
Overview of bottom-up parsing; LR(0); Simple LR(1)
|
L5.1-3
|
|
13
|
Tuesday, April 2
|
Overview of bottom-up parsing; LR(0); Simple LR(1)
|
L5.1-3
|
|
|
Thursday, April 4
|
LALR(1), Error Recovery etc.
|
L5.5-7
|
|
14
|
Tuesday, April 9
|
Pushdown Automata
|
S2.2
|
|
|
Thursday, April 11
|
Turing Machines
|
S3.1
|
|
15
|
Tuesday, April 16
|
Turing Machines
|
S3.1
|
|
|
Thursday, April 18
|
Turing machines
|
S3.1
|
|
16
|
Tuesday, April 23
|
Turing Machines
|
S3.1
|
|
|
Thursday, April 25
|
Review for final
|
|
|
|
April 27- May 1
|
Finals Week
|
|
|