Basics of Shift Reduce Parsing (LR(1)) used for efficiency no backtracking or backup (recursion) this obviously saves time/memory/etc… Input String id = id + id * int $ input stream (string) LR(1) 1 lookahead (now called LA) in the stream – Split input string into two substrings Right substring (a string of terminals) is as yet unexamined by parser Left substring has terminals and non-terminals The dividing point is marked by a The is not part of the string Grammar Assign = Sums id ← Sums Sums + Products ← Sums Products ← Products Products * Value ← Products Value ← Value int ← Value id ← Bottom-up parsing uses only two kinds of actions: Shift and Reduce Move one place to the right, add LA to stack Shift: Shifts a terminal to the left string E + ( int ) E + (int ) Apply an inverse production at the right end of the left string Reduce:
Basics of Shift Reduce Parsing (LR(1)) used for efficiency no backtracking or backup (recursion) this obviously saves time/memory/etc… Input String id = id + id * int $ input stream (string) LR(1) – 1 lookahead (now called LA) in the stream Split input string into two substrings Right substring (a string of terminals) is as yet unexamined by parser Left substring has terminals and non-terminals The dividing point is marked by a The is not part of the string Grammar Assign ← id = Sums Sums ← Sums + Products Sums ← Products Products ← Products * Value Products ← Value Value ← int Value ← id Bottom-up parsing uses only two kinds of actions: Shift and Reduce Shift: Move one place to the right, add LA to stack Shifts a terminal to the left string E + ( int ) E + (int ) Reduce: Apply an inverse production at the right end of the left string
Parsing.docx