# LR Parsing for LCFRS
## 4 LR for LCFRS
### Comparison to TAG Parsing  
As mentioned in the beginning, LR parsing has also been proposed for TAG [(31; 41)]. The LR states in this case contain dotted productions that correspond to small subtrees (a node and its daughters) in the TAG elementary trees. They are closed under moving up and down in these trees, predicting adjunctions and predicting subtrees below foot nodes. There are two different transitions labeled with non-terminal symbols in the LR automata constructed for TAG: Transitions that correspond to having finished a subtree and moving the dot over the corresponding non-terminal node and transitions that correspond to having finished the part below a foot node and moving back into the adjoined auxiliary tree. The latter transitions are labeled with the adjunction site. In the parser, when following such a transition, the adjunction site is stored on the stack of the parser. Adjunctions can be nested, consequently, we can have a list (actually a stack) of such adjunction sites that we have to go back to later. This way to keep track of where to go back to once the adjoined tree is entirely processedcorresponds to the derivation node addresses we have in the thread automata and the LCFRS LR parser since both mechanisms capture the derivation structure. The difference is that with TAG, we have a simple nested structure without any interference of nested adjunctions in different places. And the contribution of auxiliary trees in the string contains only a single gap, consequently only a single element in the daughter list of a node contains such information about where to go back to when having finished the auxiliary tree. Therefore each of these chains of adjunctions can be kept track of locally on the parser stack. Restricting our LR parser to well-nested 2-LCFRS amounts to restricting it to TAG. This restriction means that our LCFRS rules have the following form: Assume that \(\gamma=A(\alpha_{0},\ldots,\alpha_{dim(A)-1})\to A_{1}(x_{0}^{(1)},\ldots,x_{ dim(A_{1})-1}^{(1)})\cdots A_{m}(x_{0}^{(m)},\ldots,x_{dim(A_{m})-1}^{(m)})\) is a rule in such an LCFRS. Then we can partition the righthand side into minimal subsequences \(A_{1}\ldots A_{i_{1}},\ldots,\,A_{i_{k}}\ldots A_{m}\) such that a) the yields of these subsequences do not cross; b) every subsequence either (i) contains only a single non-terminal or (ii) has a first element of fan-out 2 that wraps around the yields of the other non-terminals. In this latter case, the yield of the second to last non-terminals can again be partitioned in the same way. Consider as an example a rule \(A(x_{1}x_{2}x_{3}x_{4}x_{5}x_{6}\gamma)\to B(x_{1})C(x_{2},x_{6})D(x_{3},x_{5}) E(x_{4})F(x_{7})\). Here, we can partition the righthand side into the daughter sequences \(B\) and \(C,D,E\) and \(F\) that can be parsed one after the other without having to jump back and forth between them. Conceing \(C,D,E\), the \(C\) wraps around \(D,E\) and, concerning this shorter sequence, \(D\) wraps around \(E\). This means that during parsing, when processing the yield of one of these subsequences, we have to keep track of the last first component of some non-terminal that we have completed since this will be the first one for which we have to find a second component. We can push this information on a stack and have to access only the top-most element. There is no need to search through the entire partial derivation structure that has already been built in order to find a matching first component when reducing a second one. On the parse stack, it is enough to push the rule names for which we have completed a first component and still need to find a second. Pointers to the derivation structure are no longer needed. And node addresses are not needed either. Besides nestings between sisters as in this example, we can also have embedded nestings in the sense that a first component is part of some other component. In this case, we have to finish the lower non-terminal before finishing the higher.