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.

answer:

<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))

answer:

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))

answer:

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

answer:

9. Modify the grammar of Example 3.4 to add a unary minus operator that

has higher precedence than either + or *.

answer:

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

answer:

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

answer:

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.

answer:

S => a S b | a b

14. Draw parse trees for the sentences aabb and aaaabbbb, as derived from

the grammar of Problem 13.

answer:

15. Convert the BNF of Example 3.1 to EBNF.

answer:

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.

answer:

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

answer:

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.

answer:

(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.

answer:

(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

## Leave a Reply