Assignment 2

Natural Language Generation (201-2454101)

This assignment builds on the bottom-up parser studied in class: Norvig's Common Lisp implementation of a bottom-up parser with semantics.

Question 1: Top-down parser

Write a top-down parser. The top-down parser should be shorter (in code) than the bottom-up one. It should return all possible parses in a list. Can both parsers work with the same grammar? What constraints does each parsing strategy impose on the rules?

Question 2: Extended grammar

Imagine an interface to a dual tape recorder. The CD player only had one verb, "play", left implicit in the semantics (which was an ordered list of tracks to play). The new unit contains three devices - CD, Tape1 and Tape2 - and it can do three types of operations:
  1. Play: from one of the devices
  2. Record: from one of the devices to one of the tapes
  3. Erase: from one of the tapes
The unit also contains a timer to determine when to start an operation. The meaning of an expression in this case will be a program with the following predicates:
  1. (play <list of tracks> :from <unit>)
  2. (record <list of tracks> :from <unit> :to <unit>)
  3. (erase <list of tracks> :from <unit>)
Assume that the :from and :to parameters have appropriate defaults. In addition, the timer parameter can be added to all the predicates, as follows: 
> (meaning '(play 1 to 5 from CD and record 1 to 5 from CD at 300))

(PROGN (play '(1 2 3 4 5) :from 'cd)
       (record '(1 2 3 4 5) :from 'cd :at 300))
Extend the grammar *grammar6* to support this new situation. You may have to change the support function meaning as well.

Question 3: Generate from Semantics

In this question we want to use the same grammar *grammar6* to generate sentences from their semantics. In this case, the original semantics is a sequence of track numbers. Write the following function: 
(generate-all <list-of-number> <depth>)
The function must work in 3 stages to operate correctly:
  1. Content organization: turn the list of numbers into a list of structured representations using the following semantic predicates: 
         (sequence <from> <to>)
     (set-diff <set1> <set2>)
     (set-union <set1> <set2>)
    Only the structures of depth less than or equal to <depth> will be returned.
  2. Realization: turn the structured representation into a parse tree using the rules of the grammar.
  3. Linearization: turn the parse tree into a linear string.
Accordingly write the following functions: 
  1. (structure <list-of-numbers> <depth>)
    Given a list of numbers, return all the possible semantic structures using the 3 predicates listed above and of maximum depth <depth> and that evaluate to the desired list of numbers. 
  2. (realize <semantic-structure>)
    Given a semantic structure, turn it into a parse tree according to the rules of *grammar6*. 
  3. (linearize <parse-tree>)
    Given a parse tree, return an ordered list of words.
Finally, write a function: 
(generate-best <list-of-number> <scoring-function>)
which returns the "best" sentence for a given semantics according to the scoring function. For example, one scoring function can count the number of words (shortest sentence is best) or the syntactic complexity (minimum number of constituents). Experiment to find a scoring function that will eliminate semantically bizarre sentences (for example, those where the same numbers are repeated).
The end.