CH.3 REVIEW QUESTIONS
1. Define syntax and
semantics.
- The syntax of a programming
language is the form of its expressions, statements, and program units. Its
semantics is the meaning of those expressions, statements, and program units.
3. Describe the operation
of a general language generator
- A language generator is
a device that can be used to generate the sentences of a language. We can think
of the generator as having a button that produces a sentence of the language
every time it is pushed. Because the particular sentence that is produced by a
generator when its button is pushed is unpredictable, a generator seems to be a
device of limited usefulness as a language descriptor.
4. Describe the operation
of a general language recognizer.
- The syntax analysis part
of a compiler is a recognizer for the language the compiler translates. In this
role, the recognizer need not test all possible strings of characters from some
set to determine whether each is in the language.
6. Define a left-recursive
grammar rule.
- In terms of context-free
grammar, a non-terminal r is left-recursive if the left-most symbol in any of
r’s ‘alternatives’ either immediately (direct left-recursive) or through some
other non-terminal definitions (indirect/hidden left-recursive) rewrites to r
again.
7. What three extensions
are common to most EBNFs?
- The first of these
denotes an optional part of an RHS, which is delimited by Brackets.. The second extension is the use of braces in an RHS to
indicate that the enclosed part can be repeated indefinitely or left out altogether.
The third common extension deals with multiple-choice options. When a single
element must be chosen from a group, the options are placed in parentheses and
separated by the OR operator, |.
8. Distinguish between
static and dynamic semantics.
- The static semantics of
a language is only indirectly related to the meaning of programs during
execution; rather, it has to do with the legal forms of programs (syntax rather
than semantics). The dynamic semantics is the meaning, of the expressions,
statements, and program units of a programming language. Because of the power
and naturalness of the available notation, describing syntax is a relatively
simple matter.
12. What is the primary
use of attribute grammars?
- An attribute grammar is
a formal way to define attributes for the productions of a formal grammar, associating
these attributes to values. The evaluation occurs in the nodes of the abstract
syntax tree, when the language is processed by some parser or compiler.
21. What is a predicate
transformer function?
- They define the
semantics of an imperative programming paradigm by assigning to each statement
in this language a corresponding predicate transformer: a total function
between two predicates on the state space of the statement
23. On what branch of
mathematics is axiomatic semantics based?
- It is based on
mathematical logic..
24. On what branch of
mathematics is denotational semantics based?
- It is solidly based on
recursive function theory. \
Problem Set
1. Syntax error and
semantic error are two types of compilation error. Explain the difference
between the two in a program with examples.
- A syntax error is an
error in the source code of a program. Since computer programs must follow
strict syntax to compile correctly, any aspects of the code that do not conform
to the syntax of the programming language will produce a syntax error. Semantic
error is an error in logic or arithmetic that must be detected at run time.
5. Write a BNF description
of the Boolean expressions of Java, including the two operators == and !=.
== equal to
!= not equal to
< less than
> greater than
<= less than or equal to
>= greater than or equal to
&& boolean AND
|| boolean OR
8. Prove that the
following grammar is ambiguous:
<S> -> <A>
<S> -> <A>
* <A> | <id>
<id> -> x | y | z
- Since the grammar
generated 2 different parse trees, it is ambiguous.
11. Consider the following
grammar:
<S> → <A> a
<B> b
<A> → <A> b |
b
<B> → a <B> |
a
Which of the following
sentences are in the language generated by this grammar?
- B. bbaba
18. 
A fully attributed parse tree has all these features.
A fully attributed parse tree has all these features.
23. Compute the weakest
precondition for each of the following assignment statements and postconditions
:
a. a = 2 * ( b – 1 ) – 1 {a > 0}
b. b = ( c + 10 ) / 3 {b>6}
c. a = a + 2 * b – 1 {a>1}
A. 2 * ( b – 1 ) – 1 > 0
2b – 2 – 1 > 0
2b – 3 > 0
2b > 3
B > 3/2
B. ( c + 10 ) / 3 > 6
c + 10 > 18
c > 8
C. a + 2 * b – 1 > 1
a + 2 * b > 2
2 * b > 2 – a
D. 2 * y + x – 1 > 11
2 * y + x > 12
2 * y > 12 – x
26. Explain the four
criteria for proving the correctness of a logical pretest loop construct of the
form while B do S end.
- The loop invariant must
satisfy a number of requirements to be useful. Another complicating factor for
while loops is the question of loop termination. A loop that does not terminate
cannot be correct, and in fact computes nothing. The complete axiomatic
description of a while construct requires all of the following to be true, in
which I is the loop invariant:
P => I
{I and B} S {I}
(I and (not B)) => Q
the loop terminates