Data, Syntax and Semantics



This is the web site for the book  Data, Syntax and Semantics  by J V Tucker and K Stephenson.


J V Tucker is Professor of Computer Science at the University of Wales Swansea.  K Stephenson is Senior Scientist at QinetiQ. She is also an Honorary Lecturer in Computer Science at the University of Wales Swansea.


At present the book is in preparation, as are these web pages.  If you would like to read a draft of the book please contact one of us at:


J V Tucker

Department of Computer Science

University of Wales Swansea

Singleton Park

Swansea SA2 8PP

United Kingdom


K Stephenson


St Andrews Road

Malvern WR14 3PS

United Kingdom or



About the book




Data, syntax and semantics can be found everywhere in Computer Science.  Each is now an independent subject with an interesting and useful  theory, and advanced practical techniques and tools. Each has many applications in the design of languages for specifying,  implementing and reasoning about software. Their origins lie in mathematical logic, where the foundations of reasoning were analysed using mathematical models such as logics and idealised machines. However, the subjects have been transformed and moulded in tackling problems in the technologies of programming. In Computer Science,  they find their most important applications in the creation of programming and specification languages.


This book provides an elementary introduction to these three fundamental theoretical subjects through the study of models for the design of programming and specification languages. In addition to educating students in the three theories and their applications,  and laying foundations for advanced study and research, the book it  aims, more generally,  to



The book begins by reflecting on our understanding of data and programming languages.   In the first chapter a range of questions about languages are posed that clearly require a major scientific investigation. The  theories of data, syntax and semantics are developed in order to answer them.


An imperative language is based on the idea that a

Program = Data + Store + Algorithm.

We  describe informally a simple language called the language of   

while programs over abstract data types.

This language captures the essential ideas about imperative programming and acts as a kernel language for extensions to richer languages.


After a historical account of the development of data, syntax, and semantics, in Chapter 2, we divide the work into three parts:



This is an introduction to modelling data using algebras. It covers simple examples, interfaces,  axiomatic specifications, advanced examples, comparing algebras using homomorphisms, and ends with a full treatment of the real numbers.



This is an introduction to modelling rules for defining all sorts of syntax using grammars, especially context free grammars.  It begins with a wide range of case studies,  from URLs to programming and interface definition languages. Standard results about normal forms, pumping lemmas, etc., are used to chart  the scope and limits of the context-free grammars. It ends with a study of abstract syntax using term models.



This is an introduction to modelling the behaviour of programs using operations on states. The while language over abstract data types is studied in detail.  Structural induction is introduced and extensively applied. Computation on real numbers is discussed. A virtual machine is also introduced. It ends with a study of compilation.


Each part starts with elementary material and increases gently in difficulty to a  final chapter that contains material that is more advanced.




Readers must know the elements of (i) programming  and (ii) discrete mathematics and logic.


The book is designed for undergraduate students in the second year of their study.  Depending upon the curricula, it may be better suited for third year students, in courses that progress quickly through the elementary chapters.


The chapters from the different parts can be mixed together to provide a full study of an imperative language. However, the three parts enable the book to be used for independent accounts of data, syntax, and semantics for students of different years and different levels.




Support for teaching and learning the subject




A selection of overheads in a pdf form can be downloaded here.

Student projects


A selection of ideas for final year student projects that are based on the material in the book are listed here.





An important part of the education of all computer scientists should be a clear understanding of some truly basic concepts that shape the whole field. Data, syntax and semantics certainly are among those subjects. In addition the theoretical education we desire will enable the  students

All of these general aims are difficult to achieve...


Computer Science is in its infancy,  Today's students would do well to reflect on the changes in the subject and in the working careers of people in their sixties. Students need an education that prepares them for such life of technical change and volatility. Students need to master theoretical concepts and ideas, and be comfortable dealing with abstractions, idealisations, and precision in their thinking.



Swansea experiences


The Swansea education in Computer Science has been guided by nine general Educational Aims. The subject of the book serves the needs to several of these aims.


The book has grown from lectures on programming languages at the University of Wales Swansea given by both authors. All the text has been "class tested", even the advanced chapters, but at different levels.


The primary course from which it has developed is the Theory of Programming Languages. This is a compulsory course for second year students, normally taught in the first term of the academic year. The advanced chapters have been used in other courses including Algebraic Specification of Software and Hardware.


The philosophy, the choice of material, the exposition in the text, and the suggested projects have proved to be practical and, in our opinion, successful in the education of computer scientists.



 About the book    Support for teaching  Swansea experiences  Philosophy


Top of Page