Elimination of left recursion from context-free grammars

• US 6,449,589 B1
• Filed: 11/16/1999
• Issued: 09/10/2002
• Est. Priority Date: 11/16/1999
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Moore, Robert C.
• Primary Examiner(s): EDOUARD, PATRICK NESTOR
• Application Number:
  US09/441,685
• Time in Patent Office: 1,029 Days
• Field of Search: 704/9-10, 704/1, 704/255, 704/257, 707/530, 707/531, 707/532
• US Class Current: 704/9
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking

Abstract

A method for transforming a first set of rule expressions forming a first grammar to a second set of rule expressions forming a second grammar includes identifying at least one left-recursive category of the first grammar; and applying a left-corner transform to substantially only the left-recursive rule expressions of the first grammar in forming the second grammar.

Claims

1. A method for transforming a first set of rule expressions forming a first grammar to a second set of rule expressions forming a second grammar for use as a language model in a language processing system, the method comprising:

identifying at least one left-recursive category of the first grammar; and

applying a left-corner transform to substantially only the left-recursive category rule expressions of the first grammar in forming the second grammar.

2. The method of claim 1 and further comprising:

reducing the number of rule expressions in the first grammar having a left-recursive category on a left-hand side of an rule expression.

3. The method of claim 2 wherein the step of reducing the number of rule expressions in the first grammar having the left-recursive category on the left-hand side of the rule expression comprises:

replacing a set of rule expressions of the form,

4. The method of claim 3 wherein the step of reducing the number of rule expressions in the first grammar having the left-recursive category on the left-hand side of the rule expression is performed before the step of identifying at least one left-recursive category of the first grammar.

5. The method of claim 3 wherein the step of reducing the number of rule expressions in the first grammar having the left-recursive category on the left-hand side of the rule expression is performed after the step of identifying at least one left-recursive category of the first grammar.

6. The method of claim 3 wherein the step of reducing the number of rule expressions in the first grammar having the left-recursive category on the left-hand side of the rule expression further comprises:

replacing a set of rule expressions of the form,

7. The method of claim 6 and further comprising:

deleting any rule expression of the form, A→

B, from the first grammar, where A occurs only once on the left-hand side within the set of rule expressions in the first grammar and B is a single word or category of the first grammar; and

replacing the category A with B for each occurrence of A in the first grammar.

8. The method of claim 6 and further comprising:

transforming the second grammar to eliminate rule expressions of the form A→

ε

, where A is a category and ε

is an empty string.

9. The method of claim 8 and, after transforming the second grammar to eliminate rule expressions of the form A→

ε

, further comprising;

deleting any rule expression of the form A→

B from the second grammar, where A occurs only once on the left-hand side within the set of rule expressions in the second grammar and B is a single word or category of the second grammar; and

replacing the category A with B for each occurrence of A in the second grammar.

10. The method of claim 1 and further comprising:

transforming the second grammar to eliminate rule expressions of the form Aε

ε

, where A is a category and ε

is an empty string.

11. The method of claim 2 wherein reducing the number of rule expressions in the first grammar having the left-recursive category on the left-hand side of the rule expression comprises:

replacing a set of rule expressions of the form,

12. The method of claim 2 wherein an original grammar is cyclic, and the method further comprises:

transforming the original grammar to be the first grammar, where the first grammar is noncyclic.

13. A method for transforming a first set of rule expressions forming a first grammar to a second set of rule expressions forming a second grammar for use as a language model in a language processing system, the method comprising:

replacing a set of rule expressions of the form,

14. A computer readable medium including instructions readable by a computer which, when implemented, build a language model for use in a language processing system by transforming a first set of expressions forming a first context-free grammar to a second set of expressions forming a second context-free grammar, the instructions comprising:

identifying at least one left-recursive category of the first grammar; and

applying a left-corner transformation to substantially only the left-recursive category expressions of the first grammar in forming the second grammar.

15. The computer readable medium of claim 14 having instructions further comprising:

reducing a number of expressions in the first grammar having a left-recursive category on a left-hand side of an expression.

16. A computer readable medium including instructions readable by a computer which, when implemented, build a language model for use in a language processing system by transforming a first set of expressions forming a first grammar to a second set of expressions forming a second grammar, the method comprising:

replacing a set of expressions of the form,