ALL 16 CHAPTERS COVERED
SOLUTIONS MANUAL
, 1
Introduction
1.9 Solutions Manual
This manual contains suggested solutions to many of the PLP exercises. It is provided
only to instructors who have adopted the text in their course.1
1.1 Errors in a computer program can be classified according to when they are de-
tected and, if they are detected at compile time, what part of the compiler detects
them. Using your favorite imperative language, give an example of each of the
following.
(a) A lexical error, detected by the scanner
(b) A syntax error, detected by the parser
(c) A static semantic error, detected by semantic analysis
(d) A dynamic semantic error, detected by code generated by the compiler
(e) An error that the compiler can neither catch nor easily generate code to catch
(this should be a violation of the language definition, not just a program bug)
Answer: There are many possible answers to this question. Here are possibilities in C:
Lexical error: ‘@’ sign outside of a string or comment
Syntax error: mismatched parentheses in an arithmetic expression
Static semantic error: use of an identifier that was never declared
Dynamic semantic error: divide by zero
Error that can’t reasonably be caught: failure to reclaim dynamically allocated objects that are no
longer needed (“memory leak”)
1
S 1.1
,S 1.2 Solutions Manual
1.2 Consider again the Pascal tool set distributed by Niklaus Wirth (Example 1.15).
After successfully building a machine language version of the Pascal compiler, one
could in principle discard the P-code interpreter and the P-code version of the
compiler. Why might one choose not to do so?
Answer: One obvious answer is that if the machine language version of the compiler were
lost, or if one upgraded to a new machine architecture, one might need the tools to rebuild
the compiler. Even if the compiler remains perfectly usable, however, it may be worthwhile
to keep the tools around. The P-code version of a program tends to be significantly smaller
than its machine language counterpart. On a circa 1970 machine, the savings in memory and
disk requirements could really be important. Moreover, as noted in Section 1.4, an interpreter
will often provide better run-time diagnostics than will the output of a compiler; these can be
particularly valuable during program development. Finally, an interpreter allows a program
to be rerun immediately after modification, without waiting for recompilation and linking—a
feature that can also be handy for development. Some of the best programming environments
for imperative languages (including most implementations of Java) include both a compiler and
an interpreter.
1.3 Imperative languages like Fortran and C are typically compiled, while scripting
languages, in which many issues cannot be settled until run time, are typically
interpreted. Is interpretation simply what one “has to do” when compilation is
infeasible, or are there actually some advantages to interpreting a language, even
when a compiler is available?
Answer: Compiled code usually runs significantly faster than interpreted code, so program-
mers interested in performance tend to demand compilers. Compilation also catches some errors
earlier, when they are easier to fix, rather than waiting to detect them until the program actually
runs. Interpretation definitely has its advantages, however; it is not just a last resort. It is very
handy during development because it allows a newly modified program to be executed without
waiting for potentially time-consuming compilation and linking steps. It may be desirable on
small machines because it takes less space, both in memory when running and on disk (because
there are no executables). Interpretation facilitates higher quality error messages, because the
interpreter has access to the full program source. It is much easier to bootstrap or port an
interpreter than a compiler, so experimental language implementations are very often based on
interpreters.
1.4 The gcd program of Example 1.20 might also be written
int main() {
int i = getint(), j = getint();
while (i != j) {
if (i > j) i = i % j;
else j = j % i;
}
putint(i);
}
Does this program compute the same result? If not, can you fix it? Under what
circumstances would you expect one or the other to be faster?
, 1.9 Solutions Manual S 1.3
Answer: The difference between the two programs is in the two assignment statements: i
:= i - j and j := j - i, versus i := i % j and j := j % i. Suppose i > j. Then i % j
== i - (j * (i / j)), where the slash (/) indicates integer division. The computation i % j
therefore comes close to accomplishing in one iteration of the loop what would happen over
the course of (i / j) iterations of the original loop. The exception arises in the case where i is
a multiple of j. In this case modular division produces a zero, after which the program aborts
with a divide-by-zero error. One possible fix capitalizes on the observation that (for positive
numbers) i % j is always smaller than i:
int main() {
int large = getint(), small = getint();
if (large < small) {
int temp = small;
small = large;
large = temp;
}
while (small != 0) {
int temp = small;
small = large % small;
large = temp;
}
putint(i);
}
If we observe that when i < j, i % j = i, then we can also employ the following simpler
program, at the expense of one useless extra division when i is initially smaller than j:
int main () {
int i, j, t;
i = getint(); j = getint();
while (i != 0) {
t = i;
i = j % i;
j = t;
}
putint(j);
}
If i and j are about the same magnitude, the original (subtraction-based) program may be
faster, because subtraction is faster than division on many machines. If i and j are of different
magnitude, the %-based version is likely to be faster.
1.5 Expanding on Example 1.25, trace an interpretation of the gcd program on the
inputs 12 and 8. Which syntax tree nodes are visited, in which order?
Answer: program
:=
call
(3) call getint
SOLUTIONS MANUAL
, 1
Introduction
1.9 Solutions Manual
This manual contains suggested solutions to many of the PLP exercises. It is provided
only to instructors who have adopted the text in their course.1
1.1 Errors in a computer program can be classified according to when they are de-
tected and, if they are detected at compile time, what part of the compiler detects
them. Using your favorite imperative language, give an example of each of the
following.
(a) A lexical error, detected by the scanner
(b) A syntax error, detected by the parser
(c) A static semantic error, detected by semantic analysis
(d) A dynamic semantic error, detected by code generated by the compiler
(e) An error that the compiler can neither catch nor easily generate code to catch
(this should be a violation of the language definition, not just a program bug)
Answer: There are many possible answers to this question. Here are possibilities in C:
Lexical error: ‘@’ sign outside of a string or comment
Syntax error: mismatched parentheses in an arithmetic expression
Static semantic error: use of an identifier that was never declared
Dynamic semantic error: divide by zero
Error that can’t reasonably be caught: failure to reclaim dynamically allocated objects that are no
longer needed (“memory leak”)
1
S 1.1
,S 1.2 Solutions Manual
1.2 Consider again the Pascal tool set distributed by Niklaus Wirth (Example 1.15).
After successfully building a machine language version of the Pascal compiler, one
could in principle discard the P-code interpreter and the P-code version of the
compiler. Why might one choose not to do so?
Answer: One obvious answer is that if the machine language version of the compiler were
lost, or if one upgraded to a new machine architecture, one might need the tools to rebuild
the compiler. Even if the compiler remains perfectly usable, however, it may be worthwhile
to keep the tools around. The P-code version of a program tends to be significantly smaller
than its machine language counterpart. On a circa 1970 machine, the savings in memory and
disk requirements could really be important. Moreover, as noted in Section 1.4, an interpreter
will often provide better run-time diagnostics than will the output of a compiler; these can be
particularly valuable during program development. Finally, an interpreter allows a program
to be rerun immediately after modification, without waiting for recompilation and linking—a
feature that can also be handy for development. Some of the best programming environments
for imperative languages (including most implementations of Java) include both a compiler and
an interpreter.
1.3 Imperative languages like Fortran and C are typically compiled, while scripting
languages, in which many issues cannot be settled until run time, are typically
interpreted. Is interpretation simply what one “has to do” when compilation is
infeasible, or are there actually some advantages to interpreting a language, even
when a compiler is available?
Answer: Compiled code usually runs significantly faster than interpreted code, so program-
mers interested in performance tend to demand compilers. Compilation also catches some errors
earlier, when they are easier to fix, rather than waiting to detect them until the program actually
runs. Interpretation definitely has its advantages, however; it is not just a last resort. It is very
handy during development because it allows a newly modified program to be executed without
waiting for potentially time-consuming compilation and linking steps. It may be desirable on
small machines because it takes less space, both in memory when running and on disk (because
there are no executables). Interpretation facilitates higher quality error messages, because the
interpreter has access to the full program source. It is much easier to bootstrap or port an
interpreter than a compiler, so experimental language implementations are very often based on
interpreters.
1.4 The gcd program of Example 1.20 might also be written
int main() {
int i = getint(), j = getint();
while (i != j) {
if (i > j) i = i % j;
else j = j % i;
}
putint(i);
}
Does this program compute the same result? If not, can you fix it? Under what
circumstances would you expect one or the other to be faster?
, 1.9 Solutions Manual S 1.3
Answer: The difference between the two programs is in the two assignment statements: i
:= i - j and j := j - i, versus i := i % j and j := j % i. Suppose i > j. Then i % j
== i - (j * (i / j)), where the slash (/) indicates integer division. The computation i % j
therefore comes close to accomplishing in one iteration of the loop what would happen over
the course of (i / j) iterations of the original loop. The exception arises in the case where i is
a multiple of j. In this case modular division produces a zero, after which the program aborts
with a divide-by-zero error. One possible fix capitalizes on the observation that (for positive
numbers) i % j is always smaller than i:
int main() {
int large = getint(), small = getint();
if (large < small) {
int temp = small;
small = large;
large = temp;
}
while (small != 0) {
int temp = small;
small = large % small;
large = temp;
}
putint(i);
}
If we observe that when i < j, i % j = i, then we can also employ the following simpler
program, at the expense of one useless extra division when i is initially smaller than j:
int main () {
int i, j, t;
i = getint(); j = getint();
while (i != 0) {
t = i;
i = j % i;
j = t;
}
putint(j);
}
If i and j are about the same magnitude, the original (subtraction-based) program may be
faster, because subtraction is faster than division on many machines. If i and j are of different
magnitude, the %-based version is likely to be faster.
1.5 Expanding on Example 1.25, trace an interpretation of the gcd program on the
inputs 12 and 8. Which syntax tree nodes are visited, in which order?
Answer: program
:=
call
(3) call getint
