An Exploration of Left-Corner Transformations
Andreas Opedal Eleftheria Tsipidi Tiago Pimentel Ryan Cotterell Tim Vieira
The left-corner transformation (Rosenkrantz and Lewis, 1970) is used to
remove left recursion from context-free grammars, which is an important step
towards making the grammar parsable top-down with simple techniques. This paper
generalizes prior left-corner transformations to support semiring-weighted
production rules and to provide finer-grained control over which left corners
may be moved. Our generalized left-corner transformation (GLCT) arose from
unifying the left-corner transformation and speculation transformation (Eisner
and Blatz, 2007), originally for logic programming. Our new transformation and
speculation define equivalent weighted languages. Yet, their derivation trees
are structurally different in an important way: GLCT replaces left recursion
with right recursion, and speculation does not. We also provide several
technical results regarding the formal relationships between the outputs of
GLCT, speculation, and the original grammar. Lastly, we empirically investigate
the efficiency of GLCT for left-recursion elimination from grammars of nine
languages.