Definition of The sir()parsing algorithm(2) 2.(Continue) a reduction by the rule s→→S, is equivalent to acceptance; This will happen only if the next input token is In all other cases, remove the stringy and a corresponding states from the parsing stack Correspondingly back up in the dfa to the state from which the construction of y began This state must contain an item of the form B-a AB Push a onto the stack, and the state containing the Item B→Aβ
Definition of The SLR(1) parsing algorithm(2) 2. (Continue) A reduction by the rule S' →S, is equivalent to acceptance; – This will happen only if the next input token is $. In all other cases, Remove the stringγ and a corresponding states from the parsing stack – Correspondingly, back up in the DFA to the state from which the construction of γ began. – This state must contain an item of the form B → α·Aβ. Push A onto the stack, and the state containing the item B → αA·β
Definition of The sir(I) parsing algorithm(3) 3. If the next input token is such that neither of the above two cases applies an error is declared
Definition of The SLR(1) parsing algorithm(3) 3. If the next input token is such that neither of the above two cases applies, – an error is declared
A grammar is an Siro grammar if the application of the above siro 1) parsing rules results in no ambiguity A grammar iS SLR( 1) if and only if, for any state S, the following two conditions are satisfied For any item A→aXβ Bin s with x a terminal There is no complete item B-Y in s with X in Follow B) For any two complete items A→·andB→β·ins, FollOw(A)∩ Follow (B)is empty a violation of the first of these conditions represents a shift-reduce conflict a violation of the second of these conditions represents a reduce-reduce conflict
A grammar is an SLR(l) grammar if the application of the above SLR( 1 ) parsing rules results in no ambiguity A grammar is SLR( 1) if and only if, for any state s, the following two conditions are satisfied: – For any item A → α·Xβin s with X a terminal, There is no complete item B → γ. in s with X in Follow(B). – For any two complete items A → α·and B →β·in s, Follow(A) ∩ Follow(B) is empty. A violation of the first of these conditions represents a shift-reduce conflict A violation of the second of these conditions represents a reduce-reduce conflict
Example 5. 10 Consider the grammar: E-E E→→E+n|n This grammar is not LR(O), but it iS SIro The Follow sets for the nonterminals Follow(e)=s and Follow(e=S,+ EEE ·E E E’→E E+1 E→E·nN E E→E+ E→E+n
• Example 5. 10 Consider the grammar: – E’→E – E→E + n | n • This grammar is not LR(0), but it is SLR(l). – The Follow sets for the nonterminals: – Follow(E') ={$ } and Follow(E) = { $, +} . E’ →·E E →·E+n E →·n 0 E E’ →E· E →E·+n 1 E → n· 2 n + E → E+·n 3 E → E+n· 4 n
The slr(i) parsing table for above Grammar State Input Goto E S2 01234 S3 accep r(E→n) r(E→m) S4 r(E→E+n r(E→E+ a shift is indicated by the letter s in the entry, and a reduction by the letter r In state I on input + a shift is indicated, together with a transition to state 3 In state 2 on input + a reduction by productione-n is indicated The action"accept in state l on input s instead ofr(E-E)
The SLR(1) parsing table for above Grammar • A shift is indicated by the letter s in the entry, and a reduction by the letter r – In state 1 on input +, a shift is indicated, together with a transition to state 3 – In state 2 on input +, a reduction by production E → n is indicated – The action “accept’’ in state 1 on input $ instead of r (E’ →E ) State Input Goto 0 1 2 3 4 n + $ E S2 S4 S3 r(E → n) r(E → E+n) accept r(E → n) r(E → E+n) 1