CSA305 Exercise 2 - Simple Recognition Algorithms

Lexical rules will look like this

C >>> [W]
where W is a word (i.e. atomic symbol).

1. Write an appropriate operator declaration to handle this kind of rule. Hint: To find out about operator declarations try
   ?- help(op)

2. Use your formalism to write a grammar/lexicon that recognises the following sentence.
   1. Jack fed the cat.

3. Without using DCG rules, implement a top down recogniser for these rules. To do this you must define a predicate rec(S) which succeeds (returns yes) if the grammar generates the sentence S, and fails if the grammar does not. Hint: use this code as a starting point, adapting it to deal with the new rule format.

4. Adapt the recogniser (without changing the rules) so that it produces a "standard" parse tree. Hint: to achieve this you will almost certainly need to make use of the built in =.. operator which has the following behaviour

   ?- A =.. [a,b].  
    
   A = a(b) 
   

5. How would you write a rule for an "empty category"? Adapt your definition of np so that is uses an empty category, and then verify that it works top down.

6. Augment the grammar to handle the following sentences by adding a left-recursive rule for np. Test the recogniser on them. What behaviour do you notice?
   2. Jack fed the cat and the dog.
   3. The cat, the dog and the chicken licked their chops.

7. Typically, the top-down recogniser loops whenever the sentence is not generated by the grammar (why?). There are two ways to fix this:
   1. Rewrite the grammar rules to remove the left recursion. Try to figure out whether there is a is a mechanical procedure for removing left recursion from a grammar.
   2. Recognise the sentence bottom up, e.g. using a shift-reduce algorithm. In this case you may use the algorithm given in the lecture. However, you will need to transform the rules into "backward form" so that the form "a >>> b, c." is compiled to the form "brule([c,b|X],[A|X])" and then asserted into the database.