Understanding and Writing Compilers

Understanding

and Writing

Compilers

A do-it-yourself guide

Richard Bornat

Middlesex University, London.

richard@bornat.me.uk

First published—1979.

Internet edition—2007.

Original edition published by Macmillan Press Ltd., Basingstoke, UK.

Internet edition published by Richard Bornat, 28 Albany Road, LONDON N4

4RL, UK. richard@bornat.me.uk

Preface to the online

edition

I wrote this book on compiling in the late 1970s. It was a success. I still meet

people who learnt about compiling from it. I get three or four requests a year

from people who’d like a copy. I used to tell them to use Abebooks.com, but

now there aren’t any copies even there. Since I own the copyright (thanks to

Macmillan), I can publish it again, for free.

otherwise tried to change as little as possible.

Why isn’t it in C?

When I began to write this book I was heavily into BCPL. By the time it was

finished I was a C programmer. The display editor ded that I developed to write

the book was written in C. C is in many respects a direct descendant of BCPL.

I was pressed, even before the book came out, to rewrite all the examples in C.

I didn’t do that for various reasons, some good and some bad. It would be an

enormous effort to do it now, because C is now so far from its origins.

Old-fashioned opinions

I agree with quite a lot of this book, but by no means all of it. I’ve decided to

Preface

of the computing public, whether it was once deserved or not, is no longer

merited now that the principles of programming-language implementation are

so well understood. Compiler-writing is no longer a mystery.

This book attempts to explain and demystify the principles of compiler writing

so that you can go out and build a working compiler of your own. There is

enough detail in this book for you to build a compiler for quite a complicated

language – certainly PASCAL, perhaps ALGOL 68 or SIMULA 67 – but it

doesn’t attempt an encyclopaedic coverage of the field. It is intended more as an

introduction to compiler-writing and a do-it-yourself kit for the compiler-writer,

giving enough detail for you to understand the principles of the subject, than as

than is perhaps usual to the topic of parsing or syntax analysis and the discussion

of translation is totally oriented to tree-walking. I have presented the subject

in this way for both practical and educational reasons. First, the object code

instruction sequences which implement run-time support are more important

in practice than is usually recognised. It is differences in run-time mechanisms,

as much as or more than anything else, which distinguish one language from

another – say SIMULA 67 from ALGOL 68, POP-2 from ALGOL 60 – and

the efficiency of run-time support code fragments is crucial to the efficiency of

the object program. Second, I believe it is more important to give a practical

description of syntax analysis in a book which is intended for the practical

compiler-writer than to give a more formal and complete introduction to the

topic. The syntax analysis mechanisms chosen for illustration in section IV] are

selected for their practical relevance. Of the three mechanisms presented, the