LL Parsing

FIRST and FOLLOW

FIRST

for ∀A ∈ NON-TERMINAL do FIRST(A) = ∅ // FIRST(A)는 공집합으로 시작
  for A → α ∈ P do 
    if α = aβ where a ∈ TERMINAL then --------------------- [1]
      FIRST(A) = FIRST(A) ∪ {a} and P = P - {A - a} 
    else if α = ε then ------------------------------------ [2]
      FIRST(A) = FIRST(A) ∪ {ε} and P = P - {A - ε} 
REPEAT
  for A → Y1, Y2, ..., Yk ∈ P do -------------------------- [3]
    FIRST(A) = FIRST(A) ∪ (FIRST(Y1) ⊕ ... ⊕ FIRST(Yk))
UNITL NO CHANGE // 변화가 없을 때 까지 반복

• [1]; TERMINLA로 시작할 경우 FIRST(A)에 TERMINAL을 추가하고, Production rule set에서 a를 제거
• [2]; A가 Nullable set의 원소일 경우, FIRST(A)에 ε을 추가하고, Production rule set에서 ε을 제거
• [3]; NON-TERMINLA로 시작할 경우 FIRST(A)에 Ring sum을 사용해서 FIRST(A)에 추가

FOLLOW

for ∀A ∈ NON-TERMINAL do FOLLOW(A) = ∅ and FOLLOW(S) = {$} // FOLLOW(S)는 starting symbol이면 `

LL Parsing


FIRST and FOLLOW


FIRST


for ∀A ∈ NON-TERMINAL do FIRST(A) = ∅ // FIRST(A)는 공집합으로 시작
  for A → α ∈ P do 
    if α = aβ where a ∈ TERMINAL then --------------------- [1]
      FIRST(A) = FIRST(A) ∪ {a} and P = P - {A - a} 
    else if α = ε then ------------------------------------ [2]
      FIRST(A) = FIRST(A) ∪ {ε} and P = P - {A - ε} 
REPEAT
  for A → Y1, Y2, ..., Yk ∈ P do -------------------------- [3]
    FIRST(A) = FIRST(A) ∪ (FIRST(Y1) ⊕ ... ⊕ FIRST(Yk))
UNITL NO CHANGE // 변화가 없을 때 까지 반복


[1]; TERMINLA로 시작할 경우 FIRST(A)에 TERMINAL을 추가하고, Production rule set에서 a를 제거
[2]; A가 Nullable set의 원소일 경우, FIRST(A)에 ε을 추가하고, Production rule set에서 ε을 제거
[3]; NON-TERMINLA로 시작할 경우 FIRST(A)에 Ring sum을 사용해서 FIRST(A)에 추가

FOLLOW
로 시작

  for A → αBβ ∈ P where β ≠ ε do --------------- [1]

    FOLLOW(B) = FOLLOW(B) ∪ (FIRST(β) - {ε})

REPEAT

  for ∀A → α ∈ P do

    if α = ?B or (α = ?Bβ and β ⇒ ε) then ------ [2]

      FOLLOW(B) = FOLLOW(B) ∪ FOLLOW(A)

UNTIL NO CHANGE



[1]; β가 ε이 아니면(즉, β가 TERMINAL이거나 NON-TERMINAL) FIRST(β)에서 ε을 제외한 원소를 FOLLOW(B)에 추가
[2]; β가 ε이면(즉, β가 Nullable set이면) FOLLOW(A)를 FOLLOW(B)에 추가

Examples1




FIRST
FOLLOW




S -> ABCDE
{a,b,c}
{$}


A -> a | ε
{a, ε}
{b,c}


B -> b | ε
{b, ε}
{c}


C -> c
{c}
{d,e,$}


D -> d | ε
{d, ε}
{e,$}


E -> e | ε
{e, ε}
{$}



FIRST

FIRST(S) = {a,ε,b,c}

S ⇒ A, {a,ε} ∈ FIRST(S)
S ⇒ B, {b,ε} ∈ FIRST(S)
S ⇒ C, {c} ∈ FIRST(S)


FIRST(A) = {a, ε}

A ⇒ a, {a} ∈ FIRST(A)
A ⇒ ε, {ε} ∈ FIRST(A)


FIRST(B) = {b, ε}

B ⇒ b, {b} ∈ FIRST(B)
B ⇒ ε, {ε} ∈ FIRST(B)


FIRST(C) = {c}

C ⇒ c, {c} ∈ FIRST(C)


FIRST(D) = {d, ε}

D ⇒ d, {d} ∈ FIRST(B)
D ⇒ ε, {ε} ∈ FIRST(B)


FIRST(E) = {e, ε}

E ⇒ e, {e} ∈ FIRST(B)
E ⇒ ε, {ε} ∈ FIRST(B)



FOLLOW

FOLLOW(S) = {$}

S ⇒ ∅, {$} ∈ FOLLOW(S)


FOLLOW(A) = {b,c}

A ⇒ FOLLOW(B), FIRST(B) ∈ FOLLOW(A), {b} ∈ FOLLOW(A)
A ⇒ FOLLOW(C), FIRST(C) ∈ FOLLOW(A), {c} ∈ FOLLOW(A)


FOLLOW(B) = {c}

B ⇒ FOLLOW(C), FIRST(C) ∈ FOLLOW(B), {c} ∈ FOLLOW(B)


FOLLOW(C) = {d,e,$}

C ⇒ FOLLOW(D), FIRST(D) ∈ FOLLOW(C), {d} ∈ FOLLOW(C)
C ⇒ FOLLOW(E), FIRST(D) ∈ FOLLOW(C), {e} ∈ FOLLOW(C)
C ⇒ ε, FOLLOW(S) ∈ FOLLOW(C), {$} ∈ FOLLOW(C)


FOLLOW(D) = {e,$}

D ⇒ FOLLOW(E), FIRST(E) ∈ FOLLOW(D), {e} ∈ FOLLOW(C)
D ⇒ ε, FOLLOW(S) ∈ FOLLOW(D), {$} ∈ FOLLOW(D)


FOLLOW(E) = {$}

E ⇒ ε, FOLLOW(S) ∈ FOLLOW(E), {$} ∈ FOLLOW(E)



Examples2




FIRST
FOLLOW




S -> Bb | Cd
{a, b, c, d}
{$}


B -> aB | ε
{a, ε}
{b}


C -> cC | ε
{c, ε}
{d}




풀이 생략

Examples3




FIRST
FOLLOW




E -> TE’
{id, (}
{$, )}


E’ -> +TE’ | ε
{+, ε}
{$, )}


T -> FT’
{id, (}
{+, $, )}


T’ -> *FT’ | ε
{*, ε}
{+, $, )}


F -> id | ( E )
{id, (}
{*, +, $, ) }




풀이 생략

Examples4




FIRST
FOLLOW




S -> ACB | CbB | Ba
{d, g, h, ε, b, a}
{$}


A -> da | BC
{d, g, h, ε}
{h, g, $}


B -> g | ε
{g, ε}
{$, a, h, g}


C -> h | ε
{h, ε}
{g, $, b, h}



Examples5




FIRST
FOLLOW




S -> ACB | CbB | Ba
{d, g, h, ε, b, a}
{$}


A -> da | BC
{d, g, h, ε}
{h, g, $}


B -> g | ε
{g, ε}
{$, a, h, g}


C -> h | ε
{h, ε}
{g, $, b, h}



Examples6




FIRST
FOLLOW




S -> aABb
{a}
{$}


A -> C | ε
{c, ε}
{d, b}


B -> d | ε
{d, ε}
{b}



Examples7




FIRST
FOLLOW




S -> aBDh
{a}
{$}


B -> cC
{c}
{g, f, h}


C -> bC | ε
{b, ε}
{g, f, h}


D -> EF
{g, f, ε}
{h}


E -> g | ε
{g, ε}
{f, h}


F -> f | ε
{f, ε}
{h}