Grammar authoring system

• US 20030121026A1
• Filed: 12/05/2001
• Published: 06/26/2003
• Est. Priority Date: 12/05/2001
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Acero, Alejandro, Wang, Ye-Yi
• Granted Patent: US 7,080,004 B2
• Time in Patent Office: Days
• US Class Current: 717/124
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars

Abstract

A grammar authoring system uses multiple sources of information to aid grammar authoring. This produces a semantic grammar derived semi-automatically with a relatively small amount of data.

Claims

1. A method of building a learned context free grammar (CFG) for an application, comprising:

generating a semantic schema for the application, the semantic schema having associated semantic constraints;

generating a template grammar based on the semantic schema such that the template grammar inherits the semantic constraints associated with the semantic schema; and

building the learned CFG by parsing training expressions using the template grammar.

2. The method of claim 1 wherein building the learned CFG comprises:

obtaining a training expression.

3. The method of claim 2 wherein building the learned CFG comprises:

providing an annotated training expression by annotating the training expression against the semantic schema to provided one or more anchor points that are known correct alignments between the training expression and one or more preterminals in the template grammar.

4. The method of claim 3 wherein building the learned CFG further comprises:

parsing the annotated expression to produce a parse result that complies with the anchor points.

5. The method of claim 4 wherein building the learned CFG further comprises:

learning alignments for a remainder of the training expression, other than portions aligned at the anchor points, with the template CFG.

6. The method of claim 5 wherein learning alignments comprises:

obtaining a set of preselected syntactic constraints; and

employing the syntactic constraints to learn alignments for the remainder of the training expression.

7. The method of claim 5 wherein learning alignments comprises:

identifying as ambiguities a pluralities of different potential alignments of words in the training expression with preterminals in the template CFG.

8. The method of claim 7 wherein learning alignments further comprises:

providing an output query to a user, the output query prompting a clarifying user input to disambiguate the ambiguities; and

receiving the clarifying user input.

9. The method of claim 8 wherein providing an output query comprises:

providing the potential alignments as a plurality of user selectable alignment options.

10. The method of claim 2 and further comprising:

parsing the training expression to produce a parse result;

displaying an abstraction of the parse result; and

receiving a correction input, indicative of a user correction to the parse result.

11. The method of claim 10 wherein the correction input annotates at least one anchor point that is a known correct alignment between the training expression and a preterminal in the template grammar.

12. The method of claim 11 wherein receiving the correction input comprises:

receiving a selection input selecting an incorrectly aligned portion of the training expression in the parse result;

receiving a movement input indicative of a user dragging the incorrectly aligned portion to a correct object in the abstraction of the parse result; and

receiving a placement input indicative of a user dropping the incorrectly aligned portion on the correct object in the abstraction of the parse result.

13. The method of claim 12 and further comprising:

re-parsing the training expression to produce a new parse result that complies with the anchor point; and

displaying a new abstraction of the new parse result.

14. The method of claim 1 wherein building the learned CFG comprises:

associating at least one pre-existing library grammar with the template grammar based on a user input.

15. The method of claim 14 wherein associating at least one pre-existing library grammar with the template grammar comprises:

selecting one of a plurality of available library grammars; and

operating the selected library grammar in a generative mode to generate at least one example of an expression supported by the selected library grammar.

16. The method of claim 14 wherein building the learned CFG comprises:

simultaneously displaying an indication of the semantic schema and an indication of available library grammars;

selecting one of the library grammars;

dragging the selected library grammar to a desired place in the semantic schema;

dropping the selected library grammar; and

associating the selected library grammar with the template grammar.

17. A method of building a learned context free grammar (CFG) comprising:

generating a semantic schema for the learned CFG;

obtaining a template CFG;

receiving a training expression;

providing an annotated expression by annotating the training expression against the semantic schema to provide at least one anchor point that is a known correct alignment between a portion of the training expression and the template CFG;

parsing the annotated expression to provide a parse result that complies with the anchor point; and

building the learned CFG based on the parse result.

18. The method of claim 17 wherein obtaining a template CFG includes generating a template CFG based on the semantic schema, and wherein parsing the annotated expression comprises:

parsing the annotated expression with the template CFG.

19. The method of claim 18 wherein building the learned CFG comprises:

learning alignments of a remainder of the training expression, other than the portion aligned at the anchor point, with the template CFG.

20. A system for developing a domain-specific, context free grammar (CFG), comprising:

a template grammar generator receiving a semantic schema and generating a template grammar that inherits the semantic constraints from the semantic schema;

an annotation interface receiving a user annotation input indicative of a user designated anchor point that is an alignment of at least a portion of a training expression with the semantic schema;

a parser, coupled to the template grammar generator and the annotation interface, receiving the template grammar and the user annotation input and parsing the training expression to provide a parse result that complies with the anchor points; and

a learner, coupled to the parser, learning the domain-specific CFG based on the parse result.

21. The system of claim 20 and further comprising:

a grammar manager configured to access a library of pre-existing grammars, to receive a user association input, and to associate a selected pre-existing grammar with the learned CFG based on the user association input.

22. The system of claim 21 wherein the learner is configured to operate at least one of the pre-existing grammars in a generative mode generating examples of expressions supported by the pre-existing grammar.

23. The system of claim 20 wherein the learner is configured to resolve ambiguities in the parse result by prompting a user for additional alignment inputs, in addition to the anchor point, to align the training expression with the template grammar.

24. The system of claim 20 wherein the learner is configured to employ predetermined syntactic constraints in learning the learned CFG to limit portions of the training expression for which alignments with the template CFG must be learned.

25. A method of generating a context free grammar (CFG), comprising:

generating an underspecified template CFG;

annotating a training expression, against an abstraction of the template CFG, with one or more anchor points aligning portions of the training expression with preterminals in the CFG;

parsing the training expression with the template CFG to provide a parse result, given the anchor points;

learning alignments of the training expression with the template CFG, in addition to the anchor points; and

adding CFG rules to the template CFG to reflect the learned alignment and anchor points.

26. The method of claim 25 and further comprising:

receiving user correction inputs indicative of a user correction of the parse result.

27. The method of claim 26 wherein learning alignment comprises:

accessing pre-existing syntactic constraints; and

utilizing the pre-existing syntactic constraints to learn the alignments by limiting portions of the training expression for which alignments with the template CFG must be learned.

28. The method of claim 26 wherein learning alignments comprises:

using the user correction of the parse result as an anchor point.

29. The method of claim 25 wherein learning alignments comprises:

identifying ambiguities in the parse result; and

prompting user alignment inputs to disambiguate the ambiguities.

30. The method of claim 25 and further comprising:

associating pre-existing library CFG rules with the template CFG based on a user association input of the pre-existing library CFG rules with the abstraction of the template CFG.

31. The method of claim 30 wherein the user association input comprises:

dragging a graphic representation of a pre-existing library CFG containing the pre-existing library CFG rules from one portion of a display to another portion of the display that is a desired place in a graphic representation of the abstraction of the template CFG; and

dropping the graphic representation of the pre-existing library CFG at the desired place.

32. A method of generating a context free grammar (CFG) for an application in an application domain, comprising:

generating an underspecified template CFG;

displaying a schema of the application domain instead of the CFG;

annotating a training expression against the schema instead of the template CFG, identifying one or more points of alignment between the training expression and the template CFG;

parsing the training expression with the template CFG to provide a parse result that complies with the points of alignment;

learning alignments of the training expression with the CFG; and

adding CFG rules to the template CFG to reflect the learning alignments.