Shift-Reduce Parsing Example in Mr. Lupoli's F2012
Shift-Reduce Parsing
Example 1
Mr. Lupoli
F2012
Mechanics
•
Goal
–
trace that the given input can be reduced BACK to the
original start symbol
•
Shift
–
marker that moves along the input
–
from left to right
–
what is on left needs to be reduced
–
match with production table
•
Reduce
–
apply the inverse production
What’s Given
•
Original Production
–
E → int
–
E
E + (E)
•
Syntax to be checked
–
int + (int) + (int)
E → int
E
E + (E)
•
| int + (int) + (int)
E → int
E
E + (E)
•
int | + ( int ) + ( int )
–
we have a match!! Reduce
•
E | + ( int ) + ( int )
E → int
E
E + (E)
•
E + | ( int ) + ( int )
–
no match shift
E → int
E
E + (E)
•
E + ( | int ) + ( int )
–
no match shift
E → int
E
E + (E)
•
E + ( int | ) + ( int )
–
match !!! Reduce
•
E + ( E | ) + ( int )
E → int
E
E + (E)
•
E + ( E ) | + ( int )
–
match!! Reduce
•
E | + ( int )
E → int
E
E + (E)
•
E + | ( int )
–
no match, shift
E → int
E
E + (E)
•
E + ( | int )
–
no match, shift
E → int
E
E + (E)
•
E + ( int | )
–
found a match!! Reduce!!
•
E + ( E | )
E → int
E
E + (E)
•
E + ( E ) |
–
found a match!! Reduce!!
•
E
E → int
E
E + (E)
•
E
–
starting production!!! ACCEPT!!!
E → int
E
E + (E)
In total
•
int
+ (int) + (int)$
shift
•
int
+ (int) + (int)$
red. E
int
•
E
+ (int
) + (int)$
shift 3 times
•
E + (
int
) + (int)$
red. E
int
•
E + (E
)
+ (int)$
shift
•
E + (E)
+ (int)$
red. E
E + (E)
•
E
+ (int
)$
shift 3 times
•
E + (
int
)$
red. E
int
•
E + (E
)
$
shift
•
E + (E)
$
red. E
E + (E)
•
E
$
accept
Sources
CS 671 – University of Virginia
This example explains shift-reduce parsing by tracing the input to the original start symbol. It demonstrates how shifting and reducing operations work in parsing mechanics, using the given original production and syntax rules for matching and reduction steps.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Shift-Reduce Parsing Example 1 Mr. Lupoli F2012
Mechanics Goal trace that the given input can be reduced BACK to the original start symbol Shift marker that moves along the input from left to right what is on left needs to be reduced match with production table Reduce apply the inverse production
Whats Given Original Production E int E E + (E) E int E E + (E) Syntax to be checked int + (int) + (int)
| int + (int) + (int) E int E E + (E)
int | + ( int ) + ( int ) we have a match!! Reduce E | + ( int ) + ( int ) E int E E + (E)
E + | ( int ) + ( int ) no match shift E int E E + (E)
E + ( | int ) + ( int ) no match shift E int E E + (E)
E + ( int | ) + ( int ) match !!! Reduce E + ( E | ) + ( int ) E int E E + (E)
E + ( E ) | + ( int ) match!! Reduce E | + ( int ) E int E E + (E)
E + | ( int ) no match, shift E int E E + (E)
E + ( | int ) no match, shift E int E E + (E)
E + ( int | ) found a match!! Reduce!! E + ( E | ) E int E E + (E)
E + ( E ) | found a match!! Reduce!! E E int E E + (E)
E starting production!!! ACCEPT!!!E int E E + (E)
In total int + (int) + (int)$ shift int + (int) + (int)$ red. E E + (int) + (int)$ shift 3 times E + (int ) + (int)$ red. E E + (E ) + (int)$ shift E + (E) + (int)$ red. E E + (int)$ shift 3 times E + (int )$ red. E E + (E )$ shift E + (E) $ red. E E $ accept int int E + (E) int E + (E)
Sources CS 671 University of Virginia
