Calendar Description: General principles and techniques for disciplined low-level software design. BNF and basic theory of grammars and parsing. Use of parser generators. Basics of language and protocol design. Formal languages. State-transition and table-based software design. Formal methods for software construction. Techniques for handling concurrency and inter-process communication. Tools for model-driven construction. Introduction to Middleware. Hot-spot analysis and performance tuning. - Prerequisite: SEG-2105, CSI-2110

Time table: Lectures : Tuesday 14:30 - 16:00 and Friday 16:00 - 17:30; TUT/LAB : (Group 1) Monday 17:30 - 20:30, (Group 2) Tuesday 19:00 - 22:00 (see also Course Timetable at UofO)

General themes: The general theme of the course is the construction of software by using high-level specification formalisms and corresponding CASE tools. More specifically, the main subjects covered are:

• Design of real-time systems using an approach of concurrent processes defined by state transition models; methods of verification and implementation; use of specialized CASE tools for this purpose.
• Definition of computer languages and interaction protocols by grammars and automata; design and implementation of lexical and syntatic analysers; use of specialized CASE tools for this purpose.
• Design, verification and implementation of programs with concurrency and synchronization problems, in the context of languages like UML State Machines and Java; performance experiments and simulations.

Learning objectives

The following list contains learning objectives for each chapter of the course. Each objective is preceeded by references to the "graduate attribute" to which they belong. These graduate attributes are explained in Section 3.1 of the CEAB Accreditation Criteria and Procedures (the attributes covered in this course are: (1) A knowledge base for engineering, (2) Problem analysis, (3) Investigation, (4) Design, (5) Use of engineering tools, (6) Individual and team work, and (7) Communication skills). In addition, at the end of each objective, there is an indication of the labs and assignments which are intended to help you attain the objective. The course includes 10 Lab sessions, including three "formal" labs for which a report should be prepared, and the students will have four assignments.

Section 1: Requirement engineering, structural and behavioral modeling using state machines

• Introduction to requirements modeling
  • (1-Knowledge) - revision of knowledge from course SEG-2105
  • (2-Analysis; 4-Design; 5-Tools) To construct a domain model for a given development project. (Lab-1; Assignment 1)
• Behavioral modeling using state machines
  • (1-Knowledge) To understand modeling concepts of UML State Machines and Activity Diagrams, including hierarchical states and (independent) concurrency; real-time modeling with timers
  • (2-Analysis; 4-Design; 5-Tools) To construct a state machine that models the behavior of a system satisfying given requirements (Lab-1; Lab-3; Assignment 1)
• Communicating state machine
  • (1-Knowledge) To understand the concepts of interleaving concurrency, reachability analysis, state machines communicating by rendezvous or by message passing, and non-deterministic system behavior
  • (2-Analysis; 4-Design; 5-Tools) To design systems with communicating state machines, analysing the behavior of such systems, possibly using tools (Lab-1; Lab-4)

Section 2: Languages, grammars, and analyzers

• Introduction
  • (1-Knowledge) To understand the basic concepts of language definition and the purpose of lexical analysis, syntax analysis and semantic analysis of sentences or programs.
• Lexical analysis
  • (1-Knowledge) To understand the concepts of formal languages, language definition by regular expressions or "acceptor" state machines (so-called Finite State Automata), non-deterministic state machines and equivalent deterministic ones, systematic implementation methods of lexical analysers (Lab-5).
  • (4-Design) To find a regular expression, or a Finite State Automaton, that defines a language that satisfies certain given requirements. (Lab-5; Assignment 2)
  • (2-Analysis; 5-Tools) To demonstrate the derivation of a deterministic automaton that defines the same language as a given regular expression. (Lab-6; Assignment 2)
  • (2-Analysis; 4-Design; 5-Tools) To build a lexical analyser for a language defined by a given regular expression, by direct programming or using an automated tool. (Lab-5; Assignment 2, Assignment 3)
• Syntax analysis
  • (1-Knowledge) To understand the following concepts: syntax tree, language definition by a context-free grammar, (deterministic) top-down syntax analysis, LL(1) conditions, methods for constructing syntax analysers, semantic attributes, and the complexity of language recognition problems.
  • (4-Design) To find a grammar that defines a language that satisfies certain given requirements. (Lab-6; Lab-7, Assignment 3)
  • (2-Analysis) For a given grammar, identify ambiguity, generated sentences and syntax trees (Lab-6)
  • (2-Analysis; 5-Tools) To check whether a given grammar allows for LL(1) syntax analysis; if not, derive an equivalent grammar that does. (Lab-7, Assignment 3)
  • (2-Analysis; 4-Design; 5-Tools) To build an LL(1) syntax analyser for a language that satisfies certain given requirements; use semantic attributes for realizing certain semantic properties (Assignment 3)

Section 3: Concurrency: specification, verification, and implementation

• Concurrency
  • (1-Knowledge) To understand concepts of concurrency, such as logical and physical concurrency, process scheduling, mutual exclusion for access to shared resources and communication between concurrent processes.
  • (1-Knowledge) To understand how concurrency is supported by the Java programming language.
  • (2-Analysis; 5-Tools; 4-Design) To design, verify and implement applications with concurrency to solve real problems. (Lab-9)
• Performance issues
  • (2-Analysis; 3-Investigation; 4-Design) Identify performance issues in a given system implementation; suggest alternative designs to solve these issues. (Lab-11)
  • (2-Analysis; 5-Tools; 4-Design) Study the performance properties of a projected system design through simulations. (Lab-10; Assignment 4)

Other leaning objectives

During the Lab sessions and for the assignments, the students will normally work in groups of two people. In this context, their work will address (to some extend) the following grauduate attributes:

• (6) Individual and team work
• (7) Communication skills

Student evaluation

• Assignments 24%
• Labs 16% (3 "formal" labs counting 4% , 3% and 3% , the other ("informal") labs counting 1% each)
• Midterm Exam: 20%
• Final Exam 40%
• Notes:
  • According to a standard rule at EECS, the marks for the assignments and labs will not be taken into account if the average for the exams is below 50%. (For this purpose, the average will be calculated with the following weights: 40% for the mid-term exam, and 60% for the final exam). - revision as of Jan. 26

Textbooks (there is not one book covering all aspects of this course)

• Required readings
  • Course notes
  • Extracts from certain books that will be on sale in the McDonalds building.
    • [Booch] chapters 21 - 25
    • Scanning [Louden, chapt.2] (suggested reading)
    • Syntax Analysis I [Parson, chapt. 3] (suggested reading)
    • Concurrency [Sebesta, part of chapt. 13]
• Recommended textbooks (for most books, only a few chapters are used for this course)
  • [Booch] G. Booch, J. Rumbaugh and I. Jacobson, The Unified Modeling Language User Guide (Second Edition), Addison-Wesley, 2005.
  • [Braek] R. Braek and O. Haugen, Engineering Real Time Systems - An object-oriented methodology using SDL, Prentice Hall, 1993, ISBN: 0-13-034448-6 (out of print). Extracts are included in printouts distributed in 2010 - you can find them in the reserve at the Library.
  • [Louden] K.C. Louden, Compiler Construction - Principles and Practices, PWS Publishing, 1997
  • [Parson] T. W. Parson, Introduction to Compiler Construction, Computer Science Press, 1992
  • [Aho] A. V. Aho, R. Sethi and J. D. Ullman, Compilers, Principles, Techniques and Tools, Addison
    Wesley, 1986, ISBN: 0-201-10088-6
  • [Sebesta] R.W.Sebesta, Concepts of Programming Languages, 5th ed., Addison-Wesley, 2002, ISBN: 0-201-75295-6. (Note: only a few chapters from this book will be used in this course)
• Other textbooks
  • T. Pittman and J. Peters, The Art of Compiler Design, Prentice hall, 1992, ISBN: 0-13-
    048190-4
  • John R. Levine, Tony Mason & Doug Brown, lex & yacc, O'Reilly & Associates, 1995, Unix
    Programming Tools Series. ISBN 1-56592-000-

Class policies

• Assignments and Labs can be prepared in groups of maximum two students.
• Late assignments or lab reports are accepted for a maximum of 24 hours and they will receive a 30% penalty.
• Plagiarism is a serious academic offence that will not be tolerated. 
  • Note that the person providing solutions to be copied is also committing an offence as they are an active participant in the plagiarism. 
  • The person copying and the person copied from will be reprimanded equally according to the regulations set by the University of Ottawa. 
  • Please refer to the link for more information: www.uottawa.ca/academic/info/regist/crs/0305/home_5_ENG.htm.
• Class attendance is mandatory. As per academic regulations, students who do not attend 80% of the class will not be allowed to write the final examinations.
  • All components of the course (i.e laboratory reports, assignments, etc.) must be fulfilled otherwise students may receive an INC as a final mark (equivalent to an F).
  • Absence from a laboratory session or an examination because of illness will be excused only if you provide a certificate from Health Services (100 Marie Curie, 3rd Floor) within the week following your absence.