Formal Syntax
and
Semantics of
Programming Languages
A Laboratory Based Approach
Addison-Wesley Publishing Company
Reading, Massachusetts • Menlo Park, California • New York • Don Mills, Ontario
Wokingham, England • Amsterdam • Bonn • Sydney • Singapore
Tokyo • Madrid • San Juan • Milan • Paris
Kenneth Slonneger
University of Iowa
Barry L. Kurtz
Louisiana Tech University
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.
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
12345678910-MA-979695
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
Dedications
To my father, Robert
Barry L. Kurtz
To Marybeth and my family
Ken Slonneger
xi
Contents
Chapter 1
SPECIFYING SYNTAX 1
1.1 GRAMMARS AND BNF 2
Context-Free Grammars 4
Context-Sensitive Grammars 8
Exercises 8
1.2 THE PROGRAMMING LANGUAGE WREN 10
Ambiguity 12
Context Constraints in Wren 13
Semantic Errors in Wren 15
Exercises 16
1.3 VARIANTS OF BNF 18
Exercises 20
1.4 ABSTRACT SYNTAX 21
Abstract Syntax Trees 21
Abstract Syntax of a Programming Language 23
Exercises 29
1.5 FURTHER READING 30
Chapter 2
INTRODUCTION TO LABORATORY ACTIVITIES 31
2.1 SCANNING 33
Exercises 39
2.2 LOGIC GRAMMARS 40
Motivating Logic Grammars 41
Improving the Parser 44
Prolog Grammar Rules 46
Parameters in Grammars 47
Executing Goals in a Logic Grammar 49
Exercises 49
2.3 PARSING WREN 50
Handling Left Recursion 52
Left Factoring 55
Exercises 56
2.4 FURTHER READING 57
Chapter 3
ATTRIBUTE GRAMMARS 59
3.1 CONCEPTS AND EXAMPLES 59
Examples of Attribute Grammars 60
Formal Definitions 66
xii CONTENTS
Semantics via Attribute Grammars 67
Exercises 71
3.2 AN ATTRIBUTE GRAMMAR FOR WREN 74
The Symbol Table 74
Commands 80
Expressions 82
Exercises 90
3.3 LABORATORY: CONTEXT CHECKING WREN 92
Declarations 96
Commands 99
Expressions 101
Exercises 102
3.4 FURTHER READING 103
Chapter 4
TWO-LEVEL GRAMMARS 105
4.1 CONCEPTS AND EXAMPLES 105
Fortran String Literals 111
Derivation Trees 113
Exercises 115
4.2 A TWO-LEVEL GRAMMAR FOR WREN 116
Declarations 117
Commands and Expressions 124
Exercises 132
4.3 TWO-LEVEL GRAMMARS AND PROLOG 132
Implementing Two-Level Grammars in Prolog 133
Two-Level Grammars and Logic Programming 136
Exercises 138
4.4 FURTHER READING 138
Chapter 5
THE LAMBDA CALCULUS 139
5.1 CONCEPTS AND EXAMPLES 140
Syntax of the Lambda Calculus 140
Curried Functions 143
Semantics of Lambda Expressions 145
Exercises 146
5.2 LAMBDA REDUCTION 147
Reduction Strategies 151
Correlation with Parameter Passing 155
Constants in the Pure Lambda Calculus 156
Functional Programming Languages 158
Exercises 158
5.3 LABORATORY: A LAMBDA CALCULUS EVALUATOR 160
Scanner and Parser 160
The Lambda Calculus Evaluator 162
Exercises 165
