# LR Parsing for LCFRS
## 4 LR for LCFRS
### Deterministic Parsing  
As mentioned, with one lookahead, LR parsing of the LCFRS in the previous example would become deterministic. In general, when doing natural language processing, the grammars will always be ambiguous and a deterministic parsing is not possible. Instead, some way to share structure in the style of _generalized LR_[29] parsing has to be found. In other applications, however, we might have LCFRSs that allow for a deterministic parsing, similar to LR(\(k\)) parsing as in [27]. Non-determinism with LCFRS can arise not only from shift-reduce or reduce-reduce conflicts as in CFGs but also from a conflict between different _goto_ transitions that have the same component non-terminal but different node addresses (see the multiple entries in the _goto_ table of our example). We therefore need lookheads not only for reduce (and, if \(k>1\), shift) but also for the _goto_ entries. We now define, similar to the CFG case [27], sets of _First_ symbols for dotted productions, which contain all terminals that are reachable as first element of the yield, starting from the dotted production. For every \(\gamma_{i,j}\), let us define \(\mathit{First}(\gamma,i,j)\) as follows. (Remember that \(\mathit{lls}(\gamma,i,j)\) gives the \(j\)th symbol of the \(i\)th component in the lefthand side of \(\gamma\), i.e., the element following the dot.) 1. \(\varepsilon\in\mathit{First}(\gamma,i,j)\) if \(\mathit{lls}(\gamma,i,j)\) is not defined (i.e, the dot is at the end of the \(i\)th component);
2. \(a\in\mathit{First}(\gamma,i,j)\) if \(\mathit{lls}(\gamma,i,j)=a\) (i.e., the dot precedes \(a\));
3. \(a\in\mathit{First}(\gamma,i,j)\) if \(\mathit{lls}(\gamma,i,j)=x\in V\), \(x\) is the \(l\)th component in a righthand side element of \(\gamma\) with non-terminal \(B\), and there is a \(\gamma_{B}\in P\) with \(\mathit{lls}(\gamma_{B})=B\) such that \(a\in\mathit{First}(\gamma_{B},l,0)\). 4. Nothing else is in \(\mathit{First}(\gamma,i,j)\). Besides this, we also need the notion of _Follow_. _Follow_ sets are defined for all component nonterminals \(A_{i}\) (\(A\in N,1\leq i\leq\mathit{dim}(A)\)) of our LCFRS. They contain the terminals that can immediately follow the yield of such a component nonterminal. 1. \(\$\in\mathit{Follow}(S_{1})\) where \(S\) is the start symbol and \(\$\
otin T\) is a new symbol marking the end of the input. 2. For every production \(\gamma\) with \(x\in V\) being the \(j\)th element of the \(i\)th lefthand side component (indices start with \(i=0\) and \(j=0\)) and \(x\) being the \(l\)th element of the yield of a nonterminal \(B\) in the righthand side (also starting with \(l=0\)), we have \(\mathit{First}(\gamma_{i,j+1})\subseteq\mathit{Follow}(B_{l+1})\), provided \(\mathit{First}(\gamma_{i,j+1})\) is defined. 3. For every production \(\gamma\) with \(\mathit{lls}(\gamma)=A\) and with \(x\in V\) being the last element of the \(i\)th lefthand side component (indices start with \(i=0\)) and the \(l\)th element of the yield of a nonterminal \(B\) in the righthand side (also starting with \(l=0\)), we have \(\mathit{Follow}(A_{i+1})\subseteq\mathit{Follow}(B_{l+1})\). 4. Nothing else is in the sets \(\mathit{Follow}(A_{i})\) of our component nonterminals. For \(LR(1)\) parsing, i.e., LR parsing with 1 lookahead, we replace the items in our states with triples consisting of the adress (regular expression), the dotted production \(\gamma_{i,j}\) and the possible next terminal symbols. To this end, we define sets \(\mathit{Next}(\gamma,i,j)\) that are the _First_ sets for dots that are not at the end of components and otherwise the _Follow_-sets of the component non-terminal:  
\(\mathit{Next}(\gamma,i,j)=\mathit{First}(\gamma,i,j)\) if \(\gamma_{i,j+1}\) exists and \(\mathit{Next}(\gamma,i,j)=\mathit{Follow}(\mathit{lls}(\gamma)_{i+1})\) otherwise. A simple way to extend our automaton to \(LR(1)\) is by extending the items in the states as follows: Every item with dotted production \(\gamma_{i,j}\) is equipped with the lookahead set \(\mathit{Next}(\gamma,i,j)\).