Dalhousie University    [  http://www.cs.dal.ca/~vlado/csci3136/coursecalendar.html  ]
Winter 2008 (Jan7-Apr9)
Faculty of Computer Science
Dalhousie University

CSCI 3136 - Course Calendar

#DateTitle 
  Introduction
1 Mo Jan 7Course Introduction
Why is it useful to learn PPL? Basic course information, logistics: evaluation, plagiarism policy; course content overview, evolution of programming languages; handouts: course overview, slides, A0 Reading: [PLP] Ch.1
A0 out
2 We Jan 9Phases of Compilation
Evolution of programming languages, major programming paradigms, why are there so many PLs? What makes a PL successful? Compilation vs. interpretation: tradeoff, fuzzy boundary; Phases of compilation
 
T1 Th Jan 10Perl Tutorial (10:00-11:30am, T.Lab 2)  
T1 Fr Jan 11Perl Tutorial (10:30am-12:00, T.Lab 2)  
  Part I: Lexical Analysis and Automata Theory
3 Fr Jan 11Regular Languages
Phases of compilation, front end and back end of a compiler, a sample Pascal program: lexical analysis, syntactic and semantic analysis; Part I: Lexical analysis and automata theory, basic notions in formal language theory, regular languages Reading: [PLP] Ch.2
A0 due, A1 out
4 Mo Jan 14Regular Expressions
Regular expressions: operator predence, examples, applications; practical regular expressions: character classes, anchors, back references, shortest match, regular expressions in Perl
 
5 We Jan 16Deterministic and Non-deterministic Automata (DFA, NFA)
History of regular expressions, implementation; DFA - Deterministic Finite Automaton: idea, examples, formal definition; NFA - Non-deterministic Finite Automaton, examples, formal definition, example of conversion NFA to DFA
 
6 Fr Jan 18RegEx-DFA-NFA Equivalence
NFA conversion to DFA, examples, RegEx conversion to NFA, example
A1 due, A2 out
7 Mo Jan 21Automata-to-RegEx Transformation
NFA-to-RegEx Conversion, example with all words from [01]* except those that contain 11 or 101, general algorithm; why 0^n1&n is not a regular language, Pumping Lemma for regular languages
 
8 We Jan 23Properties of Regular Languages
Pumping lemma for regular languages, proof sketch; closure properties of regular languages; Scanner generators; DFA minimization, examples; scanner implementation
 
T2 Th Jan 24Scheme Tutorial (10:00-11:30am, T.Lab 2)  
T2 Fr Jan 25Scheme Tutorial (10:30am-12:00, T.Lab 2)  
  Part II: Syntactic Analysis
9 Fr Jan 25Scanning, Context-Free Grammars
Scanner implementation, extensions to DFA model, scanningexample - Pascal, Part II: Syntactic Analysis and Context-FreeGrammars; Context-Free Grammars (CFG): examples, formal definition,notational variations, derivation, sentential form, parse tree
A2 due, A3 out
10 Mo Jan 28CFGs for Programming Languages
Parse tree examples, CFL - Context-Free Languages, examples of Context-Free Languages, Regular Languages and CF Languages, example grammar for arithmetic expressions, ambiguity, leftmost and rightmost derivations, grammars for programming languages
 
11 We Jan 30LL and LR Parsing
A better expression grammar, regular grammars, LL(k) and LR(k) grammars, LL parsing, example; LR parsing, example; S-Grammar, examples
 
  Fr Feb 1Munro Day (University closed)  
12 Mo Feb 4 LL(1) Grammars
LL grammars, LL predictors, examples; LL(1) grammars, verifying that a grammar is LL(1), FIRST(X): definition, algorithm, example; FOLLOW(X): definition, algorithm, example
A3 due
13 We Feb 6 LL(1) Grammars, 2nd part
Veryfing that a grammar is LL(1), continued: PREDICT(A\rightarrow\alpha): definition, algorithm, example; Some facts about LL(1) grammars, Converting a grammar to LL(1): left recursion, common prefix; example
 
  Fr Feb 8XML (reading)
XML (eXtensible Markup Language): an application of CFGs, introduction, examples, DTD, defining elements, attributes, entities
 
14 Mo Feb 11Recursive Descent Parsing
XML, handout, overview; Parsing LL(1) grammars: recursive descent and PDA; Recursive descent parsing, example; LL(1) parsing usind PDA; Pushdown automata (PDA): introduction, definition, language recognition
 
  Part III: Semantic Analysis; Names, Scopes and Bindings
15 We Feb 13PDAs, Semantic Analysis
PDA recognition by empty stack and final states, example; Some PDA properties, DCFLs, example; Parsing LL(1) grammars using DPDA, implementation; Semantic Analysis: role of semantic analysis, static and dynamic semantic rules, attribute grammars Reading: [PLP] Ch.4
 
16 Fr Feb 15Attribute Flow
Attribute grammar examples; Synthesize and inherited attributes; Parse tree decoration: examples; Attribute flow: S-attributed and L-attributed grammars; example
A4 due
17 Mo Feb 18Names, Scopes and Bindings
Action routines, XML and DTDs as an application of CFGs (reminder note); Names, scopes and bindings; Binding times, object and binding lifetime; Storage allocation: static, stack, and heap; C++ case example; static objects; stack-based allocation Reading: [PLP] Ch.3
 
18 We Feb 20Stack and Heap Management
Stack Frame (Activation Record): stack pointer and frame pointer, typical sequence in stack maintenance, typical contents of stack frame, C99 example; Heap-based allocation: first-fit and best-fit allocation, heap fragmentation problem
 
19 Fr Feb 22Midterm Review  
  Feb 25-29Study break  
  Mo Mar 3Midterm Exam (3:30pm - 5:30pm, Auditorium, CS bldg. 127) Midterm
20 We Mar 5Lexical and Dynamic Scoping
Buddy Fibonacci heaps; Deallocation in a heap; lexical and dynamic scoping: example, Perl example; Deep and shallow binding (or fun-arg problem)
 
21 Fr Mar 7Modules
Deep and shallow binding examples; notion of subroutine closure, lexical scoping in Pascal, static chains; Modules and information hiding, static variables in C: examples
 
22 Mo Mar 10Scoping in Scheme
Modules in Modula-2 and -3, open and closed scopes; constructs similar to modules, module types and classes; example: Perl packages; Scoping in Scheme: let, let* and letrec, referencing environments (frames), procedure objects in Scheme, using frames for storing state and information hiding in Scheme Reading: SICP 3.2
 
  Part IV: Control Flow
23 We Mar 12Control Flow
Aliasing and overloading; Aliasing examples: union in C, FORTRAN, Pascal; pointers, references in C++; keyword "restrict" in C99; aliasing in C++, Perl; overloading and operator overloading; Part VI: Control Flow (Ch.6), expression evaluation, assignment, l-values and r-values, returning an l-value from a function Reading: PPL ch.6
A5 due
T3 Fr Mar 14Prolog Tutorial (10:30am-12:00, T.Lab 2)  
24 Fr Mar 14Short-Circuit Operators, Branching
Reference and value model of variables, evaluation order in expressions, short-circuit evaluation, Goto and alternatives; Selection: if-then-elsif-else, switch (case); Iteration: enumeration and logically controlled
 
25 Mo Mar 17Iterators and Generators, Recursion
Logically controlled loops; Iterators and generators: motivation, Clue and Icon examples, iterators in C, Java, and C++, Python iterators and generators; Recursion: tail-recursion, examples
 
26 We Mar 19Subroutines and Control Abstraction
Applicative and normal order of evaluation, lazy evaluation in Scheme, delay and force, C macros; Subroutines and control abstraction (ch.8), basic definitions, functions calls, static and dynamic chains, in-line functions, parameter passing modes: by-value, by-reference, by-sharing, by-result, parameter passing examples in different languages Reading: PLP ch.8
A6 due
(written
part)
T3 Th Mar 20Prolog Tutorial (10:00-11:30am, T.Lab 2)  
  Fr Mar 21Good Friday (University closed)  
27 Mo Mar 24Exceptions and Continuations
Parameter passing modes: example - Java and C#, Read-only parameters: uses of keywrod const in C++, Default parameters and named parameters, Exception handling: Java and C++ examples; continuations in Scheme
 
  Part V: Lambda Calculus
28 We Mar 26Lambda Calculus
Variable number of arguments in C and C++; Call/cc: Example 3, setjmp/longjmp mechanism in C; Lambda Calculus: lambda expressions, interpretation, free and bound variables, computing in lambda calculus
A6 due
(prog-
ramm
ing)
29 Fr Mar 28Control Flow in Lambda Calculus
Precedence in lambda expressions, evaluation, variable naming and re-naming, labels (meta-variables), examples; Logic and control flow in lambda calculus, examples; Building data structures
A7 due
30 Mo Mar 31Recursion in Lambda Calculus
Curry-ing, looping in lambda calculus -- recursion: Y combinator, building recursive functions, example with factorial functions, terminating reductions, normal vs. applicative order of evaluation, Church-Rosser theorem
 
  Part VI: Data Types and Object-Oriented Programming
31 We Apr 2Pointers and Garbage Collection
Type system; strongly, statically, and dynamically typed languages; Classification of typpes; associative arrays: Perl and Scheme examples (C++ and Java); pointers: syntax, preventing dangling references: tombstones and locks and keys; garbage collection: reference counts Reading: PLP ch.7
 
32 Fr Apr 4Principles of Object-Oriented Programming
Garbage collection: mark-and-sweep method, stop-and-copy method, generational technique; Object-oriented programming: advantages, some OO langauges, inheritance, visibility: C++ rules, Java, Dynamic method binding
A8 due
33 Mo Apr 7Inheritance and Polymorphism
Dynamic method binding, virtual methods, abstract methods and abstract classes, implementation of virtual methods, dynamic cast; Polymorphism
 
34 We Apr 9Overview of Type Casting in C++
Course evaluation; Overview of type casting in C++: Implicit conversions (also static_cast), class-type conversions (to-class and from-class); Explicit conversions: static_cast, dynamic_cast, const_cast, reinterpret_cast, old-style casts: (type) expr and type(expr), old style: try static_cast or const_cast, otherwise reinterpret_cast
 
  Fr Apr 11A9 due A9 due
  Mo Apr 14Final Exam (2pm-5pm, DalArena) Exam schedule Final

© 2003-2008 Vlado Keselj, last update: 13-May-2008