Write a Yacc program tha t takes boolean expressions as input [as given by the grammar of Exercise 4.2.2(g)] and produces the truth value of the expressions. Exercise 4.2.2 Repeat Exercise 4.2.1 for...

Write a Yacc program tha t takes boolean expressions as input [as given by the grammar of Exercise 4.2.2(g)] and produces the truth value of the expressions.

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.