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.

该研究论文通过泛化之前的左角转换方法，支持半环加权产生规则，并提供了对可以移动的左角进行更精细控制的能力。该泛化的左角转换方法通过用右递归替换左递归，与猜测转换方法定义了等价的加权语言，同时在生成树结构上存在重要差异。除此之外，对GLCT、猜测转换和原始语法的输出之间的形式关系进行了几项技术结果的探讨，并在九种语言的语法中对GLCT的效率进行了实证研究。

左角转换探索