# Chapter 3 Solutions

Concepts of Programming Languages Chapter 3 Solutions from Solutions Manual

## Problem Set :

3. Rewrite the BNF of Example 3.4 to give + precedence over * and force + to be right associative.

<assign> => <id> = <expr>

<id> => A | B | C

<expr> => <expr> + <term> | <term>

<term> => <term> * <factor> | <factor>

<factor> => (<expr>) | <id>

6. Using the grammar in Example 3.2, show a parse tree and a leftmost
derivation for each of the following statements:
a. A = A * (B + (C * A))
b. B = C * (A * C + B)
c. A = A * (B + (C))

for a.

Left derivation:

<assign> => <id> = <expr>

=> A = <expr>

=> A = <id> * <expr>

=> A = A * <expr>

=> A = A * (<expr>)

=> A = A * (<id> + <expr>)

=> A = A * (B + <expr>)

=> A = A * (B + (<expr>))

=> A = A * (B + (<id> * <expr>))

=> A = A * (B + (C * <expr>))

=> A = A * (B + (C * <id>))

=> A = A * (B + (C * A))

Parse Tree :

7. Using the grammar in Example 3.4, show a parse tree and a leftmost
derivation for each of the following statements:
a. A = ( A + B ) * C
b. A = B + C + A
c. A = A * (B + C)
d. A = B * (C * (A + B))

for a.

Left derivation:

<assign> => <id> = <expr>

=> A = <expr>

=> A = <term>

=> A = <term> * <factor>

=> A = <factor> * <factor>

=> A = (<expr>) * <factor>

=> A = (<expr> + <term>) * <factor>

=> A = (<term> + <term>) * <factor>

=> A = (<factor> + <term>) * <factor>

=> A = (<id> + <term>) * <factor>

=> A = (A + <term>) * <factor>

=> A = (A + <factor>) * <factor>

=> A = (A + <id>) * <factor>

=> A = (A + B) * <factor>

=> A = (A + B) * <id>

=> A = (A + B) * C

Parse Tree:

8. Prove that the following grammar is ambiguous:

<S> => <A>

<A> => <A> + <A> | <id>

<id> => a | b | c

9. Modify the grammar of Example 3.4 to add a unary minus operator that
has higher precedence than either + or *.

Assume that the unary operators can precede any operand. Replace the rule
<factor> => <id>
with
<factor> => + <id>
| – <id>

10.Describe, in English, the language defined by the grammar:

<S> -> <A> <B> <C>

<A> -> a <A> | a

<B> -> b <B> | b

<C> -> c <C> | c

One or more a’s followed by one or more b’s followed by one or more c’s.

11) Consider the 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. baab
b. bbbab
c. bbaaaaa
d. bbaab

a) baab is valid

b) bbbab is not valid

c) bbaaaaaS is not valid

d) bbaab is valid

13. Write a grammar for the language consisting of strings that have n
copies of the letter a followed by the same number of copies of the
letter b, where n > 0. For example, the strings ab, aaaabbbb, and
aaaaaaaabbbbbbbb are in the language but a, abb, ba, and aaabb are not.

S => a S b | a b

14. Draw parse trees for the sentences aabb and aaaabbbb, as derived from
the grammar of Problem 13.

15. Convert the BNF of Example 3.1 to EBNF.

BNF:

<program> -> begin <stmt_list> end

<stmt_list> -><stmt>

| <stmt> ; <stmt_list>

<stmt> -> <var> = <expression>

<var> -> A | B | C

<expression> -> <var> + <var>

| <var> – <var>

| <var>

EBNF:

<program> -> begin <stmt_list> end

<stmt_list> -> <stmt> [<stmt_list>]

<stmt> -> <var> = <expression>

<var> -> A | B | C

<expression> -> <var> ( + | – ) <var>

| <var>

16. Convert the BNF of Example 3.3 to EBNF.

BNF:

<assign> -> <id> = <expr>

<id> -> A|B|C

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

| <id> * <expr>

|<expr> )

| <id>

EBNF:

<assign> -> <id> = <expr>

<id> -> A|B|C

<expr> -> <id> (+ | *) <expr>

|(<expr> )

| <id>

17.Convert the following EBNF to BNF:

S -> A{bA}

A -> a[b]A

S -> A     |bA

A -> aA  |abA

19. Write an attribute grammar whose BNF basis is that of Example 3.6 in
Section 3.4.5 but whose language rules are as follows: Data types cannot
be mixed in expressions, but assignment statements need not have the
same types on both sides of the assignment operator.

(a)

a = 2 * (b – 1) – 1 {a > 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}
29
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

20. Write an attribute grammar whose base BNF is that of Example 3.2 and
whose type rules are the same as for the assignment statement example
of Section 3.4.5.

(a)

a = 2 * b + 1
b = a – 3 {b < 0}
a – 3 < 0
a < 3
Now, we have:
a = 2 * b + 1 {a < 3}
2 * b + 1 < 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
Now we have:
a = 3 * (2 * b + a) {a > 3}
3 * (2 * b + a) > 3
6 * b + 3 * a > 3
2 * b + a > 1
n > (1 – a) / 2