The assignment #5 due date is now extended to December 12.

It turns out to be very difficult to write an efficient parser for the grammar of Assignment 5, that is similar to the Prolog parsers presented in class, unless difference lists are used.

To deal with this, I have

  1. extended the due date, as described above (all submissions are to be turned in at or before the beginning of the final exam)
  2. put a new sample English grammar (that uses difference lists) on the class web site (check the new English grammar link). This grammar contains examples of the constructions that you will need for Assignment 5's grammar, but that we haven't seen in other Prolog examples.
  3. formulated a couple of additional hints, and a new policy for partial credit, which I will share with you below.
The first hint is a suggestion about how to relate difference lists to the use of scanners in earlier assignments. If you think of a difference list as representing a scanner, then the part before the slash represents the contents of the scanner before processing, and the part after the slash represents the contents of the scanner after processing. So for example the predicate
np(S/VP)
should succeed if and only if the contents of the scanner is initially S, a noun phrase is consumed from the scanner, and after consuming the noun phrase, the contents of the scanner is VP.

Naturally a complete parse should not only find a sentence, but should exhaust the scanner. This is why, in the difference list grammar presented in class, the only way that the

parse(S,P)
predicate can be true is if the
s(S/[],P)
predicate is true.

The second hint deals with what you might try if you still can't get difference lists to work. My recommendation is that you don't start with the program predicate or the block predicate, but with the predicates corresponding to symbols on the right-hand side of the block rule. For example, even in an inefficient approach that doesn't use difference lists, you might be able to get a relatively quick successful answer to a query like

declarations(['declare', 'x', 'int', '3', ';',
'declare', 'y', 'real', '4', ';']).
or
declaration(['declare', 'x', 'int', '3', ';']).

A third hint is that if you do try to proceed without using difference lists, you might try moving any append subgoals ahead of some of the other subgoals. The new grading policy is simply that I will give generous partial credit if you can find partial parses of the sort mentioned in the second hint. And although I can't simply ignore anyone's grade on this assignment, I will be more forgiving that I might have been if your grade on this assignment is one of a few low scores.