bottom-up parsing - LR Parser
Lecture 6
LR parser
▪ In this lecture, we will discuss the LR parser and its overview
and then will discuss the algorithm.
▪ Also, we will discuss the parsing table and LR parser working
diagram. Let’s discuss it one by one.
LR PARSER
LR PARSER
▪ LR parsing is divided into four parts:
Least powerful
▪ LR (0) parsing,
▪ SLR(1) parsing (simple LR),
▪ LALR(1) parsing (Look A-head LR).
▪ CLR (1) parsing (canonical LR )
Most powerful
LR PARSER
▪ LR parser is a non-recursive shift-reduced bottom-up parser, it is for context-free grammar
that is used by computer programming language compilers and other associated tools.
▪ LR parser scans the input stream from left to right and produces a right-most derivation.
▪ It is called a Bottom-up parser because it attempts to reduce the top-level grammar
productions by building up from the leaves.
▪ LR parsers are the most powerful of all deterministic parsers in practice.
DESCRIPTION OF LR PARSER :
▪ The term parser LR(k) parser, here the
▪ L refers to the left-to-right scanning for the input stream,
▪ R refers to the construction of the rightmost derivation in reverse
▪ k refers to the number of unconsumed “look ahead symbol” input symbols that are
used in making parser decisions. Typically, k is 1 and is often omitted.
▪ A context-free grammar is called LR (k) if the LR (k) parser exists for it.
This first reduces the sequence of tokens to the left.
DESCRIPTION OF LR PARSER :
▪ LR(1):
▪ LR parser
▪ Works on complete set of LR(1) grammar
▪ Has large numbers of states
▪ Slow construction
DESCRIPTION OF LR PARSER :
▪ SLR(1):
▪ simple LR parser
▪ Works on smallest class of grammar
▪ Has few numbers of states
▪ Simple and fast construction
DESCRIPTION OF LR PARSER :
▪ LALR(1):
▪ Look A head LR parser
▪ Works on intermediate-size of grammar
▪ numbers of states are same as SLR(1)
STRUCTURE OF LR PARSER :
DESCRIPTION OF LR PARSER :
LR Parsing structure is the same for all the parser, but the parsing table is
different for each parser. It consists following components as follows.
Input Buffer –
It contains the given string, and it ends with a $ symbol.
Stack –
The combination of state symbol and current input symbol is used to refer
to the parsing table to take the parsing decisions.
DESCRIPTION OF LR PARSER :
Parsing Table :
▪ Parsing table is divided into two parts- The action table and the Go-To
table.
▪ The action table gives a grammar rule for implementing the current state
and terminal in the input stream. There are four cases used in the action
table as follows.
DESCRIPTION OF LR PARSER :
In shift action, we remove the present terminal from the input
stream, push state n onto the stack, and it becomes the new
present state.
Reduce Action- The number m is written to the output stream.
An accept - the string is accepted
No action -
DESCRIPTION OF LR PARSER :
The symbol m mentioned in the left-hand side of rule m says that state is
removed from the stack.
The symbol m mentioned in the left-hand side of rule m says that a new
state is looked up in the go to table and made the new current state by
pushing it onto the stack.
DESCRIPTION OF LR PARSER :
Various steps involved in the LR (1) Parsing:
▪ For the given input string write a context free grammar.
▪ Check the ambiguity of the grammar.
▪ Add Augment production in the given grammar.
▪ Create Canonical collection of LR (0) items.
▪ Draw a data flow diagram (DFA).
▪ Construct a parsing table.
AUGMENT GRAMMAR
▪ Augmented grammar G` will be generated if we add one more
production in the given grammar G.
▪ It helps the parser to identify when to stop the parsing and announce the
acceptance of the input.
AUGMENT GRAMMAR
▪Example
▪ Given grammar
▪ S → AA
▪ A → aA | b
▪ The Augment grammar G` is represented by
▪ S`→ S
▪ S → AA
▪ A → aA | b
CANONICAL COLLECTION OF LR(0) ITEMS
▪ AnLR (0) item is a production G with dot at some
position on the right side of the production.
▪ LR(0) items is useful to indicate that how much of
the input has been scanned up to a given point in
the process of parsing.
CANONICAL COLLECTION OF LR(0) ITEMS
▪ Example
▪ Given grammar
▪ S → AA
▪ A → aA | b
▪ Add Augment Production and insert '•' symbol at the first
position for every production in G
▪ S` → •S
▪ S → •AA
▪ A → •aA
▪ A → •b
CANONICAL COLLECTION OF LR(0) ITEMS
▪ I0 State:
▪ Add Augment production to the I0 State and Compute the Closure
▪ I0 = Closure (S` → •S)
▪ Add all productions starting with S in to I0 State because "•" is followed
by the non-terminal. So, the I0 State becomes
▪ I0 = S` → •S
▪ S → •AA
▪ Add all productions starting with "A" in modified I0 State because "•" is
followed by the non-terminal. So, the I0 State becomes.
CANONICAL COLLECTION OF LR(0) ITEMS
▪ I0 State:
▪ Add all productions starting with "A" in modified I0 State
because "•" is followed by the non-terminal. So, the I0 State
becomes.
▪ I0= S` → •S
▪ S → •AA
▪ A → •aA
▪ A → •b
CANONICAL COLLECTION OF LR(0) ITEMS
▪ I1 State:
▪ I1= Go to (I0, S) = closure (S` → S•) = S` → S•
▪ Here, the Production is reduced so close the State.
▪ I1= S` → S•
CANONICAL COLLECTION OF LR(0) ITEMS
▪ I2 State:
▪ I2= Go to (I0, A) = closure (S → A•A)
▪ Add all productions starting with A in to I2 State because "•" is followed
by the non-terminal. So, the I2 State becomes
▪ I2 =S→A•A
▪ A → •aA
▪ A → •b
▪ Go to (I2,a) = Closure (A → a•A) = (same as I3)
▪ Go to (I2, b) = Closure (A → b•) = (same as I4)
CANONICAL COLLECTION OF LR(0) ITEMS
▪ I3 State:
▪ I3= Go to (I0,a) = Closure (A → a•A)
▪ Add productions starting with A in I3.
▪ A → a•A
▪ A → •aA
▪ A → •b
▪ Go to (I3, a) = Closure (A → a•A) = (same as I3)
▪ Go to (I3, b) = Closure (A → b•) = (same as I4)
CANONICAL COLLECTION OF LR(0) ITEMS
▪I4,I5,I6 States:
▪ I4= Go to (I0, b) = closure (A → b•) = A → b•
I5= Go to (I2, A) = Closure (S → AA•) = S→AA•
I6= Go to (I3, A) = Closure (A → aA•) = A → aA•
DRAWING DFA:
▪ The DFA contains the 7 states I0 to I6.
LR(0) TABLE
▪ If a state is going to some other state on a terminal, then it
correspond to a shift move.
▪ If a state is going to some other state on a variable(non-
terminal), then it correspond to go to move.
▪ If a state contain the final item in the particular row, then write
the reduce node completely.
LR(0) TABLE
EXPLANATION:
I0 on S is going to I1 so write it as 1.
I0 on A is going to I2 so write it as 2.
I2 on A is going to I5 so write it as 5.
I3 on A is going to I6 so write it as 6.
I0, I2and I3on a are going to I3 so write it as S3 which means that shift 3.
I0, I2 and I3 on b are going to I4 so write it as S4 which means that shift 4.
I4, I5 and I6 all states contains the final item because they contain • in the
right most end. So rate the production as production number.
PRODUCTIONS ARE NUMBERED AS FOLLOWS:
S → AA ... (1)
A → aA ... (2)
A → b ... (3)
• I1 contains the final item which drives(S` → S•), so action {I1, $} =
Accept.
• I4 contains the final item which drives A → b• and that production
corresponds to the production number 3 so write it as r3 in the entire row.
PRODUCTIONS ARE NUMBERED AS FOLLOWS:
S → AA ... (1)
A → aA ... (2)
A → b ... (3)
• I5 contains the final item which drives S → AA• and that production
corresponds to the production number 1 so write it as r1 in the entire row.
• I6 contains the final item which drives A → aA• and that production
corresponds to the production number 2 so write it as r2 in the entire row.
Thank you for listening
