4.4.1 : For each of the following grammars, devise predictive parsers and show the parsing tables. You may left-factor and/of eliminate left-recursion from your grammars first.  a) The grammar of...

4.4.1 : For each of the following grammars, devise predictive parsers and show the parsing tables. You may left-factor and/of eliminate left-recursion from your grammars first.

a) The grammar of Exercise 4.2.2(a).

b) The grammar of Exercise 4.2.2(b).

c) The grammar of Exercise 4.2.2(c).


d) The grammar of Exercise 4.2.2(d).


e) The grammar of Exercise 4.2.2(e).

f) The grammar of Exercise 4.2.2(g).

Exercise 4.2.2

Repeat Exercise 4.2.1 for each of the following grammars and strings:

a) S 0 5 1 | 0 1 with string 000111.


b) S + 5 5 | * S S | a with string + * aaa.

! c ) S S (S) S\e with string (()()).

! d ) S -> S + S\S S\(S)\S * \ a with string (a + a) * a.


! e ) S -» ( L ) | a and L -» L , 5 | 5 with string ((a ,a),a,(a)).


!! f) S -» a565|&5 , a5| e with string aabbab.

The following grammar for boolean expressions: bexpr -» 6e:rpr or fcierm | frterm ftterra —>• frterm and bfactor | bfactor bfactor -» no t bfactor | ( fcezpr) | true | false

Exercise 4.2.1

Consider the context-free grammar:


5 -> S S + \ S S * \ a

and the string aa + a*.

a) Give a leftmost derivation for the string.

b) Give a rightmost derivation for the string.

c) Give a parse tree for the string.

! d) Is the grammar ambiguous or unambiguous? Justify your answer.


! e) Describe the language generated by this grammar.