ICS 171 Homework #14

1. (30) What is the internal horn clause representation of the following 5 grammar rules.

( (s) --> (np)(verb)(prep_phrase))
( (prep_phrase) --> (prep) (np))
((prep) --> (:word to))
((proper_name) --> (:word UCI))
((verb) --> (:word went))

If you can't figure it out, you can do something like this 5 times;

(convert-rule '( (s) --> (np)(verb)(prep_phrase))).

2. (40) Modify the simple grammar *dcg-rules* so that the following goals succeeds.

(prove-and-ask '((s (I went to UCI) ())))
(prove-and-ask '((s (I ate an apple at UCI) ())))

Hint 1. Use the above 5 grammar rules

Hint 2. "I" is a pronoun. Pronouns are noun phrases (np).

Hint 3. Some other rules are also needed.

You will type something like this

(load "unify")
(load "fast-traced-prove")
(load "dcg")
(load "dcg-rules")  ;;modify *dcg-rules*
(store-clauses (convert-rules *dcg-rules*))
(prove-and-ask '((s (I went to UCLA) ())))

3. (10) Find all the solutions to (prove-and-ask '((s (?A ?B ?C ?D ?E) ())))

4. (20) Think of 4 other ways of saying "Please add ADDRESS to your mailing list", 4 other ways of saying "Please delete ADDRESS from ML-LIST" and 4 other ways of saying "Please change ADDRESS to ADDRESS" where ADDRESS could be something like "me" or "pazzani @ ics.uci.edu" (Three words). Create a grammar in DCG format to recognize these three different types of requests and test it on the 3 sentences above and the 12 you make up. Your sentences should show some variety (e.g., "Subscribe me to ML-LIST", "Remove me from your mailing list" "Please send mail to pazzani@ics.uci instead of pazzani@cs.ucla.edu" etc.) Page 401 of Rich and Knight has a similar example IN A DIFFERENT FORMAT.

Hint ((adresss) --> (:word ?name) (:word @) (:word ?domain)) will recognize anything of the form "NAME @ DOMAIN" We will assume that a space is inserted before and after the @ to make this easier.

EXTRA CREDIT Write a DCG grammar to parse infix arithmetic expressions and construct a lisp representation of the expressions. This will be somewhat similar to


For example, given (x ^ 3 + 5 * x ^ 2 + 3 * x + -7) the following structure should be built:

(+  (^ x 3) (+  (* 5 (^ x 2))  (+ (* 3 x) -7)))
Watch out for precedence and left recursion. In addition, to include parentheses in your input, you can use |(| and |)| to treat parentheses as a symbol rather than the start or end of a list. Interface this to the derivative horn clauses, so you can take the derivative of something in infix. Also, you should be able to use the grammar rules to convert a lisp representation of a derivative back into an infix list.
Back to http://www.ics.uci.edu/~pazzani/171-p.html (text only) or http://www.ics.uci.edu/~pazzani/171.html .

Michael Pazzani
Department of Information and Computer Science,
University of California, Irvine
Irvine, CA 92717-3425