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