Method of parsing unification based grammars using disjunctive lazy copy links

• US 5,727,222 A
• Filed: 12/14/1995
• Issued: 03/10/1998
• Est. Priority Date: 12/14/1995
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Maxwell, John T. III
• Primary Examiner(s): Hayes, Gail O.
• Assistant Examiner(s): Bainbridge, Barton L.
• Application Number:
  US08/572,393
• Time in Patent Office: 817 Days
• Field of Search: 395/759, 395/792, 395/793, 395/758
• US Class Current: 704/9
• CPC Class Codes: G06F 40/253 Grammatical analysis; Style critique

Abstract

A method of unifying feature structures using disjunctive lazy copy links. The method begins with unification of two daughter feature structures to generate their mother feature structure. Lazy copy links point from the mother feature structure back to her daughter feature structures. If unification activates any of these lazy copy links, then a selected one of the two daughter feature structures is expanded. Expansion of a disjunctive feature structure may generate a number of alternative feature structures. If so, the alternative feature structures are examined to determine if their number can be reduced by replacing multiple feature structures with one feature structure having multiple disjunctive lazy copy links, each disjunctive lazy copy link pointing to an alternative value. Two or more feature structures can be merged together if they have the same attributes and attribute values. Unification of the two daughter feature structures then resumes, an attribute at a. Whenever the unification of an attribute activates a lazy copy link, expansion is again triggered. The process of expanding, merging, and unifying is repeated until a mother feature structure is generated that includes no activated lazy copy links.

Claims

1. A method of parsing a language string using a unification based grammar that includes disjunctive lazy copy links, the method being executed by a processor coupled to a memory storing instructions for implementing the method, the method comprising the steps of:

a) unifying a first disjunctive feature structure associated with a first constituent and a second disjunctive feature structure associated with a second constituent to generate a third feature structure associated with a third constituent, the first disjunctive feature structure having a first attribute and two disjunctive lazy copy links, each disjunctive lazy copy link pointing to an alternative value of the first attribute, the third feature structure being underspecified and having a first lazy copy link to the first disjunctive feature structure;

b) if unification activates the first lazy copy link, expanding the specification of the first disjunctive feature structure to generate a first multiplicity of alternative feature structures, each of the first multiplicity of alternative feature structures being further specified than the first disjunctive feature structure and having at least one attribute, each attribute having a value;

c) if possible, reducing the first multiplicity of alternative feature structures to a first minimum of first disjunctive feature structures by merging together those of the first alternative feature structures having a first set of identical attributes to create a one of the first minimum disjunctive feature structures, the one of the first minimum disjunctive features having the first set of identical attributes and having at least a pair of disjunctive lazy copy links pointing to alternative values within the alternative feature structures merged together; and

d) unifying the first minimum of first feature structures with the second feature structure to increase the level of specification of the third feature structure, the third feature structure having at least one lazy copy link to the first feature structures.

2. The method of claim 1 further comprising the step of:

e) if a one of the lazy copy links from the third feature structure to the first minimum of first feature structures is activated;

1) expanding a one of the first minimum of first feature structures pointed to by the one of the lazy copy links into a second multiplicity of first alternative feature structures;

2) if possible, reducing the second multiplicity of first alternative feature structures to a second minimum of first feature structures by merging together those of the second multiplicity of first feature structures having a second set of identical attributes to generate a one of the second minimum of first feature structures, the one of the second minimum of first feature structures having the second set of identical attributes and at least a pair of disjunctive lazy copy links pointing to alternative values within the second multiplicity of first alternative feature structures;

3) unifying the second minimum of first feature structures with the second feature structure to increase the level of specification of the third feature structure, the third feature structure having lazy copy links to the first feature structures;

4) if a one of the lazy copy links from the third feature structure to a one of the second minimum of first feature structures is activated, repeating steps e1) through e3) until the third feature structure includes only non-activated lazy copy links.

3. An article of manufacture comprising:

a) a memory; and

b) instructions stored in the memory, the instructions representing a method of parsing a natural language string using a unification based grammar that includes disjunctive lazy copy links to take advantage of context-freeness, the method being executed by a processor coupled to the memory, the method comprising the steps of;

1) unifying a first disjunctive feature structure associated with a first constituent and a second disjunctive feature structure associated with a second constituent to generate a third feature structure associated with a third constituent, the first disjunctive feature structure having a first attribute and two disjunctive lazy copy links, each disjunctive lazy copy link pointing to an alternative value of the first attribute, the third feature structure being underspecified and having a first lazy copy link to the first disjunctive feature structure;

2) if unification activates the first lazy copy link, expanding the specification of the first disjunctive feature structure to generate a first multiplicity of alternative feature structures, each of the first multiplicity of alternative feature structures being further specified than the first disjunctive feature structure and having at least one attribute, each attribute having a value;

3) if possible, reducing the first multiplicity of alternative feature structures to a first minimum of first disjunctive feature structures by merging together those of the first alternative feature structures having a first set of identical attributes to create a one of the first minimum disjunctive feature structures, the one of the first minimum disjunctive features having the first set of identical attributes and having at least a pair of disjunctive lazy copy links pointing to alternative values within the alternative feature structures merged together; and

4) unifying the first minimum of first feature structures with the second feature structure to increase the level of specification of the third feature structure, the third feature structure having at least one lazy copy link to the first feature structures.