| / F T' | F num | id Consider the grammar E T + E E T T int T int * T T ( E ) Answer: Hard to predict because for T, two productions with int For E, it is not clear how to predict which rule to use What you JUST did is called “pairwise disjointness test” What if the Grammar fails disjointness test? Must left-factor to create a predictive parsing grammar Left-factoring involves rewriting rules so that if a non-terminal has > 1 rule, each begins with a terminal add new non-terminals (new letters) to factor out common prefixes of Left Factoring Example Left factor the grammar below: S ==> 0S1 | 01 Answer: S ==> 0S’ S’ ==> S1 | 1 S ==> abx | aby | acx | acy Answer: S ==> aS’ S’ ==> bS’’ | cS’’ S’’ ==> x | y A bcW | bcE W x E q Answer: A->bcX X->W | E W->x E->q A-> bcX X-> W
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
The action is read from a table containing all syntactically valid combinations of stack and lookahead symbols. I created a table for you to better explain some of the actions Grammar Assign ← id = Sums Sums ← Sums + Products Sums ← Products Products ← Products * Value Products ← Value Value ← int Value ← id BUT, the parser wants the BIGGEST match possible for RHS in Stack so it might wait until something doesn’t match this works only if 2 or more productions START with the same symbol like <Value> and <Assign>, both start with “id” in many references, this is not mentioned A LR(1) Shift Reduce Example again must be given a Grammar and Input String use LR Shift Reduce Parser Table please use overall exercise table given broken up into, step, parse stack, look ahead, etc… Example Grammar and Input for LR(1) Shift Reduce Parser Grammar Input String Assign ← id = Sums Sums ← Sums + Products Sums ← Products Products ← Products * Value Products ← Value id = id + id * int $
Sums ← Sums + Products Sums ← Products Products ← Products * Value Products ← Value Value ← int Value ← id Shift(S) lookahead has a partial Grammar match, wait for more combo of lookahead and rightmost in parse stack has a partial Grammar match, wait for more Parse(P) no for lookahead, reduce rightmost symbol in stack (find largest match) Step Parse Stack Look Ahead Unscanned Parser Action 15 id = Sums $ P Reduce “id = Sums” to “Assign” Grammar String Assign ← id = Sums Sums ← Sums + Products Sums ← Products Products ← Products * Value Products ← Value ← int Value ← id id = id + id * int $ lookahead has a partial Grammar match, wait for more combo of lookahead and rightmost in parse stack has a partial Grammar match, wait for more Parse(P) no match for lookahead, reduce rightmost symbol in stack (find largest match) Step Parse Stack Look Unscanned Parser Action 16 Assign $ ACCEPT Grammar Input String Assign ← id = Sums Sums ← Sums + Products Sums ← Products Products ← Products * Value Products ← Value id = id + id * int $