Concepts of Programming Languages - Chapter 3

Review Questions

1. Define syntax and semantics.
Syntax is the form or structure of the expressions, statements, and program units.
Semantics is the meaning of the expressions, statements, and program units.

2. Who are language descriptions for?
The language descriptions is important for the programming language implementers to determine how the expressions, statements, and program units of a language are formed, and also their intended effect when executed.

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.

7. What three extensions are common to most EBNFs?
Three extensions are commonly included in the various versions of EBNF. The first extension denotes an optional part of an RHS, which is delimited by brackets. The second extension is the use of the brackets in an RHS to indicate that the enclosed part can be repeated indefinitely or left out altogether. And the third extension deals with multiple-choice options.

10. What is the difference between a synthesized and an inherited attribute?
The attributes are divided into two groups: synthesized attributes and inherited attributes. The synthesized attributes are the result of the attribute evaluation rules, and may also use the values of the inherited attributes. The inherited attributes are passed down from parent nodes.

12. What is the primary use of attribute grammar?
Attribute grammar is primary used to provide complete descriptions of the syntax and static semantics of programming languages.

21. When is a grammar rule said to be left recursive?
When a grammar rule has its LHS also appearing at the beginning of its RHS, the rule is said to be left recursive. This left recursion specifies left associativity.

22. Give an example of an ambiguous grammar.
<assign> -> <id> = <expr>

<id> -> A | B | C

<expr> -> <expr> + <expr>

| <expr> * <expr>

|  (  <expr>  )

| <id>

23. On what branch of mathematics is axiomatic semantic based?
Axiomatic semantics, thus named because it is based on mathematical logic.

24. Give an unambiguous grammar for if-then-else.
<if_stmt> -> if <logic_expr> then <stmt>

if <logic_expr> then <stmt> else <stmt>


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.
Syntax error is a code error and semantic error is a logical error.
An example of syntax error, for example in C, is forget to put semicolon
assume that printf("Hello world");
It is a syntax error if we make printf("Hello world")
An example of semantic error is: const int pi = 123;
It is syntactically correct but logically incorrect.

3. Rewrite the BNF of Example 3.4 to represent operator – and operator / instead of operator + and operator *.
<assign> -> <id> = <expr>
<id> -> A | B | C
<expr> -> <expr> - <term>
|<term>
<term> -> <term> * <factor>
|<factor>
<factor> -> ( <expr> )
|<id>

8. Prove that the following grammar is ambiguous:
<S> -> <A>
<S> -> <A> * <A> | <id>
<id> -> x | y | z
The grammar is ambiguous, because the grammar generates different parse trees.

9. Modify the grammar of Example 3.4 to add a unary minus operator that has higher precedence than either + or *.
Assume that the operators can precede any operand
<factor> -> <id>
with
<factor> -> + <id>
| - <id>

10. Describe, in English, the language defined by the following grammar:
<S> -> <X><Y>
<X> -> x<X> | x
<Y> -> y<Y> | y
x can be followed by one or more than one x, then followed by one or more than one y.

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?
a. bbaabb
d. abaabb

12. Consider the following grammar:
<S> -> a <S> c <B> |<A> |b
<A> -> c <A> |c
<B> -> d |<A>
Which of the following sentences are in the language generated by this
grammar:
b. accbcbccc

18.  What is a fully attributed parse tree?
A fully attributed parse tree is a condition when all the attributed values in parse tree have been computed.

23. Compute the weakest precondition for each of the following sequences of assignment statements and their postconditions:
a. a = 2 * (b - 1) - 1 {a > 0}
2 * (b - 1) - 1 > 0
2*b - 2 > 1
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
a + 2 * b > 2
2 * b > 2 - a
b > (2 - a) / 2

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

24. Compute the weakest precondition for each of the following sequences of assignment statements and postconditions:
a. a = 2 * b + 1;
b = a - 3
{b < 0}

a - 3 < 0
a < 3

2 * b + 1 < 3
2 * b < 2
b < 1

b. a = 3 * (2 * b + a);
b = 2 * a - 1
{b > 5}

2 * a - 1 > 5
2 * a > 6
a > 3

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