An Exploration of Left-Corner Transformations (2023)

Abstract: 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. Code: https://github.com/rycolab/left-corner

## introduction grammar transformations are functions that map one context-free grammar to another. the formal language theory literature contains numerous examples of such transformations, including nullary rule removal, rule binarization, and conversion to normal forms, e.g., those of chomsky (1959) and greibach (1965). in this work, we study and generalize the left-corner transformation (rosenkrantz and lewis, 1970). qualitatively, this transformation maps the derivation trees of an original grammar into isomorphic trees in the transformed grammar. the trees of the transformed grammar will be such that the base subtree of a left-recursive chain (the left corner) is hoisted up in a derivation tree while replacing the left-recursive path to the * equal contribution. left corner with a right-recursive path to an empty constituent. fig. 1 provides an example. a common use case of the left-corner transformation is to remove left recursion from a grammar, which is necessary for converting the grammar to greibach normal form and for several top-down parsing algorithms (aho and ullman, 1972). as an additional effect, it reduces the stack depth of top-down parsing (johnson, 1998), which makes it an interesting method for psycholinguistic applications (roark et al., 2009; charniak, 2010). the closely related left-corner parsing strategy has been argued to be more cognitively plausible than alternatives due to its constant memory load across both left-and right-branching structures and low degree of local ambiguity for several languages (johnson-laird, 1983; abney and johnson, 1991; resnik, 1992); indeed, empirical evidence has shown that certain left-corner parsing steps correlate with brain activity (brennan and pylkkänen, 2017; nelson et al., 2017) and reading times (oh et al., 2022). @xcite this paper uncovers an interesting connection between the left-corner transformation and the speculation transformation (eisner and blatz, 2007). @xcite we show that speculation also hoists subtrees up the derivation tree, as in the left-corner transformation. however, in contrast, it does not remove left recursion. in uncovering the similarity to speculation, we discover that speculation has been formulated with more specificity than prior left-corner transformations: it has parameters that allow it to control which types of subtrees are permitted to be hoisted and which paths they may be hoisted along. we bring this flexibility to the left-corner transformation with a novel generalized left-corner transformation (glct). @xcite it turns out that the latter functionality is provided by the selective left-corner transformation (johnson and roark, 2000); however, the former is new. we provide several new technical results: 4 (i) we prove that glct preserves the weighted languages and that an isomorphism between derivation trees exists (theorem 1). (ii) we provide explicit methods for mapping back and forth between the derivation trees (algs. 1 and 2). (iii) we prove that the set of derivation trees for speculation and glct are isomorphic (theorem 2). (iv) we prove that our glct-based left-recursion elimination strategy removes left recursion (theorem 4). additionally, we empirically investigate the efficiency of glct for left-recursion elimination from grammars of nine different languages in §4.1. ## preliminaries this section provides the necessary background on the concepts pertaining to semiring-weighted context-free grammars that this paper requires. definition 1. a semiring is a tuple ⟨w, ⊕, ⊗, 0, 1⟩ where w is a set and the following hold: the semiring is commutative if ⊗ is commutative. we highlight a few commutative semirings and their use cases: • boolean ⟨{⊥, ⊤}, ∨, ∧, ⊥, ⊤⟩: string membership in a language, • nonnegative real ⟨@xmath0, +, •, 0, 1⟩: the total probability of a string, • viterbi ⟨[0, 1], max, •, 1, 0⟩: the weight of the most likely derivation of a string. for further reading on semirings in nlp, we recommend goodman (1999) and huang (2008). our work studies weighted context-free grammars (wcfgs), which define a tractable family of weighted languages-called weighted context-free languages-that is frequently used in nlp applications (see, e.g., jurafsky and martin, 2020). we will use the following notational conventions: • x, y, @xmath1, b, @xmath2, y, @xmath3, β, γ ∈ (v ∪n ) for a terminal or nonterminal symbol • α, β, γ ∈ (v ∪ n ) * for a sequence of nonterminals or terminals • @xmath4, v, s, r⟩ and when describing a grammar and its rules, we may use the following terms: the size of a grammar is (x-→α)∈r (1+|α|). the arity of a rule x -→ α is equal to |α|; thus, a rule is nullary if |α| = 0, unary if |α| = 1, and so on. for technical reasons, it is often convenient to eliminate nullary rules from the grammar. @xcite a derivation is a rooted, (n ∪ v)-labeled, ordered tree where each internal node must connect to its children by a production rule. @xcite to access the root label of a derivation δ, we write ℓ(δ). the set of all derivations of g is the smallest set d satisfying the weighted language of α ∈ (v ∪ n ) is a function g α : v * → w defined as follows: given a set of symbols x , we write d x as shorthand for α∈x d α . lastly, let δ denote the weighted language generated by the tree δ. @xcite we define the following operations on weighted languages g and g ′ , for @xmath5: note that these operations form a (noncommutative) semiring over weighted languages where 0 is the language that assigns weight zero to all strings @xcite formally, δ (x and 1 is the language that assigns one to the empty string and zero to other strings. the weighted language of g may also be expressed as a certain solution foot_4 to the following system of equations: we say that grammars g and g ′ are equal (@xmath6. we say they are equivalent (g ≡ g ′ ) if they define the same weighted language. @xcite we say that they are a benefit of this stronger notion of equivalence is that derivations in g and g ′ are interconvertible: we can parse in g and convert to a parse in g ′ and vice versa, assuming @xmath7. foot_6 ## transformations this section specifies our novel generalized leftcorner transformation, its correctness guarantees, and its connections to prior left-corner transformations. we also describe the speculation transformation (eisner and blatz, 2007) and discuss the connections between the speculation transformation and our generalized left-corner transformation. ## left-recursion elimination motivated by the desire for efficient top-down parsing for which left-recursion poses challenges ( §1), we describe how glct may be used to transform a possibly left-recursive grammar g into a bijectively equivalent grammar g ′ without left-recursion. @xcite the bijective equivalence (theorem 1) ensures that we can apply an inverse transformation to the derivation tree of the transformed grammar into its corresponding derivation tree in the original grammar. this section provides an efficient and (provably correct) recipe for left-recursion elimination using glct. we experiment with this recipe on natural language grammars in §4.1. our left-recursion elimination recipe is based on a single application of glct, which appropriately chooses parameters c and r. we describe how to determine these parameters by analyzing the structure of the rules in g. we define the left-recursion depth of a derivation tree d(δ) as the length of the path from the root to the leftmost leaf node. the left-recursion depth of a grammar is d(g) to analyze whether g is left-recursive, we can analyze its left-recursion graph, which accurately characterizes the left-recursive paths from the root of a derivation to its leftmost leaf in the set of deriva- it should be clear that the g is left-recursive iff g has a cyclic subgraph. we classify a rule r as left-recursive if the edge labeled r is an edge in any cyclic subgraph of g. to determine the set of left-recursive rules, we identify the strongly connected components (sccs) of g (e.g., using tarjan's (1972) algorithm). the scc analysis returns a function π that maps each of g's nodes to the identity of its scc. then, a rule r is leftrecursive iff its corresponding edge α r -→ β satisfies π(α) = π(β). @xcite to ensure that left recursion is eliminated, r must include all left-recursive rules. we use the following set to provide a sufficient condition on c to eliminate left recursion: this set captures the set of nodes that may appear at the bottom of a spine (for the given r). this is because the spine is defined as the longest sequence of rules in r along the left of a derivation; thus, a spine can end in one of two ways (1) it reaches a terminal, or (2) it encounters a rule outside of r. thus, the bottom elements of the spine are the set of terminals, and the set of nodes with at least one (r \ r)-labeled outgoing edge-which we refine to nodes that might appear in the spine (i.e., those in the leftmost position of the rules in r). with these definitions in place, we can provide sufficient conditions on the glct parameter sets that will remove left recursion: ## conclusion this work generalized the left-corner transformation to operate not only on a subset of rules but also on a subset of nonterminals. we achieve this by adapting frozen nonterminals from the speculation transformation. we exposed a tight connection between generalized left-corner transformation and speculation (theorem 2). finally, and importantly, we proved the transformation's correctness (theorem 1) and provided precise sufficient conditions for when it eliminates left recursion (theorem 4).