Verification of the C0 compiler implementation on the source code level
Petrova, Elena · Publications of the UdS (Saarland University) · 2007
This thesis concerns practical application of two methods for program verification. The programming language we consider is a C dialect, called C0, which supports dynamic memory allocation, recursion, pointer types, etc. First, we verify a program using a formalization of small-step semantics of C0. The example we study is a small loop program, which allocates a linked list of the given length on the heap. Second, we describe the verification of a compiler implementation in a Hoare Logic in the sense of partial correctness. The source and implementation language of the compiler is C0. The correctness statement is divided into independent parts: i) the correctness of the compilation algorithm with respect to the target machine and ii) the correctness of the implementation with respect to the specified algorithm. This thesis considers the second task. We give the formal specification of the compilation algorithm and develop the connection of the implementation data structures to the abstract types used in the specification. Finally, we show the correctness of the compiler implementation with respect to the specification.