An Exploration of Left-Corner Transformations
Authors: Andreas Opedal
Eleftheria Tsipidi
Tiago Pimentel
Ryan Cotterell
Tim Vieira
Venue: EMNLP 2023 Main (2023)
Keywords: left-corner transformation
top-down parsing
left-recursion
grammar transformations
speculation
formal language theory
weighted CFG
left-corner transform
TL;DR: The left-corner grammar transformation is typically used to remove left-recursion. We generalize it, motivated by the speculation transformation.

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

An Exploration of Left-Corner Transformations
Andreas Opedal Eleftheria Tsipidi Tiago Pimentel 1.3
Ryan Cotterell' Tim Vieira'
EET Zürich
Max Planck ETH Center for Learning Systems University of Cambridge
(andreas. opedall.ppaall... mmndreas.opedalleleftheeee eleffheria tsipidi, ryan. wotterellleint ethz.ch
tp472@cam. ac. uk
tim. viei ra@gmail com
Abstract
The left-corner transformation (Rosenkrantz and Lewis, 1970) is used to remove left recur- sion from context-free grammars, which an important step towards making the grammar parsable top-down with simple techniques. This paper generalizes prior left-corner transfor- mations to support semiring-weighted produc- tion rules and to provide finer-grained control which left corners may be moved. Our generalized left-comner transformation (GLCT) arose from unifying the left-comer transforma- tion 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 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 nine languages.
NP
VP
NP
#JSP
NN
My sister
's
8/PouP
NP
diploma
NN
//PP
My sister
diploma
VP
arrived
Figure Left: example derivation containing left- recursive rules. Right: The corresponding derivation after our left-corner transformation. Observe that (i) the lower NP subtree has been hoisted up the tree, (ii) the left recursion from NP to NP has been replaced with right recursion from S/NP to S/NP.
left corner with a right-recursive path to an empty constituent. Fig. 1 provides an example.
A common case of the left-corner transfor- mation to remove left recursion from grammar, which 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 appli- cations (Roark al., 2009; Charniak, 2010). The closely related left-corner parsing strategy has been argued to more cognitively plausible than alter- natives due to its constant memory load across both left- and right bratthbranching 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).'
https://github hetggithub.ccoorreee com/rycolab/ left-corner
1 Introduction
Grammar transformations are functions that map one context-free grammar to another. The formal language theory literature contains numerous ex- amples of such transformations, including nullary rule removal, rule binarization, and conversion to normal forms, c.g., those of Chomsky (1959) and Greibach (1965). In this work, we study and gener- alize the left-corner transformation (Rosenkrantz and Lewis, 1970). Qualitatively, this transforma- tion maps the derivation trees of an original gram- mar into isomorphic trees in the transformed gram- mar. The trees of the transformed grammar will be such that the base subtree of left-recursive chain (the left corner) is hoisted up in derivation tree while replacing the left-recursive path to the
This paper uncovers an interesting connec- tion between the left-corner transformation and
'Morovvrr, statistical left-corner pansers have proven them- selves empirically effective for several grammar formalisms (Roark and Johnson, 1999; Roark, 2001; Díaz et al., 2002; Noji and Miyao, 2014; Noji et al., 2016; Shain et al., 2016; Stanojević and Stabler, 2018; Kitaev and Klein, 2020).
Equal contribution.

---

the speculation transformation (Lisner and Blatz, 2007). We show that speculation also hoists sub- trees up the derivation tree, as 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-comnr transformations: it has parameters that allow it to control which types of subtrees are per- mitted to be hoisted and which paths they may be hoisted along. We bring this flexibility to the left-comer transformation with a novel generalized left-corner transformation (GLCT). It turns out that the latter functionality is provided by the selec- tive left-corner transformation (Johnson and Roark, 2000); however, the former is new.
The semiring is commutative i is commutative.
We highlight few commutative semirings and their use cases: boolean ,, string membership in a language, nonnegative real (82oU(oo), +.. 0,,,0,,, 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 fur- ther reading on semirings in NLP, we recommend Goodman (1999) and Huang (2008).
Our work studies weighted context-free gram- mars (WCFGs), which define a tractable family of weighted languages called weighted context-free languages that is frequently used in NLP applica- tions (see, e.g., Jurafsky and Martin, 2020).
Definition 2. A weighted context-free grammar is tuple 6 - (N, S, R) where
We provide several new technical results: We prove that GLCT preserves the weighted lan- guages and that an isomorphism between derivation
.N is set of nonterminal symbols
trees exists (Theorem 1). (ii) We provide explicit
V is a set of terminal symbols, VON= 0
methods for mapping back and forth between the
N is the start symbol
derivation trees (Algs. 1 and 2). (iii) We prove that
R is a bag (multiset) of weighted production rules. Each rule
the set of derivation trees for speculation and GLCT
R is of the form X " where E N, a E (VUN)), and w C W. We assume that W is commutative semiring.
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.
We will use the following notational conventions: X,Y,Z 7 E / for nonterminals a, b, c V for terminals y, z E V for sequence of terminals a. 3. E (VUN) for a terminal or nonterminal symbol ar, B. E (V UN)" for a sequence of nonterminals or terminals 6 = (N. V.S, S, R) and 6' ='= S',R') RR) for WCFGs. We write w(r) to access the weight of rule r.
2 Preliminaries
This section provides the necessary background on the concepts pertaining to semiring-weit weighted context-free grammars that this paper requires.
When describing a grammar and its rules, we may use the following terms: The size of a gram- mar is E(x~xa)ER (1 [al).. The arity of a rule X -> a is equal to |al: thus, a rule is nullary if lal 0, unary if [ 1, and so on. For tech- often convenient to eliminate nullary rules from the grammar. 5
Definition 1. A semiring is a tuple (W, O,, 80 0, I) where W is a set and the following hold:
@ is an associative and commutative binary op- erator with an identity element E W
& is an associative binary operator with an iden-
nical reasons,
tity element 1 '
Distributivity: Va, b, E W. (a o b) c=
A derivation is a rooted, (N V)-lablled, or- dered tree where each internal node must connect to its children by a production rule. To access the root label of a derivation ö, we write {(8). The set of all derivations of & is the smallest set 'D
c) C: (b @ c) and & (a b) (c a) 0 (cobb)
Annihilation: Va E W. a @ 0 - 0
"Speculation originally a transformation for weighted logic programs, which we have adapted to CFGs.
'We note that generalized left-comner pursers also exist (Demers, 1977; Nederhof, 1993). However, they are general- ized differently our transformation.
'Opedal et al. (2023, $F) provides an efficient method to remove nullary rules from semiring- semiring--eeghteed CFGs, which we make use in our experiments ($4.1).
'These technical results fill some important gaps in the literature, as prior work (Rosenkrantz and Lewis, 1970; John- son, 1998; Johnson and Roark, 2000; Moore, 2000; Fisner and Blatz, 2007) did not provide formal proofs.
"Note a derivation may be built by rule with an empty right-hand side; thus, the leaves may be elements of N. When rendering such a derivation, childlessness is marked with e.

---

satisfying
and 1 is the language that assigns one to the empty string and zero other strings.
(1)
The weighted language of & may also be ex- pressed as a certain solution to the following sys- tem of equations:
(X 01 aak E R,
01 ED. ax ED
8. a l
Va E V (5a)
8x
B
83x
v (5b)
The yield (6) E V of a derivation 8 is
(x "> ... (....K))E JRR
if 0 E:V: (ō) {(0) = a
(2)
where La is the weighted language that assigns 1 to the string and 0 to other strings.
We say that a is useless if there does not exist a derivation å E Ds that has a subderivation with ((5' - at We define trimming TRIM( as removing each useless nonterminal and any rule in which they participate. It is easy to see that trimming does not change the weighted language of the grammar because no useless nonterminals participate in a derivation rooted S. We can trim useless rules in línear time using well-known algorithms (Hopcroft and Ullman, 1979).
else:
ak
where denotes concatenation. The weight (6) E W of a derivation 5 is
if ô E V (6) 4f
(3)
x
w
X
a1
akK
elset
def
a1
ok
w
&w
We say that grammars & and 8' are equal (6 8') if they have the same tuple represen- tation after trimming. We say they equiva- lent (6 B') if they define the same weighted language.' 9 We say that they are X--bijectively equivalent (6 =x B') if a structure-preserving bijection of type Φ: Dx + D's exists. The map- ping & is prructure-preserving if (vō E Dx) it is (i) label-preserving (f(6) = ((((()()))))) (ii) yield- preserving (a(6) = o(o()))), and (iii) weight- preserving (w(6) (((()) Suppose 6 =x 6', S E X and S S then C == G', but not conversely. A benefit of this stronger notion of equivalence is that derivations in and & are interconvertible: we can parse in & and convert to a parse in & and vice versa, assuming S' and S E X. 10
The weighted language of a E (VUN) is func- tion Ba V* + W defined as follows:
(x) der
w())
(4)
8CDa(x)
where Da ( D ((6) = a) denotes the sub- set of DD containing trees labeled a, and D. (x) {8 D.: (8) }} denotes those with yield In words, the value of a string x E V in the weighted language Ga the (D-sum of the weights of all trees in Da with x as its yield. The weighted language of the grammar C is ((x) de (x(x). Given set of symbols X, write Dx short- hand for Usex D.. Lastly, let [ denote the weighted language generated by the tree 8.7
3 Transformations
This section specifies our novel generalized left- corner transformation, its correctness guarantees,
We define the following operations on weighted languages and G', for x E Y":
Union:
( + 6 (x)
(xx) @ ('(x)
"Note that the system of equations does not necessarily have unique solution. In the case of an w-continuous semir- ing, (4) coincides with the smallest solution to (5) under the natural ordering (Droste and Kuich, 2009).
Concatenation:
[6 G'] (x)
+ ((y) o (z)
yo2=x
Note that these operations form a (noncommuta- tive) semiring over weighted languages where 0 is the language that assigns weight zero all strings
LLe. (8 =6) + E (VUV")": 6s(x) = (x). 10 Under these conditions, our X'-bijective equivalence no- tion becomes a weighted extension of what Gray and Harrison (1969) call complete covers and Nijholt (1980) calls proper covers. However, their definitions assume traditional string- rewriting derivations instead of tree-structured derivations.
Formaally [6] (x) def (66 x x8) else 0.

---

and its connections prior left-corner transforma- tions. We also describe the speculation transfor- mation (Eisner and Blatz, 2007) and discuss the connections between the speculation transforma- tion and our generalized left-corner transformation.
X). The frozen and slashed nonterminals are each defined recursively.
Slashed nonterminals are built by a base case (6c) and recursive case (6d).
Frozen nonterminals are built by a base case (6e) and a recursive case (6f).
3.1 Generalized Left-Corner Transformation
We see in (6a) and (6b) that GLCT replaces the rules defining the original nonterminals (A) with rules that use GLCT's new nonterminals; the only way to build a nonterminal from A is using one of these two rules. We refer to these as recovery rules because they recover the original symbols from the new frozen and slashed symbols. We also see that (6d) is responsible for converting left recursion into right recursion because the slashed nonterminal its right-hand side is moved to the right of B. We will return to this when we discuss speculation in $3.2. Fig. 2 illustrates how GLCT transforms trees.
This section introduces the generalized left-corner transformation (GLCT)." " This transformation tends prior left-corner transformations by providing additional parameters that control which subtrees can be hoisted.
The generalized left-corner transfor- mation ( C) takes as inpul
Definition 3.
grammar = (N, V,
subset of (non-nullary) rules R. C R (called left-corner recognition rules)
subset of symbols C S NV (called left- corner recognition symbols)
Left corner and spine. To better understand the parameters C and R. we define the spine and left corner of derivation ô E D of the original gram- mar. Suppose 5 has the following general form:
and outputs a grammar &' (N", V', 8', ,') with superset of nonterminals (N' 2 N2
the same set of terminals (V* = V)
the same start symbol (S' S) the weighted production rules (R'):
g
x 4 X:
NENYZ (6a)
X 4 ā X/a:
X (6b)
y01) A
g
A
x/x 4 E: 1/a BY/x:
XEVUN (6c)
Then, we define the spine ((0) as the maximum-length sequence of rules (y((k) + ((-1)) g(K ... (7 + (1) g())
X RE (6d)
X x"a a:
x - R (6e)
along the left edges of 8 where each rule is in R. The left corner A(6) of a tree 8 E D is the bottommost subtree 8, of 5 with ((51) C that is reachable starting at the root E(d) along the left edges of 8 where each edge comes from rule in R. If no such subtree exists, we say that 8 has no left corner and write A(5) =L. We write 8/ 8/5(5) to denote the ò with X(ō) replaced by the empty subtree; define 5/1 def 8. Lastly, D/o (5/\(5) 5 e D, (((()) = a} where D is a set of derivations and a E E NVVULLL.
X " 8
x Ra हे (6f)
The transformation creates two kinds of new non- terminals using ã and X/a." 13
In Def. 3, see that GLCT introduces new non- terminals of two varieties: slashed nonterminals (denoted 8/a) and frozen 14 nonterminals (denoted
define
A generalized right-corner transformation can be defined analogously- applications of such a transformation are given in Schuler et al. (2010) and Amini and Cotterell (2022).
12 - [X] E A/) {a/s| o, E (N' VV}
To illustrate, let ò be the derivation on the left in Fig. 1. The right-hand side derivation results from applying GLCT with C = (NP) and R (S NP VV, + PossP NN, PossP + NP "s. The spine of 5, then, is the sequence of rules in (in the same order), and its left corner is the lower subtrree Note how the left comer is the subtree
This notation works as follows: we associate a unique identifier with the transformation instance. Then, ā (id, a) a e N else a and X/a def (id. X, a). This ensures that the symbols produced cannot conflict with those A No: ā, x/u N).
(i.e., Ya E N ENUV. U.V.
14 Our notion of frozen nonterminals is borrowed directly from the speculation transformation (Fisner and Blatz, 2007),
where they are called other.

---

hoisted by the transformation.
control over the left-corner recognition symbols. as C is required to be N U V. Thus, SLCT takes any subtree at the bottom of the spine to be its left corner. Frozen nonterminals enable us to restrict the left comners to those labeled
Interpretation. The symbol 8/a represents the weighted language X where we have replaced its left corner subtrees labeled a (if one exists) with E. We can see that the recovery rule (6b) uses these slashed nonterminals to reconstruct X by each of its left-corner types (found in C). We also have recovery rule (6a) that uses frozen nonterminal X, which represents the other ways to build X (i.e., those that do not have a left corner in C). Thus, the weighted language of decomposes as certain sum of slashed nonterminals and its frozen version (formalized below).
Formal guarantees. We now discuss the formal guarantees related to our transformation in the form of an equivalence theorem (Theorem 1) and asymptotic bound on the number of rules in the output grammar (Proposition 3). Theorem es- tablishes that the GLCT's output grammar is AC- bijectively equivalent to its input grammar.
Theorem 1 (N-bijective equivalence). Sup- pose @ (N, is WCFG and G' GLCT(B, R.C.) where R S R and CEVUN. Then, =v 8'.
Proposition 1 (Decomposition). Suppose 8' GLCTT(8, C.C.. Then, for any X C N:
6x 3 C
B
X/o
We prove this theorem in Appendix To our knowledge, this is the only formal correctness proof for any left-corner transformation." 17 In ad- dition, Appendix C provides pseudocode for the derivation mapping Φ: Dx + Div and its inverse Φ-1, in Algs. 1 and 2, respectively.
aEC
See Appendix A for proof. Next, we describe the weighted languages of the slashed and frozen non- terminals in relation to the derivations in the orig- inal grammar. Proposition establishes that the weighted language of ā is the total weight of derivations without left corner, and X/a the to- tal weight of all derivations with an a left corner that has been replaced by E.
We can bound the number of rules in the output grammar as function of the input grammar and the transformation's 's parameters C and R.
Proposition 3. The number of rules in e' GLCT(B, R) is no more than
Proposition 2 (Weighted language relationship). Suppose G = - R). Then, for any X E N and E N.::
|R| + WW
+ (R) + W +
Proof. We bound the maximum number of rules in each rule category of Def. 3:
+ [ō] SEDa/1
and 8%2/2-
+ [o] 8cDx/a
(6a) < [ \ C
(6b) < W |C|
See Appendix B for proof.
(6c) W + V
((6d) < R W
(6e) S R R
(66)) S R
Special cases. We now discuss how our trans- formation relates to prior left-corner transforma- tions. The basic left-corner transformation (Rosenkrantz and Lewis, 1970; Johnson, 1998) is (G) = GL, R.N U V), i.e., we set R = R and C = A' 1. This forces the left- most leaf symbol of the tree to be the left cor- ner, which is either a terminal or the left-hand side of nullary rule. The selective left-corner transformation (SLCT; Johnson and Roark, 2000) (L R) = GLCC(66. R,W VV) supports left- corner recognition rules R, but it does not allow
Each of these bounds can be derived straightfor- wardly from Def. 3. Summing them, followed by algebraic simplification, proves Proposition 3.
The bound in Proposition 3 is often loose in prac- tice, many of the rules created by the transfor- mation are useless. In $4, describe how use GLCT eliminate left recursion, and we investi- gate the growth of the transformed grammar for nine natural language grammars in $.
1 More precisely, we are using SLCT with top-down factoring (Johnson Roark, 2000, $2.5).
15 That is, the output grammars are equal post trimming. The only useful rules are instances of (6b). (6c). and (6d). Furthermore, the (6b) rules will be useless unless is termi- nal. With these observations, verifying that GLCT matches Johnson's 's ( (1998) presentation of LCT is straightforward.
We note that Aho and Ullman (1972) prove correctness for an alternaive method to remove left recursion, which is used as a first step when converting grammar to Greibach normal form. This method, however, might lead to an exponential increase in grammar size (Moore, 2000).

---

Original derivation
(b) GLCT
(K-1)
B(K-1)
-(A)
100
y(R-1)
g 11
g(
g
g1
(2)
9(3)
g00)
y(1)
((3)
B(R-2)
g(o)
g(K-1)
(c) Frozen recovery
(d) Speculation
(K)
700
-(--1)
g(k-1)
7
1 11
(K-1)
g(x-1)
(g002)
(iK-2)
709
700)
703
g()
y01
/00
(R)
g
(())
gg
Figure 2: This figure is a schematic characterization of the one-to-one correspondence of derivations of the original grammar, speculation. and GLCT transformations. The diagram assumes that the rules exposed in the derivation 8 form its spine (6)). However, (b) and (d) assume that (() T is the left corner A(0), and (c) assumes that A(5)= = Note that the rules in the spine that are below the left comnrr are frozen. When the left corner is 1 (i.e.. case (c)), the spines of the GLCT and speculation trees are transformed in the same manner. We note that in each transformation case ((b). (c), or (d)), each 3-labeled subtree is recursively transformed, and its root label is preserved. We see that both speculation (d) and GLCT (b) hoist the same left-corner subtree (i.c., the (8) subtree in the diagram) to attach at the top of the new derivation. However, the left recursion is transformed into a right-recursive tree GLCT. Lastly, we observe that the slashed nonterminals in GLCT have a common numerator (? (x()),, whereas, in speculation, they have a common denominator ()).
Optimizations.
We briefly describe two improve- ments to our method's practical efficiency.
our transformations (i.e., the base case for slashed rules), there turns out to be special linear structure that can be exploited for efficiency. We describe the details of this speedup in Appendix H.
C, Reducing the number of useless rules. For efficiency, we may adapt two filtering strategies from prior work that aim reduce the number of useless rules created by the transformation." We provide equations for how to modify R' in GLCT to account for these filters in Appendix G.
3.2 Speculation Transformation
In this section, we adapt Eisner and Blatz's 's (2007; $6.5) speculation transformation from weighted logic programming to WCFGs. We will provide
+, Fast nullary rule elimination. Nullary rule climination is often required as a preprocessing step in parsing applications (Aho and Ullman, 1972). When eliminating the nullary rules introduced by
Thee translation was direct and required essentially no in- vention on our behalf. However, we have made one aesthetic change to their transformations that we wish to highlight: the closest WCFG interpretation of Eisner and Blatz's 's (2007) speculation transformation restricts the slashed nonterminals heyond (9c) and (9d); their version constrains the denomi-
Thehee strategics are provided in our implementation.

---

X/x 4 e: new interpretation for speculation that does not appear in the literature. In particular, we observe that speculation, like the left-corner transformation, is a subtree hoisting transformation.
whereas, for speculation, Y is passed along the denominator. Theorem 2 (below) establishes that speculation and GLCT are bijectively equivalent for their complete set of nonterminals." 22
Definition 4. The speculation transformation SPEC(8, R, C) takes as input
Theorem (Speculation- alence). For any grammar B, and choice of C and R. SPEC( RRC)) and GLCT(6, R,C) are X-bijectively equivalent where X is the complete set of symbols (i.e., frozenal,frozen, and slashed).
bijective equiv-
grammar 6 (N,,)
subset of (non-nullary) rules R. C R (called the left-comer recognition rules)
subset of symbols Č S ( UV) (called the left-corner recognition symbols)
See Appendix D for the proof sketch. We also pro- vide the first proof of equivalence for speculation.
and outputs a grammar G' = (N', 8' R') with
Theorem 3. For any grammar -= (N, V, R), R C R, and C C VUN: SPEC R. C) = 8.
superset of nonterminals (N" 2 20
the same set of terminals (V'=V)
Proof. The theorem follows directly from Theo- rem 1, Theorem 2, and the compositionality bijective functions.
the same start symbol (S' S)
the weighted production rules (R'):
x 4 X: X f 2x/a:
XENIZ (9a)
4 Reft-Recursion Elimination
XEN,aEE (9b)
Motivated by the desire for efficient top-down pars- ing for which left-recursion poses challenges ($1), we describe how GLCT may be used to transform a possibly left-recursive grammar @ into a bijectively equivalent grammar &' without left-recursion." 23 The bijective equivalence (Theorem 1) ensures that can apply an inverse transformation to the derivation tree of the transformed grammar into its correspouding derivation tree in the original grammar. This section provides an efficient and (provably correct) recipe for left-recursion elimina- tion using GLCT. We experiment with this recipe on natural language grammars in $4.1.
XEVUN (9c)
X/r " B
(9d)
_ a:
x _ E RAR (9c)
x " :
x x a E R, 2 (9f)
Upon inspection, we see that the only difference between speculation and GLCT is how they define their slashed nonterminals, as the other rules are identical. The slashed nonterminals have the same base case (6e) and (9c). However, their recursive cases (6d) and (9d) differ in an intriguing way:
Our left-recursion elimination recipe is based on 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 8.
Y/a " V/x:
X x R. N (6d) X/y " B: + a REVEVUN (9d)
This difference is why GLCT can climinate left recursion and speculation cannot: GLCT's slashed nonterminal appears to the right of B, and specu- lation's s appears on the left. For GLCT, Y is passed along the numerator of the slashed nonterminal,
We define the left-recursion depth of a deriva- tion tree d()) as the length of the path from the root to the leftmost leaf node. The left-recursion depth of a grammar dl ((() that @ is left-recursive iff d(() is unbounded. To analyze whether & is left-recursive, we can analyze its left-recursion graph, which accurately charac- terizes the left-recursive paths from the root of a derivation its leftmost leaf in the set of deriva- tions D. The left-recursion graph of the grammar
daf
maxsed (()). We say
nator to be E C. This difference disappears after trimming because usefial slashed nonterminals must be consumed by the recovery rule (9h), which imposes the C constraint one level higher. We prefer which shows that GL.CT and speculation produce X bijectivee equivalent grammars for all nonterminals. The pruned version would result in weaker theorem with X' being a subser of the nonterminals with nuanced specification.
version enables Theorem 2,
We note that the set of useful slashed and frozen nonter- minals typically differs between GLCT and speculation. Noot: when we say left recursion, we often mean un- bounded left recursion.
20 Vieiir''s (2023) dissertation, which appeared contempora- ncously with this paper, adopts our same interpretation. 21 See footnote 12.

---

@ is a labeled directed graph G = E) with nodes N- N= --VVUA U. and edges [ 4 a) r R, r r (X + a.... a...).. should be clear that the @ is leftrrecursive iff G has a cyclic subgraph. We classify a rule r as left-recursive if the edge labeled r is an edge in any eyclic subgraph of G. To deter- mine the set of left-recursive rules, we identify the strongly connected components (SCCs) of G (e.g.. using Tarjan's s (1972) algorithm). The SCC analy- sis returns function that maps each of G's nodes to the identity of its SCC. Then, a rule r is left- recursive iff its corresponding edge a + 3 satis- fies = = To ensure that left recursion is eliminated, R must include all left-recursive rules.
Our recipe. We take R as the set of left rules in @ and C as bottoms(RR).2 This minimizes the upper bound given by Proposition subject to the constraints given in Theorem 4.
Special cases. Theorem 4 implies that the basic left-corner transformation and the selective left- corner transformations (with R 2 the left-recursive rules) will eliminate left recursion. Experimentally, we found that our recipe produces slightly smaller grammar than the selective option (see $4.1).
Unary rules. The reason Theorem 4 requires that & is unary-free is that the left-corner transforma- tion cannot remove unary cycles of this type. 27 To why, note that thus, the transformed rule will have slashed non- terminal in its leftmost position, so may be left- recursive. Fortunately, unary rule cycles can be climinated from WCFGs by standard preprocess- ing methods (e.g., Stolcke (1995, $4.5) and Opedal et al. (2023, ŞE)). However, we note that elimi- nating such unary chain cycles does not produce an --bieectively equivalent grammar infinitely many derivations are mapped single one that accounts for the total weight of all of them.
We use the following set to provide sufficient condition on C to eliminate left recursion:
for unary rule (6d);
bottoms R)
(10)
E) R)
(X-
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) -lbelee outgoing which we refine to nodes that might appear the spine (i.e., those in the leftmost position of the rules R).
Nullary rules. We also note that the case where the & may derive & as its leftmost constituent also poses challenge for top-down parsers. For exam- ple, that would be the case in Fig. 1 if PossP + NP POS was replaced by PossP + X NP POS and X E; this grammar is not left-recursive. but the subgoal of recognizing an NP in top-down parser will still, unfortunately, lead to infinite recur- sion. Thus, a complete solution to transforming a grammar into a top-down-pane parser- parser-friendly grammar should also treat these cases. To that end, we can transform the original grammar into an equivalent nullary-free version with standard methods (Opedal et al., 2023, $F) before applying our GLCT-based left-recursion elimination recipe. As with unary rule climination, nullary rule elimination does not produce an A V-bieectively equivalent grammar.
With these definitions in place, we can provide sufficient conditions on the GLCT parameter sets that will remove left recursion:
Theorem (Left-recursion climination). Suppose that G' = (GLC(G, T)) where
6 has no unary rules
R 2 the left-recursive rules in G
2 bottoms(()
Then, G' is not left-recursive. Moreover, d((3)= S
2. O where C is the number of SCCs in the left-
recursion graph for S
4.1 Experiments
See Appendix for the proof.
In this section, we investigate how much the gram- mar size grows in practice when our GLCT recipe is used to eliminate left recursion. We compare our
Example. In Fig. 1, we made use of Theorem to remove the left-recursion from NP to NP. applying GLCT with = (NP) and R = (S -> NPVP,
NP + PossP NN, PossP + NP 's..25 's}.2
obtained different output tree in the figure. "Ourr choice for is consistent with the recommendation for SLCT in Johnson and Roark (2000).
24 Note that nullary rules cannot left-recursive.
25 Note that omitting S + NP VP from R would have also climinated left recursion in this example, but we would have
P'rior left-corner transformations (Johnson and Roark, 2000; Moore, 2000) are limited in the same manner.

---

Language (size)
so we additionally apply trimming the output grammars. When parsing, often practical first binarize the grammar and remove nullary rules, so we perform those postprocessing steps as well.
Method
Raw
+Trim
-e's
Basque
SLCT
3,354,445 445
245,90 ,89
411,023
(73,173)
GLCT
644,125
245,923
411,023
English
SL.T
514,338
26,655
46,088
As sanity check, we verify that left recursion is removed in all settings by checking that the left- recursion graph of the output grammar is acyelic. We present the results evaluated on grammar size in Table Appendix F provides further results in terms of the number of rules.
(21,272)
GLCT
203,664
26,289
46,088
French
SLCT
5,902,552
106,860
173,375
(105,896)
GLCT
147,860
106,628
173,375
German
SL.CT
21,204,060
272,406
434,787
(100,346)
GLCT
1,930,386
271,752
434,787
Hebrew
SLCT
14,304,366
564,456
979,040
(84,648)
GLCT
2,910,538
564,074
979,040
Hungarian
SLCT
77333,603
151,373
242,360
Discussion. Interestingly, the increase in size compared to the input grammar varies a lot be- tween languages. Previous work (Johnson and Roark, 2000; Moore, 2000) only evaluated on En- glish and thus appear to have underestimated the blow-up caused by the left-corner transformation when applied to natural language grammars. Com- pare, for instance, the ratio between the trimmed size and the original size in Table of English (1.2) to Basque (3.4), Hebrew (6.7), and Swedish (23.7). By Proposition 3, the number of rules in the output grammar scales with [ which by Theorem 4 is set as the left-recursive rules.
(134,461)
GLCT
748,398
151,013
242,360
Korean
SLCT
54,575,826
87,937
96,023
(59,557)
GLCT
3,706,444
86,529
96,023
Polish
SLCT
2,845,430
61,333
79,341
(41,957)
GL.CT
177,610
61,253
79,341
Swedish
SL.CT
20,483,899
1,894,346
3,551,917
(79,137)
GLCT
6,896,791
1,871,789
3,551,917
Table I: Results of applying GLCT and SLCT on the ATIS and SPMRL grammars broken down by each of the nine languages. We present the resulting size in the raw output grammar (Raw), trimming (+Trim), and binarization plus nullary removal (-e's).
The GLCT produces smaller grammars than the SLCT for all languages before either of the post- processing steps. This difference is (almost) elimi- nated post-trimming, however, which is unsurpris- ing given that SLCT a special case of GLCT ($3.1). J. The small difference in size after trimming happens since two rules of the form X + X x/x (6b) and X/x -> (6c) in SLCT are replaced by one rule X + X (6a) in GLCT. However, this difference disappears after nullary removal.
results to SLCT with top-down factoring ($3.1) to see whether the additional degree of freedom given by C leads to any reduction in size. We apply both transformations to nine grammars of different lan- guages: Basque, English, French, German, Hebrew, Hungarian, Korean, Polish, and Swedish. We use the ATTS grammar (Dahl et al., 1994) as our En- glish grammar." 28 We derived the other grammars from the SPMRL 2013/2014 shared tasks treebanks (Seddah et al., 2013, 2014).
5 Conclusion
Experimental setup. For GLCT, we set R and T according to our recipe. For SLCT, we set R according to Theorem 4's conditions for removing left-recursion. We compare the grammar size and the number of rules of the raw output grammar to those of the input grammar. However, the raw output sizes can be reduced using useless rule filters (discussed in $3.1 and Appendix G),
This work generalized the left-corner transforma- tion to operate not only on a subset of rules but also subset of nonterminals. We achieve this by adapting frozen nonterminals from the speculation transformation. We exposed tight connection between generalized left-corner transformation and speculation (Theorem 2). Finally, and importantly, we proved the transformation' 's correctness (The- orem 1) and provided precise sufficient conditions for when it eliminates left recursion (Theorem 4).
We selected the (boolcan- weighted) ATIS grammar he- cause it was used prior work (Moore, 2000). We note, however, that despies our best efforts we were unable replicate Moore's (2000) exact grammar size on it.
" "Specifically, we load all trees from the SPMRL 5k training dataset, delete the morphological annotations, collapse unary chains like X - Y Z -> a into X a. and create a grammar from the remaining rules. The weights of the SPMRL grammars are set using maximuum-ikellhhee estimation. None of the treebanks contained nullary rules.
Limitations
Parsing runs time proportional the grammar size. $4.1 shows that we obtain the same grammar size after postprocessing from our method and the

---

selective left-corner transformation, which gave us no reason to provide an empirical comparison on parsing runtime.
each nonterminal is replaced by two versions: one that generates only E, and one that generates any- thing else. Preprocessing the grammar in this way is also done in nullary rule elimination (see Opedal et al. (2023, $F) for details).
Moreover. it is thus of practical importance to restrict the growth of the grammar constant. We have discussed theoretical bound for grammar growth in Proposition investigated it empirically in $4.1, and provided further tricks to reduce it in Appendix G. Orthogonally the left-corner trans- formation itself, is possible to factor the grammar so that the grammar size is minimally affected by the transformation. Intuitively, reducing the num- ber of left-recursive rules in R will also reduce the number of rules that are required in R, which, in turn, leads to fewer rules in the output gram- mar. We did not present any such preprocessing techniques here, but Moore (2000) provides ref- erence for two methods: left-factoring and non- left-recursive grouping. Johnson and Roark (2000) give a second factoring trick in addition to top- down factoring (see footnote 16), which is similar to Moore's (2000) left-factoring. We also mention that Vieira's s (2023) search- technique for op- timizing weighted logic programs could be directly applied to grammars. In particular, the search over transformations can be used to find a smaller grammar that encodes the same weighted language.
Ethical Statement
We do not foresee any ethical issues with our work.
Acknowledgments
We thank Alex Warstadt, Clemente Pasti, Ethan Wilcox, Jason Eisner, and Josef Valvoda for valu- able feedback and discussions. We especially thank Clemente for pointing out the nullary removal op- timization in Proposition 4. We also thank the reviewers for their useful comments, suggestions, and references to related work. Andreas Opedal acknowledges funding from the Max Planck ETH Center for Learning Systems.
References
Steven P. Abney and Mark Johnson. 1991. Memory requirements and local ambiguities of parsing strate- gies. Journal of Psycholinguistic Research, 20(3).
sequences of definc-uufold-ie
Alfred V. Aho and Jeffrey D. Ullman 1972. The Theory of Parsing, Translation, and Compiling, volume I. Prentice- Hall, Inc.
There appear to be connections between our no- tion of slashed nonterminals and the left quotient of formal languages that we did not explore in this paper. For example, the simplest case of the left quotient is the Brzozowski (1964) derivative. The Brzozowski derivative of & with respect to a e V is equal to the weighted language of $/a in the out- put grammar G produced by speculation or GLCT, provided that the 6 is nullary-free, R = R, and a E C. We suspect that other interesting connec- tions are worth formalizing and exploring further. Finally, we note that we could extend our trans- formation to deal with nullary rules directly rather than eliminating them by preprocessing (as dis- cussed in $4). The idea is to modify (6d) in GLCT so that the slashed nonterminal on its right-hand side is formed from the leftmost nonterminal that derives something other than e, rather than the left- most symbol. For this extension to work out, we require that the grammar is preprocessed such that
Afra Amini and Ryan Cotterell. 2022. On parsing as tag- ging. In Proceedings of the Conference on Empirical Methods in Natural Language Processing.
Arthur Baars, S. Doaitse Swierstra, and Marcos Viera. 2010. Typed transformations of typed grammars: The left corner transform. In Proceedings of the Workshop Language Descriptions Tools and Ap- plications.
Ychoshua Bar-Hillel, M. Perles, and E. Shamir. 1961. On formal properties of simple phrase structure gram- mars. Zeitschrifi für Phonetik, Sprachwissenschaft und Kommunikaiiossforsche Y.
14. Reprinted in (1964). Language and Information: Selected Essays on their Theory and Application, 1964, 116-150.
Jonathan R. Bremnan and Linna Pylkkänen. 2017. MEG evidence for incremental sentence composition in the anterior temporal lobe. Cognitive Science, 416))..
Janusz A. Brzozowski. 1964. Derivatives of regular expressions. Journal of the ACM, 11(4).
TThe left quotient of a WCFG by a weighted regular lan- guage can be represented as unother WCFG using modified intersection construction (Bar- Hillel et al., 1961; Pasti et al., 2023)-sce Li et al. (2022) for details.
Rod M. Burstall. 1969. Proving properties of pro- grams by structural induction. The Computer Jour- nal, 12(1).

---

Eugene Charniak. 2010. Top-down peatey-context- sensitive parsing. In Proceedings of the Conference on Empirical Methods in Natural Language Process- ing. Association for Computational Linguisties.
Mark Johnson and Brian Roark. 2000. Compact non-left-recursive grammars using the selective left- corner transform and factoring. In Proceedings of the International Conference on Computational Lin- guistics.
Noam Chomsky. 1959. On certain formal properties of grammars. Information and Control, 2(2).
Philip N. Johnson-Laird. 1983. Mental Models: To- wards a Cognitive Science of Language, Inference, and Consciousness, volume 6 of Cognitive Science Series. Cambridge University Press.
Deborah A. Dahl, Madeleine Bates, Michael Brown, William Fisher, Kate Hunicke-Smith, David Palleu, Christine Pao, Alexander Rudnicky, and Elizabeth Shriberg. 1994. Expanding the scope of the ATIS task: The ATIS-3 corpus. In Human Language Tech- nology: Proceedings of a Workshop held at Plains- boro, New Jersey, March 8-11, 1994.
Dan Jurafsky and James H. Martin. 2020. Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition, Third Edition, third edition. (Draft).
Alan J. Demers. 1977. Generalized left corner pars- ing. In 4th Annual ACM Symposium on Principles of Programming Languages.
Nikita Kitaev and Dan Klein. 2020. Tetra-tagging: word-synchronous parsing with linear-time infer- ence. In Proceedings of the Annual Meeting of the Association for Computational Linguistics.
Victor J. Díaz, Vicente Carrillo, and Miguel A. Alonso. 2002. A left corner parser for tree adjoining gram- mars. Proceedings of the International Workshop on Tree Adjoining Grammar and Related Frame- works.
Daniel J. Lehmann. 1977. Algebraic structures for tran- sitive closure. Theoretical Computer Science, 4(1).
Manfred Droste and Werner Kuich. 2009, Semirings and formal power series. In Handbook of Weighted Automata. Springer.
Yongming Li, Qian Wang, and Sanjiang Li. 2022. On quotients of formal power series. Information and Computation, 285.
Jason Eisner and John Blatz. 2007. Program transfor- mations for optimization of parsing algorithms and other weighted logic programs. Proceedings of the Conference on Formal Grummar.
Robert C. Moore. 2000. Removing left recursion from context-free grammars. In Proceedings of the Meet- ing of the North American Chapter of Association for Computational Linguistics.
Javier Esparza, Stefan Kiefer, and Michael Lutten- berger. 2007. An extension of Newton's 's method to w-continuous semirings. In Proceedings of the Inter- national Conference on Developments Language Theory, volume 4588 of Lecture Notes in Computer Science.
Mark-Jan Nederhof. 1993. Generalized left-comner pars- ing. In Proceedings of the European Chapter of the Association for Computational Linguistics.
Mark-Jan Nederhof and Giorgio Satta. 2008. Com- puting partition functions of PCFGs. Research on Language and Computation, 6(2).
Joshua Goodman. 1999. Semiring parsing. Computa- tional Linguistics, 25(4).
James N. Gray and Michael A. Harrison. 1969. Single pass precedence analysis. In Proceedings of the An- nual Symposium on Switching and Automata Theory.
Matthew J. Nelson, Imen El Karoui, Kristóf Giber, Xi- aofang Yang. Laurent D. Cohen, Hilda J Koopman, Sydney S. Cash, Lionel Naccache, John Tracy Hale, Christophe Pallier, and Stanislas Dehaene. 2017. Neurophysiological dynamics of phrase-structure building during sentence processing. Proceedings of the National Academy of Sciences, 114.
Sheila A. Greibach. 1965. A new normal-form theorem for context-free phrase structure grammars. Journal of the ACM, 12(1).
John E. Hoperoft and Jeffrey D. Ullman. 1979. Intre- duction to Automata Theory, Languages and Compu- tation, volume 1. Addison Addison-Wesley.
Anton Nijholt. 1980. Context- Free Grammars: Covers, Normal Forms, and Parsing, volume 93 of Lecture Notes in Computer Science. Springer.
Liang Huang. 2008 Advanced dynamic programming in semiring and hypergraph frameworks. In Coling 2008: Advanced Dynamic Programming in Compu- tational Linguistics: Theory, Algorithms and Appli- cations- Tutorial notes.
Hiroshi Noji and Yusuke Miyao. 2014. Left-corner transitions dependency parsing. In Proceedings of the International Conference on Computational Linguistics: Technical Papers.
Mark Johnson. 1998. Finite-star state approximation of constraint-based grammars using left-corner gram- mar transforms. In Proceedings of the Association for Computational Linguistics and the International Conference on Computational Linguistics.
Hiroshi Noji, Yusuke Miyao, and Mark Johnson. 2016. Using left-corner parsing to encode universal struc- tural constraints in grammar induction. In Proceed- ings of the Conference on Empirical Methods Nat- ural Language Processing.

---

Byung-Doff Oh, Christian Clark, and William Schuler. 2022. Comparison of structural parsers and neural language models surprisal estimators. Frontiers in Artificial Intelligence,
Workshop on Statistical Parsing of Morphologically- Rich Languages.
Cory Shain, William Bryce, Lifeng Jin, Victoria Krakovna, Finale Doshi-Velez, Timothy Miller, William Schuler, and Lane Schwartz. 2016. Memory- bounded left-corner unsupervised grammar induction child-directed input. In Proceedings of the Inter- national Conference on Computational Linguisties: Technical Papers.
Andreas Opedal, Ran Zmigrod, Tim Vieira, Ryan Cot- terell, and Jason Eisner. 2023. Efficient semiring- weighted Earley parsing. In Proceedings of the An- nual Meeting of the Association for Computational Linguistics (Volume I: Long Papers).
Clemente Pasti, Andreas Opedal, Tiago Pimentel, Tim Vieira, Jason Eisner, and Ryan Cotterell. 2023. On the intersection of context-free and regular languages. Proceedings of the Conference of the European Chapter of the Association for Computational Lin-
Miloš Stanojević and Edward Stabler. 2018. A sound and complete left-corne, parsing for minimalist gram- mars. In Proceedings of the Workshop on Cognitive Aspects of Computational Language Learning and Processing.
guistics.
Andreas Stolcke. 1995. An efficient probabilistic context-free parsing algorithm that computes prefix probabilities. Computational Linguistics, 21(2).
Philip Resnik. 1992. Left-comer parsing and psycholog-
ical plausibility. In Proceedings of the International Conference on Computational Linguistics.
Robert Tarjan. 1972. Depth-first search and linear graph algorithms. SIAM Journal on Computing. 1(2).
Brian Roark. 2001. Probabilistic top-down parsing and language modeling, Computational Linguistics, 27(2).
Robert Endre Tarjan. 1981. A unified approach path problems. Journal of the Association for Computing Machinery, 28(3).
Brian Roark. Asaf Bachrach, Carlos Cardenas, and Christophe Pallier. 2009. Deriving lexical and syntac- tic expectation- based measures for psycholinguistic modeling incremental top-down parsing. In Pro- ceedings of the Conference on Empirical Methods in Natural Language Processing.
Tim Vieira. 2023. Automating the Analysis and Improve- ment of Dynamic Programming Algorithms with Ap- plications to Natural Language Processing. Ph.D. thesis, Johns Hopkins University.
Brian Roark and Mark Johnson. 1999. Efficient prob- abilistic top-down and left-corner parsing. In Pro- ceedings of the Annual Meeting of the Association for Computational Linguistics.
Daniel J. Rosenkrantz and Philip M. Lewis, II. 1970. Deterministic left corner parsing. In IEEF Confer- ence Record of the Annual Symposium on Switching and Automata.
William Schuler. Samir AbdelRahman, Tim Miller, and Lane Schwartz. 2010. Broad-coverage parsing us- ing human-like memory constraints. Computational Linguistics, 36(1).
Djamé Seddah, Sandra Kübler, and Reut Tsarfaty. 2014. Introducing the SPMRL 2014 shared task parsing morphologically-rict languages. In Proceedings of the Joint Workshop on Statistical Parsing of Morpho- logically Rich Languages and Syntactic Analysis of Non- Mon--Caonical Languages.
Djamé Seddah, Reut Tsarfaty, Sandra Kübler, Marie Candito, Jinho D. Choi, Richárd Farkas, Jennifer Fos- ter, lakes Goenaga, Koldo Gojenola Galletebeitia, Yoav Goldberg. Spence Green, Nizar Habash, Marco Kuhlmann, Wolfgang Maier, Joakim Nivre, Adam Przepiórkowski, Ryan Roth, Wolfgang Seeker. Yan- nick Versley, Veronika Vineze, Marcin Wolinski. Alina Wróhlewska, and Erii Villemonte de la Clerg- erie. 2013. Overview of the SPMRL 2013 shared task: A cross- foosefrr evaluation of parsing mor- phologically rich languages. In Proceedings of the

---

A Proof of Proposition (Decomposition)
Proposition 1 (Decomposition). Suppose 8' GGLCT(6, R, C). Then, for any X E N:
8x = 8
+
8%/o
(7)
X
á
aEC
Proof.
8x 8x
by Theorem 1]
(11)
θ w o B
o 3xxx
[by Eq. 5]
(12)
(x " AXiRR'
1 X + 1o B 8%/o
bby Def. 3]
(13)
AJJRRR (x-ta X/aEER'
B' 8%
[by Def. and algebra]
(14)
aEc
Note that (13) specializes the sum to the only kinds of rules that can build X E N: rules (6a) and (6b).

---

B Proof of Proposition 2 (Weighted Language Relationship)
Lemma 1. Va E ENUV there exists a weight- and yield- preserving bijection between Da/ 1 and a Proof (Sketch). On the left, we have a prototypical derivation from Da/L with its spine exposed. Here a == (K),, By definition, the spine elements -(1), ((k) & C. On the right, we have its corresponding derivation in 2/::
(K)
y(R3
yER
g
y( 13
1314
19
2)
di
7.90
9033
g
where the function Alg. 1. Call the function that maps the left tree to the right one v/; all it does is freeze the spine and then call & on the f subtrees. Recall that Theorem I established that ø is A- structure-preserving bijection. Thus, it is straightforward to see that á is also weight- and bijection, as its inverse 1p" undoes these steps and calls ø on the subtrees. This proves Lemma 1.
Lemma 2. VX & there exists weight- and yield-preserving bijection between Dx/a and D x//=
Proof (Sketch). On the left, we have prototypical derivation from Dx/a with its spine exposed. Recall that these trees result from replacing the left corner, which is why there is an E. Here X = -((k) and a 7 (k), On the right, we have its corresponding derivation D'rju'
(K)
1181/118
(K 1)
g
1-1)
grk)
(1
g(f+1)
(3
(1-11
(K)
(3()
(gCx-1))
100 (8)
where the function Φ is Alg. 1. Call the mapping from left right ar; it very straightforward. All it does is (1) transpose, (2) relabel the spine, and (3) call 6 on the , subtrees. Note that ø does not recurse v) because can already convert the subtrees by Theorem 1. Thus, is straightforward to see that s is also weight- and yield-preserving bijection. This proves Lemma 2.
Proposition (Weighted language relationship). Suppose B' -G,CCT,,,,CCRR R). Then, for any X N and a E A U
B/
+ [8] SED./1
and B
θ [ø]
SEDx/a
Proof. The equations follow directly from Lemma 1 and Lemma 2. each case, the left- and the
right-hand sides are sums of the derivations that are part of a weight- and yield-preserving bijection.

---

C Proof of Theorem 1 (Bijective Equivalence)
Roadmap. We will show that 6 = GLCT( R.C) for any choice of and R. Our proof makes use of two lemmas, Lemma 3 and Lemma 4, to establish that the derivation mapping & (Alg, 1) and its inverse Φ-1 (Alg. 2) define a bijection of the necessary type. Lemma 3 shows that & preserves label, weight, and yield. Lemma 4 shows that é is invertible and, thus, that a bijection exists.

---

Algorithm Derivation mapping for the generalized left-corner transformation GI.CT C.
def (66):
i E V
Basee case
return 5
else if ô is sequence 81 å return (6)1) Φ(6k)
Seeuuenc
5.
6.
else
((K-1)
where (7(K) + -(k-1) g(k-1)) ... (7(2) - 7(1) (())
8
3.
B(K-2)
is ((5) the spine of the
<00
g
k min (fi 10 Eč,iE (1, (1)).. if 00:
Ddetermine the left corner; take min(0) = 0c
return
((0)
y085
-(
Bix 2)
7.99
7(3)
1910
g(
else return
7(
7.R
g(--1)
130
(3(
g(C--1)

---

Algorithm/ 2 Inverse derivation mapping for the generalized left-corner transformation GLCT( ( R,C)
def Φ (68): i E :
Daase case
return 8'
else if 8' is sequence 81 8'x
D-Sequence
5. return (8)) ø (8'))
6. else if top rule of 8' is an instance of (6b):
Slashee recovery rule; must have the following form:
x(K)
y(k
13
g 9(N-1)
3(k
(4)
6-1
((-
((k-1)
g(f-2)
g(++)
8': return
((-11)
(K-)
Φ-1
B(k-2)
700 g
BiK-
(10)
30
gro)
else
Frrozen recovery rule; top rule of 8' is instance (6a) and 5' must have the following form:
((K)
y00)
(K--1
g(k
BER D)
19(
d-1
BIK 2)
8';
return
(())
((2)
((3)
g0)
1942
B(0)

---

Lemma 3. Let 6 - S, R, w) be a WCFG. Let B' GLCT( R,C) where C = (N V) and
R S R. Then, Alg. defines a function & that is
(i) type o: D D
(i) laeee-ngg
(ii)) piese-ireserving
(iv) weight-pressrrvng
Proof. Let B' = For notational convenience, we extend w and to apply to sequence of derivations ... C D':
Note: by construction (Def. 3). 2 N, S' = S, and V = V.
w
a
ak
w
w
ax
and a ai ... an
a
ax
It is straightforward to verify that & satisfies properties (i-iv) for sequences of derivations; for brevity, we will not do so.
Fix an arbitrary derivation tree 8 D. Our proof will proceed by structural induction the subtree relation: 6, 5 < 51 is (strict) subtree of 6. well-known that is well-founded ordering. making it suitable for induction (e.g., Burstall, 1969).
Inductive hypothesis (IH): vō1 < 8: properties (i-iv) hold.
Base case (Ō E V): Here @ is the identity mapping. Thus, properties (i-iv) are clearly preserved. Inductive case (Ō & V): Here 8 must have the general form:
where K > 1, (1.... (y(K) + ((K 3(R-1)) (7(2) 71) ((1) is (()),
K): 3 E (VUN). and
()
(K-1)
the spine of the 6.
BiK
(() g()
7:4
Observation
The subtree (()) is either a terminal or it is of the form with 711) (0(0) $ R.
Let it be the index of the left corner (i.e., bottom-most element of C that occurs along the spine of 6).31 More formally, let k- = min { (0) C, E {1, k}}). no such element exists, define 1: mi=mmn()) co. The cases correspond to X(8) + and A(0) = 1, respectively.
We consider two cases: To oo and 1 < oo:
We chose the notation & because the is visually similar "kink" the transformed tree that is determined in the case where < oo.

---

Case (k- o0)): In this case, we observe 2 Vi
100 $ C. and line 10 of Alg. returns:
(
y(K)
YER)
7(K
(B(K-2)
y())
(31))
gra)
We check each of the properties:
(i) o: + D': In this case, we can check that 66) E D' by verifying that each rule used the definition of Φ appears in G', and then invoking the inductive hypothesis on the subtrees.
It is straightforward to verify that the mapping (6)) preserves weight and that the tree exists in D by crosschecking each of the rules that appear in it with the GLCT construction (Def. 3):
The top rule (K) + (() is an instance of (6a). The side condition X E W C is satisfied by
2 (Vi E (1,..., K} ()) $ C).
Each middle rule 700 + 7(-11) G(--1) is instance of (6f). The side condition
X X1 3 X1 C is satisfied in each case because spine guarantees inclusion
R. and by 2 (Vi {1, (I...., K] ((()) $ Z).
The bottom rule 7(1) > ((0) is an instance of (6e). The side condition X ", B & R is satisfied by
Since we have verified that each of the rules the construction (66) are in B', and the subtrees are in D' by IH, then it follows that (()) E D'.
(ii) label-pres:rving: It is clear by inspection that 8 and (0)) have the same root label.
(iii yield- preserving:
(ō)
g
(K--1)
[definition]
(00)
B(K-11)
[H]]
=((()))
[definition]
(iv) weight-preserving
Recall that if 72) E V, then (0)) = 00

---

R-1
w(6) w (0(2(1) -> ((0)
w (000) - 2(0-11 g(i
x
x
w
==
equal by constr.
1n ((1) - 1 Looe
equal by constr.
K
- 7/1 1) g/ (66-111)
((0
m
equal by IN
8 w
? (K)
7(k)
by
K-
= (()
We have used the specific weight settings in Def. 3, and that 1 is the @-identity element.
Case (k < co): Here, 8 has the form the left and Φ transforms into the form the right:
(K)
UK
B (K-)
7(h
g (()-
7
di
(k)
((4)
1. 2)
(2-13
((9)
5.83/,08 2)
g
(2)
4003
19(1)
(0)
g()
d ((o) A
((x-1))
200/000
(00
In this case, we observe 3 Vi E (1,..., Ro 13 7 $ C.
We check each of the properties:
(i) o: D + D': We verify that the rules in the derivation s()) are in 6':
The top rule (K) - (()) 70 / is an instance of (6b). The side condition X c N, e T holds because the definition of Ie ensures that (k) E T.

---

The rules in the left subtree follow the same argument as the proof of the k 20 case.
Each middle rule of the right subtree 7( //-- ((--1) 700) 70000n (for = -++1,.... ..... K) is an instance of (6d). The side condition X - 81 E R. E N hold because (k) EN, and each of the y > (6 (((-1) rules was part of the spine (thus, in R).
The bottom rule of the right subtree 7/00 1000)000 + E is an instance of (6f).
Lastly, because each ((i) subtree is in D'' by IH, we have that (6)) C D
(ii) root-preserving: clear by inspection that 8 and ((6) have the same root label.
(iii preservge:: The argument here is essentially the same the k case. The only difference is that the empty string (e) will be concatenated the right-most element, which does not change the yield as the identity element of the dring-concatenation operator.
(iv) weight-preserving The argument is similar to the k- case
R
w(6) w (2(00 3(0)
w (7(0) > (1-11) )(i-1)) x
w
equal by constr.
1 + 3
k
+ 1 (li
8
(90
1=2
(k)
+ 7(0
1ii-1) your (,10
1
equal
1-++1
w(1
(1) /.10)
5)
cousir.
K-
gr0)
w
i=0
(()()))
We have used the specific weight settings and the fact that is the identity element of the @-operator. Conclusion. We have successfully verified that the propertics (i-iv) hold in each possible case; thus, by the principle of induction, Lemma 3 is true.

---

6' GLCT(6, R,C) for any choice of and C. Then, the functions @ and 6 defined by Alg. and Alg. (respectively) are inverses of each other. Thus, a bijection of type DN + D'x exists.
Lemma 4. Let B
Proof. N.B. We first explain why only bijection of type DN - D'y rather than bijection of type D D'. The reason is that the set 'D' contains derivations rooted at the new slashed and frozen nonterminals, which do not exist in G. However. all derivations with root label in N are preserved in the bijection; that is why restricted the type of the bijection to have the range D'x-
DN
D'
6-1
D
Note that it would be sufficient to show bijection between Ds D's, but prove the stronger version it fits with inductive proof strategy. We note that the derivations in D' D'y are each labeled by either a frozen or slashed nonterminals symbol. The meanings of these frozen and slashed symbols do not need be preserved since they are undefined in 6. What important that the derivations in D'y that use these derivations use them a
manner.
Our proof will refer to the explicit functions & and Φ (Alg. and Alg. 2). We will prove that á and & are inverses of each other in two parts:
Part 1: We will show that vo' E Div: ((0 =
Part 2: We will show that v6 e Dy: (- = 6.
Proof of Part 1: Our proof will proceed by structural induction on the subtree relation (<). Fix an arbitrary derivation tree 8' E D'x-
Inductive hypothesis (IH): For all subtrees 8" 8' where (68") N: 6(0-)(8")) 8".
Base case (8' V): Φ and Φ the identity function; thus, @ 1(8') 8' as required.
Sequence case: Both @ and ø-1 apply pointwise to sequences; thus, 0 ... 8kk)
(01((x))) (00-1(8))
= ( ((4)) s( (8k)) = 84 ... ...8'k as required.
Inductive case: There are two cases to consider: (1) the top rule is an instance of (6b) or (2) the top rule is instance of (6a). These cases are mutually exclusive, difference in the top rule ensures any pair of derivations unequal. We see that these cases exhaustive, as the only way to have derivation labeled A that in G is if the top rule of 8' is instance of (6b) or (6a).

---

Case (top rule is (6a)): In this case, 8' must have the following form:
We note that the chain of rules exposed along the left edge must have the following structure: we start with an instance of (6a) followed by zero or more instances of (6f) ending in an instance of (6c). None of the 3 subtrees contain slashed or frozen symbols in their labels. However, note that the subtrees of the -uubtree may contain slashed frozen symbols.
(K)
y(R)
-3
((N-1)
B(N-2) 22)
y(3)
(2
We verify that (8') 8' below:
(00
7(0)
(K-1)
gik
7(K
B3 1)
grr
6-
(0)- o
g((k
8'
(2)
70
--1 g(z)
7033
30))
gg00)
(rios)
The first step applies Alg. 2, and the second step applies Alg. 1. By induction, each recursive call this expression successfully inverts ø for their respective argument. is also clear, by inspection, that line 10 of Alg. correctly inverts the transformation of the spine performed on line 9 of Alg. Thus, by induction, our definition of the inverse is correct for this case.

---

Case (top rule is (6b)): In this case, 8' must have the following form:
Here, the top rule is an instance of (6b); thus, it combines a derivation labeled by some frozen nonterminal 7((0) with a derivation of some slashed nonterminal yx*3 //th) No- tice that the attached frozen nonterminals 7.()) must match the slashed nonterminal's 's denominator, and the slashed nonterminal's 's numerator must match the label {(8'). The left subtree exposes the chain of rules that built the frozen nonterminal (R) This chain is a (possibly empty) quence of (6f) followed by the base case (6e). The right subtree exposes the chain of rules that built slashed nonter- minal 7(8) //00 These are a (possibly empty) sequence of (6d) ending in an instance of the base case (6c). By con- 1(8-13 1087/189 struction, none of the ( may contain slashed frozen symbols in their root labels, as they must be instances of one of the rules (6c), (6d), (6e), (6f).
(K)
7(0)
(4 (k)
(1-1))
(g
(((-2)
((8)
0 K
7(1)
(g()
g 2) (01/111-11
We verify that (8)) 8 by applying Alg. 2 and Alg. in the equations below: Φ (87)
(()
g(x-1))
g((
(k+1)
(1-11
1908 1)
(g(E22) 2)
30
gro)
300
7(
gcks
(00//0441)
g(++1)
((83/1(K-2)
1311)
1101//1-111
,180/100)
g(0)
8'

---

By induction, each recursive call in this expression successfully inverts e for its respective argument. It is also clear, by inspection, that line 12 of Alg. correctly inverts the transformation of the spine performed on line 7 of Alg. 2. Thus, by induction, our definition of the inverse is correct for this case.
Conclusion (Part 1). We have verified the two cases of the inductive step; thus, by the principle induction, we have shown that Part 1 of Lemma 4 holds.
We now continue to Part 2 (next page).

---

Proof of Part 2: Our proof will proceed by structural induction on the subtree relation (-). Fix an arbitrary derivation tree 8 D.
Inductive hypothesis (IH): For all subtrees 51 < 6: ( = Ö1.
Base case (Ō V): & and ø are the identity function; thus, ( = å as required.
Sequence case: Both and お- apply pointwise to sequences; thus, & ( ... 8x)) (~b()) ..- v(Ōk)) ()(())) ( ()(ók)))) = 61 8g as required.
Inductive case: Recall from the proof of the inductive case of Lemma 3, must have the general form:
where K (() c (VUN),, vi (1,1,.... ..... K), and (7(K) -> (1- 3(k 1)) ... (7(2) + 7(1) (()) is its spine ((8). (We
(K-1)
g(K-1)
only show the cases for when y(1) E The case when y()) e V follows the same argument.)
3 ((C-2)
Now, let 1: be the index of the left corner, or oo if it does not exist. We consider two cases: ko oo and k <
7
(8
(1))
Case (k: oo): We seek to show that / ()(()) 6 for this case. The equations below depict how spine transformations performed by Alg. 1 and Alg. cancel each other out:
(
Y0R5
3(K-1)
3(K-1)
BIK
2))
Φ (6(8) = --
2()
(2)
700
70
g(
g
Thus, by induction, o ((((8) for all derivations that fall into this case.

---

Case <o):: We seek show that (d(()) 8 for this case.
((8)
(R 1)
1312 17
7003/-011
(o(6)) 6-1
g((-2))
g(++1)
1
5000
1964 2))
(00
B(R-2)
(8+1))
g(8-1)
16
(
(90
700
(99)))
((0)
- 8
Thus, by induction, (ò(() for all derivations that fall into this case.
Conclusion (Part 2). Since we have shown that each of the possible cases (f - oo and & < 0o) satisfy (ő(6)) = 6, it follows that Part 2 of Lemma 4 is true.
Conclusion. We have proven Part 1 and Part 2; thus, Lemma 4 holds.

---

Theorem (N -ijeectvv equivalence), Suppose @ (N, is a WCFG and 6' R,, where R S and 2 VUN. Then, = 8
Proof. Recall from $2 that --biecctive equivalence (6 = (') requires the existence of a structure- preserving bijective mapping of type DN > D'y- Lemma 3 shows that e in Alg. 1 is mapping of type - D' that preserves the desired structure (label, weight, and yield). Thus, ø is structure-preserven Lemma 4 shows that & is bijection of Φ: DN - D'x- Thus, we have verified the existence of a bijection and, therefore, 6 = 6'.

---

D Proof (Sketch) of Theorem (Speculation-GL.T Bijective Equivalence)
Theorem 2 Speculation-GLLC bijective equivalence), For any grammar B, and choice of C and R, SPEC( C, and GLCT C) are X-bijectively equivalent where X is the complete set of symbols (i.e., original, frozen, and slashed).
Proof (Sketch). A straightforward inductive argument can be made show that the derivations of specu- lation and GLCT under the conditions of Theorem 2 will produce isomorphic trees.
We sketch the derivation mapping from speculation to GLCT. We not only provide a sketch for the fact that the mapping is a structure- prasuurrnng bijection. It is straightforward. albeit laborious, to extend our proof sketch to proof; such proof would follow the same structure as our proof of Theorem 1.
Base case (terminals). This case trivial, as terminals are identical between the transformations.
Inductive Case. We consider three cases for each kind of nonterminal: original, frozen, and slashed. the diagrams below, we show how the backbone of the derivation is changed. We note that the B-subtrees the tree are transformed recursively. In each of the diagrams below, the speculation derivation is on the left, and its corresponding GLCT derivation is on the right.
Original nonterminals. This case was discussed in Fig. 2.
Frozen nonterminals. The rules defining the frozen nonterminals are identical between the transformations, the backbone is unchanged in this case.
(RR
8 -1
B 1)
(93
7(1
(9(1)
(3(1)
g/0)
Slashed nonterminals. Recall from $3.2 that the difference between the slashed nonterminals in speculation
and GLCT is the recursive rule defining slashed nonterminals ((9d) vs. (6d)). The only effect of this difference is that slashed nonterminals in speculation have left-branching derivations, and in GLCT, they have brathbbranchig derivations. The mapping below works for any slashed nonterminal:
000
0004400
(
1(R-1)
g 1)
((K-2)
(k4
UK0AA 23
B 99
g(h)
g(x-1)

---

Strucfuree-reeservation and invertibility. In each of the cases above, it straightforward see that mapping
label-preserving: the trees in the diagrams each have the same label.
yield- jield-preserving: the yield of each B-subtree is preserved (by induction hypothesis), and string concate- nation is associative with identity element E.
the weights of rule weights multiplied are equal (by construction), associative and commutative (by assumption), and each subtree equally weighted (by induction hypothesis). invertible: the mapping between the trees invertible because the manipulation of its backbone (i.e., its exposed structure) invertible, and the mapping for each subtree invertible (by induction hypothesis).
Conclusion.
The above cases cover all possibilities. Each sketches the structure-presere bijective mapping between speculation and GLCT derivations for all their nonterminals (original, slashed, and frozen). Therefore, we have sketched a proof of Theorem 2.

---

E Proof of Theorem (Left-Recursion Elimination)
Theorem (Lest-recusioon elimination). Suppose that e' -TRRIM(GICCTOO,R.. where
C has no wnary rules
R 2 the left-recursive rules in
C 2 bottoms(R)
Then, B' is not left-recursive. Moreover, d(@') S 2-C where C' is the number of SCCs in the left-recursion graph for G.
Proof. Recall from Theorem 1 that there exists crructure-preserving bijection between Dx and D'v- Our proof shows how the mapping é (Alg. 1) removes (unbounded) left recursion from @ by analyzing the structure of its transformed trees. Below, we show how Φ takes any derivation tree 8' = (()) where 8' DD' (right).
D (left) and maps a
(3)
(1)
((U)
(00/1
(
(3)
(2)
40/00
spine
(
(2)
/9 (2)
00/-
0
100
7am
(7
(0
(8)
The
spine
((K)
(AAA (R)
Teet
where g(k) is (possibly empty) sequence of terminals. We note that the A-subtrees on the right are isomorphic to their counterparts on the left because à has (implicitly) transformed them. Let
((I) ((2) ((K) denote the segmentation of the left edge of i into sequence of spines. The node (() names indicate its top and bottom elements. Note that spines may contain single node; 7rop - in
these cases. We also note that the transitions between spines occur when rule the left is not in R.
Avoiding a subtle mistake. We may assume that each A-subtree non-empty because the is unary- free by assumption. This unary-free free assumption is important because ensures that the form of 8 will not be left-recursive simply because some of its A-subtrees are empty.

---

The accordion effect. Recall that e (recursively) hoists each left-corner subtree along its respective spine. 33 'hee accordion effect the result of repeatedly hoisting: Each spine is contracted into two nodes on the left side of 8' corresponding to their respective spine's ' top and bottom elements. Each of the top nonterminals has an unbounded chain of right-reeursive rules corresponding to the extracted spine.
The accordion effect assumes that the bottommost node of the spine is always C-labeled and, thus, is hoisted by & in the diagram. It is easy to see that our condition on C. guarantees this because every node that might end the spine is included in C (by eq. (10)). Furthermore, if C is a superset of (ottoms((R). then & (by definition) will be unaffected because the bottommost elements of the spines (i.e., those that are hoisted) already included." 34
For simplicity, the accordion diagram only illustrates the case where each spine (()) not a singleton
containing one element outside of C. We now address that case. Here, Ttop Tho and the rule Yto +
(6) (8)
(t)
Ttop Shop cannot be in R. Like the case depicted, the spine contracts into two nodes on the right: Ttop
((+1)
(4)
(i)
and 'Topp However, we now have an instance of (6a) instead of (6b) in the tree the right; thus, there is no slashed chain of nonterminals.
Bounding the left-recursion depth. The result of the accordion effect is that each spine on the left (of unbounded length) is contracted into two nodes in the tree on the right. From here, we can see that 8' has bounded left-recursive depth as long as there is a bounded number of spines. Recall that each spine is the maximum-length sequence of rules along the left of the derivation starting at the root. Since R includes all left-recursive rules, this means that each spine in the sequence C(),c(2), ,.., C(K) completes least one SCC- meaning its nodes cannot be visited later in the path. Thus, d(8') S 2-C where is the number of SCCs in the left-recursion graph for 35
Conclusion. The above argument bounds d((())) as a function of 6. We can bound d(0²) by m d((())) because ô and 8' are in one-to-one correspondence and, thus, no trees in D'v will be overlooked. Note that G' is trimmed so we can focus on --derivations. Because our earlier bound, d()())) S 2- C, is independent of 8, the maximization is trivial: d d(3') s 2-C. Thus, the left-recursion in G' is bounded, and Theorem 4 holds.
Thhss interpretation is discussed throughout the paper: informally in Fig. 1 and $3.1, semi--orrmall in Fig. 2, and formally in the proof of Theorem 1 (Appendix C).
3WW note that other ways exist set Z that can break left-recursion eycles. For example, if is feedhack node set (i.c., subset of nodes such that removing them and their incoming and outgoing edges results in an acyelic graph). However, the construction is messier, as there will instances (6f) along the left of 8'. This still eliminates left recursion, as those frozen nonterminals will not be left recursive. Additionally, is unclear whether there any benefit terms of grammar size or left-recursion depth to these alternatives: thus, we only analyze the simpler case.
39This bound can be reduced by including more rules in R. at the cost of inereasing the size of 6'. For example, if R R, the left-rocursion depth is two, but 6 will likely he larger according to Proposition 3.

---

F Additional Experimental Results
This section presents additional results the experiments discussed $4.1. Table 2 complements Table with ratios comparing the size of the output grammar' resulting from SLCT with those from GLCT, Appendix F gives analogous results as evaluated on the number of rules. (We note that these results are consistent with those presented in Table 1.)
Language (size)
Language Method (size)
Method
Raw
+Trim
Raw
+Trim
Basque SLCT
3,354.445
245.989
411,023
English SLCT (21.272) GLCT
514,338
26,655
46, 46,088
(73,173) GLCT
644.125
245,923
411,023
203,664
26,289
46,088
SLCT//LCC
5.21
SLCTT/GCCT
2.53
1.01
French SLCT
5,902.552
106,860
173.375
German SLCT (100.346) GLCT
21,204,060
272, 772,406
434,787
(105,896) GLCT
147,860
106,628
173,375
1,930,386
271,752 434,787
SLCT/GLCTT
39.92
SLCT/GLCT
10.98
Hebrew SLCT
14,3043366
564,456
979,040
Hungarian SLCT (134,461) GLCT
17,823,603
151,373 242.360
(84,648) GLCT
2,910,538
564,074
979,040
748,398
151,013 242,360
SLCT/GLCT
4.91
SLCT/GLCT
23.82
Korean SLCT
54,575,826
87,937
96,023
Polish SLCT (41,957) GLCT SLCT/GLCT
2,845,430
61,333
79,341
(59,557) GLCT
3,706.444
86,529
96,023
177.610
61,253
79,341
SLCTIGLCT
14.72
1.02
16.02
Swedish SLCT
20,483.899
1,894.346
3,551,917
(79.137) GLCT
6,896.791
1,871,789 3,551,917
SLCT/GLCT
2.97
Table 2: Same numbers as Table 1 but complemented with the additional SLCT/GLCT rows, which measures the ratio of the SLCT size to the GLCT size.
Language rules)
Language of rules)
Method
Raw
+Trim
-e's
Method
Raw
+Trim
-e's
Basque
SLCT
1,060,702
62,836
145.345 145,345
English (4,592)
SLCT
147,221
5,941
15,653
(28,178)
GLCT
157,273
62,803
GLCTT
43,724
5,758
15,653
SLCT/GLCT
6.74
SLCT/GLCT
3.37
1.03
French
SLCT
1,970,737
31,317
64,571 64,571
German (31,156)
SLCT
6,891, ,427
71,218
152,391
(30,963) GLCT
52,545
31,201
GLCT
466,978
70,891
152,391
SLCTIGLCT
37.51
SLCTTGLCT
14.76
Hebrew
SLCT
4,410,783
128,186
335,456 335,456
Hungarian (43,344)
SLCT
5,868,984
46,494
91,980
(31,587)
GLCT
612,904
127,995
GLCT
177,309
46,314
91,980
SECT/GLCT
7.20
SLCT/GLCC
33.10
Korean
SLCT
18,113,579
37,342
41,382 41,382
Polish (20,109)
SLCT
951,176
24,105
33,104
(28,132)
GLCT
1,157,353
36,638
GLCT
61,916
24,065
33,104
SLCT/GLCT
15.65
1.02
SLCT/GLCT
15.36
Swedish (27,062)
SLCT
5,801,173
355,783
1.191.574
GLCT
1,272,201
351,552
1,191,574
SLCT/GLCT
4.56
1.01
Table
Same settings as Table but evaluated the number rules rather than grammar size.

---

G Filtering Optimization for GLCT
This section shows how the filtering tricks mentioned in $3.1 can be incorporated into the left-corner transformation to reduce the number of useless rules created by Def. 3.
Our first filtering trick is based on Johnson's (1998) strategy for reducing the number of uscless rules, It works as follows: the slashed nonterminal x/x is useless if X is not reachable from Y in a left-recursion graph for é which only includes the rule set R.
Our second filtering trick is based on Moore's (2000) filtering strategy, which extends Johnson's 's (1998) with additional filtering based on retained nonterminals. The slashed nonterminal Y/X useless if none of the following hold: (i) Y Y-S, (ii) Y appears on the right-hand side of some rule in R in a position other than the leftmost position, (ii) Y appears on the right-hand side some rule in R R. More formally, the set of retained nonterminals
R def
([S) (3, (X- R, ( B) R - E
(15)
Let X ~ a denote whether a is reachable from X in the left-recursion graph for R. Let X ~ C denote whether 3a C: X mn Then, we use the following equations for the rules R':
x X:
X R/C (16a)
X + ā 8/a:
X ~ a, a, EC (16b)
x/X 4 s:
X C (16c)
Y/a - B 8/x:
X aaBe R, R, a,a C (16d)
r a:
X t a (16e)
x aB:
X a R c (16f)
Verifying that these filters only drop useless rules is straightforward.
36Baur et al. (2010) adopt similar filtering techniques.

---

H Fast Nullary Elimination
Opedal et al. (2023, $F) gives an approach for eliminating nullary rules from grammar & that requires computing the null weight xx(e) of each nonterminal (X E N). These null weights are the (smallest) solution to the system of polynomial equations given by (5) where we replace 1 with 0 in the base case (5a). In general, this system can be solved numerically using fixed-point iteration or Newton's method (see, e.g., Esparza et al., 2007; Nederhof and Satta, 2008; Vieira, 2023). In our case, where B' is the output of GLCCT, free of nullary rules." 37 Specifically, this system of equations for o' is linear and can be solved exactly in O (IN))) time by using an algorithm for the algebraie path problem (e.g., Lehmann, 1977; Tarjan, 1981) instead of relying on cammericl--pproximmale
solve the system exactly and efficiently, assuming the original grammar @ is
methods.
Proposition 4 (Fast null-weight computation). The null-weight equations for 8' -GICT( R,C) are linear, provided @s is nullary free.
Proof. First, observe that only the nullary rules those with slashed nonterminal on its left-hand side, x x/x- E (6c). We can see that rules created by (6d) and (6b) dictate that these slashed nonterminals only occur on the right-corner position of other rules. It then follows that any derivation with an e-yield contains at most one nullary rule X/x + E as well as a (possibly zero) number of unary rules on the form X/Y >> X/z. This is the case because rules of the form X/y + 3 X/2 with |3] > contribute a null weight of 0 by the assumption that the original grammar has no nullary rules (i.e., each of the original symbols has a null weight of zero, and because GLCT is A --bjeectively equivalent, they continue to have a null weight of zero).
The null- null-weight equations simplify to the following system:
6 (c) + w & Gy
(8)
(17)
(8/1 -11--88 X/Z)ER'
(x/Y Se
θ w & 6K
(18)
(x/y /2/
(X/Y "')jRR''
We can represent this system as a linear equation. We define a matrix W c WPV">"" and vector v E WA
For each x/y, X X/2,X/xEWX
W Wx W and
Vx/x θ
(19)
(X/Y "X/2)/R
(X/x ">)CR
Then, the null weight for each E is
G (E) = [W"v]a
(20)
where W is the solution to W' W W In the case of the real semiring =*= -[--W)- For other semirings, it may be computed in (11)) time using algebraic path solver (e.g., Lehmann, 1977; Tarjan, 1981).
W)-1,
37 Suppose (() = w. If w o 0, we require at least one nullary rule of the form S - This limited type of rule is straightforward to accommodate in our approach, but we have omitted it from this discussion for simplicity.


Reviews:
[{"review_id": "Tmsbww3r5M", "reviewer": "Reviewer_tJ8c", "summary": "", "questions": "", "limitations": "", "rating": 2, "confidence": 4, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and feedback. We appreciate that you see the contributions in exploring new variants of existing algorithms and the new research opportunities that arise from making the connections between LCT and speculation explicit.\n\n> I am not sure that EMNLP be the best place for this paper. It is really a very formal paper, with a very long technical appendix.\n\nRegarding the \"long technical appendix\": We believe that several *ACL papers could benefit from more formal treatments of their claims, but reading the appendix is by no means necessary for using or welcoming the method proposed in our paper. Besides, the length of the appendix stems mostly from the many diagrams, which we felt were important to include. The proofs themselves do not use particularly sophisticated techniques (they should be accessible to an undergraduate CS student). Previous papers on the LCT and speculation were informal and we felt that the literature deserved a more complete treatment.\n\n> The empirical part only addresses the application of GLCT on an English grammar with or without the post-processing phases. There is no run-time evaluation of the resulting grammar. [...] Also, the comparison have been tried only a single grammar, when it would have been relatively easy to apply it of other existing PCFGs (or to PCFGs extracting from existing treebanks) \n\nYour main concern seems to be that the paper could benefit from more experiments and stronger results. We agree that the paper would be more complete with experiments on more (possibly non-English) grammars and that it would be interesting to see how our method affects parsing runtime. We therefore plan to make the following additions to the final version:\n1. Add experiments on the SPMRL dataset (Seddah et al., 2013, 2014), which includes grammars in nine different languages.\n2. Compare runtime on the output grammars using a top-down parser (i.e., a parser that fails in the presence of left-recursion), such as NLTK’s recursive-descent parser.  This comparison will be easy for us to include. Note that the running time complexity of parsing depends linearly on the grammar size so we would expect parsing to run faster following our generalized LCT. However, we agree that it will be useful to include an analysis of how the grammar size affects parsing speed in practice and thus we will include it in the final version.\n\n> The gains in terms of sizes versus SLCT are real without post-processing, but are just linear (in Figure 6) and essentially disappear on the large English grammar after post-processing (removing useless non-terminals and productions). And of course I believe one wish to run the reduced grammars rather the non-reduced ones \n\nRegarding our experimental results, you point out that our method only leads to marginally smaller grammars after post-processing. While true, the post-processing still incurs a computational cost and without them our method is significantly better. \n\nWe also note that producing a smaller grammar is not the only contribution of our new transformation. We also unearthed an interesting connection to speculation (Eisner & Blatz, 2007) and have endowed the LC transformation with additional flexibility (beyond that of the selective LC transformation). The fact that it produces smaller grammars is a nice result, but should be viewed as a bonus in terms of contributions. These results also provide insights on how Johnson and Roark’s (2000) transformation, with fewer degrees of freedom, already achieves performance that is hard to improve on (after post-processing), which we think is interesting to note as well.\n\n> My final reserve (even if I don't like it) is more general about the usefulness nowadays of such an algorithm, when grammars have essentially been replaced by neural parsing. But the authors rightly motivate the interest for psycho-linguistics\n\nWhile it may be true that modern, state-of-the-art parsing is achieved by neural parsers, many of these methods still involve context-free grammars (e.g, Durrett and Klein, 2015; Drozdov et al., 2019; Kitaev, Lu and Klein, 2022). Our work is complementary to these neural parsers. We can for instance imagine a setting where a practitioner who wants to train a neural Earley parser applies our transformation as a preprocessing step in order to eliminate left-recursion (see Opedal et al. (2023) on how left-recursion interacts with Earley’s algorithm). Similarly, if one wishes to train a top-down neural parser, left-recursion should be eliminated.\n\n> Line 147: it would nice to mention \\sigma (the yield \\sigma) Line 149: similar with weight w Figure 6: the definition of grammar size could be precised\n\nThank you for spotting these typos!\n\nReferences that are not already cited in the paper:\n* Overview of the SPMRL 2013 Shared Task: A Cross-Framework Evaluation of Parsing Morphologically Rich Languages (Seddah et al., SPMRL 2013)\n* Introducing the SPMRL 2014 Shared Task on Parsing Morphologically-rich Languages (Seddah et al., SPMRL 2014)\n* Neural CRF Parsing (Durrett & Klein, ACL-IJCNLP 2015)\n* Unsupervised Latent Tree Induction with Deep Inside-Outside Recursive Auto-Encoders (Drozdov et al., NAACL 2019)\n* Learned Incremental Representations for Parsing (Kitaev et al., ACL 2022)", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "It is always interesting to explore new variants of algorithms, potentially with better performance (in terms of speed or space). This is the case for this algorithm, at least before the post-processing phase. Still,  the gains in terms of number of productions or grammar size are essentially linear on the small toy proposed grammars in Fig. 6\nThe relationship with the speculation algorithm is also interesting, opening potentially the way to various strategies to slash non-terminals leading to various ways to reorganize parts of derivation trees.", "reasons_to_reject": "I am not sure that EMNLP be the best place for this paper. It is really a very formal paper, with a very long technical appendix. The empirical part only addresses the application of GLCT on an English grammar with or without the post-processing phases. There is no run-time evaluation of the resulting grammar. \nThe gains in terms of sizes versus SLCT are real without post-processing, but are just linear (in Figure 6) and essentially disappear on the large English grammar after post-processing (removing useless non-terminals and productions). And of course I believe one wish to run the reduced grammars rather the non-reduced ones\nAlso, the comparison have been tried only a single grammar, when it would have been relatively easy to apply it of other existing PCFGs (or to PCFGs extracting from existing treebanks)\nMy final reserve (even if I don't like it) is more general about the usefulness nowadays of such an algorithm, when grammars have essentially been replaced by neural parsing. But the authors rightly motivate the interest for psycho-linguistics\n", "questions_to_authors": "", "paper_topic_and_main_contributions": "The paper propose a novel algorithm called Generalized Left-Corner Transformation (GLTC) to transform weighted left-recursive CFGs into weakly equivalent ones without left-recursion (same yield, same weight, but different parse trees). Interestingly the transformation proves to be close to the so-called \"speculation\" transformation introduced by Eisner and Blatz (2007), with similar notions of added slashed and frozen non-terminals. The paper is rather formal, with a very long proof of equivalence provided in Appendix B (around 14 pages !).  The only empirical part of the paper is the application of the transformation to a large English PCFG, with a comparison in terme of resulting grammar size with an other existing similar algorithm (SLTC), with or without post-processing (trimming and co-trimming) used to remove useless extra non-terminals and productions.", "excitement": 2, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Typos_Grammar_Style_and_Presentation_Improvements": "Line 147: it would nice to mention \\sigma (the yield \\sigma)\nLine 149: similar with weight w\nFigure 6: the definition of grammar size could be precised"}, "extra_text": {}}, {"review_id": "QH6QS8xppE", "reviewer": "Reviewer_FNxN", "summary": "", "questions": "A) What do you mean by stating that transformation to Greibach normal form requires no left recursion. Do you subsume the weighted context-free grammars, not the usual ones? As I know, the algorithm for usual CFGs starts from a grammar in Chomsky normal form and left recursion does not make a problem for it.\n\nB) Despite your method produces smaller grammars, the difference might be negligible for practical applications. Do you have any performance measurements on ATIS grammar and some standard parsing algorithm? It would be nice to show that the produced speedup is significant, if so.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your overall positive review and feedback. We are glad that you appreciate both the theoretical and empirical results and that you found the paper to be well-written.\n\n> The scope of the work seems to be slightly different from typical EMNLP paper, it better suits for a mathematical formal language conference.\n\nRelated to this, we acknowledge your comment on our work having a slightly different scope from a typical EMNLP paper. However, we believe that there is great benefit in seeing contributions in regard to theory and methods in the same venue as you see empirical applications of those methods, not the least for the sake of sparking new ideas. For instance, the LCT is known to improve the stack depth of parsers for left- and right-branching structures (Johnson, 1998), which makes them better for beam search decoding. \n\n> The empirical results are mathematical by nature (for a grammar of a certain structure our algorithm produces smaller grammars), not empirical (for a grammar of a certain structure our algorithm produces grammars that are parsed faster). Thus, the absence of really empirical results.\n\nWe chose to evaluate on grammar size following in previous work on LCT transformations (Johnson and Roark, 2000; Moore, 2000). Moreover, (nearly) all context-free parsing algorithms run linearly in grammar size. Experiments on grammar size are more replicable because they do not depend on the details of the computer it was run on or the various orthogonal choices of the parsing algorithm’s implementation. However, we will add a running time comparison in the final version (see response above for detail).\n\n> From the point of pure mathematics, the results are rather incremental.\n\nThe LCT is an old well-known transformation and is an integral part of the conversion to GNF. Yet, we were able to generalize and improve upon it. This seems notable to us. Furthermore, the prior transformations: LCT, selective LCT, and speculation do not have correctness proofs. We have provided a detailed correctness proof of bijective equivalence (Thm. 2, App. B.2) and for left-recursion elimination (Thm. 1, App. B.1).\n\n> A) What do you mean by stating that transformation to Greibach normal form requires no left recursion. Do you subsume the weighted context-free grammars, not the usual ones? As I know, the algorithm for usual CFGs starts from a grammar in Chomsky normal form and left recursion does not make a problem for it.\n\nGNF requires that the leftmost symbol on the rhs of every production rule is a terminal. Thus, a grammar in GNF is not left-recursive (and even stricter – there are no left-corner relations at all). See Greibach (1965) for the conversion algorithm. You may be referring to an alternative conversion algorithm that goes through CNF (possibly Koch and Blum (1997)?).\n\n> B) Despite your method produces smaller grammars, the difference might be negligible for practical applications. Do you have any performance measurements on ATIS grammar and some standard parsing algorithm? It would be nice to show that the produced speedup is significant, if so.\n\nWe agree that even though the grammar factor will be made smaller it is still useful to examine the effects on parsing speed. We plan to add experiments using NLTK’s top-down recursive descent parser (which is sensitive to left-recursion) in the camera-ready version of the paper in order to get more insights on this and strengthen the empirical section of the paper. \n\nReferences that are not already cited in the paper:\n* Greibach normal form transformation, revisited (Koch and Blum, STACS 1997)", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "* A nice mathematical result with both formal and informal justification. The paper is very clearly written.\n* The proposed algorithms has better empirical properties than its predecessors. These properties are demonstrated on a dataset of context-free grammars for several typologically diverse languages.", "reasons_to_reject": "* The scope of the work seems to be slightly different from typical EMNLP paper, it better suits for a mathematical formal language conference. However, the empirical evaluation made in the rebuttal makes the paper appropriate for EMNLP as well.\n* From the point of pure mathematics, the results are rather incremental. However, there are still", "questions_to_authors": "A) What do you mean by stating that transformation to Greibach normal form requires no left recursion. Do you subsume the weighted context-free grammars, not the usual ones? As I know, the algorithm for usual CFGs starts from a grammar in Chomsky normal form and left recursion does not make a problem for it.\n\nB) Despite your method produces smaller grammars, the difference might be negligible for practical applications. Do you have any performance measurements on ATIS grammar and some standard parsing algorithm? It would be nice to show that the produced speedup is significant, if so.", "paper_topic_and_main_contributions": "The paper proposes a new version of Left-corner transformation for weighted context-free grammars. This transformation is required for using some standard parsing techniques. The authors show that their method combine the ideas behind Selective Left-Corner Transformation and Speculation Transformation but produces smaller grammars than the former and eliminates left recursion in contrast to the latter. They demonstrate the smaller size of the produced grammars on several artificial examples and the ATIS grammar of English.", "excitement": 4, "reproducibility": null, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Typos_Grammar_Style_and_Presentation_Improvements": "A) I prefer notation A\\B for \"something that can be appended to A to form B\". It corresponds to natural rule B -> A A\\B, e.g. of Lambek calculus."}, "extra_text": {}}, {"review_id": "R5SvHZTu2F", "reviewer": "Reviewer_WpEo", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review and positive feedback. We are glad that you find our work to be an interesting contribution and appreciate that you caught our hints to future research!\n\n> l. 228: There could be a more formal definition of the condition on \\vec{\\Gamma}.\n\nGreat suggestion – we will add that in the final version.\n\n> l. 432: Regarding the empirical evaluation, it would be interesting to understand if/how the efficiency gains (l. 471) relate to particular grammar properties. This could be verified with grammars extracted from treebanks with different annotation schemes.\n\nWe agree that an empirical evaluation on how different grammar properties affect the outputs would be an interesting addition. We are going to evaluate and compare these gains on the grammars from the multilingual SPMRL dataset (Seddah et al., 2013, 2014) for the final version.\n\nReferences that are not already cited in the paper:\n\n* Overview of the SPMRL 2013 Shared Task: A Cross-Framework Evaluation of Parsing Morphologically Rich Languages (Seddah et al., SPMRL 2013)\n* Introducing the SPMRL 2014 Shared Task on Parsing Morphologically-rich Languages (Seddah et al., SPMRL 2014)", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "* This elegant generalization of left-corner parsing (which is more than 50 years old) and its application on other left-corner transform evolutions is without a doubt a very interesting contribution for the parsing, FG and MOL communities.\n* The material is presented in an accessible way, with very good knowledge of the related literature. \n* Many details for further research are addressed, not only in the \"Limitations\" section, but throughout the paper, such as, e.g., the transferability to a right-corner scenario ", "reasons_to_reject": "None as per reviewing guidelines.", "questions_to_authors": "", "paper_topic_and_main_contributions": "* This paper introduces a generalization of the original left-corner transformation (\"generalized left-corner transform\", GLCT) from Rosenkrantz, building on the \"speculation\" transformation from Eisner & Blatz (2007). \n* Proofs are provided that confirm that 1. GLCT indeed removes left-recursion and 2. it produces bijectively equivalent grammars.\n* Futhermore, the relation between GLCT and \"selective left-corner transformation\" (SLCT) from Johnson & Roark is studied, and SLCT is found to be a special case of the GLCT. \n* Finally, it is emprically shown that GLCT produces smaller grammars than SLCT.\n\n", "excitement": 4, "reproducibility": 5, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {"Typos_Grammar_Style_and_Presentation_Improvements": "* l. 228: There could be a more formal definition of the condition on \\vec{\\Gamma}.\n* l. 432: Regarding the empirical evaluation, it would be interesting to understand if/how the efficiency gains (l. 471) relate to particular grammar properties. This could be verified with grammars extracted from treebanks with different annotation schemes. "}}]

Author rebuttal:

Meta-review: This paper proposes a generalized Left-Corner Transformation which eliminates left recursion in left-corner transformations yet can produce bijectively equivalent grammars. The authors also provide a detailed correctness of their bijevtive equivalence and prove to be close to the “speculation” transformation of Eisner and Blatz (2007). Empirical comparison with the selective left-corner transformation of the work of Johnson and Roark (2000) show that their approach can reduce the size of output grammar significantly over eight languages.
Decision: Accept-Main