Programming Languages and Compilers (CS 421)LR ParsingExample: <Sum> = 0 | 1 | (<Sum>) | <Sum> + <Sum>Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16ExampleSlide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31LR Parsing TablesAction and Goto TablesLR(i) Parsing AlgorithmSlide 35Slide 36Slide 37Slide 38Adding Synthesized AttributesShift-Reduce ConflictsSlide 41Example - contReduce - Reduce ConflictsSlide 44Using OcamlyaccParser CodeOcamlyacc InputOcamlyacc <header>Ocamlyacc <declarations>Slide 50Ocamlyacc <rules>Example - Base typesExample - Lexer (exprlex.mll)Example - Parser (exprparse.mly)Slide 55Slide 56Slide 57Example - Using ParserSlide 59Programming Languages and Compilers (CS 421)Elsa L Gunter2112 SC, UIUChttp://www.cs.uiuc.edu/class/sp07/cs421/Based in part on slides by Mattox Beckman, as updated by Vikram Adve and Gul AghaElsa L. Gunter LR Parsing•Read tokens left to right (L)•Create a rightmost derivation (R)•How is this possible?•Start at the bottom (left) and work your way up•Last step has only one non-terminal to be replaced so is right-most•Working backwards, replace mixed strings by non-terminals•Always proceed so that there are no non-terminals to the right of the string to be replacedElsa L. Gunter Example: <Sum> = 0 | 1 | (<Sum>) | <Sum> + <Sum><Sum> => = ( 0 + 1 ) + 0 shiftElsa L. Gunter Example: <Sum> = 0 | 1 | (<Sum>) | <Sum> + <Sum><Sum> => = ( 0 + 1 ) + 0 shift = ( 0 + 1 ) + 0 shiftElsa L. Gunter Example: <Sum> = 0 | 1 | (<Sum>) | <Sum> + <Sum><Sum> => => ( 0 + 1 ) + 0 reduce = ( 0 + 1 ) + 0 shift = ( 0 + 1 ) + 0 shiftElsa L. Gunter Example: <Sum> = 0 | 1 | (<Sum>) | <Sum> + <Sum><Sum> => = ( <Sum> + 1 ) + 0 shift => ( 0 + 1 ) + 0 reduce = ( 0 + 1 ) + 0 shift = ( 0 + 1 ) + 0 shiftElsa L. Gunter Example: <Sum> = 0 | 1 | (<Sum>) | <Sum> + <Sum><Sum> => = ( <Sum> + 1 ) + 0 shift = ( <Sum> + 1 ) + 0 shift => ( 0 + 1 ) + 0 reduce = ( 0 + 1 ) + 0 shift = ( 0 + 1 ) + 0 shiftElsa L. Gunter Example: <Sum> = 0 | 1 | (<Sum>) | <Sum> + <Sum><Sum> => => ( <Sum> + 1 ) + 0 reduce = ( <Sum> + 1 ) + 0 shift = ( <Sum> + 1 ) + 0 shift => ( 0 + 1 ) + 0 reduce = ( 0 + 1 ) + 0 shift = ( 0 + 1 ) + 0 shiftElsa L. Gunter Example: <Sum> = 0 | 1 | (<Sum>) | <Sum> + <Sum><Sum> => => ( <Sum> + <Sum> ) + 0 reduce => ( <Sum> + 1 ) + 0 reduce = ( <Sum> + 1 ) + 0 shift = ( <Sum> + 1 ) + 0 shift => ( 0 + 1 ) + 0 reduce = ( 0 + 1 ) + 0 shift = ( 0 + 1 ) + 0 shiftElsa L. Gunter Example: <Sum> = 0 | 1 | (<Sum>) | <Sum> + <Sum><Sum> => = ( <Sum> ) + 0 shift => ( <Sum> + <Sum> ) + 0 reduce => ( <Sum> + 1 ) + 0 reduce = ( <Sum> + 1 ) + 0 shift = ( <Sum> + 1 ) + 0 shift => ( 0 + 1 ) + 0 reduce = ( 0 + 1 ) + 0 shift = ( 0 + 1 ) + 0 shiftElsa L. Gunter Example: <Sum> = 0 | 1 | (<Sum>) | <Sum> + <Sum><Sum> => => ( <Sum> ) + 0 reduce = ( <Sum> ) + 0 shift => ( <Sum> + <Sum> ) + 0 reduce => ( <Sum> + 1 ) + 0 reduce = ( <Sum> + 1 ) + 0 shift = ( <Sum> + 1 ) + 0 shift => ( 0 + 1 ) + 0 reduce = ( 0 + 1 ) + 0 shift = ( 0 + 1 ) + 0 shiftElsa L. Gunter Example: <Sum> = 0 | 1 | (<Sum>) | <Sum> + <Sum><Sum> => = <Sum> + 0 shift => ( <Sum> ) + 0 reduce = ( <Sum> ) + 0 shift => ( <Sum> + <Sum> ) + 0 reduce => ( <Sum> + 1 ) + 0 reduce = ( <Sum> + 1 ) + 0 shift = ( <Sum> + 1 ) + 0 shift => ( 0 + 1 ) + 0 reduce = ( 0 + 1 ) + 0 shift = ( 0 + 1 ) + 0 shiftElsa L. Gunter Example: <Sum> = 0 | 1 | (<Sum>) | <Sum> + <Sum><Sum> => = <Sum> + 0 shift = <Sum> + 0 shift => ( <Sum> ) + 0 reduce = ( <Sum> ) + 0 shift => ( <Sum> + <Sum> ) + 0 reduce => ( <Sum> + 1 ) + 0 reduce = ( <Sum> + 1 ) + 0 shift = ( <Sum> + 1 ) + 0 shift => ( 0 + 1 ) + 0 reduce = ( 0 + 1 ) + 0 shift = ( 0 + 1 ) + 0 shiftElsa L. Gunter Example: <Sum> = 0 | 1 | (<Sum>) | <Sum> + <Sum><Sum> => => <Sum> + 0 reduce = <Sum> + 0 shift = <Sum> + 0 shift => ( <Sum> ) + 0 reduce = ( <Sum> ) + 0 shift => ( <Sum> + <Sum> ) + 0 reduce => ( <Sum> + 1 ) + 0 reduce = ( <Sum> + 1 ) + 0 shift = ( <Sum> + 1 ) + 0 shift => ( 0 + 1 ) + 0 reduce = ( 0 + 1 ) + 0 shift = ( 0 + 1 ) + 0 shiftElsa L. Gunter Example: <Sum> = 0 | 1 | (<Sum>) | <Sum> + <Sum><Sum> => <Sum> + <Sum > reduce => <Sum> + 0 reduce = <Sum> + 0 shift = <Sum> + 0 shift => ( <Sum> ) + 0 reduce = ( <Sum> ) + 0 shift => ( <Sum> + <Sum> ) + 0 reduce => ( <Sum> + 1 ) + 0 reduce = ( <Sum> + 1 ) + 0 shift = ( <Sum> + 1 ) + 0 shift => ( 0 + 1 ) + 0 reduce = ( 0 + 1 ) + 0 shift = ( 0 + 1 ) + 0 shiftElsa L. Gunter Example: <Sum> …
View Full Document
Unlocking...