Instructor’s Solutions Manual

to

Concepts of Programming Languages
Tenth Edition R.W. Sebesta

©2013 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

Preface
Changes for the Tenth Edition

T

he goals, overall structure, and approach of this tenth edition of Concepts of Programming Languages remain the same as those of the nine earlier editions. The principal goals are to introduce the main constructs of contemporary programming languages and to provide the reader with the tools necessary for the critical evaluation of existing and future programming languages. A secondary goal is to prepare the reader for the study of compiler design, by providing an indepth discussion of programming language structures, presenting a formal method of describing syntax and introducing approaches to lexical and syntatic analysis. The tenth edition evolved from the ninth through several different kinds of changes. To maintain the currency of the material, some of the discussion of older programming languages has been removed. For example, the description of COBOL’s record operations was removed from Chapter 6 and that of Fortran’s Do statement was removed from Chapter 8. Likewise, the description of Ada’s generic subprograms was removed from Chapter 9 and the discussion of Ada’s asynchronous message passing was removed from Chapter 13. On the other hand, a section on closures, a section on calling subprograms indirectly, and a section on generic functions in F# were added to Chapter 9; sections on Objective-C were added to Chapters 11 and 12; a section on concurrency in functional programming languages was added to Chapter 13; a section on C# event handling was added to Chapter 14;. a section on F# and a section on support for functional programming in primarily imperative languages were added to Chapter 15. In some cases, material has been moved. For example, several different discussions of constructs in functional programming languages were moved from Chapter 15 to earlier chapters. Among these were the descriptions of the control statements in functional programming languages to Chapter 8 and the lists and list operations of Scheme and ML to Chapter 6. These moves indicate a significant shift in the

©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

philosophy of the book—in a sense, the mainstreaming of some of the constructs of functional programming languages. In previous editions, all discussions of functional programming language constructs were segregated in Chapter 15. Chapters 11, 12, and 15 were substantially revised, with five figures being added to Chapter 12. Finally, numerous minor changes were made to a large number of sections of the book, primarily to improve clarity.

The Vision
This book describes the fundamental concepts of programming languages by discussing the design issues of the various language constructs, examining the design choices for these constructs in some of the most common languages, and critically comparing design alternatives. Any serious study of programming languages requires an examination of some related topics, among which are formal methods of describing the syntax and semantics of programming languages, which are covered in Chapter 3. Also, implementation techniques for various language constructs must be considered: Lexical and syntax analysis are discussed in Chapter 4, and implementation of subprogram linkage is covered in Chapter 10. Implementation of some other language constructs is discussed in various other parts of the book. The following paragraphs outline the contents of the ninth edition.

Chapter Outlines
Chapter 1 begins with a rationale for studying programming languages. It then discusses the criteria used for evaluating programming languages and language constructs. The primary influences on language design, common design trade-offs, and the basic approaches to implementation are also examined. Chapter 2 outlines the evolution of most of the important languages discussed in this book. Although no language is described completely, the origins, purposes, and contributions of each are discussed. This historical overview is valuable, because it provides the background necessary to understanding the practical and theoretical basis for contemporary language design. It also motivates further study of language design and evaluation. In addition, because none of the remainder of the book depends on Chapter 2, it can be read on its own, independent of the other chapters. Chapter 3 describes the primary formal method for describing the syntax of programming language—BNF. This is followed by a description of attribute grammars, which describe both the syntax and static semantics of languages. The difficult task of semantic description is
©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

then explored, including brief introductions to the three most common methods: operational, denotational, and axiomatic semantics. Chapter 4 introduces lexical and syntax analysis. This chapter is targeted to those colleges that no longer require a compiler design course in their curricula. Like Chapter 2, this chapter stands alone and can be read independently of the rest of the book. Chapters 5 through 14 describe in detail the design issues for the primary constructs of programming languages. In each case, the design choices for several example languages are presented and evaluated. Specifically, Chapter 5 covers the many characteristics of variables, Chapter 6 covers data types, and Chapter 7 explains expressions and assignment statements. Chapter 8 describes control statements, and Chapters 9 and 10 discuss subprograms and their implementation. Chapter 11 examines data abstraction facilities. Chapter 12 provides an in-depth discussion of language features that support object-oriented programming (inheritance and dynamic method binding), Chapter 13 discusses concurrent program units, and Chapter 14 is about exception handling, along with a brief discussion of event handling. The last two chapters (15 and 16) describe two of the most important alternative programming paradigms: functional programming and logic programming. However, some of the data structures and control constructs of functional programming languages are discussed in Chapters 6 and 8. Chapter 15 presents an introduction to Scheme, including descriptions of some of its primitive functions, special forms, and functional forms, as well as some examples of simple functions written in Scheme. Brief introductions to ML, Haskell, and F# are given to illustrate some different directions in functional language design. Chapter 16 introduces logic programming and the logic programming language, Prolog.

To the Instructor
In the junior-level programming language course at the University of Colorado at Colorado Springs, the book is used as follows: We typically cover Chapters 1 and 3 in detail, and though students find it interesting and beneficial reading, Chapter 2 receives little lecture time due to its lack of hard technical content. Because no material in subsequent chapters depends on Chapter 2, as noted earlier, it can be skipped entirely, and because we require a course in compiler design, Chapter 4 is not covered. Chapters 5 through 9 should be relatively easy for students with extensive programming experience in C++, Java, or C#. Chapters 10 through 14 are more challenging and require more detailed lectures. Chapters 15 and 16 are entirely new to most students at the junior level. Ideally, language processors for Scheme and Prolog should be available for students required to learn the material in these chapters.
©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

Sufficient material is included to allow students to dabble with some simple programs. Undergraduate courses will probably not be able to cover all of the material in the last two chapters. Graduate courses, however, should be able to completely discuss the material in those chapters by skipping over parts of the early chapters on imperative languages.

Supplemental Materials
The following supplements are available to all readers of this book at www.pearsoninternationaleditions.com/sebesta. • • A set of lecture note slides. PowerPoint slides are available for each chapter in the book. PowerPoint slides containing all the figures in the book.

To reinforce learning in the classroom, to assist with the hands-on lab component of this course, and/or to facilitate students in a distancelearning situation, access the companion Web site at www.pearsoninternationaleditions.com/sebesta. This site contains minimanuals (approximately 100-page tutorials) on a handful of languages. These proceed on the assumption that the student knows how to program in some other language, giving the student enough information to complete the chapter materials in each language. Currently the site includes manuals for C++, C, Java, and Smalltalk. Solutions to many of the problem sets are available to qualified instructors in our Instructor Resource Center at www.pearsoninternationaleditions.com/sebesta. Please contact your school’s Pearson Education representative.

Language Processor Availability
Processors for and information about some of the programming languages discussed in this book can be found at the following Web sites: C, C++, Fortran, and Ada C# and F# Java Haskell Lua Scheme Perl Python Ruby gcc.gnu.org microsoft.com java.sun.com haskell.org www.lua.org www.pltscheme.org/software/drscheme www.perl.com www.python.org www.ruby-lang.org

©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

JavaScript is included in virtually all browsers; PHP is included in virtually all Web servers. All this information is also included on the companion Web site.

©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

Acknowledgments
The suggestions from outstanding reviewers contributed greatly to this book’s present form. In alphabetical order, they are: DePaul University University of Colorado Virginia Tech Southern University–Baton Rouge Georgia State University Louisiana State University California State University– Northridge Mark Llewellyn University of Central Florida Bruce R. Maxim University of Michigan–Dearborn Gloria Melara California State University– Northridge Frank J. Mitropoulos Nova Southeastern University Euripides Montagne University of Central Florida Bob Neufeld Wichita State University Amar Raheja California State Polytechnic University–Pomona Hossein Saiedian University of Kansas Neelam Soundarajan Ohio State University Paul Tymann Rochester Institute of Technology Cristian Videira Lopes University of California–Irvine Salih Yurttas Texas A&M University Numerous other people provided input for the previous editions of Concepts of Programming Languages at various stages of its development. All of their comments were useful and greatly appreciated. In alphabetical order, they are: Vicki Allan, Henry Bauer, Carter Bays, Manuel E. Bermudez, Peter Brouwer, Margaret Burnett, Paosheng Chang, Liang Cheng, John Crenshaw, Charles Dana, Barbara Ann Griem, Mary Lou Haag, John V. Harrison, Eileen Head, Ralph C. Hilzer, Eric Joanis, Leon Jololian, Hikyoo Koh, Jiang B. Liu, Meiliu Lu, Jon Mauney, Robert McCoard, Dennis L. Mumaugh, Michael G. Murphy, Andrew Oldroyd, Young Park, Rebecca Parsons, Steve J. Phelps, Jeffery Popyack, Raghvinder Sangwan, Steven Rapkin, Hamilton Richard, Tom Sager, Joseph Schell, Sibylle Schupp, Mary Louise Soffa, Neelam Soundarajan, Ryan Stansifer, Steve Stevenson, Virginia Teller, Yang Wang, John M. Weiss, Franck Xia, and Salih Yurnas. Matt Goldstein, editor; Chelsea Bell, editorial assistant; and Meredith Gertz, senior production supervisor of Addison-Wesley, and Gillian Hall of The Aardvark Group Publishing Services, all deserve my gratitude for their efforts to produce the tenth edition both quickly and carefully.
©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

I-ping Chu Amer Diwan Stephen Edwards Nigel Gwee K. N. King Donald Kraft Simon H. Lin

About the Author
Robert Sebesta is an Associate Professor Emeritus in the Computer Science Department at the University of Colorado–Colorado Springs. Professor Sebesta received a BS in applied mathematics from the University of Colorado in Boulder and MS and PhD degrees in computer science from Pennsylvania State University. He has taught computer science for more than 38 years. His professional interests are the design and evaluation of programming languages.

©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

Contents
Chapter 1 Preliminaries
1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 Reasons for Studying Concepts of Programming Languages Programming Domains Language Evaluation Criteria Influences on Language Design Language Categories Language Design Trade-Offs Implementation Methods Programming Environments

Summary • Review Questions • Problem Set

Chapter 2

Evolution of the Major Programming Languages
2.1 2.2 2.3 2.4 2.5 2.6 2.7 Zuse’s Plankalkül Minimal Hardware Programming: Pseudocodes The IBM 704 and Fortran Functional Programming: LISP The First Step Toward Sophistication: ALGOL 60 ............................................ Computerizing Business Records: COBOL ....................................................... The Beginnings of Timesharing: BASIC ............................................................

Interview: Alan Cooper—User Design and Language Design ........................................................................................................... 2.8 2.9 2.10 2.11 2.12 Everything for Everybody: PL/I .......................................................................... Two Early Dynamic Languages: APL and SNOBOL ......................................... The Beginnings of Data Abstraction: SIMULA 67 ............................................. Orthogonal Design: ALGOL 68 ......................................................................... Some Early Descendants of the ALGOLs .........................................................

©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

2.13 2.14 2.15 2.16 2.17 2.18 2.19 2.20

Programming Based on Logic: Prolog .............................................................. History’s Largest Design Effort: Ada ................................................................. Object-Oriented Programming: Smalltalk ......................................................... Combining Imperative and Object-Oriented Features: C++ .............................. An Imperative-Based Object-Oriented Language: Java ................................... Scripting Languages The Flagship .NET Language: C# .................................................................... Markup/Programming Hybrid Languages ..........................................................

Summary • Bibliographic Notes • Review Questions • Problem Set • Programming Exercises...................................................................................................

Chapter 3

Describing Syntax and Semantics ..................................................................
3.1 3.2 3.3 3.4 3.5 Introduction ....................................................................................................... The General Problem of Describing Syntax ...................................................... Formal Methods of Describing Syntax .............................................................. Attribute Grammars ...........................................................................................
History Note

Describing the Meanings of Programs: Dynamic Semantics ............................
History Note .........................................................................................

Summary • Bibliographic Notes • Review Questions • Problem Set .................... ...........

Chapter 4

Lexical and Syntax Analysis............................................................................
4.1 4.2 4.3 4.4 4.5 Introduction ....................................................................................................... Lexical Analysis ................................................................................................ The Parsing Problem ........................................................................................ Recursive-Descent Parsing .............................................................................. Bottom-Up Parsing ............................................................................................

Summary • Review Questions • Problem Set •Programming Exercises..........................

Chapter 5

Names, Bindings, and Scopes.........................................................................
5.1 5.2 Introduction ....................................................................................................... Names ...............................................................................................................
History Note ......................................................................................... History Note .........................................................................................

©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

5.3 5.4

Variables ...........................................................................................................
History Note

........................................................................................

The Concept of Binding .....................................................................................

Interview: Rasmus Lerdorf—Scripting Languages and Other Examples of Slick Solutions......................................................................................................................... 5.5 5.6 5.7 5.8 Scope .................................................................................................................
History Note

........................................................................................

Scope and Lifetime ............................................................................................ Referencing Environments ................................................................................ Named Constants .............................................................................................

Summary • Review Questions • Problem Set • Programming Exercises .........................

Chapter 6

Data Types.........................................................................................................
6.1 6.2 6.3 6.4 6.5 Introduction ........................................................................................................ Primitive Data Types ......................................................................................... Character String Types .....................................................................................
History Note

........................................................................................

User-Defined Ordinal Types .............................................................................. Array Types .......................................................................................................
History Note History Note

........................................................................................ ........................................................................................

6.6

Associative Arrays .............................................................................................

Interview: ROBERTO IERUSALIMSCHY—Lua............................................................ 6.7 6.8 6.9 6.10 6.11 6.12 6.13 6.14 6.15 Record Types .................................................................................................... Tuple Types List Types Union Types ...................................................................................................... Pointer Types
History Note

........................................................................................

Type Checking .................................................................................................. Strong Typing .................................................................................................... Type Equivalence .............................................................................................. Theory and Data Types .....................................................................................

©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

Summary • Bibliographic Notes • Review Questions • Problem Set • Programming Exercises............................................................................

Chapter 7

Expressions and Assignment Statements......................................................
7.1 7.2 7.3 7.4 7.5 7.6 7.7 7.8 Introduction ....................................................................................................... Arithmetic Expressions ..................................................................................... Overloaded Operators ...................................................................................... Type Conversions .............................................................................................
History Note .........................................................................................

Relational and Boolean Expressions ................................................................
History Note .........................................................................................

Short-Circuit Evaluation .................................................................................... Assignment Statements ....................................................................................
History Note .........................................................................................

Mixed-Mode Assignment ...................................................................................

Summary • Review Questions • Problem Set • Programming Exercises.........................

Chapter 8

Statement-Level Control Structures................................................................
8.1 8.2 Introduction ....................................................................................................... Selection Statements ........................................................................................
History Note ......................................................................................... History Note .........................................................................................

8.3

Iterative Statements ..........................................................................................
History Note .........................................................................................

Interview: Larry Wall—Part 1: Linguistics and the Birth of Perl..............................................................................................................................
History Note ........................................................................................................................................

8.4 8.5 8.6

Unconditional Branching ................................................................................... Guarded Commands ......................................................................................... Conclusions ......................................................................................................

Summary • Review Questions • Problem Set • Programming Exercises.........................

©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

Chapter 9

Subprograms .....................................................................................................
9.1 9.2 9.3 9.4 9.5 Introduction ........................................................................................................ Fundamentals of Subprograms ......................................................................... Design Issues for Subprograms ........................................................................ Local Referencing Environments ...................................................................... Parameter-Passing Methods ............................................................................

Interview: Larry Wall—Part 2: Scripting Languages in General and Perl in Particular .....................................................................................................
History Note ........................................................................................................................................ History Note ........................................................................................ History Note ........................................................................................

9.6 9.7 9.8 9.9 9.10 9.11 9.12 9.13

Parameters That Are Subprograms ..................................................................
History Note ........................................................................................

Calling Subprograms Indirectly Overloaded Subprograms ................................................................................. Generic Subprograms ....................................................................................... Design Issues for Functions .............................................................................. User-Defined Overloaded Operators ................................................................. Closures Coroutines .........................................................................................................
History Note ........................................................................................

Summary • Review Questions • Problem Set • Programming Exercises .........................

Chapter 10

Implementing Subprograms .............................................................................
10.1 10.2 10.3 10.4 The General Semantics of Calls and Returns ................................................... Implementing “Simple” Subprograms ................................................................ Implementing Subprograms with Stack-Dynamic Local Variables................................................................................................... Nested Subprograms ........................................................................................

Interview: Niklaus Wirth—Keeping It Simple.............................................................. 10.5 10.6 Blocks ................................................................................................................ Implementing Dynamic Scoping ........................................................................

Summary • Review Questions • Problem Set • Programming Exercises ........................

Chapter 11

Abstract Data Types and Encapsulation Constructs .....................................
11.1 11.2 11.3 11.4 The Concept of Abstraction ............................................................................... Introduction to Data Abstraction ........................................................................ Design Issues for Abstract Data Types ............................................................. Language Examples ..........................................................................................

©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

Interview: Bjarne Stroustrup—C++: Its Birth, Its Ubiquitousness, and Common Criticisms ................................................................... 11.5 11.6 11.7 Parameterized Abstract Data Types ................................................................. Encapsulation Constructs .................................................................................. Naming Encapsulations .....................................................................................

Summary • Review Questions • Problem Set • Programming Exercises .........................

Chapter 12

Support for Object-Oriented Programming.....................................................
12.1 12.2 12.3 12.4 12.5 Introduction ........................................................................................................ Object-Oriented Programming .......................................................................... Design Issues for Object-Oriented Languages ................................................. Support for Object-Oriented Programming in Smalltalk .................................... Support for Object-Oriented Programming in C++ ............................................

Interview: Bjarne Stroustrup—On Paradigms and Better Programming....................................................................................................... 12.6 12.7 12.8 12.9 12.10 12.11 Support for Object-Oriented Programming in Objective-C ................................ Support for Object-Oriented Programming in Java Support for Object-Oriented Programming in C# .............................................. Support for Object-Oriented Programming in Ada 95 ....................................... Support for Object-Oriented Programming in Ruby ........................................... Implementation of Object-Oriented Constructs .................................................

Summary • Review Questions • Problem Set • Programming Exercises .........................

Chapter 13

Concurrency ......................................................................................................
13.1 13.2 13.3 13.4 13.5 13.6 13.7 13.8 13.9 13.10 Introduction ........................................................................................................ Introduction to Subprogram-Level Concurrency ................................................
History Note ........................................................................................

Semaphores ...................................................................................................... Monitors ............................................................................................................. Message Passing .............................................................................................. Ada Support for Concurrency ............................................................................ Java Threads ..................................................................................................... C# Threads ........................................................................................................ Concurrency in Functional Programming Languages Statement-Level Concurrency ...........................................................................

Summary • Bibliographic Notes • Review Questions • Problem Set • Programming Exercises ...................................................................................................

Chapter 14

Exception Handling and Event Handling.........................................................
14.1 Introduction to Exception Handling .................................................................... 2

©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

History Note ........................................................................................

14.2 14.3 14.4

Exception Handling in Ada ................................................................................ Exception Handling in C++ ................................................................................ Exception Handling in Java ...............................................................................

Interview: James Gosling—The Birth of Java ............................................................ 14.5 14.6 14.7 Introduction to Event Handling .......................................................................... Event Handling with Java .................................................................................. Event Handling with C# .....................................................................................

Summary • Bibliographic Notes • Review Questions • Problem Set • Programming Exercises........ ...........................................................................................

Chapter 15

Functional Programming Languages ..............................................................
15.1 15.2 15.3 15.4 15.5 15.6 15.7 15.8 15.9 15.10 15.11 Introduction ........................................................................................................ Mathematical Functions .................................................................................... Fundamentals of Functional Programming Languages ..................................... The First Functional Programming Language: LISP ......................................... An Introduction to Scheme ................................................................................ COMMON LISP ................................................................................................. ML ..................................................................................................................... Haskell ............................................................................................................... F# ...................................................................................................................... Support for Functional Programming in Primarily Imperative Languages ......... A Comparison of Functional and Imperative Languages ..................................

Summary • Bibliographic Notes • Review Questions • Problem Set • Programming Exercises ...................................................................................................

Chapter 16

Logic Programming Languages.......................................................................
16.1 16.2 16.3 16.4 16.5 16.6 16.7 16.8 Introduction ........................................................................................................ A Brief Introduction to Predicate Calculus ......................................................... Predicate Calculus and Proving Theorems ....................................................... An Overview of Logic Programming .................................................................. The Origins of Prolog ........................................................................................ The Basic Elements of Prolog ........................................................................... Deficiencies of Prolog ........................................................................................ Applications of Logic Programming ..................................................................

Summary • Bibliographic Notes • Review Questions • Problem Set • Programming Exercises ...................................................................................................

Bibliography ....................... ...............................................................................

3
©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

Index ......................... ..........................................................................................

4
©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

Answers to Selected Problems
Chapter 1 Problem Set: 3. Lack of standards; the programmer is required to know multiple programming languages, and so on. 4. Typically, the scientific applications of that time used relatively simple data structures but required large numbers of floating-point arithmetic computations. Business languages are characterized by facilities for producing elaborate reports, precise ways of describing and storing decimal numbers and character data, and the ability to specify decimal arithmetic operations. 5. Artificial intelligence (AI) is a broad area of computer applications characterized by the use of symbolic rather than numeric computations. Symbolic computation means that symbols consisting of names, rather than numbers, are manipulated. Also, symbolic computation is more conveniently performed with linked lists of data rather than arrays. This kind of programming sometimes requires more flexibility than other programming domains. The World Wide Web is supported by an eclectic collection of languages, ranging from markup languages, such as HTML, which is not a programming language, to general-purpose programming languages, such as Java. Because of the pervasive need for dynamic Web content, some computation capability is often included in the technology of content presentation. This functionality can be provided by embedding programming code in an HTML document. 7. The argument for using the semicolon to close all statements is simplicity—a semicolon always terminates a statement. The argument against it is that you require a semicolon for every statement or it can create a compilation error. 8. Functions and subroutines are used for modularity and reusability. They require highlevel design. 10. In earlier times, the cost of hardware was relatively higher than that of software, but currently, it would be right to say the cost of software is relatively higher. 15. C, C++ use preprocessor directives. Java doesn’t use preprocessor directives. 18. At the time of installation of a compiler or an interpreter, the software recognizes different processor architecture properties.

5
©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

Chapter 2 Problem Set: 6. (a) Semicolon (;) missing. (b) Unmatched parentheses. (c) Function prototype mismatch. (d) Undeclared variables. 7. The main reason why imperative features were put in LISP was to increase its execution efficiency. 10. The most important new developments were the following: • The concept of block structure was introduced. This allowed the programmer to localize parts of programs by introducing new data environments, or scopes. Two different means of passing parameters to subprograms were allowed: pass by value and pass by name. Procedures were allowed to be recursive. The ALGOL 58 description was unclear on this issue. Note that although this recursion was new for the imperative languages, LISP had already provided recursive functions in 1959. Stack-dynamic arrays were allowed. A stack-dynamic array is one for which the subscript range or ranges are specified by variables, so that the size of the array is set at the time storage is allocated to the array, which happens when the declaration is reached during execution. Stack-dynamic arrays are described in detail in Chapter 6, “Data Types.”

• •

•

11. IBM was, for the most part, incorrect in its view of the future of the uses of computers, at least as far as languages are concerned. Commercial applications are nearly all done in languages that are specifically designed for them. Likewise for scientific applications. On the other hand, the IBM design of the 360 line of computers was a great success—it still dominates the area of computers between supercomputers and minicomputers. Furthermore, 360 series computers and their descendants have been widely used for both scientific and commercial applications. These applications have been done, in large part, in Fortran and COBOL. 14. The argument for typeless languages is their great flexibility for the programmer. Literally any storage location can be used to store any type value. This is useful for very low-level languages used for systems programming. The drawback is that type checking is impossible, so that it is entirely the programmer's responsibility to insure that expressions and assignments are correct.

6
©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

18. A good deal of restraint must be used in revising programming languages. The greatest danger is that the revision process will continually add new features, so that the language grows more and more complex. Compounding the problem is the reluctance, because of existing software, to remove obsolete features. 22. One situation in which pure interpretation is acceptable for scripting languages is when the amount of computation is small, for which the processing time will be negligible. Another situation is when the amount of computation is relatively small and it is done in an interactive environment, where the processor is often idle because of the slow speed of human interactions. 24. New scripting languages may appear more frequently than new compiled languages because they are often smaller and simpler and focused on more narrow applications, which means their libraries need not be nearly as large.

Chapter 3 Instructor's Note: In the program proof on page 180, there is a statement that may not be clear to all, specifically, (n + 1)* … * n = 1. The justification of this statement is as follows: Consider the following expression:
(count + 1) * (count + 2) * … * n

The former expression states that when count is equal to n, the value of the later expression is 1. Multiply the later expression by the quotient:
(1 * 2 * … * count) / (1 * 2 * … * count)

whose value is 1, to get
(1 * 2 * … * count * (count + 1) * (count + 2) * … * n) / (1 * 2 * … * count)

The numerator of this expressions is n!. The denominator is count!. If count is equal to n, the value of the quotient is n! / n!

or 1, which is what we were trying to show.

7
©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

Problem Set: 2a. → {} class [extends class_name] [implements {, }] → public | abstract | final 2c. → switch ( ) {case : {case : } [default : ] } 3 → = → A ‫ ׀‬B ‫ ׀‬C → - ‫< ׀‬term> → / ‫< ׀‬factor> → ( ) ‫< ׀‬id> 6. (a) => = => A = => A = * => A = A * => A = A * ( ) => A = A * ( * ) => A = A * ( B * )

=> A = A * ( B * ( ) ) => A = A * ( B * ( + ) ) => A = A * ( B * ( C + ) ) => A = A * ( B * ( C + ) )
8
©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

=> A = A * ( B * ( C + A ) ) 7. Follow the answer of the previous example.

9
©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

8. If the grammar generates a different parse tree, then we can say the grammar is ambiguous. The grammar generates two different parse trees. 9. Assume that the unary operators can precede any operand. Replace the rule → with → + | - 10. One or more x's followed by one or more y's. 13. S → a S b b | a b b| ƙ Here ƙ is null. 14. The parse tree for abb is:

The parse tree for aabbbb is:

16. → = → A | B | C → (+ | -) | ()

10
©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

| 18. A parse tree of an attribute grammar is the parse tree based on its underlying BNF grammar, with a possibly empty set of attribute values attached to each node. If all the attribute values in a parse tree have been computed, the tree is said to be fully attributed. 19. Replace the second semantic rule with: [2].env ← .env [3].env ← .env .actual_type ← [2].actual_type predicate: [2].actual_type = [3].actual_type 21. (a) (Java do-while) We assume that the logic expression is a single relational expression. loop: (do body) if goto out goto loop out: ...

(b) (Ada for) for I in first .. last loop

I = first loop: if I < last goto out ... I=I+1 goto loop out: ...

11
©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

(c) (Fortran Do) K = start loop: if K > end goto out ... K = K + step goto loop out: ...

(e) (C for) for (expr1; expr2; expr3) ... evaluate(expr1) loop: control = evaluate(expr2) if control == 0 goto out ... evaluate(expr3) goto loop out: ...

22a. Mpf(for var in init_expr .. final_expr loop L end loop, s) if VARMAP(i, s) = undef for var or some i in init_expr or final_expr then error else if Me(init_expr, s) > Me(final_expr, s) then s else Ml(while init_expr - 1 0} 2 * (b - 1) - 1 > 0 2*b-2-1>0 2*b>3 b>3/2

(b)

b = (c + 10) / 3 {b > 6} (c + 10) / 3 > 6 c + 10 > 18 c>8

(c)

a = a + 2 * b - 1 {a > 1} a+2*b-1>1 2*b>2-a b>1-a/2

(d)

x = 2 * y + x - 1 {x > 11} 2 * y + x - 1 > 11 2 * y + x > 12

14
©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

24. (a) a=2*b+1 b = a - 3 {b < 0}

a-3 3 6*b+3*a>3 2*b+a>1 n > (1 - a) / 2

15
©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

Chapter 4 Problem Set: 1. (a) FIRST(aB) = {a}, FIRST(b) = {b}, FIRST(cBB) = {c}, Passes the test (b) FIRST(aB) = {a}, FIRST(bA) = {b}, FIRST(aBb) = {a}, Fails the test (c) FIRST(aaA) = {a}, FIRST(b) = {b}, FIRST(caB) = {c}, Passes the test

3. a + b * c
Call lex /* returns a */

Enter Enter Enter Call lex /* returns + */

Exit Exit Call lex /* returns b */

Enter Enter Call lex /* returns * */

Exit Call lex /* returns c */

Enter Call lex /* returns end-of-input */

Exit Exit

16
©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

Exit

5. (a) aaAbb S

a

A

b

a

A

B

b Phrases: aaAbb, aAb, b Simple phrases: b Handle: b

(b) bBab

S

b

B

A

a Phrases: bBab, ab Simple phrases: ab Handle: ab 7. Stack 0 0id5 Input

b

Action

id * (id + id) $ Shift 5 * (id + id) $ Reduce 6 (Use GOTO[0, F])

17
©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

0F3 0T2 0T2*7 0T2*7(4 0T2*7(4id5 0T2*7(4F3 0T2*7(4T2 0T2*7(4E8 0T2*7(4E8+6

* (id + id) $ * (id + id) $ (id + id) $ id + id ) $ + id ) $ + id ) $ + id ) $ + id ) $ id ) $

Reduce 4 (Use GOTO[0, T]) Reduce 2 (Use GOTO[0, E]) Shift 7 Shift 4 Shift 5 Reduce 6 (Use GOTO[4, F]) Reduce 4 (Use GOTO[4, T]) Reduce 2 (Use GOTO[4, E]) Shift 6 Shift 5 Reduce 6 (Use GOTO[6, F]) Reduce 4 (Use GOTO[6, T]) Reduce 1 (Use GOTO[4, E]) Shift 11 Reduce 5 (Use GOTO[7, F]) Reduce 5 (Use GOTO[0, T]) Reduce 2 (Use GOTO[0, E])

0T2*7(4E8+6id5 ) $ 0T2*7(4E8+6F3 0T2*7(4E8+6T9 0T2*7(4E8 0T2*7(4E8)11 0T2*7F10 0T2 0E1 --ACCEPT-)$ )$ )$ $ $ $ $

Programming Exercises: 1. Every arc in this graph is assumed to have addChar attached. Assume we get here only if charClass is SLASH. other / start slash * com other
18
©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

* end

/ return COMMENT

return SLASH_CODE

3.

int getComment() { getChar(); /* The slash state */ if (charClass != AST) return SLASH_CODE; else { /* The com state-end state loop */ do { getChar(); /* The com state loop */ while (charClass != AST) getChar(); } while (charClass != SLASH); return COMMENT; }

Chapter 5 Problem Set: 2. The address of a variable is called its l-value. int i = 10, j; j = i+++++i; // this statement will give compile time error—“ l-value required” 4. The type of a variable determines the range of values the variable can store and the set of operations that are defined for values of the type. The int type in Java have a value range of –2147483648 to 2147483647. 5. Static binding: A class with multiple methods that have the same name, but with different parameter lists, requires static binding to call these methods.
19
©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

Dynamic binding: In case of inheritance, if both the base class and the derived class have methods of the same name with the same parameter list and return type, dynamic binding would be used to call these methods. 6. (a) i. sub1 ii. sub1 iii. main (b) i. sub1 ii. sub1 iii. sub1

7. Static scoping: x

is 5 is 10

Dynamic scoping: x

8.

Variable In sub1: a y z x

Where Declared

sub1 sub1 sub1 main

In sub2: a b z y x sub2 sub2 sub2 sub1 main

20
©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

In sub3: a x w y z sub3 sub3 sub3 main main

10. Point 1:

a b c d

1 2 2 2 1 2 3 3 3

Point 2:

a b c d e

Point 3: same as Point 1 Point 4: a b c

1 1 1 Where Declared fun3 fun2 fun1 main

11. (a)

Variable d, e, f c b a

21
©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

(b)

d, e, f b, c a

fun3 fun1 main fun1 fun3 main fun1 fun3 main fun2 fun3 fun1 main fun1 fun2 fun3 main

(c)

b, c, d e, f a

(d)

b, c, d e, f a

(e)

c, d, e f b a

(f)

b, c, d e f a

12. (a)

Variable a, x, w b, z y

Where Declared sub3 sub2 sub1 sub3 sub1 sub1 sub3 sub2 22

(b)

a, x, w y, z

(c)

a, y, z x, w b

©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

(d)

a, y, z x, w

sub1 sub3 sub2 sub3 sub1 sub1 sub2 sub3

(e)

a, b, z x, w y

(f)

a, y, z b x, w

Chapter 6 Problem Set: 1. bytes (1 byte), short(2 bytes), integer (4 bytes), long (8 bytes). As a result, depending on the domain of the variable required, data types are used. 2. A negative integer could be stored in sign-magnitude notation, in which the sign bit is set to indicate negative and the remainder of the bit string represents the absolute value of the number. Sign-magnitude notation, however, does not lend itself to computer arithmetic. Most computers now use a notation called twos complement to store negative integers, which is convenient for addition and subtraction. 5. When implicit dereferencing of pointers occurs only in certain contexts, it makes the language slightly less orthogonal. The context of the reference to the pointer determines its meaning. This detracts from the readability of the language and makes it slightly more difficult to learn. 7. A C++ reference type variable is a constant pointer that is always implicitly dereferenced. 9. If all data members of the variables are to be used at once then struct type variables are required, otherwise union type variables should be used. 10. Row major order – location(a[i,j]) = address of a[0, 0] + ((((number of rows above the ith row) * (size of a row)) + (number of elements left of the jth column)) * element size) 11. The advantage of this scheme is that accesses that are done in order of the rows can be made very fast; once the pointer to a row is gotten, all of the elements of the row can
23
©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

be fetched very quickly. If, however, the elements of a matrix must be accessed in column order, these accesses will be much slower; every access requires the fetch of a row pointer and an address computation from there. Note that this access technique was devised to allow multidimensional array rows to be segments in a virtual storage management technique. Using this method, multidimensional arrays could be stored and manipulated that are much larger than the physical memory of the computer. 15. Single-size Allocation Heap: In a single-size allocation heap, all available cells are linked together using the pointers in the cells, forming a list of available space. Allocation is a simple matter of taking the required number of cells from this list when they are needed. Deallocation is a much more complex process. A heap-dynamic variable can be pointed to by more than one pointer, making it difficult to determine when the variable is no longer useful to the program. Simply because one pointer is disconnected from a cell obviously does not make it garbage; there could be several other pointers still pointing to the cell. Variable-size Allocation Heap: The initial setting of the indicators of all cells in the heap to indicate that they are garbage is difficult. Because the cells are different sizes, scanning them is a problem. One solution is to require each cell to have the cell size as its first field. Then the scanning can be done, although it takes slightly more space and somewhat more time than its counterpart for fixed-size cells. The marking process is nontrivial. How can a chain be followed from a pointer if there is no predefined location for the pointer in the pointed-to cell? Cells that do not contain pointers at all are also a problem. Adding an internal pointer to each cell, which is maintained in the background by the run-time system, will work. However, this background maintenance processing adds both space and execution time overhead to the cost of running the program. Maintaining the list of available space is another source of overhead. The list can begin with a single cell consisting of all available space. Requests for segments simply reduce the size of this block. Reclaimed cells are added to the list. The problem is that before long, the list becomes a long list of various-size segments, or blocks. This slows allocation because requests cause the list to be searched for sufficiently large blocks. Eventually, the list may consist of a large number of very small blocks, which are not large enough for most requests. At this point, adjacent blocks may need to be collapsed into larger blocks. Alternatives to using the first sufficiently large block on the list can shorten the search but require the list to be ordered by block size. In either case, maintaining the list is additional overhead. 21. Static checking reduces programmer flexibility. 22. In the locks-and-keys approach, pointer values are represented as ordered pairs (key, address), where the key is an integer value. Heap-dynamic variables are represented as the storage for the variable plus a header cell that stores an integer lock value. When a heap-dynamic variable is allocated, a lock value is created and placed both in the lock cell of the heap-dynamic variable and in the key cell of the pointer that is specified in the call to new.

24
©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

Chapter 7 Problem Set: 1. Suppose Type1 is a subrange of Integer. It may be useful for the difference between Type1 and Integer to be ignored by the compiler in an expression. 7. An expression such as a + fun(b), as described on page 300. 8. Consider the integer expression A + B + C. Suppose the values of A, B, and C are 20,000, 25,000, and -20,000, respectively. Further suppose that the machine has a maximum integer value of 32,767. If the first addition is computed first, it will result in overflow. If the second addition is done first, the whole expression can be correctly computed. 9. (a) ( ( ( a * b )1 - 1 )2 + c )3 (b) ( ( ( a * ( b - 1 )1 )2 / c )3 mod d )4 (c) ( ( ( a - b )1 / c )2 & ( ( ( d * e )3 / a )4 - 3 )5 )6 (d) ( ( ( - a )1 or ( c = d )2 )3 and e )4 (e) ( ( a > b )1 xor ( c or ( d ( xor ( c or ( d = | → → + | - | & | mod | → * | / | not | → a | b | c | d | e | const | ( )

26
©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

12. (a) * a b + 1 c

27
©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

12. (b) mod / * a c c

( ) b 1

28
©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

12. (c) & / ( )

( )

c

b / * d e

a 3

a

29
©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

12. (d)

and

or

-

= e d

a c

30
©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

12. (e) xor or

> a b

c

right) sum1 is 46; sum2 is 48 (b) (right -> left) sum1 is 48; sum2 is 46 15. One reason functional side effects would be difficult to remove from C is that all of C's subprograms are functions, providing the ability of returning only a single data value (though it could be an array). The problem is that in many cases it is necessary (or at least convenient) to return more than one data value, which is done through the use of pointer actual parameters, which are a means of creating functional side effects. 20. (a) 7 (b) 12 21. Java specifies that operands in expressions are all evaluated in left-to-right order to eliminate the problem described in Section 7.2.2.1.

32
©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

Chapter 8 Problem Set: 1. The design issues for two-way selectors can be summarized as follows: • What is the form and type of the expression that controls the selection? • How are the then and else clauses specified? • How should the meaning of nested selectors be specified? 4. A multiple selector can be built from two-way selectors and gotos, but the resulting structures are cumbersome, unreliable, and difficult to write and read. 5. • • Compound statements are required in control statements when the body of the if or else clause requires multiple statements. Java uses braces to form compound statements, which serve as the bodies of if and else clauses.

9. int i=10; if( i ) { // block of statements } This block of statement is valid in C++ but not in Java. 11. The Java variable in the argument of a switch statement can be of type integral ( byte, short etc.), char and String( JDK 1.7 onwards), whereas in C++ the argument can be int or char. 14. Premature exits from loops.

Programming Exercises: 1. (a)
Do K = (J + 13) / 27, 10 I = 3 * (K + 1) - 1 End Do

(b)

for k in (j + 13) / 27 .. 10 loop i := 3 * (k + 1) - 1; end loop;

33
©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

(c) 2. (a)

for (k = (j + 13) / 27; k j := 4 * k - 1; when 6..8 => j := k - 2; when others => Put ("Error in case, k ='); Put (k); New_Line; end case; (c) switch (k) { case 1: case 2: j = 2 * k - 1; break; case 3: case 5: j = 3 * k + 1; break; case 4: j = 4 * k - 1; break; case 6: case 7: case 8: j = k - 2; break; default: printf("Error in switch, k =%d\n", k); }

4. j = -3; key = j + 2; for (i = 0; i < 10; i++){ if ((key == 3) || (key == 2)) 35
©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

j--; else if (key == 0) j += 2; else j = 0; if (j > 0) break; else j = 3 - i; }

5. (C) for (i = 1; i