Formal Syntax and Semantics of Programming Languages - Kenneth Slonneger.pdf

(1654 KB) Pobierz
Formal Syntax
and
Semantics of
Programming Languages
A Laboratory Based Approach
Kenneth Slonneger
University of Iowa
Barry L. Kurtz
Louisiana Tech University
Addison-Wesley Publishing Company
Reading, Massachusetts • Menlo Park, California • New York • Don Mills, Ontario
Wokingham, England • Amsterdam • Bonn •
Sydney • Singapor
e
Tokyo • Madrid • San Juan • Milan • Paris
Senior Acquisitions Editor:
Tom Stone
Assistant Editor:
Kathleen Billus
Production Coordinator:
Marybeth Mooney
Cover Designer:
Diana C. Coe
Manufacturing Coordinator:
Evelyn Beaton
The procedures and applications presented in this book have been included
for their instructional value. They have been tested with care but are not
guaranteed for any particular purpose. The publisher does not offer any war-
ranties or representations, nor does it accept any liabilities with respect to
the programs or applications.
Library of Congr ess Cataloging-in-Publication Data
Slonneger, Kenneth.
Formal syntax and semantics of programming languages: a laboratory
based approach / Kenneth Slonneger, Barry L. Kurtz.
p.cm.
Includes bibliographical references and index.
ISBN 0-201-65697-3
1.Pr ogramming languages (Electronic computers)--Syntax.
2.Pr ogramming languages (Electronic computers)--Semantics.
I. Kurtz, Barry L. II. Title.
QA76.7.S59 1995
005.13'1--dc20
94-4203
CIP
Reproduced by Addison-Wesley from camera-ready copy supplied by the
authors.
Copyright © 1995 by Addison-Wesley Publishing Company, Inc.
All rights reserved. No part of this publication may be reproduced, stored in
a retrieval system, or transmitted, in any form or by any means, electronic,
mechanical, photocopying, recording, or otherwise, without the prior written
permission of the publisher. Printed in the United States of America.
ISBN 0-201-65697-3
1234 5 6 7 8 9 10-MA-979695
Dedications
To my father, Robert
Barry L. Kurtz
To Marybeth and my family
Ken Slonneger
Preface
This text developed out of our experiences teaching courses covering the
formal semantics of programming languages. Independently we both devel-
oped laboratory exercises implementing small programming languages in
Prolog following denotational definitions. Prolog proved to be an excellent
tool for illustrating the formal semantics of programming languages. We
found that these laboratory exercises were highly successful in motivating
students since the hands-on experience helped demystify the study of for-
mal semantics. At a professional meeting we became aware of each other’s
experiences with a laboratory approach to semantics, and this book evolved
from that conference.
Although this text has been carefully written so that the laboratory activities
can be omitted without loss of continuity, we hope that most readers will try
the laboratory approach and experience the same success that we have ob-
served in our classes.
Overall Goals
We have pursued a broad spectrum of definitional techniques, illustrated
with numerous examples. Although the specification methods are formal,
the presentation is “gentle”, providing just enough in the way of mathemati-
cal underpinnings to produce an understanding of the metalanguages. We
hope to supply enough coverage of mathematics and formal methods to jus-
tify the definitional techniques, but the text is accessible to students with a
basic grounding in discrete mathematics as presented to undergraduate
computer science students.
There has been a tendency in the area of formal semantics to create cryptic,
overly concise semantic definitions that intimidate students new to the study
of programming languages. The emphasis in this text is on clear notational
conventions with the goals of readability and understandability foremost in
our minds.
As with other textbooks in this field, we introduce the basic concepts using
mini-languages that are rich enough to illustrate the fundamental concepts,
yet sparse enough to avoid being overwhelming. We have named our mini-
languages after birds.
v
vi
PREFACE
Wren
is a simple imperative language with two types, integer and Bool-
ean, thus allowing for context-sensitive type and declaration checking. It
has assignment, if, while, and input/output commands.
Pelican,
a block-structured, imperative language, is an extension of Wren
containing the declaration of constants, anonymous blocks, procedures,
and recursive definitions.
The description of continuations in denotational semantics requires a modi-
fied version of Wren with goto statements, which we call
Gull.
This mini-
language can be skipped without loss of continuity if continuations are not
covered.
Organization of the Text
The primary target readership of our text is first-year graduate students,
although by careful selection of materials it is also accessible to advanced
undergraduate students. The text contains more material than can be cov-
ered in a one semester course. We have provided a wide variety of tech-
niques so that instructors may choose materials to suit the particular needs
of their students.
Dependencies between chapters are indicated in the graph below. We have
purposely attempted to minimize mutual interdependencies and to make
our presentation as broad as possible.
1
2
3
4
5
6
8
9
11
12
7
8
10
13
Only sections 2 and 3 of Chapter 8 depend on Chapter 5. The text contains
a laboratory component that we describe in more detail in a moment. How-
ever, materials have been carefully organized so that no components of the
non-laboratory sections of the text are dependent on any laboratory activi-

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin