Assignment 5: Prolog: A Natural Language for Natural Language
CSE 341: Programming Languages
The University of Washington, Seattle, Winter 2012
Purposes: The purposes of this assignment are (a) to explore the special syntax in Prolog for working with natural language text that has grammatical structure, and (b) to provide an opportunity to develop a small application in Prolog.
Due: Monday, February 13 at 5:00 PM via Catalyst CollectIt.
Individual Work.
Do this assignment individually. DO NOT COLLABORATE on this assignment. This is not a partnership or teamwork assignment.
What to Turn In: You should turn in the following files: 
EnglishishDCG.pl
EnglishishDCG.pdf
The Prolog file should begin with comment lines that give the name of the file, a program name (that is more descriptive and English-like than the filename), the author's (your) name, and a brief description (2-5 lines) of what the program does.

It should contain the definitions of the Prolog predicates ("procedures") that you define.

The PDF file should contain examples of results from your program. There should be a heading at the beginning of your PDF file giving your name, the assignment number, and a few lines of explanation of what the file contains.

Read the Wikipedia article on Definite Clause Grammar. Then, using Prolog's special syntax for definite clause grammars, do the following problems.
  1. (This problem is recommended as a stepping stone to Problem 2, but should not be turned in.) Write a program that generates sentences of the "Englishish" language presented in Assignments 2 and 3. You may rearrange the productions of the grammar so that any left-recursive productions come last among the productions for their LHS non-terminal. Note that you do NOT have to read in the grammar. You may simply hard-code the grammar into the program using definite clauses.
  2. (100 points, required) Write a program that can generate and parse sentences of the "Englishish" language presented in Assignments 2 and 3. The parses should be returned as compound terms in the same manner as illustrated in the Wikipedia article. In your EnglishishDCG.pdf file, show the first 20 sentences generated by your program. Then include the output parsing result for the sentence "John worked quickly under the house and oh my".
  3. (10 points of extra credit). Include a predicate prettyPrint(ParseTree) that will print out the parse trees using hierarchical indentation; the root functor should begin against the left margin; and each argument of that functor should be indented 4 spaces. Any subterm of one of these arguments should be indented four more spaces, etc. Your EnglishishDCG.pdf file should contain an example of output from this predicate for the sample sentence, "John worked quickly under the house and oh my".
Last updated 7 February at 12:01 PM (extra credit section adjusted); previously updated 6 Feb. at 6:04 PM.