한 토큰 앞만 보고 결정하는 파서: LL에서 SLR·CLR·LALR까지

이 글은 개인 학습 아카이브에 보관된 컴파일러 강의 PDF·슬라이드·코드 예제를 교차 검토해 새로 구성한 학습 노트입니다. 오래된 표기, 오탈자, 실행되지 않는 예시는 본문에서 별도로 바로잡았으며 원본 파일이나 내부 경로는 공개하지 않습니다.

LL과 LR은 무엇을 결정하는가

LL과 LR parser는 모두 입력 token을 왼쪽에서 오른쪽으로 읽는다. 차이는 현재 결정의 종류다.

• LL은 leftmost derivation을 top-down으로 만들며 “이 nonterminal을 어느 production으로 expand할까?”를 결정한다.
• LR은 rightmost derivation을 bottom-up으로 거꾸로 만들며 “token을 shift할까, 어느 production으로 reduce할까?”를 결정한다.

아카이브의 “LR은 rightmost derivation을 한다”는 문장은 절반만 맞다. LR parser가 실제로 출력하는 reduction sequence는 rightmost derivation in reverse다. 이 방향을 놓치면 handle과 parsing stack의 의미가 뒤집힌다.

Top-down parsing을 위한 grammar 정리

backtracking parser는 production 하나를 골라 진행하다 실패하면 input position과 parser state를 되돌리고 다음 production을 시도한다. 구현은 가능하지만 left recursion에서는 끝나지 않고, 선택지가 중첩되면 시간이 급격히 늘 수 있다.

direct left recursion은 다음처럼 제거한다.

A -> A α1 | A α2 | ... | A αm | β1 | β2 | ... | βn

A  -> β1 A' | β2 A' | ... | βn A'
A' -> α1 A' | α2 A' | ... | αm A' | ε

expression grammar는 다음 형태가 된다.

E  -> T E'
E' -> + T E' | ε
T  -> F T'
T' -> * F T' | ε
F  -> ( E ) | id

indirect left recursion은 nonterminal을 A1 ... An 순서로 놓고 Ai -> Aj γ, j<i인 production을 Aj의 alternatives로 치환한 뒤 Ai의 direct recursion을 제거한다. archived pseudocode는 outer loop를 i=2에서 시작해 A1 자체의 direct recursion을 검사하지 않는다. 올바른 일반 알고리즘은 i=1부터 시작하고, 첫 번째 반복에서는 inner loop가 비어 있도록 해야 한다.

공통 prefix는 left factoring으로 늦게 결정한다.

A -> α β | α γ

A  -> α A'
A' -> β | γ

그러나 factoring은 ambiguity를 자동으로 해결하지 않는다. 대표적인 dangling-else grammar를

S  -> if C then S S' | other
S' -> else S | ε

로 바꾸어도 else가 FIRST(else S)와 FOLLOW(S')에 함께 나타날 수 있다. 가장 가까운 unmatched if에 붙인다는 policy나 grammar redesign이 추가로 필요하다.

FIRST, FOLLOW, SELECT

FIRST(α)는 sentential form α가 처음 만들 수 있는 terminal 집합이고, α가 빈 문자열을 만들 수 있으면 ε도 포함한다. FOLLOW(A)는 어떤 유도에서 A 바로 다음에 올 수 있는 terminal 집합이다. 계산은 한 번의 대입이 아니라 더 이상 집합이 변하지 않을 때까지 반복하는 fixed point다.

핵심 규칙은 다음과 같다.

$ is in FOLLOW(S)

For A -> α B β:
  FIRST(β) - {ε} is included in FOLLOW(B)
  if β is nullable, FOLLOW(A) is included in FOLLOW(B)

production의 실제 선택 집합은 다음처럼 정의하는 편이 명확하다.

SELECT(A -> α)
  = FIRST(α) - {ε}
    union FOLLOW(A), if α is nullable

같은 LHS를 가진 alternatives의 SELECT가 pairwise disjoint하면 LL(1) table의 한 cell에 production이 하나만 들어간다. archived LL(1) 설명은 FIRST(α) ∩ FIRST(β) = empty만 제시하는데, nullable alternative가 있으면 FOLLOW까지 보지 않아 불충분하다. archived FOLLOW 공식의 “β=ε, 즉 A→ε”라는 괄호도 잘못됐다. 정확히는 A -> α B, 곧 B 뒤의 β가 비어 있는 경우다.

다음 연습 grammar의 완성된 집합은 fixed-point 계산을 점검하기 좋다.

S -> a B b | B c b | ε
A -> a A b | B B d
B -> b | ε

FIRST(S)  = {a, b, c, ε}
FIRST(A)  = {a, b, d}
FIRST(B)  = {b, ε}
FOLLOW(S) = {$}
FOLLOW(A) = {b}
FOLLOW(B) = {b, c, d}

아카이브의 LL(2) 예제는 S의 alternatives가 aa, ab, ac prefix로 구별된다고 설명하면서도 A -> a | A c c라는 left-recursive rule을 포함한다. left-recursive grammar 전체를 LL(2)라고 부를 수 없으므로 이 예제는 “S에서 두 글자 prefix가 필요한 현상”까지만 사용해야 한다. 일반 LL(k) 판정도 단순한 FIRST_k 교집합이 아니라 context와 end marker를 포함한 k-symbol selection을 다룬다.

Recursive descent와 predictive table

recursive-descent parser는 terminal을 match하는 함수와 nonterminal마다 하나의 함수를 둔다.

parseA():
  choose a production whose SELECT contains lookahead
  parse each RHS symbol from left to right
  otherwise report an error

main:
  lookahead = nextToken()
  parseS()
  accept only if lookahead is $

archived C-like pseudocode의 void main()은 표준 C/C++ signature가 아니다. 실행 코드라면 int main(void) 또는 환경에 맞는 entry point를 써야 한다.

table-driven predictive parser는 call stack 대신 explicit stack과 table M[A, token]을 쓴다. 예제 grammar의 rule number를 다음처럼 둔다.

1 S -> b A b    2 S -> a B    3 S -> ε
4 A -> a A b    5 A -> b B a
6 B -> b        7 B -> ε

stack top이 nonterminal이면 table의 RHS를 오른쪽부터 push해야 가장 왼쪽 symbol이 top에 온다. terminal이면 lookahead와 match하고 둘을 전진시킨다. “둘 중 하나가 비면 loop 종료” 같은 조건은 premature success를 만들 수 있다. stack과 input의 end marker가 함께 만나는지, table cell이 비어 있지 않은지로 accept와 error를 나눠야 한다.

archived implementation은 char[16] rule, char[128] stack, char[64] input과 한 글자 grammar symbol을 사용한다. 학습용 구조로는 parsing table, rule, input, stack의 책임을 잘 보여 주지만 production code에는 token/symbol enum, bounds-safe collection, source span, structured diagnostic가 필요하다.

Bottom-up parsing과 handle

reduce 가능한 RHS가 보인다고 모두 handle은 아니다. 정확히는 right-sentential form α β ω에서

S =>*rm α A ω =>rm α β ω
A -> β

가 성립할 때 β와 그 위치가 handle이다. archived definition은 임의 derivation만 적고 위치를 생략해 너무 넓다.

E -> E + T | T
T -> T * F | F
F -> a

에서 a+a*a는 다음처럼 진행한다.

shift a
reduce F -> a
reduce T -> F
reduce E -> T
shift +
shift a
reduce F -> a
reduce T -> F
shift *
shift a
reduce F -> a
reduce T -> T * F
reduce E -> E + T
accept

shift 때 terminal node를 만들고 reduce 때 RHS node들을 LHS node 아래에 연결하면 parse tree를 함께 구성할 수 있다. AST는 의미 있는 terminal과 production에만 semantic action을 붙여 불필요한 grammar scaffolding을 만들지 않는다.

LR runtime의 불변조건

LR stack은 state와 grammar symbol을 번갈아 저장한다.

[s0, X1, s1, X2, s2, ..., Xk, sk]

ACTION[state, terminal]은 Shift j, Reduce rule, Accept, Error 중 하나이고, GOTO[state, nonterminal]은 다음 state다.

loop:
  s = top state
  a = lookahead

  Shift j:
    push a, j
    advance input

  Reduce A -> β:
    pop 2 * |β| entries
    t = top state
    push A, GOTO[t, A]
    run semantic action

  Accept or Error:
    stop

archived trace는 reduce와 GOTO를 두 줄로 출력한다. 학습 trace로는 가능하지만 parser operation에서는 한 reduction의 두 부분이다.

간단한 grammar E -> E+F | F; F -> a의 SLR table은 LR 작동을 압축해서 보여 준다.

LR(0) item, CLOSURE, GOTO

augmented production S' -> S를 추가하고 RHS의 진행 위치에 dot을 둔다.

A -> α . β

dot 앞 α는 viable prefix에서 이미 인식한 부분이고, dot 뒤 β는 앞으로 필요한 부분이다.

CLOSURE(I)는 dot 다음이 nonterminal B일 때 모든 B -> . γ를 추가하고, 새 item에서도 같은 작업을 더 이상 변하지 않을 때까지 반복한다. GOTO(I,X)는 dot을 X 뒤로 옮긴 item들의 closure다. 이 canonical collection이 DFA state가 된다.

archived 분류의 “dot이 처음이면 closure item, 중간이면 kernel item”은 표준 partition이 아니다. kernel에는 augmented start item S' -> . S도 포함되고, 그 밖에 dot이 맨 앞인 item을 nonkernel item이라고 한다. “closure item”은 서로 배타적인 정식 item 종류가 아니다.

SLR table은 다음 규칙으로 만든다.

1. terminal transition에는 shift를 넣는다.
2. nonterminal transition에는 GOTO를 넣는다.
3. completed item A -> α .에는 FOLLOW(A)의 token마다 reduce를 넣는다.
4. S' -> S .에는 ACTION[state,$]=Accept를 넣는다.

archived construction은 네 번째 accept rule을 빠뜨렸다. 또한 FOLLOW 전체를 reduction lookahead로 쓰기 때문에 현재 viable-prefix context와 무관한 token까지 섞여 conflict가 날 수 있다.

Canonical LR(1), LALR, conflict

LR(1) item은 context를 한 token 더 기록한다.

[A -> α . β, a]

dot 다음 nonterminal B의 item을 closure에 넣을 때 lookahead는 FIRST(βa)에서 계산한다. canonical LR은 이 정확한 context 덕분에 SLR보다 많은 grammar를 다루지만 state가 더 많아질 수 있다.

LALR은 LR(0) core가 같은 canonical LR states를 merge하고 lookahead를 합친다. state 수는 LR(0)/SLR 수준이고 reduction context는 SLR보다 정밀하다. 그러나 merge가 canonical LR에는 없던 reduce/reduce conflict를 만들 수 있으므로 “CLR만큼 정확하면서 항상 작은 방식”은 아니다.

ambiguous expression grammar는 shift/reduce conflict를 만들고, 둘 이상의 completed rule이 경쟁하면 reduce/reduce conflict가 난다. precedence와 associativity declaration으로 원하는 action을 고를 수 있지만 원래 ambiguous grammar 자체가 LR grammar로 바뀌는 것은 아니다.

dangling else automaton의 한 state에는 I -> if S .와 I -> if S . else S가 함께 있다. else에서 reduce와 shift가 충돌하며 archive table은 shift를 선택한다. 이는 else를 가장 가까운 if에 연결하는 policy이지 conflict-free SLR 증명이 아니다.

아카이브 table과 trace를 검산해야 하는 이유

괄호 언어 S -> (S)S | ε의 예제에서 augmented accept state는 S' -> S .만 가진다. 따라서 )를 shift할 transition이 없는데 archived table에는 잘못된 s4가 들어 있다. 그 cell은 error여야 하고 $에서만 accept한다.

list grammar의 a,a trace는 일부 줄에서 action을 수행하기 전 stack과 수행한 뒤 stack이 섞였다. table로부터 다시 생성해야 한다. expression implementation trace도 두 곳에서 alternating stack symbol을 빠뜨렸다.

wrong:  0 E1 +6 3
right:  0 E1 +6 F3

wrong:  0 E1 +6 9
right:  0 E1 +6 T9

자료의 grammar와 ACTION table은 terminal을 id라고 쓰지만 trace input은 a라고 쓴다. a가 id token의 stand-in임을 선언하거나 표기를 하나로 통일해야 한다.

현대 구현은 action 값을 부호 있는 integer나 문자열로 겹쳐 쓰기보다 tagged variant로 둔다.

type Action =
  | { kind: "shift"; state: number }
  | { kind: "reduce"; rule: number }
  | { kind: "accept" }
  | { kind: "error" };

rule은 LHS와 RHS length를 보관하고, stack은 bounds-safe collection을 사용하며, reduction semantic action은 AST node와 source span을 만든다. error recovery와 diagnostic도 empty table cell을 단순 종료로 바꾸는 것보다 명시적으로 설계해야 한다.

마무리

LL은 grammar를 예측 가능한 형태로 정리하고 SELECT로 expansion을 고른다. LR은 지금까지 읽은 viable prefix를 automaton state로 압축하고 reduction context를 FOLLOW 또는 LR(1) lookahead로 좁힌다. “한 token만 본다”는 말은 parser가 문맥을 모른다는 뜻이 아니다. grammar transformation, call/parse stack, LR state가 축적한 문맥과 현재 token을 함께 사용해 결정한다.