 Almost all programming languages have LR grammars.
 LR parsers take time and space linear in the size of the input (with a constant factor determined by the grammar).
 LR is strictly more powerful than LL (for example, every LL(1) grammar is also both LALR(1) and LR(1), but not vice versa).
 LR grammars are more "natural" than LL grammars (e.g., the grammars for expression languages get mangled when we remove the left recursion to make them LL(1), but that isn't necessary for an LALR(1) or an LR(1) grammar).
 Although an LR grammar is usually easier to understand than the corresponding LL grammar, the parser itself is harder to understand and to write (thus, LR parsers are built using parser generators, rather than being written by hand).
 When we use a parser generator, if the grammar that we provide is not LALR(1), it can be difficult to figure out how to fix that.
 Error repair may be more difficult using LR parsing than using LL.
 Table sizes may be larger (about a factor of 2) than those used for LL parsing.
 start with the start symbol (i.e., the current string is the start symbol)
 repeat:
 choose a nonterminal X in the current string
 choose a grammar rule X $\longrightarrow$ $\alpha$
 replace X in the current string with $\alpha$
 $\Longrightarrow$ $E$ + $T$
 $\Longrightarrow$ $E$ + $T$ * $F$
 $\Longrightarrow$ $E$ + $T$ * id
 $\Longrightarrow$ $E$ + $F$ * id
 $\Longrightarrow$ $E$ + id * id
 $\Longrightarrow$ $T$ + id * id
 $\Longrightarrow$ $F$ + id * id
 $\Longrightarrow$ id + id * id
 the topofstack symbol and
 the current input symbol (token) and
 the entry in one of the parse tables (indexed by the topofstack and currentinput symbols)
 shift: push the current input symbol onto the stack, and go on to the next input symbol (i.e., call the scanner again)
 reduce: a grammar rule's righthand side is on the top of the stack! pop it off and push the grammar rule's lefthandside nonterminal
 accept: accept the input (parsing has finished successfully)
 reject: the input is not syntactically correct
 the definition of an item
 the number of states in the underlying finitestate machine
 the amount of information in a state
Shift/Reduce Parsing
Contents
There are several different kinds of bottomup parsing. We will discuss an approach called LR parsing, which includes SLR, LALR, and LR parsers. LR means that the input is scanned lefttoright, and that a rightmost derivation, in reverse, is constructed. SLR means "simple" LR, and LALR means "lookahead" LR.
Every SLR(1) grammar is also LALR(1), and every LALR(1) grammar is also LR(1), so SLR is the most limited of the three, and LR is the most general. In practice, it is pretty easy to write an LALR(1) grammar for most programming languages (i.e., the "power" of an LR parser isn't usually needed). A disadvantage of LR parsers is that their tables can be very large. Therefore, parser generators like Yacc and Java Cup produce LALR(1) parsers.
Let's start by considering the advantages and disadvantages of the LR parsing family:
Advantages
Recall that topdown parsers use a stack. The contents of the stack represent a prediction of what the rest of the input should look like. The symbols on the stack, from top to bottom, should "match" the remaining input, from first to last token. For example, earlier, we looked at the example grammar
Grammar:
$S$  $\longrightarrow$  $\varepsilon$  ( $S$ )  [ $S$ ] 
and parsed the input string ([]). At one point during the parse, after the first parenthesis has been consumed, the stack contains
[ S ] ) EOF(with the topofstack at the left). This is a prediction that the remaining input will start with a '[', followed by zero or more tokens matching an S, followed by the tokens ']' and ')', in that order, followed by endoffile.
Bottomup parsers also use a stack, but in this case, the stack represents a summary of the input already seen, rather than a prediction about input yet to be seen. For now, we will pretend that the stack symbols are terminals and nonterminals (as they are for predictive parsers). This isn't quite true, but it makes our introduction to bottomup parsing easier to understand.
A bottomup parser is also called a "shiftreduce" parser because it performs two kind of operations, shift operations and reduce operations. A shift operation simply shifts the next input token from the input to the top of the stack. A reduce operation is only possible when the top N symbols on the stack match the righthand side of a production in the grammar. A reduce operation pops those symbols off the stack and pushes the nonterminal on the lefthand side of the production.
One way to think about LR parsing is that the parse tree for a given input is built, starting at the leaves and working up towards the root. More precisely, a reverse rightmost derivation is constructed.
Recall that a derivation (using a given grammar) is performed as follows:
A rightmost derivation is one in which the rightmost nonterminal is always the one chosen.
Rightmost Derivation ExampleCFG
$E$  $\longrightarrow$  $E$ + $T$ 
  $T$  
$T$  $\longrightarrow$  $T$ * $F$ 
  $F$  
$F$  $\longrightarrow$  id 
  ( $E$ ) 
Rightmost derivation

$E$
In this example, the nonterminal that is chosen at each step is in red, and each derivation step is numbered. The corresponding bottomup parse is shown below by showing the parse tree with its edges numbered to show the order in which the tree was built (e.g., the first step was to add the nonterminal F as the parent of the leftmost parsetree leaf "id", and the last step was to combine the three subtrees representing "id", "+", and "id * id" as the children of a new root node E).
Note that both the rightmost derivation and the bottomup parse have 8 steps. Step 1 of the derivation corresponds to step 8 of the parse; step 2 of the derivation corresponds to step 7 of the parse; etc. Each step of building the parse tree (adding a new nonterminal as the parent of some existing subtrees) is called a reduction (that's where the "reduce" part of "shiftreduce" parsing comes from).
Basic LR Parsing AlgorithmL
All LR parsers use the same basic algorithm:

Based on:
The difference between SLR, LALR, and LR parsers is in the tables that they use. Those tables use different techniques to determine when to do a reduce step, and, if there is more than one grammar rule with the same righthand side, which lefthandside nonterminal to push.
Here are the steps the parser would perform using the grammar of arithmetic expressions with + and * given above, if the input is
id + id * id
Stack  Input  Action  
id + id * id  shift (id)  
id  + id * id  reduce by $F$ $\longrightarrow$ id  
$F$  + id * id  reduce by $T$ $\longrightarrow$ $F$  
$T$  + id * id  reduce by $E$ $\longrightarrow$ $T$  
$E$  + id * id  shift(+)  
$E$ +  id * id  shift(id)  
$E$ + id  * id  reduce by $F$ $\longrightarrow$ id  
$E$ + $F$  * id  reduce by $T$ $\longrightarrow$ $F$  
$E$ + $T$  * id  shift(*)  
$E$ + $T$ *  id  shift(id)  
$E$ + $T$ * id  reduce by $F$ $\longrightarrow$ id  
$E$ + $T$ * $F$  reduce by $T$ $\longrightarrow$ $T$ * $F$  
$E$ + $T$  reduce by $E$ $\longrightarrow$ $E$ + $T$  
$E$  accept 
(NOTE: the top of stack is to the right; the reverse rightmost derivation is formed by concatenating the stack with the remaining input at each reduction step)
As mentioned above, the symbols pushed onto the parser's stack are not actually terminals and nonterminals. Instead, they are states, that correspond to a finitestate machine that represents the parsing process (more on this soon).
All LR Parsers use two tables: the action table and the goto table. The action table is indexed by the topofstack symbol and the current token, and it tells which of the four actions to perform: shift, reduce, accept, or reject. The goto table is used during a reduce action as explained below.
Above we said that a shift action means to push the current token onto the stack. In fact, we actually push a state symbol onto the stack. Each "shift" action in the action table includes the state to be pushed.
Above, we also said that when we reduce using the grammar rule A → alpha, we pop alpha off of the stack and then push A. In fact, if alpha contains N symbols, we pop N states off of the stack. We then use the goto table to know what to push: the goto table is indexed by state symbol t and nonterminal A, where t is the state symbol that is on top of the stack after popping N times.
Here's pseudo code for the parser's main loop:
push initial state s_{0} a = scan() do forever t = topofstack (state) symbol switch action[t, a] { case shift s: push(s) a = scan() case reduce by A → alpha: for i = 1 to length(alpha) do pop() end t = topofstack symbol push(goto[t, A]) case accept: return( SUCCESS ) case error: call the error handler return( FAILURE ) } end do
Remember, all LR parsers use this same basic algorithm. As mentioned above, for all LR parsers, the states that are pushed onto the stack represent the states in an underlying finitestate machine. Each state represents "where we might be" in a parse; each "place we might be" is represented (within the state) by an item. What's different for the different LR parsers is: