DOC PREVIEW
U of I CS 421 - Programming Languages and Compilers

This preview shows page 1-2-3 out of 10 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

U of I CS 421 - Programming Languages and Compilers

Documents in this Course
Lecture 2

Lecture 2

12 pages

Exams

Exams

20 pages

Lecture

Lecture

32 pages

Lecture

Lecture

21 pages

Lecture

Lecture

15 pages

Lecture

Lecture

4 pages

Lecture

Lecture

68 pages

Lecture

Lecture

68 pages

Lecture

Lecture

84 pages

s

s

32 pages

Parsing

Parsing

52 pages

Lecture 2

Lecture 2

45 pages

Midterm

Midterm

13 pages

LECTURE

LECTURE

10 pages

Lecture

Lecture

5 pages

Lecture

Lecture

39 pages

Load more
Download Programming Languages and Compilers
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Programming Languages and Compilers and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Programming Languages and Compilers 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?