How To Construct LALR(1) Parsing Table

                    In this post, we will see how to construct LALR(1) parsing table for given grammar.
                    If you know how to construct CLR(1) parsing table, then directly jump to LALR(1) Parsing Table: at the last section of the post.

What is meaning of name LALR(1)???
L: Look
A: Ahead
L: Left To Right Scanning of String
R: Reverse to Right Most Derivation
(1): Size of Look ahead is 1. 


Example:

S->AA
A->aA/b

How To Find Closures:

                   In LR(0) and SLR(1), items we have used are called LR(0) items which are of the form (A->.BCD or A->B.CD etc.). In CLR(1) and LALR(1), items which we will use are called as LR(1) items. These are of the form (A->.BCD, α).  Here α is a Lookahead symbol which represents the terminals after A .  

How To find Lookahead Symbol?
1. We start with item (S'->.S). It has Lookahead symbol $ as we assume that string ends at symbol $. So complete LR(1) item becomes (S'->.S, $).
2. If (A->.BCD, α) is item in closure, then next item will be (B->.DEF, FIRST(CDα).
Similarly,  
                  If (A->B.CD, α) is item in closure, then next item will be (C->.GHI, FIRST(Dα).
                 If (A->BC.D, α) is item in closure, then next item will be (C->.JKL, FIRST(α).
3. When we have to find first item of next closure, then Lookahead symbols are retained from the previous closure.

                     
Closure and Goto:

CLR(1) Parsing Table:

Closures	Action			Goto
	a	b	$	A	S
0	s3	s4		2	1
1			Accept
2	s6	s7		5
3	s3	s4		8
4	r3	r3
5			r1
6	s6	s7		9
7			r3
8	r2	r2
9			r2

LALR(1) Parsing Table:              
             Look at the Closure and Goto diagram of CLR (1). You will find there some closures/states which are same in all aspects except Lookahead symbol. Due to this, CLR(1) has many Closures/States which in turn increases the processing time.
             In LALR(1), we merge such closures/states. For e.g. in above diagram, we can merge (I3 and I6), (I4 and I7) and (I8 and I9). So we get new closures/states I36, I47 and I89 respectively.
             Reflecting these changes in CLR(1) parsing table, we get LALR(1) parsing table as follows: 

Closures	Action			Goto
	a	b	$	A	S
0	s36	s47		2	1
1			Accept
2	s36	s47		5
36	s36	s47		89
47	r3	r3	r3
5			r1
89	r2	r2	r2

Check Other Posts on Compiler

Previous: How To Construct CLR(1) Parsing Table