# LR Parsing for LCFRS
## 4 LR for LCFRS
### Parsing Algorithm  
The parser has slightly more complex configurations than the CFG shift-reduce parser. Let \(Q\) be the set of states of the LR automaton for a given LCFRS \(G\), \(q_{0}\) the state containing \(\varepsilon:S\) and \(q_{acc}\) the _accepting_ state containing \(\varepsilon:S\bullet\). Furthermore, let \(\mathcal{N}=\{\boxed{0},\boxed{1},\boxed{2},\dots\}\) be the set of possible pointers to derivation tree nodes. The parser configurations are then triples \(\langle\Gamma,C,i\rangle\) consisting of  
* a stack \(\Gamma\in\textit{Reg}_{G}\circ Q\circ((T\cup\{\boxed{k},\boxed{2}\}\in \mathcal{N},k\leq max_{A\in N}\textit{dim}(A)\})\circ\textit{Reg}_{G}\circ Q)^ {*}\),
* a set of constraints \(C\) that are either of the form \(\{\boxed{1},\boxed{2}\}\) with \(r\in\textit{Reg}_{G}\), \(\boxed{1}\in\mathcal{N}\), \(\gamma\in P\) and \(1\leq j\leq\textit{dim}(\textit{lhs}(\gamma))\) or of the form \(\boxed{2}\lhd_{d}\) with \(\boxed{3}\boxed{1}\in\mathcal{N}\), \(1\leq d\leq rank(G)\). * and the index \(j\) up to which the input \(w\) has been recognized, \(0\leq j\leq|w|\). Concerning the constraint set \(C\), the first type of constraints describes nodes in the derivation tree while the second describes immediate dominance relations between them, more precisely the fact that one node is the \(d\)th daughter of another node. There is an immediate relation between the two: if \(\boxed{i}\lhd_{d}\boxed{2}\), then the address of \(\boxed{2}\) must be the regular expression of \(\boxed{1}\) concatenated with the daughter index \(d\) of \(\boxed{2}\). Let \(\mathcal{N}_{C}\) be the set of indices from \(\mathcal{N}\) occurring in \(C\). The initial configuration is \(\langle\textit{eq}_{0},\emptyset,0\rangle\). From a current configuration, a new one can be obtained by one of the following operations:  
* **Shift**: Whenever we have \(pq\) on top of the stack, the next input symbol is \(a\) and in our parse table we have \(\textit{action}(q,a)=s(p^{\prime},q^{\prime})\), we push \(a\) followed by \(pp^{\prime}q^{\prime}\) onto the stack and increment the index \(j\). Figure 14: The parse table. * **Reduce**: Whenever the top of the stack is \(p_{1}q\) and we have a parse table entry \(r(\gamma,i)\in action(q,-)\), we can reduce the \(i\)th component of \(\gamma\), i.e, suspend \(\gamma\). Concretely, this means the following:
* Concerning the constraint set \(C\), if \(i=1\), we add \(p_{1}\boxed{\gamma_{1}}\) to \(C\) where \(\boxed{\beta}\) is a new pointer. * If \(i\geq 1\), we check whether there is a \(p_{2}\boxed{\gamma_{i-1}}\) in \(C\) such that the intersection \(L(p_{1})\cap L(p_{2})\) of the languages denoted by \(p_{1}\) and \(p_{2}\), \(L(p_{1})\) and \(L(p_{2})\), is not empty. We then replace \(p_{2}\boxed{\gamma_{i-1}}\) in \(C\) with \(p\boxed{\gamma_{i}}\), where \(p\) is a regular expression denoting \(L(p_{1})\cap L(p_{2})\). * Concerning the stack \(\Gamma\), we remove \(3|\mathit{Ihs}(\gamma,i)|\) elements (i.e., terminals/component pointers and their regular expressions and states) from \(\Gamma\). Suppose the topmost state on the stack is now \(p^{\prime}q^{\prime}\). If \(\mathit{got}(q^{\prime},\mathit{Ihs}(\gamma)_{i})=\langle p^{\prime\prime},q ^{\prime\prime}\rangle\), we push \(\boxed{\gamma_{i}}\) followed by \(p^{\prime}p^{\prime\prime}q^{\prime\prime}\) on the stack. * Concerning the dominance relations, for every \(\boxed{\beta}\) among the symbols we removed from the stack, we add \(\boxed{\beta}\trianglelefteq_{d}\boxed{\beta}\) where \(d\) is the corresponding daughter index. * It can happen that, thanks to the new dominance relations, we can further restrict the regular expressions characterizing the addresses in \(C\). For instance, if we had \(1^{+}\boxed{\beta}\dots,1^{+}\boxed{\beta}\dots\) and \(\boxed{\beta}\trianglelefteq_{1}\boxed{\beta}\) in our set, we would replace the address of \(\boxed{\beta}\) with \(1^{+}1\). * The index \(j\) remains unchanged in reduce steps.