Report

Compilers ABHISHEK REDDY PAM DATE : 07/10/2013 (11CS30002) Viable Prefix The set of prefixes of right sentential forms that can appear on the stack of a shift-reduce parser are called viable prefixes. Right-Sentential Form : A sentential form that can be derived by a rightmost derivation The prefix of the sentential form may not be the content of the stack. Example Consider: S aABe A Abc | b Bd Rightmost Derivation of the string abbcde: S aABe aAde aAbcde abbcde The (unique) handle is underlined for each step. Continuation… A viable prefix is : (1) a string that equals a prefix of a rightsentential form up to (and including) its unique handle. (2) any prefix of a string that satisfies (1) For given example : Viable prefixes: a, aA, aAd, aAbc, ab, aAb,… Not viable prefixes: aAde, Abc, aAA,… Shift/Reduce Parser Stack Input Remark $ abbcde$ SHIFT $a bbcde$ SHIFT $ab bcde$ REDUCE $aA bcde$ SHIFT $aAb cde$ SHIFT $aAbc de$ REDUCE $aA de$ SHIFT $aAd e$ REDUCE $aAB e$ SHIFT $aABe $ REDUCE $S $ ACCEPT All strings in the stack are viable prefixes When to shift/reduce ? •Sometimes on top of the stack something appears to be a handle (i.e., matches the RHS of a production). •But: maybe we have not shifted enough elements to identify the handle. •Observe the correct sequence of Shift and Reduce steps preserves the property that the stack IS a viable prefix. Example : $aAb cde$ Shift or Reduce? •If we shift we obtain aAbc in the stack (aA is the valid item for the viable prefix aAbc). Recall that Abc is a handle. •Instead if we reduce we obtain aAA in the stack. (this is NOT a viable prefix!!!) Valid Items DEFINITION: A α.β, {a} is a valid LR(1)-item for a viable prefix γα if there exists a right-most derivation. S γAy γαβy Such that i. a is the first symbol of y (or) ii. y = ε and a = $ THE END A DFA accepting viable prefixes. Its states are sets of LR(1)-items (that are valid for the corresponding viable prefixes) Canonical LR Parser(LR(1) Parser) , States and encoding of valid items and viable prefixes are discussed in the next lecture.