Practice Questions For Chapter 3

PRACTICE QUESTIONS FOR CHAPTER 3

1. Describe in English the language that is generated by the following BNF grammar.

<pretzel> à s <pretzel> | s

Solution:

All strings containing 0 or more b, followed by 1 or more z, then one f and then one or more s.

2. Consider the following BNF grammar.

<bop> à <boop> | ( <pop> )

<boop> à x | y | z

Which of the strings below is a <pop>?

Is it a <pop>?
z / yes / no
(x) / yes / no
+y= / yes / no
(+y=) / yes / no
+(x),y= / yes / no
+(x), +y, x== / yes / no

3. Write a BNF for the following:

A set of strings over alphabet {a,b} that read the same from left to right as from right to left (palindromes)

Solution:

S → a S a | b S b | a | b | ε

4. Write a BNF for the following:

{anbn}: every a paired with b on the other side

Solution:

S ® aSb | e

5. Write a BNF for the following:

{anbjan | n ³ 0, j ³ 1}: each 'a' on the left paired with one on the right

Solution:

S ® aSa | R

R ® bR | b

6. Write a BNF for the following:

{anb3n}: Each a on the left can be paired with three bs on the right

Solution:

S à aSbbb | epsilon

7. Write an unambiguous grammar that generates: "The set of all strings of as and bs containing an even number of bs".

Solution:

G à A S

S à b A b A S

A à a A

8. 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?

1) baab

2) bbbab

3) bbaaaaa

4) bbaab

9. In the following grammar:

S -> X | X % S

X -> int | int & X | ( S )

Statement 1 / Statement 2 / Does statement 1 equal statement 2? (YES / NO)
2 % 3 % 4 / (2 % 3) % 4
2 & 3 % 4 / (2 & 3) % 4

10. Consider the following BNF grammar for a language with two operators & and @.

<UW> à term

What is the associativity of the '&' operator?

a. / b. / c. / d.
left / right / neither / highest

Which operator has higher precedence?

a. / b. / c. / d.
@ / term / & and @ have same precedence

The grammar is:

a. / b. / c. / d.
left recursive / right recursive / both left and right recursive / neither left nor right recursive

11. Which of the following grammars G1 and G2 is ambiguous?

G1: <S> à x <S> z | x <S> y <S> z | a / G2: <S> à x <S> | x <S> y <S> | a
a. / b. / c. / d.
G1 / G2 / both G1 and G2 / None are ambiguous

CONVERSION FROM EBNF TO BNF AND VICE VERSA

BNF to EBNF:

(i) Look for recursion in grammar:

A ::= a A | B

rewrite as:

A ::= { a } B

(ii) Look for common string that can be factored out with grouping and options.

A ::= a B | a

Rewrite as:

A := a [B]

EBNF to BNF:

(i) Options: []

A ::= a [B] C

Rewrite as:

A’ ::= a N C

N ::= B | empty string

(ii) Repetition: {}

A ::= a { B1 B2 ... Bn } C

Rewrite as:

A’ ::= a N C

N ::= B1 B2 ... Bn N | empty string

12. Convert the following EBNF to BNF:

S → A { bA } { } repeat – 0 or indefinitely

A → a [b] A [ ] optional – 0 or once

13. Convert the following BNF to EBNF. Assume that <S> is the starting symbol

S → A | AC

C → bA | bAC

A → aA | abA

a. / b. / c. / d.
S → Ab {A}
A → ab {A} / S → {Ab} A
A → a [b] A / S → A {bA }
A → a {b} A / S → A { bA }
A → a [b] A

RECURSIVE DESCENT PARSER

BNF:

<if statement> ::= <if part> [ <else part> ]

Recursive Parser:

boolean ifStatement(Token tok) {

if (ifPart(tok)) {

tok = tokenizer.nextToken();

} else {

return false;

}

elsePart(tok); // ignore result

return true

BNF:

<list> ::= <item> { "," <item> }

Recursive Parser:

boolean list(Token tok) {

if (item(tok)) {

tok = tokenizer.nextToken();

while (tok.value.equals(",")) {

tok = tokenizer.nextToken();

if (!item(tok)) error();

}

return true;

}

return false;

}

14. Prove that the following grammar is ambiguous:

<id> → a | b | c

Create the parse trees for a + b + c:

The sentential form yields to distinct parse trees; hence, ambiguity.

15. Show the leftmost and rightmost derivation of the following sentence from the given grammar.

2 + ( 3 * 7 + 6 )

E → E + T | E – T | T

T → T * F | T / F | F

F → number | name | ( E )

Leftmost derivation
E → E + T
→ T + T
→ F + T
→ 2 + T
→ 2 + F
→ 2 + ( E )
→ 2 + ( E + T )
→ 2 + ( T + T )
→ 2 + ( T * F + T )
→ 2 + ( F * F + T )
→ 2 + ( 3 * F + T )
→ 2 + ( 3 * 7 + T )
→ 2 + ( 3 * 7 + F )
→ 2 + ( 3 * 7 + 6 ) / Rightmost derivation
E → E + T
→ E + F
→ E + ( E )
→ E + ( E + T )
→ E + ( E + F )
→ E + ( E + 6 )
→ E + ( T * F + 6 )
→ E + ( T * F + 6 )
→ E + ( T * 7 + 6 )
→ E + ( F * 7 + 6 )
→ E + ( 3 * 7 + 6 )
→ T + ( 3 * 7 + 6 )
→ F + ( 3 * 7 + 6 )
→ 2 + ( 3 * 7 + 6 )