Understanding Shift-Reduce Parsing Example in Mr. Lupoli's F2012

Slide Note
Embed
Share

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.


Uploaded on Aug 26, 2024 | 0 Views


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


  1. Shift-Reduce Parsing Example 1 Mr. Lupoli F2012

  2. 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

  3. Whats Given Original Production E int E E + (E) E int E E + (E) Syntax to be checked int + (int) + (int)

  4. | int + (int) + (int) E int E E + (E)

  5. int | + ( int ) + ( int ) we have a match!! Reduce E | + ( int ) + ( int ) E int E E + (E)

  6. E + | ( int ) + ( int ) no match shift E int E E + (E)

  7. E + ( | int ) + ( int ) no match shift E int E E + (E)

  8. E + ( int | ) + ( int ) match !!! Reduce E + ( E | ) + ( int ) E int E E + (E)

  9. E + ( E ) | + ( int ) match!! Reduce E | + ( int ) E int E E + (E)

  10. E + | ( int ) no match, shift E int E E + (E)

  11. E + ( | int ) no match, shift E int E E + (E)

  12. E + ( int | ) found a match!! Reduce!! E + ( E | ) E int E E + (E)

  13. E + ( E ) | found a match!! Reduce!! E E int E E + (E)

  14. E starting production!!! ACCEPT!!!E int E E + (E)

  15. 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)

  16. Sources CS 671 University of Virginia

Related


More Related Content