XX(k)에서 k는 derivation에서 한 step 이동할 때 의존하는 input token의 수이다.
LL(1): 모든 parsing 단계에서 derivation 이동 발생. 각 단계에서 input token에 따라 parsing table의 entry를 선택하므로 k=1
LR(0): reduce action 때만 derivation 이동 발생. shift/goto/accept일 때는 같은 sentential form 유지. reduce/shift 선택은 input token에 무관히 state 특성에만 의존함. reduce 가능한 state라면 항상 같은 rule로 reduce하므로 k=0. 다시 말해, parsing table에서 해당 state 행의 모든 열에 reduce action 존재함
shift/reduce decision ≡ handle 판정 & production의 선택
LR(0) 파서도 실제로는 **입력의 맨 앞 토큰(lookahead)**을 보고 shift할지 말지를 판단하는 데 사용합니다.
그래서 “lookahead가 0개인데 왜 입력 토큰을 보냐?”라는 의문이 충분히 생길 수 있어요.
이 의문은 shift/reduce decision과 reduce decision을 분리해서 보면 깔끔하게 해소됩니다.
<aside> 📌
LR(0)에서 괄호 속 **0은 "reduce 할 때 lookahead를 보지 않는다"**는 뜻입니다.
</aside>
| 구분 | lookahead 사용 여부 | 설명 |
|---|---|---|
| shift 여부 결정 | ✅ 사용함 (다음 토큰 보고 shift함) | 다음 토큰이 어떤 terminal이면 shift할지 결정 |
| reduce 여부 결정 | ❌ 사용하지 않음 (lookahead 없이 reduce함) | 오직 상태만 보고 reduce할 수 있어야 함 |
S → A
A → a
이런 문법에서 a가 들어오면:
a를 보고 shift할지 말지 결정할 수 있어야 함 → shift는 lookahead 1개 사용a를 읽은 후, A → a • 상태가 되면 lookahead 없이도 reduce 가능해야 LR(0)에서 허용됨LR(0)은 reduce 시 lookahead가 없어서 shift/reduce 충돌이 많음SLR(1)이나 LALR(1), LR(1)처럼 lookahead 1개를 쓰는 버전들이 발전해서 실무에선 이걸 많이 씁니다