| |
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.
|
| 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
|
| Grammars |
- 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
|
- 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
|