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

S->AA

A->aA/b

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 .

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.

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:**__L__ook**A:**__A__head**L:**__L__eft To Right Scanning of String**R:**Reverse to__R__ight 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 |

## No comments:

## Post a Comment