UNIT - II

Syntax Analysis: Introduction, Context-Free Grammars, Writing a Grammar, Top-Down

Parsing, Bottom-Up Parsing, Introduction to LR Parsing: Simple LR, SLR, LALR, CLR,
Using Ambiguous Grammars and Parser Generators

Syntax Analysis

Syntax analysis or parsing is the second phase of a compiler, We have seen that a lexical
analyzer can identify tokens with the help of regular expressions and pattern rules. But a
lexical analyzer cannot check the syntax of a given sentence due to the limitations of the
regular expressions. Regular expressions cannot check balancing tokens, such as parenthesis.
Therefore, this phase uses context-free grammar (CFG), which is recognized by push-down
automata.
CFG, on the other hand, is a superset of Regular Grammar, as depicted below:

It implies that every Regular Grammar is also context-free, but there exists some problems,
which are beyond the scope of Regular Grammar. CFG is a helpful tool in describing the
syntax of programming languages.
Context-Free Grammar
In this section, we will first see the definition of context-free grammar and introduce
terminologies used in parsing technology.
A context-free grammar has four components:
 A set of non-terminals (V). Non-terminals are syntactic variables that denote sets of
 strings. The non-terminals define sets of strings that help define the language
generated by the grammar.
 A set of tokens, known as terminal symbols (Σ). Terminals are the basic symbols from
which strings are formed.
 A set of productions (P). The productions of a grammar specify the manner in which
the terminals and non-terminals can be combined to form strings. Each production
consists of a non-terminal called the left side of the production, an arrow, and a
sequence of tokens and/or on- terminals, called the right side of the production.
 One of the non-terminals is designated as the start symbol (S); from where the
production begins.
The strings are derived from the start symbol by repeatedly replacing a non-terminal (initially
the start symbol) by the right side of a production, for that non-terminal.
Example
We take the problem of palindrome language, which cannot be described by means of
Regular Expression. That is, L = { w | w = wR } is not a regular language. But it can be
described by means of CFG, as illustrated below:
G = ( V, Σ, P, S )
Where:
V = { Q, Z, N }
Σ = { 0, 1 }
P = { Q → Z | Q → N | Q → ℇ | Z → 0Q0 | N → 1Q1 }
S={Q}
This grammar describes palindrome language, such as: 1001, 11100111, 00100, 1010101,
11111, etc.
Syntax Analyzers
A syntax analyzer or parser takes the input from a lexical analyzer in the form of token
streams. The parser analyzes the source code (token stream) against the production rules to
detect any errors in the code. The output of this phase is a parse tree.
This way, the parser accomplishes two tasks, i.e., parsing the code, looking for errors and
generating a parse tree as the output of the phase.

Derivation
A derivation is basically a sequence of production rules, in order to get the input string.
During parsing, we take two decisions for some sentential form of input:
 Deciding the non-terminal which is to be replaced.
 Deciding the production rule, by which, the non-terminal will be replaced.
To decide which non-terminal to be replaced with production rule, we can have two options.
Left-most Derivation
If the sentential form of an input is scanned and replaced from left to right, it is called left-
most derivation. The sentential form derived by the left-most derivation is called the left-
sentential form.
Right-most Derivation
If we scan and replace the input with production rules, from right to left, it is known as right-
most derivation. The sentential form derived from the right-most derivation is called the
right-sentential form.
Example
Production rules:
E→E+E
E→E*E
E → id
Input string: id + id * id
The left-most derivation is:
E→E*E
E→E+E*E
E → id + E * E
E → id + id * E
E → id + id * id
Notice that the left-most side non-terminal is always processed first.
The right-most derivation is:
E→E+E
E→E+E*E
E → E + E * id
E → E + id * id
E → id + id * id
Parse Tree
A parse tree is a graphical depiction of a derivation. It is convenient to see how strings are
derived from the start symbol. The start symbol of the derivation becomes the root of the
parse tree. Let us see this by an example from the last topic.
We take the left-most derivation of a + b * c
The left-most derivation is:
E→E*E
E→E+E*E
E → id + E * E
E → id + id * E
E → id + id * id
Step 1:

E→E*E

Step 2:
 E→E+E*E

Step 3:

E → id + E * E

Step 4:

E → id + id * E

Step 5:
 E → id + id * id

In a parse tree:
 All leaf nodes are terminals.
 All interior nodes are non-terminals.
 In-order traversal gives original input string.
A parse tree depicts associativity and precedence of operators. The deepest sub-tree is
traversed first, therefore the operator in that sub-tree gets precedence over the operator which
is in the parent nodes.

Types of Parsing

Syntax analyzers follow production rules defined by means of context-free grammar. The
way the production rules are implemented (derivation) divides parsing into two types : top-
down parsing and bottom-up parsing.

Top-down Parsing
When the parser starts constructing the parse tree from the start symbol and then tries to
transform the start symbol to the input, it is called top-down parsing.
  Recursive descent parsing : It is a common form of top-down parsing. It is called
recursive as it uses recursive procedures to process the input. Recursive descent
parsing suffers from backtracking.
 Backtracking : It means, if one derivation of a production fails, the syntax analyzer
restarts the process using different rules of same production. This technique may
process the input string more than once to determine the right production.

Bottom-up Parsing
As the name suggests, bottom-up parsing starts with the input symbols and tries to construct
the parse tree up to the start symbol.
Example
Input string : a + b * c
Production rules:
S→E
E→E+T
E→E*T
E→T
T → id
Let us start bottom-up parsing
a+b*c
Read the input and check if any production matches with the input:
a+b*c
T+b*c
E+b*c
E+T*c
E*c
E*T
E
S
Introduction to LR Parsing

LR parser is a bottom-up parser for context-free grammar that is very generally used by
computer programming language compiler and other associated tools. LR parser reads their
input 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 parser 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, R refers to the
rightmost derivation in reverse and k refers to the number of unconsumed “look ahead” 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. But when we read from above, the derivation order first
extends to non-terminal.
1. The stack is empty, and we are looking to reduce the rule by S’→S$.
2. Using a “.” in the rule represents how many of the rules are already on the stack.
3. A dotted item, or simply, the item is a production rule with a dot indicating how much
RHS has so far been recognized. Closing an item is used to see what production rules
can be used to expand the current structure. It is calculated as follows:
Rules for LR parser :
The rules of LR parser as follows.
1. The first item from the given grammar rules adds itself as the first closed set.
2. If an object is present in the closure of the form A→ α. β. γ, where the next symbol
after the symbol is non-terminal, add the symbol’s production rules where the dot
precedes the first item.
3. Repeat steps (B) and (C) for new items added under (B).
LR parser algorithm :
LR Parsing algorithm is the same for all the parser, but the parsing table is different for each
parser. It consists following components as follows.
1. Input Buffer –
It contains the given string, and it ends with a $ symbol.

2. Stack –
The combination of state symbol and current input symbol is used to refer to the
parsing table in order to take the parsing decisions.
Parsing Table :
Parsing table is divided into two parts- Action table and Go-To table. The action table gives a
grammar rule to implement the given current state and current terminal in the input stream.
There are four cases used in action table as follows.
1. Shift Action- In shift action the present terminal is removed from the input stream and
the state n is pushed onto the stack, and it becomes the new present state.
2. Reduce Action- The number m is written to the output stream.
3. The symbol m mentioned in the left-hand side of rule m says that state is removed
 from the stack.
4. The symbol m mentioned in the left-hand side of rule m says that a new state is
looked up in the goto table and made the new current state by pushing it onto the
stack.
An accept - the string is accepted
No action - a syntax error is reported
Note –
The go-to table indicates which state should proceed.
LR parser diagram :

Types of LR Parsing Methods

 SLR parser
 LALR parser
 Canonical LR parser
SLR Parser
 LR parser is also called as SLR parser
 it is weakest of the three methods but easier to implement
 a grammar for which SLR parser can be constructed is called SLR grammar
Steps for constructing the SLR parsing table
1. Writing augmented grammar
2. LR(0) collection of items to be found
 3. Find FOLLOW of LHS of production
4. Defining 2 functions:goto[list of terminals] and action[list of non-terminals] in the
parsing table
EXAMPLE – Construct LR parsing table for the given context-free grammar
S–>AA
A–>aA|b
Solution:
STEP1: Find augmented grammar
The augmented grammar of the given grammar is:-
S’–>.S [0th production]
S–>.AA [1st production]
A–>.aA [2nd production]
A–>.b [3rd production]
STEP2: Find LR(0) collection of items
Below is the figure showing the LR(0) collection of items. We will understand everything
one by one.
The terminals of this grammar are {a,b}.
The non-terminals of this grammar are {S,A}
RULE –
If any non-terminal has ‘ . ‘ preceding it, we have to write all its production and add ‘ . ‘
preceding each of its production.
RULE –
from each state to the next state, the ‘ . ‘ shifts to one place to the right.
 In the figure, I0 consists of augmented grammar.
 Io goes to I1 when ‘ . ‘ of 0th production is shifted towards the right of S(S’->S.). this
state is the accepted state. S is seen by the compiler.
 Io goes to I2 when ‘ . ‘ of 1st production is shifted towards right (S->A.A) . A is seen
by the compiler
 I0 goes to I3 when ‘ . ‘ of the 2nd production is shifted towards right (A->a.A) . a is
seen by the compiler.
 I0 goes to I4 when ‘ . ‘ of the 3rd production is shifted towards right (A->b.) . b is
 seen by the compiler.
 I2 goes to I5 when ‘ . ‘ of 1st production is shifted towards right (S->AA.) . A is seen
by the compiler
 I2 goes to I4 when ‘ . ‘ of 3rd production is shifted towards right (A->b.) . b is seen
by the compiler.
 I2 goes to I3 when ‘ . ‘ of the 2nd production is shifted towards right (A->a.A) . a is
seen by the compiler.
 I3 goes to I4 when ‘ . ‘ of the 3rd production is shifted towards right (A->b.) . b is
seen by the compiler.
 I3 goes to I6 when ‘ . ‘ of 2nd production is shifted towards the right (A->aA.) . A is
seen by the compiler
 I3 goes to I3 when ‘ . ‘ of the 2nd production is shifted towards right (A->a.A) . a is
seen by the compiler.
STEP3: Find FOLLOW of LHS of production
FOLLOW(S)=$
FOLLOW(A)=a,b,$
To find FOLLOW of non-terminals, please read follow set in syntax analysis.
STEP 4: Defining 2 functions:goto[list of non-terminals] and action[list of terminals] in the
parsing table. Below is the SLR parsing table.

 $ is by default a nonterminal that takes accepting state.

 0,1,2,3,4,5,6 denotes I0,I1,I2,I3,I4,I5,I6
 I0 gives A in I2, so 2 is added to the A column and 0 rows.
 I0 gives S in I1,so 1 is added to the S column and 1 row.
 similarly 5 is written in A column and 2 row, 6 is written in A column and 3 row.
 I0 gives a in I3 .so S3(shift 3) is added to a column and 0 row.
  I0 gives b in I4 .so S4(shift 4) is added to the b column and 0 row.
 Similarly, S3(shift 3) is added on a column and 2,3 row ,S4(shift 4) is added on b
column and 2,3 rows.
 I4 is reduced state as ‘ . ‘ is at the end. I4 is the 3rd production of grammar(A–
>.b).LHS of this production is A. FOLLOW(A)=a,b,$ . write r3(reduced 3) in the
columns of a,b,$ and 4th row
 I5 is reduced state as ‘ . ‘ is at the end. I5 is the 1st production of grammar(S–>.AA).
LHS of this production is S.
FOLLOW(S)=$ . write r1(reduced 1) in the column of $ and 5th row
 I6 is a reduced state as ‘ . ‘ is at the end. I6 is the 2nd production of grammar( A–
>.aA). The LHS of this production is A.
FOLLOW(A)=a,b,$ . write r2(reduced 2) in the columns of a,b,$ and 6th row

CLR Parser :
The CLR parser stands for canonical LR [Link] is a more powerful LR [Link] makes use
of lookahead symbols. This method uses a large set of items called LR(1) [Link] main
difference between LR(0) and LR(1) items is that, in LR(1) items, it is possible to carry more
information in a state, which will rule out useless reduction [Link] extra information is
incorporated into the state by the lookahead symbol. The general syntax becomes [A->∝.B, a
]
where A->∝.B is the production and a is a terminal or right end marker $
LR(1) items=LR(0) items + look ahead
How to add lookahead with the production?
CASE 1 –
A->∝.BC, a
Suppose this is the 0th [Link], since ‘ . ‘ precedes B,so we have to write B’s
productions as well.
B->.D [1st production]
Suppose this is B’s production. The look ahead of this production is given as we look at
previous productions ie 0th production. Whatever is after B, we find FIRST(of that value) ,
that is the lookahead of 1st [Link],here in 0th production, after B, C is there. assume
FIRST(C)=d, then 1st production become
B->.D, d
CASE 2 –
Now if the 0th production was like this,
A->∝.B, a
Here, we can see there’s nothing after B. So the lookahead of 0th production will be the
lookahead of 1st production. ie-
B->.D, a
CASE 3 –
Assume a production A->a|b
A->a,$ [0th production]
A->b,$ [1st production]
Here, the 1st production is a part of the previous production, so the lookahead will be the
same as that of its previous production.
These are the 2 rules of look ahead.
Steps for constructing CLR parsing table :
1. Writing augmented grammar
2. LR(1) collection of items to be found
3. Defining 2 functions: goto[list of terminals] and action[list of non-terminals] in the
CLR parsing table
EXAMPLE
Construct a CLR parsing table for the given context-free grammar
S-->AA
A-->aA|b
Solution :
STEP 1 – Find augmented grammar
The augmented grammar of the given grammar is:-
S'-->.S ,$ [0th production]
S-->.AA ,$ [1st production]
A-->.aA ,a|b [2nd production]
A-->.b ,a|b [3rd production]
Let’s apply the rule of lookahead to the above productions
 The initial look ahead is always $
  Now, the 1st production came into existence because of ‘ . ‘ Before ‘S’ in 0th
[Link] is nothing after ‘S’, so the lookahead of 0th production will be the
lookahead of 1st production. ie: S–>.AA ,$
 Now, the 2nd production came into existence because of ‘ . ‘ Before ‘A’ in the 1st
[Link] ‘A’, there’s ‘A’. So, FIRST(A) is a,b
Therefore,the look ahead for the 2nd production becomes a|b.
 Now, the 3rd production is a part of the 2nd [Link], the look ahead will be the
same.
STEP 2 – Find LR(1) collection of items
Below is the figure showing the LR(1) collection of items. We will understand everything
one by one.

The terminals of this grammar are {a,b}

The non-terminals of this grammar are {S,A}
RULE-
1. If any non-terminal has ‘ . ‘ preceding it, we have to write all its production and add
‘ . ‘ preceding each of its production.
2. from each state to the next state, the ‘ . ‘ shifts to one place to the right.
3. All the rules of lookahead apply here.
 In the figure, I0 consists of augmented grammar.
 Io goes to I1 when ‘ . ‘ of 0th production is shifted towards the right of S(S’->S.).
This state is the accept state . S is seen by the compiler. Since I1 is a part of the 0th
production, the lookahead is the same ie $
 Io goes to I2 when ‘ . ‘ of 1st production is shifted towards right (S->A.A) . A is seen
by the compiler. Since I2 is a part of the 1st production, the lookahead is the same i.e.
$.
 I0 goes to I3 when ‘ . ‘ of the 2nd production is shifted towards right (A->a.A) . a is
seen by the compiler. Since I3 is a part of the 2nd production, the lookahead is the
same ie a|b.
 I0 goes to I4 when ‘ . ‘ of the 3rd production is shifted towards right (A->b.) . b is
seen by the compiler. Since I4 is a part of the 3rd production, the lookahead is the
same i.e. a | b.
 I2 goes to I5 when ‘ . ‘ of 1st production is shifted towards right (S->AA.) . A is seen
by the compiler. Since I5 is a part of the 1st production, the lookahead is the same i.e.
$.
 I2 goes to I6 when ‘ . ‘ of 2nd production is shifted towards the right (A->a.A) . A is
seen by the compiler. Since I6 is a part of the 2nd production, the lookahead is the
same i.e. $.
 I2 goes to I7 when ‘ . ‘ of 3rd production is shifted towards right (A->b.) . A is seen
by the compiler. Since I6 is a part of the 3rd production, the lookahead is the same i.e.
$.
 I3 goes to I3 when ‘ . ‘ of the 2nd production is shifted towards right (A->a.A) . a is
seen by the compiler. Since I3 is a part of the 2nd production, the lookahead is the
same i.e. a|b.
 I3 goes to I8 when ‘ . ‘ of 2nd production is shifted towards the right (A->aA.) . A is
seen by the compiler. Since I8 is a part of the 2nd production, the lookahead is the
same i.e. a|b.
 I6 goes to I9 when ‘ . ‘ of 2nd production is shifted towards the right (A->aA.) . A is
seen by the compiler. Since I9 is a part of the 2nd production, the lookahead is the
same i.e. $.
 I6 goes to I6 when ‘ . ‘ of the 2nd production is shifted towards right (A->a.A) . a is
seen by the compiler. Since I6 is a part of the 2nd production, the lookahead is the
same i.e. $.
 I6 goes to I7 when ‘ . ‘ of the 3rd production is shifted towards right (A->b.) . b is
 seen by the compiler. Since I6 is a part of the 3rd production, the lookahead is the
same ie $.
STEP 3- defining 2 functions:goto[list of terminals] and action[list of non-terminals] in the
parsing [Link] is the CLR parsing table

 $ is by default a non terminal which takes accepting state.

 0,1,2,3,4,5,6,7,8,9 denotes I0,I1,I2,I3,I4,I5,I6,I7,I8,I9
 I0 gives A in I2, so 2 is added to the A column and 0 row.
 I0 gives S in I1,so 1 is added to the S column and 1st row.
 similarly 5 is written in A column and 2nd row, 8 is written in A column and 3rd
row, 9 is written in A column and 6th row.
 I0 gives a in I3, so S3(shift 3) is added to a column and 0 row.
 I0 gives b in I4, so S4(shift 4) is added to the b column and 0 row.
 Similarly, S6(shift 6) is added on ‘a’ column and 2,6 row ,S7(shift 7) is added on b
column and 2,6 row,S3(shift 3) is added on ‘a’ column and 3 row ,S4(shift 4) is added
on b column and 3 row.
 I4 is reduced as ‘ . ‘ is at the end. I4 is the 3rd production of grammar. So write
r3(reduce 3) in lookahead columns. The lookahead of I4 are a and b, so write R3 in a
and b column.
 I5 is reduced as ‘ . ‘ is at the end. I5 is the 1st production of grammar. So write
r1(reduce 1) in lookahead columns. The lookahead of I5 is $ so write R1 in $ column.
 Similarly, write R2 in a,b column and 8th row, write R2 in $ column and 9th row.
LALR Parser (with Examples)

LALR Parser :
LALR Parser is lookahead LR parser. It is the most powerful parser which can handle large
classes of grammar. The size of CLR parsing table is quite large as compared to other parsing
table. LALR reduces the size of this [Link] works similar to CLR. The only difference
is , it combines the similar states of CLR parsing table into one single state.
The general syntax becomes [A->∝.B, a ]
where A->∝.B is production and a is a terminal or right end marker $
LR(1) items=LR(0) items + look ahead
How to add lookahead with the production?
CASE 1 –
A->∝.BC, a
Suppose this is the 0th [Link], since ‘ . ‘ precedes B,so we have to write B’s
productions as well.
B->.D [1st production]
Suppose this is B’s production. The look ahead of this production is given as- we look at
previous production i.e. – 0th production. Whatever is after B, we find FIRST(of that value) ,
that is the lookahead of 1st production. So, here in 0th production, after B, C is there. Assume
FIRST(C)=d, then 1st production become.
B->.D, d
CASE 2 –
Now if the 0th production was like this,
A->∝.B, a
Here,we can see there’s nothing after B. So the lookahead of 0th production will be the
lookahead of 1st production. ie-
B->.D, a
CASE 3 –
Assume a production A->a|b
A->a,$ [0th production]
A->b,$ [1st production]
Here, the 1st production is a part of the previous production, so the lookahead will be the
same as that of its previous production.
Steps for constructing the LALR parsing table :
1. Writing augmented grammar
2. LR(1) collection of items to be found
3. Defining 2 functions: goto[list of terminals] and action[list of non-terminals] in the
LALR parsing table
EXAMPLE
Construct CLR parsing table for the given context free grammar
S-->AA
A-->aA|b
Solution:
STEP1- Find augmented grammar
The augmented grammar of the given grammar is:-
S'-->.S ,$ [0th production]
S-->.AA ,$ [1st production]
A-->.aA ,a|b [2nd production]
A-->.b ,a|b [3rd production]
Let’s apply the rule of lookahead to the above productions.
 The initial look ahead is always $
 Now,the 1st production came into existence because of ‘ . ‘ before ‘S’ in 0th
[Link] is nothing after ‘S’, so the lookahead of 0th production will be the
lookahead of 1st production. i.e. : S–>.AA ,$
 Now,the 2nd production came into existence because of ‘ . ‘ before ‘A’ in the 1st
production.
After ‘A’, there’s ‘A’. So, FIRST(A) is a,b. Therefore, the lookahead of the 2nd
production becomes a|b.
 Now,the 3rd production is a part of the 2nd [Link], the look ahead will be the
same.
STEP2 – Find LR(0) collection of items
Below is the figure showing the LR(0) collection of items. We will understand everything
one by one.
The terminals of this grammar are {a,b}
The non-terminals of this grammar are {S,A}
RULES –
1. If any non-terminal has ‘ . ‘ preceding it, we have to write all its production and add
‘ . ‘ preceding each of its production.
2. from each state to the next state, the ‘ . ‘ shifts to one place to the right.
 In the figure, I0 consists of augmented grammar.
 Io goes to I1 when ‘ . ‘ of 0th production is shifted towards the right of S(S’->S.).
This state is the accept state . S is seen by the compiler. Since I1 is a part of the 0th
production, the lookahead is same i.e. $
 Io goes to I2 when ‘ . ‘ of 1st production is shifted towards right (S->A.A) . A is seen
by the compiler. Since I2 is a part of the 1st production, the lookahead is same i.e. $.
 I0 goes to I3 when ‘ . ‘ of 2nd production is shifted towards the right (A->a.A) . a is
seen by the [Link] I3 is a part of 2nd production, the lookahead is same i.e. a|
b.
 I0 goes to I4 when ‘ . ‘ of 3rd production is shifted towards right (A->b.) . b is seen
by the compiler. Since I4 is a part of 3rd production, the lookahead is same i.e. a|b.
 I2 goes to I5 when ‘ . ‘ of 1st production is shifted towards right (S->AA.) . A is seen
by the compiler. Since I5 is a part of the 1st production, the lookahead is same i.e. $.
 I2 goes to I6 when ‘ . ‘ of 2nd production is shifted towards the right (A->a.A) . A is
seen by the compiler. Since I6 is a part of the 2nd production, the lookahead is same
i.e. $.
 I2 goes to I7 when ‘ . ‘ of 3rd production is shifted towards right (A->b.) . A is seen
by the compiler. Since I6 is a part of the 3rd production, the lookahead is same i.e. $.
 I3 goes to I3 when ‘ . ‘ of the 2nd production is shifted towards right (A->a.A) . a is
seen by the compiler. Since I3 is a part of the 2nd production, the lookahead is same
 i.e. a|b.
 I3 goes to I8 when ‘ . ‘ of 2nd production is shifted towards the right (A->aA.) . A is
seen by the compiler. Since I8 is a part of the 2nd production, the lookahead is same
i.e. a|b.
 I6 goes to I9 when ‘ . ‘ of 2nd production is shifted towards the right (A->aA.) . A is
seen by the compiler. Since I9 is a part of the 2nd production, the lookahead is same
i.e. $.
 I6 goes to I6 when ‘ . ‘ of the 2nd production is shifted towards right (A->a.A) . a is
seen by the compiler. Since I6 is a part of the 2nd production, the lookahead is same
i.e. $.
 I6 goes to I7 when ‘ . ‘ of the 3rd production is shifted towards right (A->b.) . b is
seen by the compiler. Since I6 is a part of the 3rd production, the lookahead is same
i.e. $.
STEP 3 –
Defining 2 functions: goto[list of terminals] and action[list of non-terminals] in the parsing
[Link] is the CLR parsing table

Once we make a CLR parsing table, we can easily make a LALR parsing table from it.
In the step2 diagram, we can see that
 I3 and I6 are similar except their lookaheads.
 I4 and I7 are similar except their lookaheads.
 I8 and I9 are similar except their lookaheads.
In LALR parsing table construction , we merge these similar states.
 Wherever there is 3 or 6, make it 36(combined form)
  Wherever there is 4 or 7, make it 47(combined form)
 Wherever there is 8 or 9, make it 89(combined form)
Below is the LALR parsing table.

Now we have to remove the unwanted rows

 As we can see, 36 row has same data twice, so we delete 1 row.
 We combine two 47 row into one by combining each value in the single 47 row.
 We combine two 89 row into one by combining each value in the single 89 row.
The final LALR table looks like the below.