Resolving Conflicts in LALR(1)Finding LookaheadsExample of LALR(1) LookaheadsLALR(1) and SLR(1)Resolving Conflicts in LALR(1)• In certain LR(0) states, multiple reductions may be possible.• Also, reduction and shift might both be possible:– Is it OK to take the shift when possible, or is there a problemwith the grammar?• Resolve by computinglookahead setsfor each item in state thatrepre sents possible reduction (dot at end).• Lookahead set consis ts of terminal symbols that could legally comenext after taking the reduction.• For item ‘Q → a•’ in state S, is set of all terminal s that can followQin an i nput that puts machine in stateS.• More precise than FOLLOW set from LL(1) parsing .Last modified: Fri Feb 18 10:58:58 2005 CS164: Lecture #14 1Finding Lookaheads• Idea: try possible reductions and see wh at shifts are the n possible.• Suppose that in state S1, two p roductions Q → a and R → a areboth possible.• Look at what will happen if you reduce with Q → a:– Tra ce backwards from S1on the a arc, and then forward on Q.– Goes to new state S2.• What s hifts a re possible from S2? Add these to thelookahead setfor Q → a in S1.• Also consider further reductions from S2.• Do for all states and reduction sequences.• If lookaheads for Q → a and R → a are di stinct, we can decidewhich production to take.Last modified: Fri Feb 18 10:58:58 2005 CS164: Lecture #14 2Example of LALR(1) LookaheadsConsider this (silly) grammar and its LR(0 ) machi ne (terminals are a, x,y, a):P → S aS → Q xS → R yQ → aR → aP →•S aLast modified: Fri Feb 18 10:58:58 2005 CS164: Lecture #14 3Example of LALR(1) LookaheadsConsider this (silly) grammar and its LR(0 ) machi ne (terminals are a, x,y, a):P → S aS → Q xS → R yQ → aR → aP →•S aS →•Q xS →•R yLast modified: Fri Feb 18 10:58:58 2005 CS164: Lecture #14 3Example of LALR(1) LookaheadsConsider this (silly) grammar and its LR(0 ) machi ne (terminals are a, x,y, a):P → S aS → Q xS → R yQ → aR → aP →•S aS →•Q xS →•R yQ →•aR →•aLast modified: Fri Feb 18 10:58:58 2005 CS164: Lecture #14 3Example of LALR(1) LookaheadsConsider this (silly) grammar and its LR(0 ) machi ne (terminals are a, x,y, a):P → S aS → Q xS → R yQ → aR → aP →•S aS →•Q xS →•R yQ →•aR →•aP → S•aSP → S a•aLast modified: Fri Feb 18 10:58:58 2005 CS164: Lecture #14 3Example of LALR(1) LookaheadsConsider this (silly) grammar and its LR(0 ) machi ne (terminals are a, x,y, a):P → S aS → Q xS → R yQ → aR → aP →•S aS →•Q xS →•R yQ →•aR →•aP → S•aSP → S a•aS → Q•xQS → Q x•xS → R•yRS → R y•yLast modified: Fri Feb 18 10:58:58 2005 CS164: Lecture #14 3Example of LALR(1) LookaheadsConsider this (silly) grammar and its LR(0 ) machi ne (terminals are a, x,y, a):P → S aS → Q xS → R yQ → aR → aP →•S aS →•Q xS →•R yQ →•aR →•aP → S•aSP → S a•aS → Q•xQS → Q x•xS → R•yRS → R y•yQ → a•R → a•aLast modified: Fri Feb 18 10:58:58 2005 CS164: Lecture #14 3Example of LALR(1) LookaheadsConsider this (silly) grammar and its LR(0 ) machi ne (terminals are a, x,y, a):P → S aS → Q xS → R yQ → aR → aP →•S aS →•Q xS →•R yQ →•aR →•aP → S•aSP → S a•aS → Q•xQS → Q x•xS → R•yRS → R y•yQ → a•R → a•aLast modified: Fri Feb 18 10:58:58 2005 CS164: Lecture #14 3Example of LALR(1) LookaheadsConsider this (silly) grammar and its LR(0 ) machi ne (terminals are a, x,y, a):P → S aS → Q xS → R yQ → aR → aP →•S aS →•Q xS →•R yQ →•aR →•aP → S•aSP → S a•aS → Q•xQS → Q x•xS → R•yRS → R y•yQ → a•, xR → a•aLast modified: Fri Feb 18 10:58:58 2005 CS164: Lecture #14 3Example of LALR(1) LookaheadsConsider this (silly) grammar and its LR(0 ) machi ne (terminals are a, x,y, a):P → S aS → Q xS → R yQ → aR → aP →•S aS →•Q xS →•R yQ →•aR →•aP → S•aSP → S a•aS → Q•xQS → Q x•xS → R•yRS → R y•yQ → a•, xR → a•aLast modified: Fri Feb 18 10:58:58 2005 CS164: Lecture #14 3Example of LALR(1) LookaheadsConsider this (silly) grammar and its LR(0 ) machi ne (terminals are a, x,y, a):P → S aS → Q xS → R yQ → aR → aP →•S aS →•Q xS →•R yQ →•aR →•aP → S•aSP → S a•aS → Q•xQS → Q x•xS → R•yRS → R y•yQ → a•, xR → a•, yaLast modified: Fri Feb 18 10:58:58 2005 CS164: Lecture #14 3LALR(1) and SLR (1)• LALR(1) lookahead sets resemble FOLLOW sets.• In pr eceding grammar, in fact, could us e FOLLOW sets to choosereduction—grammar is SLR(1).• Not always true. This grammar:S → A a | b A c | dc | bdaA → dhas no reduce/reduce conflict, but in the stateb d . cMust you shift or can you also reduce to A (meaning there is shi ft/ reduceconflict in the grammar)?• SLR(1) construction won’t tell you. LALR(1) will.Last modified: Fri Feb 18 10:58:58 2005 CS164: Lecture #14
View Full Document
Unlocking...