# LR Parsing for LCFRS
## 4 LR for LCFRS
### Soundness and Completeness of the LR Algorithm
Furthermore, the dot in \(\gamma_{m_{i},n_{i}}^{i}\) precedes a terminal \(a=w_{j+1}\), we consequently can perform scans on \(c_{TA,1},\ldots,c_{TA,k}\) and there is a shift transition \(\mathit{action}(q,a)=s(r,q^{\prime}),p_{2}\in L(r)\). Consequently, we can obtain new TA configurations \(c_{TA,i}^{\prime}=\langle j+1,p,S\cup\{p:\gamma_{m_{i},n_{i}+1}^{j}\}\rangle\) and a new LR configuration \(\langle\Gamma p_{1}qw_{j+1}p_{1}p_{2}q^{\prime},C,j+1\rangle\) in the LR automaton. According to the LR automaton construction, \(\overline{\{\varepsilon:\gamma^{1}_{m_{1},n_{1}+1},\ldots,\varepsilon:\gamma^{k}_{m_{k },n_{k}+1}\}}=q^{\prime}\) with \(\varepsilon:\gamma^{i}_{m_{i},n_{i}+1}\) having a predecessor link pointing to \(p_{2}:\gamma^{i}_{m_{i},n_{i}}\) in \(q\). Further elements in \(q^{\prime}\) are obtained by predict and resume and are linked to the elements with address \(\varepsilon\) by a predecessor chain. The same predict and resume operations can be applied to the corresponding TA configurations \(c^{\prime}_{TA,1},\ldots,c^{\prime}_{TA,k}\) as well. Therefore our induction assumption holds. * **Suspend** and **Reduce**: We assume again that we have sets \(\mathcal{C}_{TA}\) of TA configurations and \(\mathcal{C}_{LR}\) of LR configurations such that \(\mathcal{C}_{TA}=\bigcup_{c_{LR},c_{LR}}f_{TA}(c_{LR})\). To show: For any pair \(c_{LR},f_{TA}(c_{LR})\) contained in the two sets: there is a \(c_{TA}\in f_{TA}(c_{LR})\) that allows to derive a new configuration \(c^{\prime}_{TA}\) via an application of _suspend_ iff \(c_{LR}\) allows to derive a new configuration \(c^{\prime}_{LR}\) via an application of _reduce_ 1/2 such that \(f_{TA}(c^{\prime}_{LR})=\overline{c^{\prime}_{TA}}\). Let \(c_{TA}=\langle i,p\rangle\), \(\mathcal{S}\cup\{p:\gamma_{k,n},pj:\beta_{l,m}\}\rangle\) such that a suspend can be applied resulting in \(\langle i,p,\mathcal{S}\cup\{p:\gamma_{k,n+1},pj:\beta_{l,m}\}\rangle\). According to our induction assumption, \(c_{LR}\) has a form \(\langle\Gamma pjq,C,i\rangle\) such that there exists a \(\varepsilon:\beta_{l,m}\in q\) (without loss of generality, we assume our grammars to be \(\varepsilon\)-free. Consequently, computation points with the dot at the end of a component cannot arise from predict or resume operations and therefore always have address \(\varepsilon\)). Furthermore, since in \(\beta_{l,m}\), the dot is at the end of the \((l+1)\)th component, we have \(r(\beta,l+1)\in action(q,-)\). Let us remind the suspend and reduce operations: TA Suspend: \(\begin{array}{ll}\langle i,p\rangle,\mathcal{S}\cup\{p:\gamma_{k,n},pj:\beta _{l,m}\}\rangle& \begin{array}{ll}\langle i,p,\mathcal{S}\cup\{p:\gamma_{k,n +1},pj:\beta_{l,m}\}\rangle&\begin{array}{ll}\langle\gamma_{k,n}|\beta_{l,m}\rightarrow\gamma_{k,n+1}|\beta_{l,m}\rangle\in\Theta\text{ or }\\ \langle i,p,\mathcal{S}\cup\{p:\gamma_{k,n+1},pj:\beta_{l,m}\}\rangle&\begin{array} []{ll}\langle\Gamma pkq_{l}\rangle\
eq\tau_{k,n+1}\in\Theta\\ \langle\Gamma pkq_{l}\rangle\
eq\tau_{k,n+1}\in\Theta\end{array}\end{array}\end{array} \) LR Reduce 1: \( \begin{array}{ll}\langle\Gamma pkq_{l}\chi_{k}\ldots p_{1}q_{1}X_{1}pjq,C,i \rangle&\begin{array}{ll}r(\beta,1)\in action(q,-),k=|\text{Jhs}(\gamma,0)|,\\ g^{\text{tot}}(q_{l,\text{Jhs}}(\gamma_{l}))=\langle r,q^{\prime}\rangle,p^{ \prime}\in L(r),\overline{\Theta}\end{array}\end{array} \) LR Reduce 2: \( \begin{array}{ll}\langle\Gamma pkq_{l}\chi_{k}\ldots p_{1}q_{1}X_{1}pjq,C\cup\{p \}\overline{\llbracket\beta_{l-1}\rangle,i\}&\begin{array}{ll}r(\beta,1)\in action(q,-),\\ 1<l,k=|\text{Jhs}(\beta,l-1)|,\\ g^{\text{tot}}(q_{l,\text{Jhs}}(\beta))=\langle r,q^{\prime}\rangle,p^{ \prime}\in L(r)\end{array}\end{array} \) where for both reduce steps, any component pointer \(\llbracket\rrbracket_{m}\), among the \(X_{1},\ldots,X_{k}\) has an address \(pjm\) for some \(m\in\{1,\ldots,|\text{Jhs}(\beta)|\}\).