Exercise 6.1

Design a simple ambiguous context free grammar. Show that your grammar is ambiguous by giving an example of a string that has two distinct parse trees. Draw the two trees.

Exercise 6.2

The following grammar (epsilon.pl ) contains a rule producing an empty terminal symbol: written as s --->[] in our Prolog notation.

s ---> [].
s ---> [left,s,right].
 
lex(a,left).
lex(b,right).

Does this grammar admit the string a b? What happens if you try to use bottomup_recognizer.pl with this grammar to recognize the string a b? Why?

Exercise 6.3

Our naive bottom-up recognizer only recognizes strings of category s. Change it, so that it recognizes strings of any category, as long as the whole string is spanned by that category, and returns the category that it found. For example:

?- recognize_bottomup_any([the,man],Cat).
Cat = np
yes
?- recognize_bottomup_any([the,man,dances],Cat).
Cat = s
yes
?- recognize_bottomup_any([the,man,dances,a],Cat).
no