Home  |   Notes  |   Languages  |   Programs  |   Homework
Program Assignment 4

80 Points
Due: 4/30/01 at the start of class


Once again, you will be diagramming sentences that match the grammar described for Program 1.

 Implementation Language
For this assignment, your program must be written in Prolog. You will be programming in a "logic programming" style, as described in Chapter 15 of the text book. Since this program must be written in Prolog, appropriate use of logic programming language features is expected. In particular, you may not use any versions of assert, retract, record, erase, flag, or any of the other database features of Prolog.

As with prior programs, your solution must adhere to good programming style, including correct use of parameter passing, identifier naming, predicate length, commenting, headers for each predicate, etc.

 Input Format

Write your program as a Prolog predicate called diagram_sentence. Your predicate should take two arguments: the first is a flat list of strings that represents the input to be diagrammed, and the second is a (nested) list representing the diagrammed result. For example, you might invoke your sentence diagrammer with the following goal:

    ?- diagram_sentence(['Alice', 'found', 'mean', 'green', 'book'], Diagram).

This setup is similar to that in Program 2, in that you are not responsible for reading from standard input or splitting a line into individual tokens (words).

One way to organize your solution (but not the only way, and certainly not a requirement for this program) is to construct one predicate for each nonterminal that takes three parameters: a list of strings representing the incoming sentence fragment, the resulting diagram for that nonterminal (if possible), and a list representing the unparsed remainder. For example:

    /* adj(Words, Diagram, Remainder) */
    adj([Word | Rest], Word, Rest) :-
        Word = 'green';
        Word = 'lean';
        Word = 'mean'.

The predicate adj does the job for <adj>. A sample invocation of adj is

    ?- adj(['green', 'cow', 'saw', 'book'], Diagram, Remainder).

which returns

    Diagram = green;
    Remainder = [cow,saw,book];

 Output Format

For purposes of our Prolog implementation, the "diagram" produced by your program will be a nested Prolog list structure that represents the grammatical structure of the sentence. For example, consider the following sentence:

    mean cow saw carefully green Alice with book

the corresponding Prolog list structure for this sample should be

    [[[mean], cow], [saw, carefully], [[green], Alice, [with, [book]]]]

Your diagram_sentence predicate should produce such a list structure for a sentence that parses successfully, or bind its second argument to a string containing the appropriate error message if the input is in error.

 Submitting Your Program

Your Prolog implementation is to be organized in a single file. All documentation and identifying information should be placed in comments within the single source file. The comments at the beginning of the file should identify the assignment and give your full name. Every Prolog predicate should be preceded by comments explaining its purpose and implementation.

Your program will be submitted electronically through the Curator for automatic grading. To submit your program, login to the Curator using your PID and password. Be sure to select the 11374-CS 3304 11:15 MWF Edwards section when logging in. Click on "Submit", choose Prolog4 from the project drop-down list, click "Browse" to specify your solution, and then click "Upload."

In addition, you must also turn in a printed version of your program source in class according to the rules specified in the syllabus, which also describes the late policy.

Home  |   Notes  |   Languages  |   Programs  |   Homework

copyright © 2001 Virginia Tech, ALL RIGHTS RESERVED
Last modified: April 23, 2001, 15:39:01 EDT, by Stephen H. Edwards <edwards@cs.vt.edu>