CS 241 | SCS | UW

Revised December 11, 2013

CS 241: Foundations of Sequential Programs

General description

CS 241 covers the relationship between high-level programming languages and the computer architecture that underlies their implementation. Students learn the fundamentals of the compilation of computer programs to machine-executable code and how to implement simple versions of relevant algorithms. The following topics are discussed:

  • Functional components of a computer (CPU, memory, I/O) and their interactions. Representation of data in a computer and its manipulation at the machine-language level and in high-level languages.
  • Assembly language and the implementation of an assembler. Overall structure of a compiler and the functions of its components. Purpose and functions of linkers and loaders.
  • Specification and recognition of regular languages and their use in lexical analysis (lexical-analysis tools). Specification and parsing of context-free languages (parsing tools). Semantic analysis and code generation for procedural languages.

Logistics

Audience

  • 2B Computer Science students
  • Optional for Computational Math students

Normally available

  • Fall, Winter, and Spring

Related courses

  • Predecessors: CS 246 or (CS 138 and enrolled in Software Engineering)
  • Successors: Most third-year CS major courses
  • Co-requisites: Taking CS 241 together with CS 251 works well
  • Conflicts: Other courses that focus on the process of turning programs into executable code

For official details, see the UW calendar.

Software/hardware used

  • UNIX/Linux, C++, and possibly Scheme

Typical reference(s)

  • D. Patterson, J. Hennessy, Computer Organization and Design, 4th ed., Morgan Kaufmann
  • A. Robbins, Unix in a Nutshell, 4th ed., O'Reilly

Required preparation

At the start of the course, students should be able to

  • Design, code, test, and debug several-hundred-line programs in C/C++
  • Describe the basic properties of the C/C++ memory model: bytes vs. words, memory as an array, pointers as memory addresses, run-time stack and stack frames, memory allocation on the heap vs. automatic allocation on the stack
  • Use basic collections (arrays, lists, dictionaries) in C/C++ programs  

Individual instructors may choose to use Scheme in addition to C/C++. Assignments written in Scheme may be at the level indicated above for C/C++ (mutatis mutandis). Prior knowledge of Scheme is not required.

Learning objectives

At the end of the course, students should be able to

  • Write short machine- and assembly-language programs to perform simple data manipulation
  • Write a basic assembler supporting labels
  • Give formal specifications for regular languages, including regular expressions and bubble diagrams
  • Write a scanner capable of dealing with a typical high-level programming language (given the specification)
  • Give a grammar for a context-free language and, given a grammar, produce a derivation for a given string in the language
  • Write a parser for an LR(1) language given a low-level representation of the LR-parsing automaton (e.g., as derived from an automatic parser generator)
  • Write a simple code generator for an imperative language, i.e., one doing little or no optimization
  • Apply appropriate design decisions when programming in C/C++ based on a detailed understanding of the way memory is used by a running C/C++ program

Note: When writing programs, students must be able to design, code, debug, test, and successfully run the programs.

Typical syllabus

Machine architecture and assembly language (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 (6 hours)

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

Regular languages and scanning (5 hours)

  • Architecture of a compiler
  • Syntax vs. semantics
  • Introduction to formal languages
  • Regular languages, regular expressions, and finite state machines

Context-free languages and parsing (8 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 and Code generation (6 hours)

  • Constructing parse trees
  • Code generation

Runtime organization and data layout (5 hours)

  • Machine-level implementation of procedure invocation and the runtime stack
  • Implications of stack vs. heap allocation
  • Main-storage layout for structures, vectors, and arrays