[PL] Syntax Analysis : Ringsom Operator, LL Parsing Table

1. Ringsom Operator

✔️ If 𝜺 ∉ A then A ⊕ B = A

✔️ If 𝜺 ∈ A then A ⊕ B = (A - {𝜺}) U B

Example

{a, b, c} ⊕ {c, d} = {a, b, c}
{a, b, c, 𝜺} ⊕ {c, d} = {a, b, c, d}
{a, b, 𝜺} ⊕ {c, d, 𝜺} = {a, b, c, d,𝜺}

2. Generate LL Parsing Table

First함수, Follow 함수와 Ringsom operator을 이용하여 LOOKAHEAD'를 계산한다.

LOOKAHEAD에 Production rule을 넣고, First와 Follow 함수의 Ringsom Operator을 계산하여 Parsing Table을 만든다.

๏ Calculate LOOKAHEAD

⬛ S -> aBA|BB|ABc, A->dA|b, B-> 𝜺
⬛ FIRST(S) = {a,𝜺,d,b}, FIRST(A) = {d,b}, FIRST(B) = {𝜺}
⬛ FOLLOW(S) = {$}, FOLLOW(A) = {c, $}, FOLLOW(B) = {c} U {d,b} = {c, d, b, $}

LOOKAHEAD(S -> aBA) = FIRST(aBA) ⊕ FOLLOW(S) = {a}

LOOKAHEAD(S -> BB) = FIRST(BB) ⊕ FOLLOW(S) = {$}

LOOKAHEAD(S -> ABc) = FIRST(ABc) ⊕ FOLLOW(S) = {d,b}

LOOKAHEAD(A -> dA) = FIRST(dA) ⊕ FOLLOW(A) = {d}

LOOKAHEAD(A -> b) = FIRST(b) ⊕ FOLLOW(A) = {b}

LOOKAHEAD(B -> 𝜺) = FIRST(𝜺) ⊕ FOLLOW(B) = {$, d, b, c}