CS 462 Formal Languages and Parsing
Watch a video introduction to this course on YouTube.
Objectives
Building on CS 360, this course discusses more advanced topics in formal languages and automata theory, with applications to compiler writing. In particular, several practical parsing methods are discussed.
Intended Audience
CS 462 is normally taken in a student's fourth year. This course should be of interest to students planning further studies in computer science.
Related Courses
Prerequisites: CS 360 or 365; Computer Science students only.
Successors: Graduate courses in compiler writing or formal languages.
References
A Second Course in Formal Languages & Automata Theory, by J. Shallit Published by Cambridge University Press.
Schedule
3 hours of lectures per week.
Outline
Properties of Strings (3 hours)
Outline of formal language theory. Strings, machines, proofs by induction. Combinatorics on words. Thue's problem.
Regular Sets (9 hours)
Review. Closure of regular sets under quotient, substitution, and inverse homomorphism. Decision algorithms for regular sets. The Myhill-Nerode theorem. Minimization of finite automata. Finite-state transducers.
Context-free Languages (6 hours)
Review. Coping with ambiguity. Inherently ambiguous CFL's. Closure of context-free languages under substitution, inverse homomorphism, and intersection with regular sets. Decision algorithms for context-free languages. Parsing arbitrary context-free grammars. Decidability results for CFG's.
Parsing (9 hours)
Phases of compilation. Top-down parsing. LL(1) grammars. Bottom-up parsing. LR(0) grammars. LR(k) grammars.
The Chomsky Hierarchy (3 hours)
Left- and right-regular grammars. Unrestricted (Type 0) grammars. Equivalence of Type 0 grammars and Turing machines. Context-sensitive languages. Linear bounded automata.
Deterministic Context-free Languages (3 hours)
Normal forms. Closure under complementation. Relationship to LR(0) grammars.
Other Language Classes (3 hours)
L-systems. Applications to computer graphics. Rational series.