Parsing VI The Last Parsing LectureExample Simple left recursive SheepNoise grammar Note: Example in book is right recursive and generates different Action and Goto tables Goal → SheepNoise SheepNoise → SheepNoise baa SheepNoise→ baaExample From SheepNoise Initial step builds the item [Goal→•SheepNoise,EOF] and takes its closure( )󳆒 Closure( [Goal→•SheepNoise,EOF] )󳆒 So, S0 is { [Goal→ • SheepNoise,EOF], [SheepNoise→ • SheepNoise baa,EOF], [SheepNoise→• baa,EOF], [SheepNoise→ • SheepNoise baa,baa], [SheepNoise→ • baa,baa] }Example from SheepNoise S0 is { [Goal→ • SheepNoise,EOF], [SheepNoise→ • SheepNoise baa,EOF], [SheepNoise→ • baa,EOF], [SheepNoise→ • SheepNoise baa,baa], [SheepNoise→ • baa,baa] } Goto( S0 , baa )󳆒 • Loop produces • Closure adds nothing since • is at end of rhs in each item In the construction, this produces s2 { [SheepNoise→baa •, {EOF,baa}]} New, but obvious, notation for two distinct items [SheepNoise→baa •, EOF] & [SheepNoise→baa •, baa]Example from SheepNoise Starts with S0 S0 : { [Goal→ • SheepNoise, EOF], [SheepNoise→ • SheepNoise baa, EOF], [SheepNoise→• baa, EOF], [SheepNoise→ • SheepNoise baa, baa], [SheepNoise→ • baa, baa] }Example from SheepNoise Starts with S0 S0 : { [Goal→ • SheepNoise, EOF], [SheepNoise→ • SheepNoise baa, EOF], [SheepNoise→• baa, EOF], [SheepNoise→ • SheepNoise baa, baa], [SheepNoise→ • baa, baa] } Iteration 1 computes S1 = Goto(S0 , SheepNoise) = { [Goal→ SheepNoise •, EOF], [SheepNoise→ SheepNoise • baa, EOF], [SheepNoise→ SheepNoise • baa, baa] } S2 = Goto(S0 , baa) = { [SheepNoise→ baa •, EOF], [SheepNoise→ baa •, baa] }Example from SheepNoise Starts with S0 S0 : { [Goal→ • SheepNoise, EOF], [SheepNoise→ • SheepNoise baa, EOF], [SheepNoise→• baa, EOF], [SheepNoise→ • SheepNoise baa, baa], [SheepNoise→ • baa, baa] } Iteration 1 computes S1 = Goto(S0 , SheepNoise) = { [Goal→ SheepNoise •, EOF], [SheepNoise→ SheepNoise • baa, EOF], [SheepNoise→ SheepNoise • baa, baa] } S2 = Goto(S0 , baa) = { [SheepNoise→ baa •, EOF], [SheepNoise→ baa •, baa] } Iteration 2 computes S3 = Goto(S1 , baa) = { [SheepNoise→ SheepNoise baa •, EOF], [SheepNoise→ SheepNoise baa •, baa] }Example from SheepNoise Starts with S0 S0 : { [Goal→ • SheepNoise, EOF], [SheepNoise→ • SheepNoise baa, EOF], [SheepNoise→• baa, EOF], [SheepNoise→ • SheepNoise baa, baa], [SheepNoise→ • baa, baa] } Iteration 1 computes S1 = Goto(S0 , SheepNoise) = { [Goal→ SheepNoise •, EOF], [SheepNoise→ SheepNoise • baa, EOF], [SheepNoise→ SheepNoise • baa, baa] } S2 = Goto(S0 , baa) = { [SheepNoise→ baa •, EOF], [SheepNoise→ baa •, baa] } Iteration 2 computes S3 = Goto(S1 , baa) = { [SheepNoise→ SheepNoise baa •, EOF], [SheepNoise→ SheepNoise baa •, baa] } Nothing more to compute, since • is at the end of every item in S3 .Example from SheepNoise S0 : { [Goal→ • SheepNoise, EOF], [SheepNoise→ • SheepNoise baa, EOF], [SheepNoise→• baa, EOF], [SheepNoise→ • SheepNoise baa, baa], [SheepNoise→ • baa, baa] } S1 = Goto(S0 , SheepNoise) = { [Goal→ SheepNoise •, EOF], [SheepNoise→ SheepNoise • baa, EOF], [SheepNoise→ SheepNoise • baa, baa] } S2 = Goto(S0 , baa) = { [SheepNoise→ baa •, EOF], [SheepNoise→ baa •, baa] } S3 = Goto(S1 , baa) = { [SheepNoise→ SheepNoise baa •, EOF], [SheepNoise→ SheepNoise baa •, baa] } S0 S3 S2 S1 baa baa SN Control DFA for SNFilling in the ACTION and GOTO Tables ∀ set sx ∈ S ∀ item i ∈ sx if i is [A→β •ad,b] and goto(sx,a) = sk , a ∈ T then ACTION[x,a] ← “shift k” else if i is [S’→S •,EOF] then ACTION[x ,a] ← “accept” else if i is [A→β •,a] then ACTION[x,a] ← “reduce A→β” ∀ n ∈ NT if goto(sx ,n) = sk then GOTO[x,n] ← k S0 S3 S2 S1 baa baa SN Control DFA for SN S0 : { [Goal→ • SheepNoise, EOF], [SheepNoise→ • SheepNoise baa, EOF], [SheepNoise→• baa, EOF], [SheepNoise→ • SheepNoise baa, baa], [SheepNoise→ • baa, baa] } S1 = Goto(S0 , SheepNoise) = { [Goal→ SheepNoise •, EOF], [SheepNoise→ SheepNoise • baa, EOF], [SheepNoise→ SheepNoise • baa, baa] } S2 = Goto(S0 , baa) = { [SheepNoise→ baa •, EOF], [SheepNoise→ baa •, baa] }Filling in the ACTION and GOTO Tables ∀ set sx ∈ S ∀ item i ∈ sx if i is [A→β •ad,b] and goto(sx,a) = sk , a ∈ T then ACTION[x,a] ← “shift k” else if i is [S’→S •,EOF] then ACTION[x ,a] ← “accept” else if i is [A→β •,a] then ACTION[x,a] ← “reduce A→β” ∀ n ∈ NT if goto(sx ,n) = sk then GOTO[x,n] ← k S0 S3 S2 S1 baa baa SN Control DFA for SN S1 = Goto(S0 , SheepNoise) = { [Goal→ SheepNoise •, EOF], [SheepNoise→ SheepNoise • baa, EOF], [SheepNoise→ SheepNoise • baa, baa] } S2 = Goto(S0 , baa) = { [SheepNoise→ baa •, EOF], [SheepNoise→ baa •, baa] } S3 = Goto(S1 , baa) = { [SheepNoise→ SheepNoise baa •, EOF], [SheepNoise→ SheepNoise baa •, baa] }Filling in the ACTION and GOTO Tables ∀ set sx ∈ S ∀ item i ∈ sx if i is [A→β •ad,b] and goto(sx,a) = sk , a ∈ T then ACTION[x,a] ← “shift k” else if i is [S’→S •,EOF] then ACTION[x ,a] ← “accept” else if i is [A→β •,a] then ACTION[x,a] ← “reduce A→β” ∀ n ∈ NT if goto(sx ,n) = sk then GOTO[x,n] ← k S0 S3 S2 S1 baa baa SN Control DFA for SNShrinking the Tables Three options: • Combine terminals such as number & identifier, + & -, * & / → Directly removes a column, may remove a row → For expression grammar, 198 (vs. 384) table entries • Combine rows or columns (table compression) → Implement identical rows once & remap states → Requires extra indirection on each lookup → Use separate mapping for ACTION & for GOTO • Use another construction algorithm → Both LALR(1) and SLR(1) produce smaller tables → Implementations are readily availableWhat can go wrong with LR table