A capstone course in which students design and implement a compiler as an application of the principles of software engineering, formal language theory, algorithms and data structures. Topics include lexical analysis, parsing, symbol table management, code generation and optimization and use of compiler tools.
Prerequisite(s): Grades of "C" or better in CMPSC 140 Data Structures and CMPSC 200 Formal Languages and Automata.
(Normally offered alternate years.)
CMPSC 140 Data Structures (4 hours)
A natural continuation of Computer Science 40 concentrating on the motivation, design, implementation, and utilization of abstract data types. Topics include linked lists, stacks, queues, trees, and recursion. A lab component is incorporated.
Prerequisite(s): Grade of "C" or better in CMPSC 040 Program Design.
(Normally offered each spring semester.)
CMPSC 200 Formal Languages and Automata (3 hours)
An overview of formal models of computation and complexity classes. Topics include formal languages (finite automata, regular expressions, push-down automata, context-free grammars, and Turing machines), Church's thesis, computability, non-determinism, and NP-completeness. Same as MATH 200 Formal Languages and Automata.
Prerequisite(s): Grade of "C" or better in either CMPSC 100 Discrete Mathematics or MATH 111 Introduction to Higher Mathematics and junior standing.
(Normally offered alternate years.)
