How To Construct CLR(1) or LR(1) Parsing Table

                      In this post, we will see how to construct CLR(1) or LR(1) parsing table for given grammar.

What is meaning of name CLR(1)???
C: Canonical
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->.EFG, FIRST(CDα).
Similarly,  
                  If (A->B.CD, α) is item in closure, then next item will be (C->.HIJ, FIRST(Dα).
                 If (A->BC.D, α) is item in closure, then next item will be (C->.KLM, 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:

Closure	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

Check Other Posts on Compiler

Next: How To Construct LALR(1) Parsing Table

Previous: How To Construct SLR(1) Parsing Table