Summer 2013 (May6-Aug2)
Faculty of Computer Science
Dalhousie University
|
|
[ http://web.cs.dal.ca/~islam/3136/coursecalendar.htm ]
Summer 2013 (May6-Aug2) Faculty of Computer Science Dalhousie University |
| # | Date | Title | |
|---|---|---|---|
| Introduction | |||
| 1 | Mon May 6 | Course Introduction
Reading: [PLP] Ch.1
History of programming languages Evolution of programming languages, major programming paradigms, why are there so many PLs? What makes a PL successful? Files: PDF slides (handout), PDF slides (presentation). |
T.starts |
| 2 | Wed May 8 | Overview of Implementation
Compilation vs. interpretation: tradeoff; Phases of compilation Files: PDF slides (handout), PDF slides (presentation). | |
| Part I: Lexical Analysis and Automata Theory | |||
| 3 | Mon May 13 | Regular Expressions
Part I: Lexical analysis and automata theory, basic notions in formal language theory, regular languages, regular expressions: operator predence, examples, applications; Files: PDF slides (handout), PDF slides (presentation) . Reading: [PLP] Ch.2 | |
| 4 | Wed May 15 | Deterministic and Non-deterministic Automata (DFA, NFA)
DFA - Deterministic Finite Automaton: idea, examples, formal definition; NFA - Non-deterministic Finite Automaton, examples, formal definition. Files: PDF slides (handout), PDF slides (presentation). Assignment 0 : PDF. | A0 out |
| Mon May 20 | Victoria Day, University closed | ||
| 5 | Wed May 22 | RegEx-DFA-NFA Equivalence
Overview of scanner generation; RegEx to NFA, examples, NFA DFA equivalency, NFA conversion to DFA, examples. | |
| T1 | Fri May 24 | Tutorial (12:05-13:25, CS Lab 3) (by TA)
Perl tutorial - 1 | |
| 6 | Mon May 27 | Properties of Regular Languages
DFA minimization, examples; Properties of regular languages; Pumping lemma for regular languages, proof sketch; | A1 out |
| Part II: Syntactic Analysis and Context-Free Grammars | |||
| 7 | Wed May 29 | Context-Free Grammars
Scanner implementation, scanning example; Part II: Syntax Analysis and Context-Free Grammars; Context-Free Grammars (CFG): examples, formal definition, Regular Languages and CF Languages, notational variations, derivation, sentential form | |
| T2 | Fri May 31 | Tutorial (12:05-13:25, CS Lab 3) (by TA)
Perl tutorial - 2 | |
| 8 | Mon June 3 | CFL and Parse tree
Parse tree, Parse tree examples, CFL - Context-Free Languages, examples of Regular Languages and CF Languages, example grammar for arithmetic expressions, ambiguity. | |
| 9 | Wed June 5 | CFGs for Programming Languages
Leftmost and rightmost derivations, grammars for programming languages, examples, A better expression grammar, regular grammars, LL(k) and LR(k) grammars, LL parsing and LR parsing, examples; S-Grammar, examples; LL(1) grammars, FIRST(X): definition, algorithm, examples; | |
| 10 | Mon June 10 | LL(1) Grammar
FOLLOW(X): definition, algorithm, examples; PREDICT: definition, algorithm, examples; | |
| 11 | Wed June 12 | LL(1) Parsing
Some facts about LL(1) grammars, Converting a grammar to LL(1): left recursion, common prefix; LL predictors ; Parser construction for LL(1) grammars. Recursive descent and PDA; Recursive descent parsing ; LL(1) parsing usind PDA; Introduction to Deterministic Pushdown automata(DPDA) | |
| 12 | Mon June 17 | LL(1) Parsing
Push-Down Automata: Formal Definition, Graph Representation of PDA, Computation in a PDA, How does a PDA Accept? Introduction to Deterministic Pushdown automata(DPDA), LL(1) parsing usind DPDA; | |
| Wed June 19 | Midterm Test from 12:05 to 13:25 at Computer Science 127 | ||
| Part III: Semantic Analysis; Names, Scopes and Bindings | |||
| 13 | Mon June 24 | Names, Scopes and Bindings
Names, scopes and bindings; binding times, object and binding lifetime; Storage allocaton: static, stack and heap; static objects; stack-based allocation. | |
| 14 | Wed June 26 | Lexical Scoping
Scopes, Lexical or static scope; Lexical scoping in Scheme; examples; Lexical scoping in Pascal; example; Implementation of lexical scoping: Static Chains. | |
| Mon July 1 | In lieu of Canada Day - University closed | ||
| 15 | Wed July 3 | Dynamic Scoping; Deep and shollow binding Aliasing and Overloading
Algorithms to determine Static Scope; Dynamic Scope; Static and Dynamic Scope in Perl; in Pascal ; Algorithm to determine the dynamic scope; Deep and shollow binding; examples; Modules, Classes; Aliasing and Overloading. | |
| Part IV: Control Flow | |||
| 16 | Mon July 8 | Contro Flow
Control Flow, expression evaluation, assignment, l-values and r-values, returning an l-value from a function Reference and value model of variables, evaluation order in expression. | |
| 17 | Wed July 10 | Short-Circuit Operators, Branching
short-circuit evaluation, Goto and alternatives; Selection: if-then-elsif-else, switch (case); Iteration: enumeration and logically controlled loops; Recursion, implementation of recursion; tail-recursion, example in C, example in Scheme. | |
| Part V: Data Types | |||
| 19 | Mon July 15 | Data Types
**Lecture Class would be at Room 226, Chemistry building ** Type system; Type equivalence, compatibility and inference; Examples in various languages; Type definition; Classification of Types; array types, pointers; examples; Problem of dangling references and garbage collection. | |
| Part VI: Subroutines and control abstractions | |||
| 20 | Wed July 17 | Subroutines and control abstractions
**Lecture Class would be at Room 226, Chemistry building ** 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; Paramether passing modes; Examples in Java and C#; Readonly parameters; Default and Named parameters. | |
| Part VII: Object-oriented programming | |||
| 21 | Mon July 22 | Object-oriented programming
Object-oriented programming, Advantages; Class example in C++, Inheritance, Syntax of inhertance, Overriding methods, Encapsulation, Visibility in C++, Altering visibility in derived classes, Constructors, Constructor and method overloading; Static and dynamic method binding; Implementation of virtual methods. | |
| 22 | Wed July 24 | Functional programming 1 | |
| 23 | Mon July 29 | Functional programming 2 | |
| 24 | Wed July 31 | Final Review | |
| TBA | Final Exam | Final | |