# LR Parsing for LCFRS
## 4 LR for LCFRS
### Soundness and Completeness of the LR Algorithm  
In order to show soundness and completeness of the LR algorithm, we will relate it to the LCFRS-TA for the same grammar. We will slightly modify the deduction rules for TA by assuming that (1) call and predict steps are combined and the initial configuration is omitted, i.e., we start with the result of the first predict steps; (2) we omit the publish steps; and (3) we don't delete threads of finished rules. The modified rules are given Figure 20. Concerning the LR automaton, we replace the regular expressions in our parsing configurations with concrete addresses. In principal we can then have infinitely many configurations in cases of left recursions (just like in the TA case), i.e., in cases where a shift or goto transition comes with a regular expression denoting an infinite language. Furthermore, we do not delete daughters of completed rules in the constraint set either, i.e., we assume that the rule 2(b) in Definition 11 concerning the application of \(f_{\vartriangleleft}\) to the constraint set does not apply. Clearly, this does not change the languages recognized by these automata, it just increases the set of possible configurations. Since we use no longer regular expressions but single addresses, the deduction rules of the LR parser get simpler. Immediate dominance constraints are no longer needed since they follow from the addresses. The relevant deduction rules are given in Figure 21.  
Figure 20: Revised deduction rules for TA configurations. Figure 22 shows the correspondence between TA configurations and LR configurations for our sample derivation of \(aaba\). We now define a function \(f_{TA}\) that gives for every LR configuration the set of corresponding TA configurations. The idea is the following: An LR configuration describes a path in our LR automaton. This path yields several possible thread contents. Before giving the formal definition, let us consider two examples from Figure 22 for illustration. Take as a first example the LR configuration \(\langle\varepsilon q_{0}\ a\ 1q_{1}\ a\ 11q_{1},\emptyset,2\rangle\). The corresponding path in our automaton is  
\[\varepsilon:q_{0}\]  
Figure 21: LR deduction rules without regular expressions. Each thread store in the corresponding TA configuration corresponds to a possible path through these states. * For every \(\varepsilon\)-element in the last state of this path (here \(\varepsilon:\beta_{0,1}\) or \(\varepsilon:\gamma_{0,1}\)), we compute the TA configurations \(\langle 2,11,\mathcal{S}_{\beta}\rangle\) and \(\langle 2,11,\mathcal{S}_{\gamma}\rangle\) respectively for these elements: Let us consider first the case of \(\mathcal{S}_{\beta}\). We first define a set \(\mathcal{S}^{\prime}_{\beta}\), starting with \(\mathcal{S}^{\prime}_{\beta}=\{11:\beta_{0,1}\}\):
* Since \(11:\beta_{0,1}\) was obtained via the \(a\)-transition, from \(1:\beta_{0,0}\) in \(1:q_{1}\), we add \(11:\beta_{0,0}\) to \(\mathcal{S}^{\prime}_{\beta}\). * \(11:\beta_{0,0}\) in turn is in the second state on the path since we obtained it via prediction from \(1:\beta_{0,1}\), which is added to \(\mathcal{S}^{\prime}_{\beta}\) as well. * Again, \(1:\beta_{0,1}\) arose out of a shift of \(a\) from \(1:\beta_{0,0}\), which is added as well and then, because of predict in \(q_{0}\), we add \(\varepsilon:\alpha_{0,0}\). This gives \(\mathcal{S}^{\prime}_{\beta}=\{11:\beta_{0,1},11:\beta_{0,0},1:\beta_{0,1},1: \beta_{0,0},\varepsilon:\alpha_{0,0}\}\). * We then remove all items where there is an item with the same address and rule in the set but with a lefthand side index that is more advanced. This yields \(\mathcal{S}^{\prime}_{\beta}=\{11:\beta_{0,1},1:\beta_{0,1},\varepsilon: \alpha_{0,0}\}\), which is the thread set \(\mathcal{S}_{\beta}\) we were looking for. * In a similar way, for the \(\gamma\) case, we obtain \(\mathcal{S}_{\gamma}=\{11:\gamma_{0,1},1:\beta_{0,1},\varepsilon:\alpha_{0,0}\}\)
* In addition, we add all configurations that we can reach from the ones constructed so far via predict or resume.