Strong LL 조건

Intro

• Strong LL조건의 이해

Strong LL 조건

임의의 택일 규칙 A -> α | β ∈ P 에 대하여 
다음을 Strong LL 조건이라 부른다.

LOOKAHEAD(A -> α) ∩ LOOKAHEAD(A -> β) = ∅

LOOKAHEAD가 같게되면 Nonterminal을 어떤 생성 규칙으로 확장해야 올바른 스트링을 유도할지 알 수 없기 때문에 LOOKAHEAD가 달라야 결정적 구문 분석이 가능하다.

Strong LL 조건을 만족하는 문법을 Strong LL(1) 문법이라 부르며, recursive-descent 구문 분석기가 결정적으로 구문 분석하기 위해서는 strong LL 조건을 만족 해야 한다.

예제

다음 문법이 strong LL(1) 문법인지 확인

S -> bRS | RcSa | ε
R -> acR | b

LOOKAHEAD(S -> bRS) = FIRST(b) ⊕ FIRST(R) ⊕ FIRST(S) ⊕ FOLLOW(S)
                    = {b} ⊕ {a,b} ⊕ {a, b, ε} ⊕ {a, $}
                    = {b}
                    
LOOKAHEAD(S -> RcSa) = FIRST(R) ⊕ FIRST(c) ⊕ FIRST(S) ⊕ FIRST(a) ⊕ FOLLOW(S)
                    = {a, b} ⊕ {c} ⊕ {a, b, ε} ⊕ {a} ⊕ {a, $}
                    = {a,b}

LOOKAHEAD(S -> bRS) ∩ LOOKAHEAD(S -> RcSa) = {b} 이므로

Strong LL 조건을 만족하지 않는다. 따라서 strong LL 문법이 아니다.

참고 저서

오세만, 컴파일러 입문, 정익사,2010, 283쪽