Thèse de Docteur Ingénieur en Informatique, Université Joseph Fourier, Grenoble, France, 14 Décembre 1974.
Ch. I (definition of programming languages) introduces the idea that a formal definition of a programming language semantics can be used to derive a correct implementation. Ch. II (Transformational definition) proposes to formally define the syntax as trees and the semantics by tree transformers. Ch. III (evaluation schemata) introduces tree traversal algorihms to recursively apply the tree transformations. Ch. IV (simple examples of language definitions) includes the formal definition of Backus's reducible languages, LISP, and a comparison with Knuth's attribute grammars. Ch. V proposed an implementation method by a tree automaton using stacks to traverse the trees and a heap to allocate data. Ch. VI is the formal definition of Wirth & Weber's language Euler. Ch. VII is on typing for Algol 68-like languages. Ch. VIII studies the problem of mapping the programming language data structures into abstract trees in the formal definition which introduces inefficiencies when deriving implementations as interpreters. The proposed answer is a manual semantic analysis of the language formal definition to transform it into an efficient implementation. Ch. IX (minimalisation of a language definition) proposes automatic optimizations of the language definition including the elimination of inapplicable and useless transformations, exhaustive enumeration, and pre-evaluation. Ch. X is the commented bibliography.
programming language, operational semantics, tree automata, tree traversal, semantic definition analysis, semantic definition transformation, language implementation.
\bibitem{Cousot74-1-TheseDI}
P. Cousot.
\newblock D{\'e}\-fi\-ni\-tion in\-ter\-pr{\'e}\-ta\-ti\-ve et im\-plan\-ta\-tion de
lan\-gua\-ges de pro\-gram\-ma\-tion (in {F}rench).
\newblock Th{\`e}\-se de Doc\-teur In\-g{\'e}\-nieur en In\-for\-ma\-ti\-que,
Uni\-ver\-si\-t{\'e} Jo\-seph Fou\-r\-ier, Gre\-no\-ble,
Fran\-ce, 14 December 1974.
@phdThesis{Cousot74-1-TheseDI,
author = {Cousot, P{.}},
title = {D{\'e}\-fi\-ni\-tion in\-ter\-pr{\'e}\-ta\-ti\-ve et im\-plan\-ta\-tion
de lan\-gua\-ges de pro\-gram\-ma\-tion (in {F}rench)},
type = {Th{\`e}\-se de Doc\-teur In\-g{\'e}\-nieur en In\-for\-ma\-ti\-que},
school = {Uni\-ver\-si\-t{\'e} Jo\-seph Fou\-r\-ier},
address = {Gre\-no\-ble, Fran\-ce},
month = {14 December},
year = 1974,
}