lalr parser presentation ppt
TRANSCRIPT
![Page 1: LALR Parser Presentation ppt](https://reader035.vdocumento.com/reader035/viewer/2022062820/58a6d38a1a28abcc458b6bef/html5/thumbnails/1.jpg)
Presentation onLALR PARSER
( Look Ahead Parser )
Submitted To
Dharemendra Sir
Submitted By
Vivek Kr Poddar
![Page 2: LALR Parser Presentation ppt](https://reader035.vdocumento.com/reader035/viewer/2022062820/58a6d38a1a28abcc458b6bef/html5/thumbnails/2.jpg)
Table Of Contento Introduction To LALR Parsero LALR Table Construction Methodo Examples – Related To Grammer, First, CLR, etc.o Computed LR( 0 ) Itemso GOTO Grapho Canonical Parsing Tableo LALR Parsing Table
2
![Page 3: LALR Parser Presentation ppt](https://reader035.vdocumento.com/reader035/viewer/2022062820/58a6d38a1a28abcc458b6bef/html5/thumbnails/3.jpg)
What is LALR Parsero LALR stands for (look ahead LR) parser.o LALR parser starts with the idea of building an LR parsing
tableo Tables generated by LALR parser are smaller in size as
compared to that of Canonical LR ( CLR ) and Simple LR ( SLR ) techniques.
o LALR parsers are slightly less powerful than LR parsers, but still more powerful than SLR parsers.
o LALR is used by YACC and other parser generators because of its effectiveness.
3
![Page 4: LALR Parser Presentation ppt](https://reader035.vdocumento.com/reader035/viewer/2022062820/58a6d38a1a28abcc458b6bef/html5/thumbnails/4.jpg)
LALR Table Construction Ideao Construct the set of LR (1) items.o Merge the sets with common core together in CLR table.o If any problem arises then grammar is not LALR.
4
![Page 5: LALR Parser Presentation ppt](https://reader035.vdocumento.com/reader035/viewer/2022062820/58a6d38a1a28abcc458b6bef/html5/thumbnails/5.jpg)
ExampleGrammar:1. S’ -> S2. S -> CC3. C -> cC4. C -> d
5
First : Where F Means First
F( S’ ) -> F( S ) -> F( C ) -> { c,d }
F ( C ) -> { c, d } -> c/d Look Ahead
Symbol
Note :: CC are two different items.
Note :: Non-terminals denoted by upper-case letters, terminals denoted by lower-case letters
S’ -> .S,$ :: This (a rule with a dot in it) is called an item, it indicates what is in the stack [ left side of . ] and what is to be expected on input [ right side of . ]Anything after ( , ) comma is termed as look ahead.
![Page 6: LALR Parser Presentation ppt](https://reader035.vdocumento.com/reader035/viewer/2022062820/58a6d38a1a28abcc458b6bef/html5/thumbnails/6.jpg)
Computed LR ( 0 ) & LR ( 1 ) Items 6
I5: S -> CC., $
I6: C -> c.C, $ C -> .cC, $ C -> .d, $
I7: C -> d., $
I8: C -> cC., c /d
I9: C -> cC., $
I0 : S’ -> .S, $ S -> .CC, $ C -> .c C, c /d C -> .d, c /dI1: S’ -> S., $I2: S -> C.C, $ C -> .c C, $ C -> .d, $ I3: C -> c. C, c /d C -> .Cc, c /d C -> .d, c /d14: C -> d., c / d
Grammar:1. S’ -> S2. S -> CC3. C -> cC4. C -> d
Grammar:1. S’ -> S2. S -> CC3. C ->
cC/d First ( c/d )
Note : I0 consist of LR ( 0 ). Items while rest are LR ( 1 ) items.
Its always suggested not to work beyond State 2 by hand as they are compicated and should be calculated using standard tools.
![Page 7: LALR Parser Presentation ppt](https://reader035.vdocumento.com/reader035/viewer/2022062820/58a6d38a1a28abcc458b6bef/html5/thumbnails/7.jpg)
7 Goto Graph
![Page 8: LALR Parser Presentation ppt](https://reader035.vdocumento.com/reader035/viewer/2022062820/58a6d38a1a28abcc458b6bef/html5/thumbnails/8.jpg)
8 Canonical Parsing TableStates
c d $ S C 0 S3 S4 1 21 acc2 S6 S7 53 S3 S4 84 R4 R45 R26 S6 S7 97 R48 R3 R39 R3
Actions GOTO
![Page 9: LALR Parser Presentation ppt](https://reader035.vdocumento.com/reader035/viewer/2022062820/58a6d38a1a28abcc458b6bef/html5/thumbnails/9.jpg)
9 LALR ParserActions GOTO
Merge the Cores:
What is core ?A core is a set of LR (0) (SLR) items for the grammar.
o 3 & 6o 4 & 7o 8 & 9
![Page 10: LALR Parser Presentation ppt](https://reader035.vdocumento.com/reader035/viewer/2022062820/58a6d38a1a28abcc458b6bef/html5/thumbnails/10.jpg)
10 LALR Parsing Table
ActionsStart
c d $ S C 0 S36 S47 1 21 acc2 S36 S47 5
36 S36 S47 8947 R47 R47 R475 R2
89 R36 R36 R36
GOTOAction
![Page 11: LALR Parser Presentation ppt](https://reader035.vdocumento.com/reader035/viewer/2022062820/58a6d38a1a28abcc458b6bef/html5/thumbnails/11.jpg)
Conflicts In LALR Parsero LALR Parser cannot introduce shift/reduce conflicts.o Such conflicts arises when the look ahead is same as the
token on which we can shift.o They depend on the core of the item but we merge only
those rows which have common cores.o The only way by which this conflict can arise in LALR is when
the conflict is already their in the LR(1).
11
![Page 12: LALR Parser Presentation ppt](https://reader035.vdocumento.com/reader035/viewer/2022062820/58a6d38a1a28abcc458b6bef/html5/thumbnails/12.jpg)
11 Refrence
ActionsGOTOActionUsed to generate First of Given Grammer
http://hackingoff.com/compilers/predict-first-follow-set
IITKGP notes for making presentationhttp://www.facweb.iitkgp.ernet.in/~niloy/COURSE/
Compilers Principles Techniques and Tools (2nd Edition) - BOOK
![Page 13: LALR Parser Presentation ppt](https://reader035.vdocumento.com/reader035/viewer/2022062820/58a6d38a1a28abcc458b6bef/html5/thumbnails/13.jpg)
Thank YouFor Listening
12