Tuesday 9 August 2016

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
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:

ClosuresActionGoto
ab\$AS
0s3s421
1Accept
2s6s75
3s3s48
4r3r3
5r1
6s6s79
7r3
8r2r2
9r2

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:

ClosuresActionGoto
ab\$AS
0s36s4721
1Accept
2s36s47
5
36s36s4789
47r3r3r3
5

r1
89r2r2r2