Uni-Logo

Program Analysis: Practise

General Information

  • 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.
    • For Haskell, download parser.tar and follow the instructions in the readme. (Alternatively, you can use Parsec which has a parser for the WHILE language shipped with.)
    • For Java, download DataFlowAnalysis.jar and use SableCC to generate scanner,parser, AST and standard visitors.
  • 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.

Worklist Algorithm

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.

Haskell

General information:

Java

General information: