[ Course Description
| Course Outline | Slides and
course handouts | Homework and Project Information
]
|
| Course
Description (back to top) |
|
Languages define the computation that should be performed to recognize
them. Typically such a computation is defined as a task to recognize a
certain class of strings that could belong to a given language. Some
strings can be recognized by simple machines, whereas some others need
certain computational power for a machine to be able to recognize them.
The objective of this course is to learn about the abstract languages
and the computations defined in them along with the corresponding
machines. Compilers and their phases illustrate practical applications
of the theory behind such abstract languages and the corresponding
machines. First, abstract languages that are regular and context free
will be learnt through corresponding phases of the compiler that
involve scanning and parsing. Following the practical applications of
such techniques, corresponding theory will be learnt. The underlying
theory shall deal with the limits of regular expressions (aka pumping
lemma) and concepts that illustrate the differences in powers of
deterministic pushdown automata and non-deterministic pushdown
automata. Finally, notion of Turing computability of functions will be
introduced through along with the halting problem. Notions of
undecidability and completeness will be briefly touched upon. The
following are the key objectives of this course:
- In depth understanding of practical applications of
regular and context free languages in light of compilers.
- Understanding of theoretical underpinnings that form the
basis of regular and context free languages along with notions of
Turing computability.
- Problem solving combining the two in light of practical
pattern matching languages such as Perl.
This course has both theoretical as well as practical work involved and
regular reading and class participation is necessary.
|
| Course Outline
(back to top) |
|
Textbooks : Bundle #1418879746
- "Compiler Construction: Principles and Practice", by
Kenneth C. Louden,Thompson Course Technology, ISBN 0-534-93972-4
- "Introduction to the Theory of Computation" by Michael
Sipser, Thompson Course Technology, ISBN 0-534-94728-X
Outline:
- Lexical Analysis, Scanners, Patten 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, determistic 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
Emphasis and Grading
- Understand the theory behind languages and computation they
specify.
- Apply the concepts learnt in compiler setting.
- Understand Limits of computation (what can and can not be
computed) and intuitively learn about
complexity of computation.
- Homeworks : 25%, Test-I: 20 %, Test-II: 15 %, Final : 25 %,
Mini-project : 15 %
|
| Slides and
course handouts (back to top) |
- Course Policies [ ppt | pdf ]
- Introduction to Compiler Concepts [ ppt | pdf ]
- Scanning and Regular Expressions [ ppt
| pdf ]
- Finite State Machines [ ppt |
pdf ]
- Deterministic and Nondeterministic Finite Automata [ ppt | pdf ]
- How to construct DFAs [ pdf ]
- Parsing - Topdown Parsing [ ppt ] LL1 Parsing [ ppt ]
|
| Homework and
Project Information (back to top) |
- Homework 1 (Due January
30th, 6 pm)
- Homework 2 (Due Feb 10th, 5
pm)
- Exam 1: Tuesday, February 14th -
from 1:35 to 2:55 pm, in class
Syllabus : Louden, Chapter 2 : 2.1 to 2.4 Sipser : Chapter 1 (except
pumping lemma, section 1.4)
- Homework 3 (Due March 9th,
5 pm)
- Project Information [ pdf ]
- Homework 4 (Due: Wed, April 5
by
5pm)
- Exam 2: Tuesday, April 11th - - from 1:35 to 2:55 pm, in
class
Syllabus includes pre-midterm, with emphasis on post-midterm.
Pre-Midterm: Sipser Chapter 1 till 1.4, Louden Chapter 2 till
2.3
Post-Midterm: Sipser Chapter 1 from 1.4 onwards, Louden Chapter 2.4,
Chapter 3, Chapter 4 till 4.4
- Homework 5 (Due: Tue,
April 24 In Class)
- Practice Questions [ pdf ]
|