In typical use when we refer to an LR parser we mean a particular parser capable of recognising a particular language specified by a context free grammar. It is not uncommon, however, to refer to an LR parser meaning a driver program that can be supplied with a suitable table to produce a wide number of different particular LR parsers.
LR parsing has many benefits:
LR parsers are difficult to produce by hand; they are usually constructed by a parser generator or a compilercompiler. Depending on how the parsing table is generated these parsers are called Simple LR parser (SLR for short), Lookahead LR parser (LALR), and Canonical LR parser. These types of parsers can deal with increasingly large sets of grammars; LALR parsers can deal with more grammars than SLR, Canonical LR parsers works on more grammars than LALR parsers. The program Yacc produces LALR parsers and is fairly popular.

A tablebased bottomup parser can be schematically presented as in Figure 1.
+++++ Input:  1  +  1  $  +++++ ^  Stack:  ++ ++    6 < Parser > Output ++    3  ++ ++   0  +++ ++   ++ ++  Action   Goto   table   table  ++ ++ 
Figure 1. Architecture of a tablebased bottomup parser 
The two LR(0) parsing tables for this grammar look as follows:
action  goto  
state  *  +  0  1  $  E  B  
0  s1  s2  3  4  
1  r4  r4  r4  r4  r4  
2  r5  r5  r5  r5  r5  
3  s5  s6  acc  
4  r3  r3  r3  r3  r3  
5  s1  s2  7  
6  s1  s2  8  
7  r1  r1  r1  r1  r1  
8  r2  r2  r2  r2  r2 
The action table is indexed by a state of the parser and a terminal (including a special nonterminal $ that indicates the end of the input stream) and contains three types of actions: a shift that is written as 'sn ' and indicates that the next state is n, a reduce that is written as 'rm ' and indicates that a reduction with grammar rule m should be performed and an accept that is written as 'acc' and inidcates that the parser accepts the string in the input stream.
The goto table is indexed by a state of the parser and a nonterminal and simply indicates what the next state of the parser will be if it has recognized a certain nonterminal.
The LR parsing algorithm now works as follows:
In practice the parser will usually try to recover from a syntax error by ignoring unexpected symbols and/or inserting missing symbols, and continue parsing, but this is outside the scope of this article.
To explain why this algorithm works we now proceed with showing how a string like "1 + 1" would be parsed by such a parser. When the parser starts it always starts with the initial state 0 and the following stack:
The first terminal that the parser sees is the '1' and according to the action table it should then go to state 2 resulting in the following stack:
The top of the stack is presumed to be on the right. For the sake of our explanation we also show the symbol that caused the transition to the next state although strictly speaking it is not part of the stack.
In state 2 the action table says that whatever terminal we see on the input stream we should do a reduction with grammar rule 5. If the table is correct then this means that the parser has just recognized the righthand side of rule 5, which is indeed the case. So in this case we write 5 to the output stream, pop one state from the stack, and push on the stack the state from the cell in the goto table for state 0 and B, i.e., state 4, onto the stack. The resulting stack is:
However, also in state 4 the action table says we also do a reduction with rule 3. So we write 3 to the output stream, pop one state from the stack, and find the new state in the goto table for state 0 and E, which is state 3. The resulting stack:
The next terminal that the parser sees is a '+' and according to the action table it should then go to state 6:
Note that the resulting stack can be interpreted as the history of a finite state automaton that has just read a nonterminal E followed by a terminal '+'. The transition table of this automaton is defined by the shift actions in the action table and the goto actions in the goto table.
The next terminal is now '1' and this means that we perform a shift and go to state 2:
Just as the previous '1' this one is reduced to B giving the following stack:
Again note that the stack corresponds with a list of states of a finite automaton that has read a nonterminal E, followed by a '+' and then a nonterminal B. In state 8 we always perform a reduce with rule 2. Note that the top 3 states on the stack correspond with the 3 symbols in the righthand side of rule 2.
Finally, we read a '$' from the input stream which means that according to the action table (the current state is 3) the parser accepts the input string. The rule numbers that will then have been written to the output stream will be [ 5, 3, 5, 2 ] which is indeed a rightmost derivation of the string "1 + 1" in reverse.
The construction of these parsing tables is based on the notion of LR(0) item (simply called item here) which are grammar rules with a special dot added somewhere in the righthand side. For example the rule E → E + B has the following four corresponding items:
It is usually not possible to characterize the state of the parser with a single item because it may not know in advance which rule it is going to use for reduction. For example if there is also a rule E → E * B then the items E → E · + B and E → E · * B will both apply after a string corresponding with E has been read. Therefore we will characterize the state of the parser by a set of items, in this case the set { E → E · + B, E → E · * B }.
If in an item there is a dot in front of a nonterminal, as for example in E → E + · B, then the grammar rules for B should also be activated. This means that if there are rules such as B → 1 and B → 0 then we also should add the items B → · 1 and B → · 0 to the item set. In general this can be formulated as follows:
It is easy to see that any set of items can be extended such that it satisfies this rule. The minimal extension is called the closure of an item set and written as clos(I) where I is an item set. It are these closed item sets that we will take as the states of the parser, although only the ones that are actually reachable from the begin state will be included in the tables.
Before we start determining the transitions between the different states, the grammar is always augmented with an extra rule
where S is a new start symbol and E the old start symbol. The parser will use this rule for reduction exactly when it has accepted the input string.
For our example we will take the same grammar as before and augment it:
It is for this augmented grammar that we will determine the item sets and the transitions between them.
The first step of constructing the tables consists of determining the transitions between the closed item sets. These transitions will be determined as if we are considering an finite automaton that can read terminals as well as nonterminals. The begin state of this automaton is always the closure of the first item of the added rule: S → · E:
The '+' in front of an item indicates the items that were added for the closure. The original items without a '+' are called the kernel of the item set.
Beginning from the begin state we will now determine all the states that can be reached from this state. The possible transitions for an item set can be found by looking at the symbols (terminals and nonterminals) we find right behind the dots, in the case of item set 0 these are the terminals '0' and '1' and the nonterminal E and B. To find the item set that a symbol x leads to we follow the following procedure:
For the terminal '0' this results in:
and for the terminal '1' in:
and for the nonterminal E in:
and for the nonterminal B in:
Note that in all cases the closure does not add any new items. We continue this process until no more new item sets are found. For the item sets 1 and 2 there will be no transitions since the dot is not in front of any symbol. For item set 3 we see that the dot is in front of the terminals '*' and '+'. For '*' the transition goes to:
and for '+' the transition goes to:
For item set 5 we have to consider the terminals '0' and '1' and the nonterminal B. For the terminals we see that the resulting closed item sets are equal to the already found item sets 1 and 2, respectively. For the nonterminal B the transition goes to:
For item set 6 we also have to consider the terminal '0' and '1' and the nonterminal B. Als here the resulting item sets for the terminals are equal to the already found item sets 1 and 2. For the nontermal B the transition goes to:
These final item sets have no symbols behind their dots so no more new item sets are added and we are finished. The transition table for the automaton now looks as follows:
item set  *  +  0  1  E  B  
0  1  2  3  4  
1  
2  
3  5  6  
4  
5  1  2  7  
6  1  2  8  
7  
8 
From this table and the found item sets we construct the action and goto table as follows:
The automaton that is constructed is by the way it is constructed always a deterministic automaton. However, when reduce actions are added to to the action table it can happen that the same cell is filled with a reduce action and a shift action (a shiftreduce conflict) or with two different reduce actions (a reducereduce conflict). However, it can be shown that when this happens the grammar is not an LL(0) grammar.
A small example of a nonLL(0) grammar with a shiftreduce conflict is:
One of the item sets we then find is:
There is a shiftreduce conflict in this item set because in the cell in the action table for this item set and the terminal '1' there will be both a shift action to state 1 and a reduce action with rule 2.
A small example of a nonLL(0) grammar with a reducereduce conflict is:
In this case we obtain the following item set:
There is a reducereduce conflict in this item set because in the cells in the action table for this item set there will be both a reduce action for rule 3 and one for rule 4.
Both examples above can be solved by letting the parser use the follow set (see LL parser) of a nonterminal A to decide if it is going to use one of As rules for a reduction; it will only use the rule A → w for a reduction if the next symbol on the input stream is in the follow set of A. This solution results in socalled Simple LR parsers.
Search Encyclopedia

Featured Article
