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.

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 :

Ekran Alıntısı - Chapter 3 Solutions

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:

Ekran Alıntısı2 - Chapter 3 Solutions

8. Prove that the following grammar is ambiguous:

<S> => <A>

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

<id> => a | b | c

answer:

Ekran Alıntısı3 - Chapter 3 Solutions

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:

Ekran Alıntısı4 - Chapter 3 Solutions


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


Be the first to comment

Leave a Reply

Your email address will not be published.


*