Natural Language Generation (201-1-2971-1)
Notes Week 4 - Spring 1996 - Michael Elhadad
previous class main page next class

Using FUF

See also:

A Simple Grammar

This code is in the following file: gsimple.l: 
((alt GSIMPLE ( 
   ;; a grammar always has the same form: an alternative
   ;; with one branch for each constituent category.

   ;; First branch of the alternative
   ;; Describe the category clause.
   ((cat clause)
    (agent    ((cat np)))
    (affected ((cat np)))
    (action   ((cat verb-group)
	       (number {agent number})))
    (cset (action agent affected))
    (pattern  (agent action affected)))

   ;; Second branch: NP
   ((cat np)
    (head ((cat noun) (lex {^ ^ lex})))
    (number  ((alt np-number (singular plural))))
    (alt (  ;; Proper names don't need an article
            ((proper yes)
             (pattern (head)))

            ;; Common names do
            ((proper no)
             (pattern (det head))
             (det ((cat article) (lex "the")))))))

   ;; Third branch: Verb
   ((cat verb-group)
    (pattern (v))
    (aux none)
    (v ((cat verb) (lex {^ ^ lex}))))

   ((cat article)))))

A simple input

Input to generate: The system advises John.

I1 =	((cat clause)
         (tense present)
   	 (action   ((lex "advise")))
	 (agent    ((lex "system") (proper no)))
	 (affected ((lex "John"))))

Unification Process

  1. Top level unification 
    	((cat clause)
         (tense present)
   	 (action   ((lex "advise")
		    (CAT VERB)
		    (NUMBER {AGENT NUMBER})))
	 (agent    ((lex "system") (proper no)
		    (CAT NP)))
	 (affected ((lex "John")
		    (CAT NP)))
	 (CSET (ACTION AGENT AFFECTED))
	 (PATTERN (AGENT ACTION AFFECTED)))
  2. Identify CSET: (action agent affected)
  3. Recursively traverse the constituent structure breadth-first
  4. Output of the total unification: 
    	((cat clause)
         (tense present)
   	 (action   ((lex "advise")
		    (cat verb-group)
		    (number {agent number})
		    (PATTERN (V))
		    (AUX NONE)
		    (V ((CAT VERB) (LEX {^ ^ LEX})))))
	 (agent    ((lex "system") (proper no)
		    (cat np)
		    (HEAD ((CAT NOUN) (LEX {^ ^ LEX})))
		    (NUMBER SINGULAR)
	 	    (PATTERN (DET HEAD))
		    (DET ((CAT ARTICLE) (LEX "the")))))
	 (affected ((lex "John")
		    (cat np)
		    (HEAD ((CAT NOUN) (LEX {^ ^ LEX})))
	 	    (NUMBER SINGULAR)
		    (PROPER YES)
		    (CSET (HEAD))
	 	    (PATTERN (HEAD))))
	 (cset (action agent affected))
	 (pattern (agent action affected)))
  5. Determination: post-processing of the unified input. (cf later why needed.)
  6. Linearization: traverse the tree of "pattern" indications until leaves are reached.

Tracing the Unifier

LISP> (trace-on)
LISP> (uni (get-test 'i1))

>========================================
>STARTING CAT CLAUSE AT LEVEL {}
>========================================


-->Entering alt GSIMPLE -- Jump indexed to branch #1: CLAUSE matches input CLAUSE
-->Updating (CAT NIL :E) with NP at level {AGENT CAT}
-->Updating (CAT NIL :E) with NP at level {AFFECTED CAT}
-->Updating (CAT NIL :E) with VERB-GROUP at level {ACTION CAT}
-->Enriching input with (NUMBER {AGENT NUMBER} NIL) at level {ACTION}
-->Enriching input with (CSET (ACTION AGENT AFFECTED) NIL) at level {}
-->Enriching input with (PATTERN (AGENT ACTION AFFECTED) NIL) at level {}
-->Success with branch #1 CLAUSE in alt GSIMPLE

>Expanding constituent {} into cset ({AFFECTED} {AGENT} {ACTION}).
>

>========================================
>STARTING CAT NP AT LEVEL {AFFECTED}
>========================================


-->Entering alt GSIMPLE -- Jump indexed to branch #2: NP matches input NP
-->Updating (CAT NIL :E) with NOUN at level {AFFECTED HEAD CAT}
-->Enriching input with (LEX {AFFECTED LEX} NIL) at level {AFFECTED HEAD}
---->Entering alt NP-NUMBER -- Branch #1
---->Updating (NUMBER NIL :E) with SINGULAR at level {AFFECTED NUMBER}
---->Success with branch 1 in alt NP-NUMBER

-->Updating (PROPER NIL :E) with YES at level {AFFECTED PROPER}
-->Enriching input with (PATTERN (HEAD) NIL) at level {AFFECTED}
-->Success with branch #2 NP in alt GSIMPLE

>Expanding constituent {AFFECTED} into cset ({AFFECTED HEAD}).
>

>========================================
>STARTING CAT NP AT LEVEL {AGENT}
>========================================


-->Entering alt GSIMPLE -- Jump indexed to branch #2: NP matches input NP
-->Updating (CAT NIL :E) with NOUN at level {AGENT HEAD CAT}
-->Enriching input with (LEX {AGENT LEX} NIL) at level {AGENT HEAD}
---->Entering alt NP-NUMBER -- Branch #1
---->Updating (NUMBER NIL :E) with SINGULAR at level {AGENT NUMBER}
---->Success with branch 1 in alt NP-NUMBER

-->Fail in trying NO with YES at level {AGENT PROPER}
-->Enriching input with (PATTERN (DET HEAD) NIL) at level {AGENT}
-->Updating (CAT NIL :E) with ARTICLE at level {AGENT DET CAT}
-->Updating (LEX NIL :E) with "the" at level {AGENT DET LEX}
-->Success with branch #2 NP in alt GSIMPLE

>Expanding constituent {AGENT} into cset ({AGENT HEAD} {AGENT DET}).
>

>========================================
>STARTING CAT VERB-GROUP AT LEVEL {ACTION}
>========================================


-->Entering alt GSIMPLE -- Jump indexed to branch #3: VERB-GROUP matches input VERB-GROUP
-->Enriching input with (PATTERN (V) NIL) at level {ACTION}
-->Updating (AUX NIL :E) with NONE at level {ACTION AUX}
-->Updating (CAT NIL :E) with VERB at level {ACTION V CAT}
-->Enriching input with (LEX {ACTION LEX} NIL) at level {ACTION V}
-->Success with branch #3 VERB-GROUP in alt GSIMPLE

>Expanding constituent {ACTION} into cset ({ACTION V}).
>Constituent {AFFECTED HEAD} is a leaf.
>Constituent {AGENT HEAD} is a leaf.
>

>========================================
>STARTING CAT ARTICLE AT LEVEL {AGENT DET}
>========================================


-->Entering alt GSIMPLE -- Jump indexed to branch #4: ARTICLE matches input ARTICLE
-->Success with branch #4 ARTICLE in alt GSIMPLE

>Constituent {AGENT DET} is a leaf.
>Constituent {ACTION V} is a leaf.

[Used 6 backtracking points - 1 wrong branches - 0 undos]
>Constituent {AFFECTED HEAD} is a leaf.
>Constituent {AGENT HEAD} is a leaf.
>Constituent {ACTION V} is a leaf.

[Used 6 backtracking points - 1 wrong branches - 0 undos]
The system advises John.
When unification fails: 
FUG5(11): (def-test i2
            ""
            ((cat clause) 
             (agent   ((lex "John") (number singular)))
             (action  ((lex "advise") (number plural)))
             (goal    ((lex "Mary")))))

FUG5(12): (test :item 'i2)

====================
I2 --> ""
>
>========================================
>STARTING CAT CLAUSE AT LEVEL {}
>========================================

-->Entering alt GSIMPLE -- Jump indexed to branch #1: CLAUSE matches input CLAUSE
-->Updating (CAT NIL :E) with NP at level {AGENT CAT}
-->Updating (CAT NIL :E) with NP at level {AFFECTED CAT}
-->Updating (CAT NIL :E) with VERB-GROUP at level {ACTION CAT}
-->Fail in trying PLURAL with SINGULAR at level {ACTION NUMBER}
OK
====================
Less verbose trace: 
LISP> (trace-level 30)  ;; This only indicates failures in alt branches
LISP> (test :item 'i1)

====================
I1 --> "The system advises John."

[Used 6 backtracking points - 1 wrong branches - 0 undos]

[Used 6 backtracking points - 1 wrong branches - 0 undos]
OK
====================


FUG5(15): (trace-level 20) ;; This shows progression of constituent structure
20
FUG5(16): (test :item 'i1)

====================
I1 --> "The system advises John."
>
>========================================
>STARTING CAT CLAUSE AT LEVEL {}
>========================================
>Expanding constituent {} into cset ({AFFECTED} {AGENT} {ACTION}).

>========================================
>STARTING CAT NP AT LEVEL {AFFECTED}
>========================================
>Expanding constituent {AFFECTED} into cset ({AFFECTED HEAD}).

>========================================
>STARTING CAT NP AT LEVEL {AGENT}
>========================================
>Expanding constituent {AGENT} into cset ({AGENT HEAD} {AGENT DET}).

>========================================
>STARTING CAT VERB-GROUP AT LEVEL {ACTION}
>========================================
>Expanding constituent {ACTION} into cset ({ACTION V}).
>Constituent {AFFECTED HEAD} is a leaf.
>Constituent {AGENT HEAD} is a leaf.

>========================================
>STARTING CAT ARTICLE AT LEVEL {AGENT DET}
>========================================
>Constituent {AGENT DET} is a leaf.
>Constituent {ACTION V} is a leaf.

[Used 6 backtracking points - 1 wrong branches - 0 undos]
>Constituent {AFFECTED HEAD} is a leaf.
>Constituent {AGENT HEAD} is a leaf.
>Constituent {ACTION V} is a leaf.

[Used 6 backtracking points - 1 wrong branches - 0 undos]
OK
====================

Linearization procedure

The linearization procedure includes the following steps:
  1. Identify the pattern feature in the top level: for I1, it is (pattern (agent action affected)).
  2. If a pattern is found:
    1. For each constituent of the pattern, recursively linearize the constituent. (That means linearize agent, action and affected).
    2. The linearization of the FD is the concatenation of the linearizations of the constituents in the order prescribed by the pattern feature.
  3. If no pattern is found:
    1. Find the lex feature of the FD, and depending on the category of the constituent, the morphological features needed. For example, if the FD is of (cat verb), the features needed are: person, number, tense.
    2. Send the lexical item and the appropriate morphological features to the morphology module. The linearization of the fd is the resulting string. For example, for (lex="advise") when the features are the default values (as they are in I1), the result is advises. When the FD does not contain a morphological feature, the morphology module provides reasonable defaults.
If a pattern contains a reference to a constituent and that constituent does not exist, nothing happens: the linearization of an empty constituent is the empty string. Finally, if one of the constituent sent to the morphology is not a known morphological category, the morphology module can not perform the necessary agreements, and returns the lex string unchanged.

Morphology coverage

Only the leaves of the constituent structure are sent to the morphology module. In the FUF implementation, the coverage of the morphology module is as follows:
CAT VERB
ENDING: {ROOT, INFINITIVE, PAST-PARTICIPLE, PRESENT-PARTICIPLE}
NUMBER: {SINGULAR, PLURAL}
PERSON: {FIRST, SECOND, THIRD}
TENSE : {PRESENT, PAST}
CAT NOUN
NUMBER: {SINGULAR, PLURAL}
POSSESSIVE: {YES, NO}
A-AN: {AN, CONSONANT}
CAT PRONOUN
PRONOUN-TYPE: {PERSONAL, DEMONSTRATIVE, QUESTION, QUANTIFIED}
CASE: {SUBJECTIVE, POSSESSIVE, OBJECTIVE, REFLEXIVE}
GENDER: {MASCULINE, FEMININE, NEUTER}
PERSON: {FIRST, SECOND, THIRD}
NUMBER: {SINGULAR, PLURAL}
DISTANCE: {NEAR, FAR}
CAT ARTICLE
NUMBER: {SINGULAR, PLURAL}
DEFINITE: {YES, NO}
A-AN: of following word.
PUNCTUATION
BEFORE: {";", ",", ":", "(", ")", ...}
AFTER : {";", ",", ":", "(", ")", ...}
ORDINAL, CARDINAL
VALUE: a number
DIGIT: {YES, NO}

Last modified March 31st, 1996 Michael Elhadad