CS 241 | SCS

To describe the relationship between high-level programming languages and the computer architecture that underlies their implementation.

Intended Audience

CS 241 is a required course for all academic plans in the Department of Computer Science and is normally completed in a student's 1B or 2A term.

Related Courses

Prerequisites: CS 134 or 136 (minimum grade of 60%) or 138 or 145; Honours Mathematics or Software Engineering students only.

Hardware/Software

Assumed Background: Programming skills including object-oriented programming and generics.

References

Modern Compiler Implememtation in Java 2nd ed by Andrew Appel, Computer Organization and Design, 4th ed., by D. Patterson and J. Hennessy, Morgan Kaufmann; and Unix in a Nutshell, 4th ed. by A. Robbins, O'Reilly, 1999 are recommended.

Schedule

3 hours of lectures and a 1 hour tutorial per week. Normally available in Fall, Winter and Spring.

Notes

Outline

Scanning (4 hours)

Compiler architecture. Syntax vs. semantics. Introduction to formal languages. Regular languages, regular expressions and finite state machines.

Debugging in the Small (1 hr)

The logical analysis of program misbehaviour, interactive source-level debugging.

Parsing (7 hours)

Context-free grammars, derivations, derivation trees, ambiguous grammars. Introduction to top-down and bottom-up parsing, LL(1) and LR(1) grammars. Tool-based parser generation.

Semantic Analysis (4 hours)

Basic Machine Architecture (6 hours)

Functional components of a computer: memory, control unit, arithmetic/logic unit, input/output devices. Data representation. Machine language: operation codes, addressing modes, indexing, base registers, register designation.

Assemblers, Linkers and Loaders (4 hours)

Mnemonic op-codes, pseudo-ops, symbolic constants and addresses, literals. Assembler algorithm, linker and loader algorithms.

C++ (9 hours)

Brief introduction to the non-object oriented features of C++ with an emphasis on pointers, references, and memory management.