Parsing VI The LR(1) Table ConstructionBuilding the Canonical Collection Start from s0 = closure( [S’→S,EOF ] ) Repeatedly construct new states, until all are found The algorithm s0 ← closure ( [S’→S,EOF] ) S ← { s0 } k ← 1 while ( S is still changing ) ∀ sj ∈ S and ∀ x ∈ ( T ∪ NT ) sk ← goto(sj,x) record sj → sk on x if sk ∉ S then S ← S ∪ sk k ← k + 1 Fixed-point computation Loop adds to S S ⊆ 2(LR ITEMS), so S is finiteExample from SheepNoise Starts with S0 s0 ← closure( { [Goal → •Expr , EOF] } ) s0 ← closure ( [S’→S,EOF] ) S ← { s0 } k ← 1 while ( S is still changing ) ∀ sj ∈ S and ∀ x ∈ ( T ∪ NT ) sk ← goto(sj,x) record sj → sk on x if sk ∉ S then S ← S ∪ sk k ← k + 1Example from SheepNoise Starts with S0 s0 ← closure( { [Goal → •Expr , EOF] } ) { [Goal→ • SheepNoise, EOF], [SheepNoise→ • baa SheepNoise, EOF], ! [SheepNoise→• baa, EOF]}Example from SheepNoise Starts with S0 S0 : { [Goal→ • SheepNoise, EOF], [SheepNoise→ • baa SheepNoise, EOF], ! [SheepNoise→• baa, EOF]} Iteration 1 computes S1 = Goto(S0 , SheepNoise)Example from SheepNoise Starts with S0 S0 : { [Goal→ • SheepNoise, EOF], [SheepNoise→ • baa SheepNoise, EOF], ! [SheepNoise→• baa, EOF]} Iteration 1 computes S1 = Goto(S0 , SheepNoise) = { [Goal→ SheepNoise •, EOF]} S2 = Goto(S0 , baa)Example from SheepNoise Starts with S0 S0 : { [Goal→ • SheepNoise, EOF], [SheepNoise→ • baa SheepNoise, EOF], ! [SheepNoise→• baa, EOF]} Iteration 1 computes S1 = Goto(S0 , SheepNoise) = { [Goal→ SheepNoise •, EOF]} S2 = Goto(S0 , baa) = { [SheepNoise→ baa •, EOF], [SheepNoise→ baa • SheepNoise, EOF], [SheepNoise→ • baa, EOF], [SheepNoise→ • baa SheepNoise, EOF]}Example from SheepNoise Starts with S0 S0 : { [Goal→ • SheepNoise, EOF], [SheepNoise→ • baa SheepNoise, EOF], ! [SheepNoise→• baa, EOF]} Iteration 1 computes S1 = Goto(S0 , SheepNoise) = { [Goal→ SheepNoise •, EOF]} S2 = Goto(S0 , baa) = { [SheepNoise→ baa •, EOF], [SheepNoise→ baa • SheepNoise, EOF], [SheepNoise→ • baa, EOF], [SheepNoise→ • baa SheepNoise, EOF]} Iteration 2 computes Goto(S2,baa) creates S2 S3 = Goto(S2,SheepNoise) = {[SheepNoise→ baa SheepNoise•, EOF]}Example from SheepNoise Starts with S0 S0 : { [Goal→ • SheepNoise, EOF], [SheepNoise→ • baa SheepNoise, EOF], ! [SheepNoise→• baa, EOF]} Iteration 1 computes S1 = Goto(S0 , SheepNoise) = { [Goal→ SheepNoise •, EOF]} S2 = Goto(S0 , baa) = { [SheepNoise→ baa •, EOF], [SheepNoise→ baa • SheepNoise, EOF], [SheepNoise→ • baa, EOF], [SheepNoise→ • baa SheepNoise, EOF]} Iteration 2 computes Goto(S2,baa) creates S2 S3 = Goto(S2,SheepNoise) = {[SheepNoise→ baa SheepNoise•, EOF]} Nothing more to compute, since • is at the end of the item in S3 .Example Simplified, right recursive expression grammar Goal → Expr Expr → Term – Expr Expr → Term Term → Factor * Term Term → Factor Factor → identExample (building the collection) Initialization Step s0 ← closure( { [Goal → •Expr , EOF] } ) Goal → Expr Expr → Term – Expr Expr → Term Term → Factor * Term Term → Factor Factor → identExample (building the collection) Initialization Step s0 ← closure( { [Goal → •Expr , EOF] } ) { [Goal → • Expr , EOF], [Expr → • Term – Expr , EOF], [Expr → • Term , EOF], [Term → • Factor * Term , EOF], [Term → • Factor * Term , –], [Term → • Factor , EOF], [Term → • Factor , –], [Factor → • ident , EOF], [Factor → • ident , –], [Factor → • ident , *] } S ← {s0 }Example (building the collection) Initialization Step s0 ← closure( { [Goal → •Expr , EOF] } ) { [Goal → • Expr , EOF], [Expr → • Term – Expr , EOF], [Expr → • Term , EOF], [Term → • Factor * Term , EOF], [Term → • Factor * Term , –], [Term → • Factor , EOF], [Term → • Factor , –], [Factor → • ident , EOF], [Factor → • ident , –], [Factor → • ident , *] } S ← {s0 } s0 ← closure ( [S’→S,EOF] ) S ← { s0 } k ← 1 while ( S is still changing ) ∀ sj ∈ S and ∀ x ∈ ( T ∪ NT ) sk ← goto(sj,x) record sj → sk on x if sk ∉ S then S ← S ∪ sk k ← k + 1Example (building the collection) Iteration 1 s1 ← goto(s0 , Expr) s2 ← goto(s0 , Term) s3 ← goto(s0 , Factor) s4 ← goto(s0 , ident ) Iteration 2 s5 ← goto(s2 , – ) s6 ← goto(s3 , * ) Iteration 3 s7 ← goto(s5 , Expr ) s8 ← goto(s6 , Term ) s0 ← closure ( [S’→S,EOF] ) S ← { s0 } k ← 1 while ( S is still changing ) ∀ sj ∈ S and ∀ x ∈ ( T ∪ NT ) sk ← goto(sj,x) record sj → sk on x if sk ∉ S then S ← S ∪ sk k ← k + 1 Let’s just create sets s1 through s4Example (Summary) S0 : { [Goal → • Expr , EOF], [Expr → • Term – Expr , EOF], [Expr → • Term , EOF], [Term → • Factor * Term , EOF], [Term → • Factor * Term , –], [Term → • Factor , EOF], [Term → • Factor , –], [Factor → • ident , EOF], [Factor → • ident , –], [Factor→ • ident, *] } S1 : { [Goal → Expr •, EOF] } S2 : { [Expr → Term • – Expr , EOF], [Expr → Term •, EOF] } S3 : { [Term → Factor • * Term , EOF],[Term → Factor • * Term , –], [Term → Factor •, EOF], [Term → Factor •, –] } S4 : { [Factor → ident •, EOF],[Factor → ident •, –], [Factor → ident •, *] } S5 : { [Expr → Term – • Expr , EOF], [Expr → • Term – Expr , EOF], [Expr → • Term , EOF], [Term → • Factor * Term , –], [Term → • Factor , –], [Term → • Factor * Term , EOF], [Term → • Factor , EOF], [Factor → • ident , *], [Factor → • ident , –], [Factor → • ident , EOF] }Example (Summary) S6 : { [Term →
View Full Document
Unlocking...