# LR Parsing for LCFRS
## 2 Preliminaries  
### Linear Context-Free Rewriting Systems  
We now introduce Linear Context-Free Rewriting Systems (LCFRS). In LCFRS, a single non-terminal can span \(k\geq 1\) continuous blocks of a string. A CFG is simply a special case of an LCFRS in which \(k=1\). We notate LCFRS with the syntax of Simple Range Concatenation Grammars (SRCG) [36], a formalism equivalent to LCFRS. Note that we restrict ourselves to the commonly used string rewriting version of LCFRS and omit the more general definition of LCFRS of [37]. Furthermore, we assume that our LCFRS are _monotone_ (see condition 3 below) and \(\varepsilon\)_-free_ (we can make this assumption without loss of generality see [20; 38]). Definition 1 (LCFRS): An Linear Context-Free Rewriting System (LCFRS) [1; 20] is a tuple \(G=(N,T,V,P,S)\) where  
* \(N\) is a finite set of non-terminals with a function \(\text{dim}:\)\(N\rightarrow\mathbb{N}\) determining the _fan-out_ of each \(A\in N\);
* \(T\) and \(V\) are disjoint finite sets of terminals and variables;
* \(S\in N\) is the start symbol with \(\text{dim}(S)=1\); and
* \(P\) is a finite set of rewriting rules (or productions). For all \(\gamma\in P\), the following holds. \(1.\quad\gamma\) has the form \[A(\alpha_{0},\ldots,\alpha_{\text{dim}(A)-1})\to A_{1}(x_{0}^{(1)}, \ldots,x_{\text{dim}(A_{1})-1}^{(1)})\cdots A_{m}(x_{0}^{(m)},\ldots,x_{ \text{dim}(A_{m})-1}^{(m)})\]  
Figure 3: LCFRS for machine translation alignments. _where_ \(A,A_{1},\ldots,A_{m}\in N\)_,_ \(m\geq 0\) _being the rank of_ \(\gamma\)_;_ \(x_{j}^{(l)}\in V\) _for_ \(1\leq l\leq m,0\leq j<dim(A_{i})\)_; and_ \(\alpha_{i}\in(V\cup T)^{+}\) _for_ \(0\leq i<dim(A)\)_; all_ \(\alpha_{i}\) _and_ \(x_{j}^{(l)}\) _are called arguments or components._ \(\gamma\) _may be abridged as_ \(A(\vec{\alpha})\to A_{1}(\vec{x_{1}})\cdots A_{m}(\vec{x}_{m})\)_; and we define_ \(\text{rank}(\gamma)=m\)_._
2. _For all_ \(x\in V\) _there is at most one unique occurrence of_ \(x\) _on each lefthand side and righthand side of_ \(\gamma\)_; furthermore, there exists an lefthand side occurrence iff there exists a righthand side occurrence._
3. _Variable occurrences in_ \(\gamma\) _are ordered by a strict total order_ \(\prec\) _which is such that for all_ \(x_{1},x_{2}\) _with occurrences in_ \(\gamma\)_, if_ \(x_{1}\) _precedes_ \(x_{2}\) _in any_ \(\vec{x}_{i}\)_,_ \(1\leq i\leq m\)_, then_ \(x_{1}\) _also precedes_ \(x_{2}\) _in_ \(\alpha\)_._  
_The rank of \(G\) is given by \(\max(\{\text{rank}(\gamma)\mid\gamma\in P\})\) and written as \(\text{rank}(G)\). \(G\) is of fan-out \(k\) if \(k\geq\max(\{\text{dim}(V)\mid V\in N\})\) and is written as \(\text{dim}(G)\). The set \(\mathcal{C}_{G}\) is defined as \(\mathcal{C}_{G}=\bigcup_{\gamma\in P}\mathcal{C}_{\gamma}\) (subscript \(G\) can be omitted if clear from the context)._  
The LCFRS derivation is based on the _instantiation_ of rules, the replacement of variable occurrences by strings of terminals. Definition 2 (Instantiation): An instantiation of a production \(\gamma\in P\) with \(\gamma=A(\vec{\alpha})\to A_{1}(\vec{\alpha}_{1})\cdots A_{m}(\vec{\alpha}_{m})\) is given by a function \(\sigma_{\gamma}:V_{\gamma}\to T^{*}\), where \(V_{\gamma}=\{x\mid\exists i,j\text{ such that }\text{rhs}(\gamma,i,j)=x\}\) the set of all \(x\in V\) occurring in \(\gamma\). \(\gamma\) is instantiated if all variable occurrences \(x\) have been replaced by \(\sigma_{\gamma}(x)\). A non-terminal in an instantiated production is an instantiated non-terminal. We now describe the LCFRS derivation process. A (_partial_) _derivation_ is specified as a pair \([D:A(\vec{\alpha})]\) called _item_. Thereby, \(A(\vec{\alpha})\) specifies the yield and \(D\) is the derivation tree. We use a bracketed representation of trees, e.g., \(\gamma_{0}(\gamma_{1}\gamma_{2})\) is a tree with a root node labeled \(\gamma_{0}\) that has two daughters, a left daughter labeled \(\gamma_{1}\) and a right daughter labeled \(\gamma_{2}\). Definition 3 (Derivation): Let \(G=(N,T,V,P,S)\) be an LCFRS.