CS 311-3
The Theory and Implementation of Programming Languages
Catalog Description
Introduction to the theory and implementation of programming languages including finite automata, regular grammars, lexical analysis, parsing, syntax-directed translation, semantic analysis, binding variables, data types, static and dynamic scope, subprograms, abstraction, and concurrency. Study of object-oriented, functional, and logic programming languages. Lab work is essential.
Prerequisite:
CS 220 with a grade of C or better.
Objectives
1. To provide students with a brief background on compilers and language compilation;
2. To give students an understanding of the basics of the theory of computing as it is applied to develop programming languages;
3. To make students aware of the range of features and capabilities that are available in programming languages;
4. To develop an understanding of the issues that arise in implementing various programming language features;
5. To increase awareness of how particular language features can affect the problem solving and programming process;
6. To survey a range of different classes of programming languages so students have a basis for selecting the best language for the task.
Course Outline
| Lectures & Labs | ||
| 1. | Introduction; domains, language evaluation criteria, language categories, implementation methods | 3 |
| 2. | Syntax and semantics; formal methods of describing syntax, attribute grammars, dynamic semantics | 6 |
| 3. | Finite automata; deterministic and nondeterministic finite automata, regular grammars | 5 |
| 4. | Lexical and syntax analysis; recursive-descent parsing, bottom-up parsing | 5 |
| 5. | Variables; Names, binding, types, scope, lifetime | 2 |
| 6. | Basic Data Types; implementations of integers, strings, etc. | 2 |
| 7. | Expressions; operators, assignment, precedence, associatively, side effects, overloading, coercion | 2 |
| 8. | Subprograms; procedural abstraction, generic functions, parameter passing, recursion | 2 |
| 9. | Abstract data types; data abstraction, user-defined data types, encapsulation, information hiding | 2 |
| 10. | Concurrency; monitors, threads | 2 |
| 11. | Exception and Event Handling | 2 |
| 12. | Object-Oriented Programming; basic features, alternative models, implementation requirements | 3 |
| 13. | Functional and Logic Programming; lisp, side-effect free, verification, PROLOG | 4 |
| Total | 40 | |
Recommended Books:
1. "Concepts of Programming Languages," 8th edition, by Sebesta; Addison Wesley.
2. "Introduction to Automata Theory, Languages, and Computation," 3th edition by Hopcroft, Motwani, and Ullman, Addison Wesley