Give bottom-up parses for the following input strings and grammars:
a) The input 000111 according to the grammar of Exercise 4.5.1.
b) The input aaa * a + + according to the grammar of Exercise 4.5.2.
Exercise 4.5.1
For the grammar 5 -> 051|01o f Exercise 4.2.2(a), indicate the handle in each of the following right-sentential forms:
a) 000111.
b) 00511.
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.
Exercise 4.5.2
Repeat Exercise 4.5.1 for the grammar S -» 5 5 + | 5 5 * | a of Exercise 4.2.1 and the following right-sentential forms:
a) SSS + a*+.
b) SS + a*a+.
c) aaa * a + +.
Exercise 4.5.1
For the grammar 5 -> 051|01o f Exercise 4.2.2(a), indicate the handle in each of the following right-sentential forms:
a) 000111.
b) 00511.
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.