# LR Parsing for LCFRS
## 3 LR Parsing  
In an LR parser (see [40] chapter 9), the parser actions are guided by an automaton, resp. a _parse table_ which is compiled offline. Consider the context-free case. An LR parser for CFG is a guided shift-reduce parser, in which we first build the LR automaton. Its states are sets of dotted productions closed under prediction, and its transitions correspond to having recognized a part of the input, e.g., to moving the dot over a righthand side element after having scanned a terminal or recognized a non-terminal. Consider for instance the CFG \(G=\langle\{S\},\{a,b,c\},\{S\to aSb\,|\,c\},S\rangle\). Its LR automaton is given in Figure 9. The construction of this automaton starts from the prediction closure of \(\{S^{\prime}\to\bullet S\}\), which contains the two \(S\)-productions with the dot at the beginning of the righthand side. The prediction closure of a set of dotted productions \(q\) is defined as follows: if \(A\to\alpha\bullet B\beta\in q\), then \(B\to\bullet\gamma\in q\) for all \(B\)-productions \(B\to\gamma\) in the grammar. From a state \(q\), a new state can be obtained by computing all items that can be reached by moving the dot over a certain \(x\in N\cup T\) in any of the dotted productions in \(q\) and then, again, building the prediction closure. The new state can be reached from the old one by an edge labeled with \(x\). This process is repeated until all possible states have been constructed. In our example, when being in \(q_{0}\), we can for instance reach \(q_{1}\) by moving the dot over an \(a\), and we can reach \(q_{5}\) (the acceptance state) by moving the dot over an \(S\). This automaton guides the shift-reduce parsing in the following way: At every moment, the parser is in one of the states. We can _shift_ an \(a\in T\) if there is an outgoing \(a\)-transition. The state changes according to the transition.We can _reduce_ if the state contains a completed \(A\to\alpha\bullet\). We then reduce  
Figure 8: Deduction rules for TA configurations. Figure 9: Sample LR automaton for a CFG. with \(A\to\alpha\). The new state is obtained by following the \(A\)-transition, starting from the state reached before processing that rule. The information about possible shift and reduce operations in a state is precompiled into a parse table: Given an LR automaton with \(n\) states, we build a _parse table_ with \(n\) rows. Each row \(i\), \(0\leq i<n\), describes the possible parser actions associated with the state \(q_{i}\), i.e., for each state and each possible shift or reduce operation, it tells us in which state to go after the operation. The table has \(|T|+|N|+1\) columns where the first are indexed with the terminals, then follows a column for reduce operations and then a column for each of the non-terminals. For every pair of states \(q_{i}\), \(q_{j}\) that are linked by an \(a\)-edge for some \(a\in T\), the field of \(q_{i}\) and \(a\) contains s\(j\), which indicates that in \(q_{i}\), one can shift an \(a\) and then move to \(q_{j}\). For every state \(q_{i}\) that contains rule number \(j\) with a dot at the end of the righthand side, we add r\(j\) to the reduce field of \(q_{i}\). Finally, for every pair of states \(q_{i}\), \(q_{j}\) that are linked by an \(A\)-edge for some \(A\in N\), the field of \(q_{i}\) and \(A\) contains \(j\), which indicates that in \(q_{i}\), after having completed an \(A\), we can move to \(q_{j}\). On the left of Figure 10, we see the parse table resulting from the automaton in Figure 9. The first \(|T|+1\) columns are the so-called _action_-part of the table while the last \(|N|\) columns form the _goto_-part. The parse table determines the possible reductions and shifts we can do at every moment. We start parsing with a stack containing only \(q_{0}\). In a shift, we push the new terminal followed by the state indicated in the table on the stack. In a reduction, we use the production indicated in the table. We pop its righthand side (in reverse order) and push its lefthand side onto the stack.