SEG-2106 "Software Construction"

What are the main themes of this course ?

From syllabus: 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 subjets covered are:

  1. 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.
  2. 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.
  3. 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

Main themes: "Construction" means "Methods" and "Automated tools"

This table shows the main issues:

  Concepts + Practice Methods Tools (in bold what we have used for practical exercises in the course)
State machines
  • Modeling notations
    • Labeled transition systems
    • FSM (Mealy and Moore versions)
    • Extended models, e.g. UML notation
  • Building state machine models
  • state machine implementation strategies
  • V&V at the model level (using model simulation )
  • UML editing tools
  • Code generation for structural aspects
  • Code generation for behavioral aspects
    • Model simulation (using UML tools)
    • Generation of implementation code (for local and distributed environments)
  • Model checking tools for verification of properties
Concurrent state machines
  • Difficulty of understanding concurrent systems
  • Analysing concurrent systems
  • Reachability analysis (for understanding global behavior)
  • Design flaws: deadlocks, non-specified message reception
  • Reachability analysis tools, e.g.
    • LTSA
    • Spin
    • Uppaal
Regular expressions
  • "String calculus" : Formal languages
  • Regular expressions
  • Non-deterministic automata
  • Finding regular expressions for certain applications
  • Conversion between regular expressions, non-deterministic automata and deterministic accepting automata
  • implementation of deterministic automata
  • Automatic generation of code representing accepting automaton for a given regular expression
    • LEX tool (or similar)
    • Java regular expression package
    • Unix (Linux) regular expression routines
  • Two-level language definition (lexical and syntactic)
  • Parsing and syntax trees
  • Ambiguity
  • Semantic attributes
  • Finding grammars for certain applications
  • LL(1) syntax analysis
    • checking LL(1) property
    • parsing algorithm using parsing table
    • recursive descent parsing
  • correspondance: recursive data types (trees) vs. grammars
    • node attributes vs. semantic attributes
  • There are tools that generate parsing routines for different types of grammars (possibly including facilities for semantic attributes)
    • for LL(1) grammars
    • for LR(1) grammars, e.g. YACC
    • and others
Concurrency and resource sharing
  • programming concepts:
    • threads
    • mutual exclusion
    • semaphores
    • programming "monitors"
  • Queuing models
  • Programming exercises
  • applying concepts to practical examples
  • performance measurements and error estimation
  • two approaches to writing simulation programs
    • with threads for active objects modeled
    • sequential program with future event list
Distributed processing infrastructure
  • encoding of data structures for transmission as messages
  • Concept of remote procedure calls
  • XML encoding
  • data structure definitions (similarity and differences)
    • UML Class diagrams
    • Java data structures
    • XML tree structure definitions
      • DTD
      • XML Schema
  • XML programming support frameworks
    • automatic code generation (from given XML structure definition) of corresponding Java data structures, Java coding and decoding routines including checking the conformance with the XML data structure definition); also for other programming languages

Created: April 1, 2011; updated Dec. 2012