Chapter 1: introduction (Lectures 1, 2, 3)

- programming languages classification
  + what makes a successful programming language?
  + declarative languages (definition)
    - functional programming languages
    - logical programming languages
  + imperative languages (definition)
    - procedureal and object-oriented languages
- compilation and interpretation
  + definition, what is the main difference between compilation and 
    interpretation?
  + compilation and execution on virtual machines
  + compilation: static linking and dynamic linking
  + preprocessing: what is its relation with compilation?
  + IDE definition
- Compiler phases and what each phase does

Chapter 2: Programming language syntax (Lectures 4, 5, 6, 7, 8, 9, 10)

- lexical analysis
  + tokens and regular expressions
    - formal definitions and how to write regular expressions for 
      different types of tokens
  + regular expressions and NFA
    - formal definition of NFA
    - algorithm to convert a regular expression to the corresponding NFA.

- syntax analysis
  + formal definition of grammar
  + derivation and the language recognized by a grammar
  + Chomsky hierarchy (grammar classification)
  + context free grammar 
    - definition
    - writing context free grammar for a language
  + leftmost and rightmost derivation
  + parse tree
  + ambiguity grammar
  + Parsing
    - two general approaches
  + Recursive descent parsing
  + LL(1) Predictive parsing
    - Parse structure
    - step by step trace of the LL(1) parsing algorithm
    - construct LL(1) parsing table
      + algorithm for computing First and Follow sets
      + Using First and Follow sets to compute the parsing table
    - Sufficient and necessary conditions for a grammar to be LL(1)
    - Left recursion and left common factor
    - Algorithms to remove left recursion and left common factor

Chapter 3: Names, Scopes, and Bindings (Lectures 13, 14, 15)

- Names and issues related to names
  + Name and binding
  + potential binding time
  + effective of binding time
  + objective lifetime and binding lifetime
  + deactivation/reactivation of bindings
- Objective storage management schemes
  + the memory layout of a process/program
  + static allocation
    - Example of objects with static allocation
    - Can static allocation be used for local variabls?
  + subroutine frame/activation record format
  + stack allocation
    - how is the storage for running subroutines managed?
  + Heap allocation
    - algorithms
    - internal and external fragmentations
    - block selection: first fit/best fit
    - garbabe collection, what does it do?
- Scope:
  + definition
  + dynamic scoping and static scoping
  + static scope implementation
    - static chains for nonlocal variables
  + dynamic scope implementation
    - binding stack
  + module and module scopes

Chapter 4: Semantic analysis (Lectures 11, 12)

- static semantics and dynamic semantics
- attribute grammar
  + definition
  + writing attribute grammar
    - adding semantic rules on a given grammar to perform some function
    - writing an attribute grammar to enhance the underlying context 
      free grammar.
- building decorated parse tree (parse tree annotated with attributes)
- synthesized and inherited attributes
- S-attributed and L-attributed grammars

--------------------------------------------------------------------

Chapter 6 Control Flow (Lectures 16, 17)

- expression and assignments
  + infix, prefix, postfix, Cambridge Polish natations
  + Operator Precedence and Associativity (definition)
  + Evaluation order of expressions
    - Why this is not specified by precedence and associativity
    - why it is important
    - Design choices for different languages
  + short circuit evaluation for boolean expressions
    - impact of short circuit evaluation
  + L-values and R-values
  + value model and reference model for assignments

- Structured and unstructured control flow
  + the concepts of structured and unstructured control flow
  + Goto's
  + Sequencing
  + Selection
    - different forms of selection
  + Iteration and iterators
    - enumeration-controlled loops
    - logically-controlled loops
      + pretest
      + posttest
      + midtest 
  + Recursion
    - tail-recursive function and its optimization

Chapter 8 Subroutines and parameter passing (8.1, 8.2, 8.3)
(Lectures 18, 19)

- Related subjects
  + Subroutine frame (activation record) format
  + Stack layout for dynamic and static binding languagues
- Calling sequences
  + prologue and Epilogue
  + issues with saving and restoring registers
  + Describe a typical calling sequence
  + Hardware/software support for efficient subroutine execution
    - Register windows
    - Inline functions
- Parameter passing:
  + Call-by-value
  + Call-by-reference
  + Call-by-sharing
  + Call-by-result, call-by-value/result
  + Call-by-name
  + need to be able to apply this in programs

Chapter 10 Functional Programming (Lectures 20, 21, 22)

Needs to know the general background of functional programming and 
programming in Scheme

- What is functional programming
- Pros and Cons of functional programming
- theory of functional languagues
  + computation model for Scheme(Lisp): Lambda Calculus
- Scheme programming
  + Read-Eval-Print loop
  + Cambridge Polish notation
  + Atoms
  + list manipulation functions
  + "if" special form
  + "cond special form
  + logical expressions
  + Lambda abstractions
  + defining global names
  + define local names
  + define local names with self references
  + scheme IO
  + Blocks
  + Do-loops
  + Higher-order functions
  + non-pure constructs
  
Scheme programming: need to be able to write scheme functions to 
achieve some tasks like those in the project and homework assignments.

Chapter 11 Logic Programming (Lectures 23, 24, 25, 26)

Need to know the background of logic programming and programming in Prolog

- Horn clause
- logical resolution strategies
- Prolog programming
  + Horn clauses for rules and facts
  + Prolog terms and built-in predicates to manipulate terms
  + variable, and unification
  + Prolog list and list manipulation
  + Prolog IO
  + Prolog Arithmetic
  + Prolog control features
  + Prolog Meta-logic
  
Prolog programming: need to be able to write prolog programs to 
achieve some tasks like those in the homework assignment.

----------------------------------------------------------------

Point distribution:
 
  materials before the midterm 30-35 points (what was tested in the midterm
  is still important in the final).

  materials after the midterm 65-70 points.

-----------------------------------------------------------------

Problem types -- similar to midterm (the difficulty level is same as homework).

  multiple choices and/or true/false
  program traces/hand execute algorithms/grammars/parsing table, etc
  Scheme and prolog programming