구문 분석에 필요한 용어의 정의 ( terms for syntax analysis )

FIRST(a)

G : context-free 문법
FIRST(α) = {x ∈VT | α-(*)->xβ, β∈V*}
의미: 문자열 α로부터 유도되어 첫 번째로 나타날 수 있는 터미널 기호들의 집합

계산방법
(1) {X} ∈VT , {X} ∈ FIRST(X) 
(2) X ∈VN, X →  aβ ,  {a} ∈ FIRST(X) 
      X →  ε , {ε} ∈ FIRST(X) 
(3) X →  Y1Y2 … Yk  
FIRST(X)＝FIRST(X)∪FIRST(Y1Y2… Yk)

Nullable

A -> ε이면 A는 nullable 하다.

ring sum Å

e Î A이면 AÅB는 A이고,
e Ï A이면 AÅB는 ( A - {e} ) È B이다.
FIRST(ABC) = FIRST(A) Å  FIRST(B) Å  FIRST(C)

FOLLOW(A)

G : context-free 문법
Non-terminal A의  FOLLOW(A)의 정의
FOLLOW(A) = {a ∈ VT ∪ {$}| S-(*)->αAaβ, α,β∈V*}
의미: Non-terminal다음에 나타나는 터미널 기호들의 집합. $는 입력문자열의 끝을 나타냄

계산방법
(1) if A = 출발기호, $ ∈ FOLLOW(A) 
(2) if B → αAβ, β≠ε,  
    FOLLOW(A) ⊃ FIRST(β) (ε 제외)     
(3) if B → αAβ  &  β -(*)→ ε,  
    FOLLOW(A) ⊃ FOLLOW(B)