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:
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.
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 |
No comments:
Post a Comment