[ http://www.cs.dal.ca/~vlado/csci3136/coursecalendar.html ]
Winter 2008 (Jan7-Apr9) Faculty of Computer Science Dalhousie University |
# | Date | Title | |
---|---|---|---|
Introduction | |||
1 | Mo Jan 7 | Course 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 9 | Phases 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 10 | Perl Tutorial (10:00-11:30am, T.Lab 2) | |
T1 | Fr Jan 11 | Perl Tutorial (10:30am-12:00, T.Lab 2) | |
Part I: Lexical Analysis and Automata Theory | |||
3 | Fr Jan 11 | Regular 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 14 | Regular Expressions
Regular expressions: operator predence, examples, applications; practical regular expressions: character classes, anchors, back references, shortest match, regular expressions in Perl | |
5 | We Jan 16 | Deterministic 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 18 | RegEx-DFA-NFA Equivalence
NFA conversion to DFA, examples, RegEx conversion to NFA, example | A1 due, A2 out |
7 | Mo Jan 21 | Automata-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 23 | Properties 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 24 | Scheme Tutorial (10:00-11:30am, T.Lab 2) | |
T2 | Fr Jan 25 | Scheme Tutorial (10:30am-12:00, T.Lab 2) | |
Part II: Syntactic Analysis | |||
9 | Fr Jan 25 | Scanning, 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 28 | CFGs 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 30 | LL 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 1 | Munro 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 8 | XML (reading)
XML (eXtensible Markup Language): an application of CFGs, introduction, examples, DTD, defining elements, attributes, entities | ||
14 | Mo Feb 11 | Recursive 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 13 | PDAs, 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 15 | Attribute 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 18 | Names, 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 20 | Stack 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 22 | Midterm Review | |
Feb 25-29 | Study break | ||
Mo Mar 3 | Midterm Exam (3:30pm - 5:30pm, Auditorium, CS bldg. 127) | Midterm | |
20 | We Mar 5 | Lexical 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 7 | Modules
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 10 | Scoping 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 12 | Control 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 14 | Prolog Tutorial (10:30am-12:00, T.Lab 2) | |
24 | Fr Mar 14 | Short-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 17 | Iterators 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 19 | Subroutines 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 20 | Prolog Tutorial (10:00-11:30am, T.Lab 2) | |
Fr Mar 21 | Good Friday (University closed) | ||
27 | Mo Mar 24 | Exceptions 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 26 | Lambda 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 28 | Control 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 31 | Recursion 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 2 | Pointers 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 4 | Principles 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 7 | Inheritance and Polymorphism
Dynamic method binding, virtual methods, abstract methods and abstract classes, implementation of virtual methods, dynamic cast; Polymorphism | |
34 | We Apr 9 | Overview 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 11 | A9 due | A9 due | |
Mo Apr 14 | Final Exam (2pm-5pm, DalArena) Exam schedule | Final |