184x Filetype PDF File size 3.23 MB Source: www.cs.ecu.edu
Concepts of Programming Languages: AUnified Approach Karl Abrahamson August 2011 2 Copyright (c) 2011 Karl Abrahamson. Contents I Fundamental Concepts 17 1 Introduction to Programming Languages 19 2 Language Classification 21 2.1 Imperative programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2 Declarative programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.3 Language classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.4 Summary of terminology and concepts . . . . . . . . . . . . . . . . . . . . . 24 2.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.6 Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3 Encapsulation and Information Hiding 27 3.1 Encapsulation and modification . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.2 Some kinds of encapsulations . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.3 Intension and extension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.4 Language support . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.5 Summary of terminology and concepts . . . . . . . . . . . . . . . . . . . . . 29 3.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4 Implementation of Programming Languages 31 4.1 Compilers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.2 Linkers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.3 Interpreters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.4 Comparison of compilers and interpreters . . . . . . . . . . . . . . . . . . . 33 4.5 Hybrid implementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.6 Libraries and run-time support . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.7 Languages are not their implementations . . . . . . . . . . . . . . . . . . . . 35 4.8 Summary of terminology and concepts . . . . . . . . . . . . . . . . . . . . . 37 4.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.10 Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 II Syntax and Semantics 41 5 Form and Function 43 5.1 The syntax of a language . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 5.2 Form suggests function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3 4 CONTENTS 5.3 Summary of terminology and concepts . . . . . . . . . . . . . . . . . . . . . 45 5.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 5.5 Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 6 Describing Syntax and Structure 47 6.1 Describing the syntax of a language . . . . . . . . . . . . . . . . . . . . . . . 47 6.2 Lexical rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 6.3 Program structure and parse trees . . . . . . . . . . . . . . . . . . . . . . . 49 6.4 Using grammars to indicate allowed trees . . . . . . . . . . . . . . . . . . . 51 6.5 Commongrammatical forms . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 6.6 Ambiguity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 6.7 Syntax is not meaning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 6.8 Extended BNF notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 6.9 Syntax diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 6.10 Summary of terminology and concepts . . . . . . . . . . . . . . . . . . . . . 59 6.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 6.12 Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 7 Semantics 63 7.1 Introduction to semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 7.2 Operational semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 7.3 Denotational semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 7.4 Axiomatic semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 7.5 Partial semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 7.6 Relational semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 7.7 Semantic black holes and infinite loops . . . . . . . . . . . . . . . . . . . . . 65 7.8 Resource limitations and semantics . . . . . . . . . . . . . . . . . . . . . . . 66 7.9 Summary of terminology and concepts . . . . . . . . . . . . . . . . . . . . . 66 7.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 7.11 Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 III Managing Information 69 8 Data and Data Representation 71 8.1 Programs and data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 8.2 Simple values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 8.3 Tuples and records . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 8.4 Lists and arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 8.5 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 8.6 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 8.7 Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 8.8 Tags and tagged values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 8.9 First class data items . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 8.10 Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 8.11 Persistent and ephemeral data . . . . . . . . . . . . . . . . . . . . . . . . . . 81 8.12 Summary of terminology and concepts . . . . . . . . . . . . . . . . . . . . . 82 8.13 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
no reviews yet
Please Login to review.