# LR Parsing for LCFRS
## 2 Preliminaries
### Thread Automata
In Figure 6, the \(\alpha\)-thread has address \(\varepsilon\), the \(\beta\)-thread address \(1\) and the \(\gamma\)-thread address \(11\), i.e., the address of the mother thread is a prefix of the address of the child thread, respectively. This is why a thread knows where to go back to in a _suspend_ step. An automaton state is given by a tuple \(\langle i,p,\mathcal{T}\rangle\) where \(\mathcal{T}\) is a set of threads, the _thread store_, \(p\) is the address of the active thread, and \(i\geq 0\) indicates that \(i\) tokens have been recognized. We use \(\langle 0,\varepsilon,\{\varepsilon:S\}\rangle\) as start state. Definition 5 (LCFRS-TA): Let \(G=(N,T,V,P,S)\) be a LCFRS. The LCFRS thread automaton for \(G\) is a tuple \(\langle N^{\prime},T,S,ret,\delta,\Theta\rangle\) with  
* \(N^{\prime}=N\cup\mathcal{C}_{G}\cup\{ret\}\);
* \(\delta\) is a function from \(\mathcal{C}\) to \(\{1,\ldots,m\}\cup\{\bot\}\) such that \(\delta(\gamma_{k,i})=j\) if there is a \(l\) such that \(\mathit{lIns}(\gamma,k,i)=\mathit{rhs}(\gamma,j-1,l)\), and \(\delta(\gamma_{k,i})=\bot\) if \(\mathit{lIns}(\gamma,k,i)\in T\cup\{\bot\}\); and
* \(\Theta\) is a finite set of transitions as defined below. Intuitively, a \(\delta\) value \(j\) tells us that the next symbol to process is a variable that is an argument of the \(j\)-th righthand side non-terminal. Definition 6 (Transitions of a LCFRS-TA): The transition set \(\Theta\) of a LCFRS-TA as in Definition 5 contains the following transitions:  
* _Call:_ \(\gamma_{k,i}\to[\gamma_{k,j}]A\in\Theta\) _if_ \(A=\mathit{rhs}(\gamma,j-1)\) _and_ \(\mathit{lIns}(\gamma,k,i)=\mathit{rhs}(\gamma,j-1,0)\) _where_ \(j=\delta(\gamma_{k,i})\)_._  
Figure 6: Sample TA-run for \(w=aaba\). * _Predict_: \(A\rightarrow\gamma_{0,0}\in\Theta\) if \(A=\mathit{lIns}(\gamma)\). * _Scan_: \(\gamma_{k,i}\xrightarrow{\mathit{lIns}(\gamma_{k,i})}\gamma_{k,i+1}\in\Theta\) if \(\mathit{lIns}(\gamma,k,i)\in T\). * _Publish_: \(\gamma_{k,j}\rightarrow\mathit{ret}\in\Theta\) if \(\mathit{dim}(\mathit{lIns}(\gamma))=k+1\) and \(j=|\mathit{lIns}(\gamma,k)|\). * _Suspend_: 1. \([\gamma_{k,i}]\mathit{ret}\rightarrow\gamma_{k,i+1}\in\Theta\) if \(\mathit{lIns}(\gamma,k,i)=\mathit{rhs}(\gamma,\delta(\gamma_{k,i})-1,\mathit{ dim}(\mathit{rhs}(\delta(\gamma_{k,i})-1))-1)\). 2. \([\gamma_{k,j}]\beta_{l,j}\rightarrow\gamma_{k,i+1}[\beta_{l,j}]\in\Theta\) if \(\mathit{dim}(\mathit{lIns}(\beta))>l+1\), \(|\mathit{lIns}(\beta,l)|=j\), \(\mathit{lIns}(\gamma,k,i)=\mathit{rhs}(\gamma,\delta(\gamma_{k,i})-1,l)\) and \(\mathit{rhs}(\gamma,\delta(\gamma_{k,i})-1)=\mathit{lIns}(\beta)\). * _Resume_: \(\gamma_{k,i}[\beta_{l,j}]\rightarrow[\gamma_{k,i}]\beta_{l+1,0}\in\Theta\) if \(\mathit{lIns}(\gamma,k,i)=\mathit{rhs}(\gamma,\delta(\gamma_{k,i})-1,l+1)\), \(\mathit{rhs}(\gamma,\delta(\gamma_{k,i})-1)=\mathit{lIns}(\beta)\) and \(\beta_{l,j+1}\
otin\mathcal{C}_{G}\). _These are all transitions in \(\Theta\)._  
A transition \(\alpha\xrightarrow{a}\beta\) roughly indicates that in the current thread store, \(\alpha\) can be replaced with \(\beta\) while scanning \(a\). Square brackets in \(\alpha\) and \(\beta\) indicate parts that do not belong to the active thread. Call transitions start a new thread for a daughter non-terminal, i.e., a righthand side non-terminal. They move down in the parse tree. Predict transitions predict a new rule for a non-terminal \(A\). Scan transitions read a lefthand side terminal while scanning the next input symbol. Publish marks the completion of a production, i.e., its full recognition. Suspend transitions suspend a daughter thread and resume the parent. i.e., move up in the parse tree. There are two cases: Either (i) the daughter is completely recognized (thread content _ret_) or (ii) the daughter is not yet completely recognized, we have only finished one of its components. Resume transitions resume an already present daughter thread, i.e., move down into some daughter that has already been partly recognized. Figure 7 shows the transitions for our sample grammar.