Program Analysis: Practise
- If you have questions and problems, please ask them in the forum!
What you have to do
Implementing a program analysis consists of several steps. We will tackle these steps one after another.
Defining an abstract syntax
As a first step we need to consider for which language we are going to write a program analysis. To go along with the lecture, we will take for now the WHILE language as defined in Nielson&Nielson, p. 3 ff.
- Taking the language of your choice, install the software you will need and download the provided stubs.
- Extend the parser with the operations ! (not) and or (|) for boolean expressions, and the relations <= and >=.
- Add unique labels to the AST.
- Write a pretty printer for the AST.
Haskell solution for this part available!
Java solution for this part available!
Data flow for Available Expressions Analysis
Now, we have to generate the information we need to setup and solve the data flow equations.
- Extract the flow graph for a given program. Implement the methods init,final,labels,blocks,flow as specified on the slides or in the book.
- Implement a method allAExps which computes all arithmetic expressions for a given program.
- Implement a method fv which extracts all free variables for a given arithmetic expression.
- Define the kill and gen functions for the Available Expressions Analysis.
To solve the data flow equations, we can iterate over the initialized data sets.
- Implement the (generic) worklist algorithm from the lecture (cf. Nielson &Nielson, p.75).
- Combine it with the data flow equations for the Available Expressions Analysis.
- Test your code with suitable examples.
- Official homepage for Haskell
- General introduction is given in Programming in Haskell von Graham Hutton (available in our library)
- Comprehensive source with lots of interesting stuff and good examples is Real World Haskell Bryan O'Sullivan, Don Stewart und John Goerzen