Elimination of left recursion from context-free grammars

DETAILED DESCRIPTION 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.
The method can be executed on a suitable computer wherein instructions are provided on a computer readable medium.
A second broad aspect of the present invention is a method for building a language model by transforming a first set of rule expressions forming a first grammar to a second set of rule expressions forming a second grammar, the method including: replacing a set of rule expressions of the form, A.
fwdarw.
X.
sub.
1.
beta.
.
sub.
1, .
.
.
, A.
fwdarw.
X.
sub.
n.
beta.
.
sub.
n with A.
fwdarw.
A-non-left-rec A-non-left-rec.
fwdarw.
X.
sub.
1.
beta.
.
sub.
1.
.
.
A-non-left-rec.
fwdarw.
X.
sub.
n.
beta.
.
sub.
n where A is a left-recursive category, X.
sub.
1 .
.
.
X.
sub.
n are each any word or non-left-recursive category of the first grammar, .
beta.
.
sub.
1 .
.
.
.
beta.
.
sub.
n are each a sequence (possibly a null sequence) of words and/or categories of the first grammar, and A-non-left-rec is a newly defined category.
The method can be executed on a suitable computer wherein instructions are provided on a computer readable medium.