Programming Languages andCompilers (CS 421)Elsa L Gunter2112 SC, UIUChttp://www.cs.uiuc.edu/class/fa05/cs421/current/Based in part on slides by Mattox Beckman, as updatedby Vikram Adve and Gul AghaElsa L. GunterLR 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 bereplaced so is right-most• Working backwards, replace mixed strings bynon-terminals• Always proceed so that there are no non-terminals to the right of the string to be replacedElsa L. GunterExample: <Sum> = 0 | 1 |(<Sum>) | <Sum> + <Sum><Sum> => = ( 0 + 1 ) + 0 shiftElsa L. GunterExample: <Sum> = 0 | 1 |(<Sum>) | <Sum> + <Sum><Sum> => = ( 0 + 1 ) + 0 shift = ( 0 + 1 ) + 0 shiftElsa L. GunterExample: <Sum> = 0 | 1 |(<Sum>) | <Sum> + <Sum><Sum> => => ( 0 + 1 ) + 0 reduce = ( 0 + 1 ) + 0 shift = ( 0 + 1 ) + 0 shiftElsa L. GunterExample: <Sum> = 0 | 1 |(<Sum>) | <Sum> + <Sum><Sum> => = ( <Sum> + 1 ) + 0 shift => ( 0 + 1 ) + 0 reduce = ( 0 + 1 ) + 0 shift = ( 0 + 1 ) + 0 shiftElsa L. GunterExample: <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. GunterExample: <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. GunterExample: <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. GunterExample: <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. GunterExample: <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. GunterExample: <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. GunterExample: <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. GunterExample: <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. GunterExample: <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. GunterExample: <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 = (
View Full Document