/ Etc...?!

FIRST and FOLLOW 알고리즘 연습

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이면 `$`로 시작
  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}