LR 파싱은 입력을 왼쪽에서 오른쪽(Left to right)으로 읽으면서 우단유도(Right parse)를 역순으로 복원하는 상향식 구문분석 기법이다.
하향식 파싱은 시작기호에서 출발해 문법규칙을 적용하며 입력 문자열까지 내려온다. LR은 반대로 간다. 입력 토큰에서 출발해 규칙의 오른쪽을 왼쪽으로 되돌리며 시작기호까지 올라간다. 이 되돌리는 동작을 reduce라고 한다.
E → E + T | T 입력: id + id * idT → T * F | FF → ( E ) | id하향식은 E부터 시작해 E + T, T + T… 로 펼쳐 나가고, 상향식은 id부터 시작해 F, T, E… 로 접어 나간다.
handle과 shift-reduce
Section titled “handle과 shift-reduce”S ⇒* αAw ⇒ αβw인 유도과정이 있을 때, 문장형태 αβw에서 A로 대체되는 부분 β를 handle이라고 한다. 한 문장형태에서 지금 reduce해야 할 바로 그 부분이다. 우단유도를 거꾸로 밟으며 handle을 계속 찾아 접는 과정을 handle pruning이라고 하고, 상향식 파싱은 전부 이 과정이다.
구현은 스택과 입력버퍼 두 개로 한다. 스택은 handle을 찾을 때까지 읽은 기호를 쌓아두고, 입력버퍼는 남은 문자열을 갖는다. 행동은 네 가지뿐이다.
shift: 입력기호 하나를 스택 top으로 옮긴다reduce: 스택 top에 handle이 나타나면 해당 생성규칙의 왼쪽 기호로 바꾼다accept: 시작기호에 도달했고 입력이 끝났다error: 그 자리에 올 수 없는 기호다
E → E+E | E*E | id 문법으로 id+id*id를 파싱하면 이렇게 된다.
단계 스택 입력 행동 0 $ id+id*id$ shift id 1 $id +id*id$ reduce E → id 2 $E +id*id$ shift + 3 $E+ id*id$ shift id 4 $E+id *id$ reduce E → id 5 $E+E *id$ shift * 6 $E+E* id$ shift id 7 $E+E*id $ reduce E → id 8 $E+E*E $ reduce E → E*E 9 $E+E $ reduce E → E+E10 $E $ accept여기의 단계 1에서 id가 handle인 건 어떻게 알 수 있을까? 단계 5에서 E+E는 왜 handle이 아닌가? handle을 어떻게 찾고, 후보가 여럿이면 어떤 생성규칙을 적용할 것인가. 상향식 파싱은 이 질문에 답하는 방법의 문제다.
초기에는 기호 사이에 순위관계 ⋖ ≗ ⋗를 정의해 handle의 경계를 찾는 순위문법(단순순위, 연산자순위 등)이 쓰였다. 하지만 문법에 제약이 많아 일반적인 프로그래밍 언어를 표현하기 어려웠고, 그 자리를 LR이 대체했다.
LR(0) 항목과 상태
Section titled “LR(0) 항목과 상태”LR은 지금까지 읽은 것으로 가능한 모든 규칙의 진행 상황을 상태 하나로 들고 다닌다.
생성규칙 오른쪽에 점을 찍은 것을 LR(0) 항목이라고 한다. A → XYZ라면 네 개가 나온다.
[A → ·XYZ] [A → X·YZ] [A → XY·Z] [A → XYZ·][A → X·YZ]는 “X는 이미 읽었고 YZ가 남았으며, 다 읽으면 A로 reduce할 수 있다”는 뜻이다. 점 뒤 기호를 마크기호라 하고, 점이 맨 끝에 온 [A → α·]가 reduce 항목이다.
먼저 시작기호가 유일하게 인식되도록 S′ → S를 얹은 증가문법을 만든다. accept 판정을 S′ → S로 reduce되는 순간으로 잡기 위해서다. 그리고 두 함수를 정의한다.
closure는 마크기호가 논터미널이면, 그 논터미널로 시작할 수 있는 규칙들을 전부 끌어와 점을 맨 앞에 찍어 추가한다. 더 변하지 않을 때까지 반복한다.
closure([E′ → ·E]) = { [E′ → ·E], [E → ·E+T], [E → ·T], [T → ·T*F], [T → ·F], [F → ·(E)], [F → ·id] }E를 읽으려는 시점에는 E+T가 시작될 수도, T가, 나아가 id가 시작될 수도 있다. 그 가능성을 전부 한 집합에 담은 것이 상태다.
GOTO는 기호 하나를 읽어 점을 오른쪽으로 옮긴 뒤 다시 closure를 취한다.
GOTO(I, X) = closure({ [A → αX·β] | [A → α·Xβ] ∈ I })closure([S′ → ·S])에서 출발해 GOTO를 닫힐 때까지 적용하면 항목 집합들의 모음(canonical collection)이 나오고, 이 집합 하나하나가 파서의 상태가 된다. 위 산술 문법이면 I0 ~ I11, 12개 상태다.
상태와 GOTO 그래프가 나오면 표로 옮긴다. 터미널로 이동하면 shift n, 논터미널로 이동하면 GOTO 칸에 n, reduce 항목이 있으면 reduce k, [S′ → S·]면 accept다.
| 상태 | id | + | * | ( | ) | $ | E | T | F |
|---|---|---|---|---|---|---|---|---|---|
| 0 | s5 | s4 | 1 | 2 | 3 | ||||
| 1 | s6 | acc | |||||||
| 2 | r2 | s7 | r2 | r2 | |||||
| 3 | r4 | r4 | r4 | r4 | |||||
| 4 | s5 | s4 | 8 | 2 | 3 | ||||
| 5 | r6 | r6 | r6 | r6 | |||||
| 6 | s5 | s4 | 9 | 3 | |||||
| 7 | s5 | s4 | 10 | ||||||
| 8 | s6 | s11 | |||||||
| 9 | r1 | s7 | r1 | r1 | |||||
| 10 | r3 | r3 | r3 | r3 | |||||
| 11 | r5 | r5 | r5 | r5 |
빈 칸은 전부 오류다. 실행은 단순하다. 스택 top 상태와 현재 입력기호로 표를 찾아 shift면 밀어넣고, reduce A → β면 2×|β|개를 pop한 뒤 A를 push하고 GOTO[새 top, A]를 push한다.
구동기 프로그램은 모든 LR 파서가 동일하고, 언어마다 다른 것은 표뿐이다. 문법이 바뀌면 코드가 아니라 표가 바뀐다. 파서 생성기가 존재할 수 있는 이유가 이것이다. 실제 언어 문법이면 상태가 수백 개가 되므로 표를 손으로 만들 수는 없고, LR을 쓴다는 것은 곧 생성기를 쓴다는 뜻이다. 빌드 파이프라인에 생성 단계가 하나 들어온다.
표를 만드는 방법에 따라 세 갈래로 나뉜다.
SLR, CLR, LALR
Section titled “SLR, CLR, LALR”가장 간단한 방법은 SLR이다. shift와 GOTO는 위와 같이 정하고, reduce는 FOLLOW 집합으로 결정한다. 상태에 [A → α·]가 있으면 FOLLOW(A)에 속한 모든 기호 자리에 reduce A → α를 넣는다.
이게 부정확할 때가 있다. 포인터 대입을 흉내 낸 문법이다.
S → L = R L → * RS → R L → id R → LFOLLOW(L) = {$, =}이므로 [R → L·]이 있는 상태 2에는 = 자리에 reduce R → L이 들어간다. 그런데 같은 상태에 [S → L·=R]도 있어서 shift 6도 들어간다. shift-reduce 충돌이다.
단계 스택 입력 행동 0 0 id=id$ shift 5 1 0 id 5 =id$ reduce L → id 2 0 L =id$ goto 2 3 0 L 2 =id$ reduce 5 ← 충돌 → shift 6옳은 답은 shift다. id = id에서 왼쪽 id는 대입의 좌변이므로 L인 채로 두고 =를 읽어야 한다. R로 접으면 안 된다. 그런데 *R = id 같은 유도에서는 같은 자리에서 R → L로 reduce하는 것이 옳다.
FOLLOW(L)은 문법 전체에서 L 뒤에 올 수 있는 기호의 집합이지, 지금 이 상태에서 올 수 있는 기호의 집합이 아니다. =는 문법 어딘가에서는 L 뒤에 오지만 이 상태에서는 오지 않는다. 상태별 문맥을 무시한 대가다.
그러면 lookahead를 항목마다 따로 들고 다니면 된다. LR(0) 항목에 기호 하나를 붙인 것이 LR(1) 항목이다.
[A → α·β, a] core lookaheada는 “이 항목이 reduce 항목이 됐을 때 a를 보면 reduce하라”는 뜻이다. closure도 lookahead를 전파하도록 바뀐다.
closure(I) = I ∪ { [B → ·γ, b] | [A → α·Bβ, a] ∈ closure(I), B → γ ∈ P, b ∈ FIRST(βa) }β 뒤에 a를 이어붙인 것의 FIRST를 취하는 게 전부다. β가 ε을 유도할 수 있으면 a가 그대로 물려받는다. 이렇게 만든 표가 CLR(canonical LR) 이고, 모호하지 않은 CFG 중 가장 넓은 범위를 처리한다.
대가는 상태 수다. core가 같아도 lookahead가 다르면 다른 상태가 되므로, 실제 프로그래밍 언어 문법에서는 상태가 수천 개로 불어난다. 이론적으로는 가장 강력하지만 그대로 쓰기는 어렵다.
LALR은 CLR을 만든 뒤 core가 같은 상태들을 하나로 합치고 lookahead는 합집합을 취한다.
S → CC, C → cC | d 문법에서 CLR은 I0 ~ I9, 10개 상태가 나온다. 그중 core가 같은 것을 합치면
I3 ∪ I6 → I36 = { [C → c·C, c/d/$], [C → ·cC, c/d/$], [C → ·d, c/d/$] }I4 ∪ I7 → I47 = { [C → d·, c/d/$] }I8 ∪ I9 → I89 = { [C → cC·, c/d/$] }10개가 7개로 줄고, 표 크기가 SLR과 같아진다. 그러면서 reduce 판단은 FOLLOW가 아니라 lookahead로 하므로 SLR보다 강하다. yacc과 bison이 쓰는 방법이 이것이다.
실제 생성기는 LR(1)을 만들어놓고 합치지 않는다. 그 중간 산물이 너무 크기 때문이다. LR(0) 항목 집합에서 시작해 reduce 항목의 lookahead만 따로 계산하는 방식을 쓴다. 상태 P에서 [A → α·β]의 lookahead는 α만큼 거슬러 올라간 이전 상태에서 A 뒤에 오는 기호들의 FIRST로 정의된다.
세 방법을 놓고 보면 SLR은 LR(0) 항목에 FOLLOW를 얹어 표가 작지만 상태 문맥을 무시해 약하고, CLR은 LR(1) 항목을 그대로 써서 가장 강하지만 표가 매우 크다. LALR은 SLR과 같은 크기의 표로 CLR에 가까운 강도를 낸다.
문법을 고쳤을 때 생성기가 내놓는 것은 “shift/reduce conflict in state 213” 같은 메시지라서, 원인을 찾으려면 그 상태의 항목 집합을 직접 봐야 한다. 생성기들이 충돌을 “shift 우선” 같은 기본 규칙으로 조용히 넘기기도 하는데, 그러면 문법의 모호성이 숨는다.
하향식과의 관계
Section titled “하향식과의 관계”같은 문장을 두 방향에서 접근하는 것이므로 성질이 대칭이다. 상향식은 파스트리를 터미널에서 루트 쪽으로 세우며 reduce로 시작기호를 찾아가고, 하향식은 루트에서 터미널 쪽으로 내려오며 유도로 문자열을 찾아간다. 상향식이 우단유도, 하향식이 좌단유도를 밟는다. 상향식의 대표 기법이 SLR, CLR, LALR이고 하향식은 recursive-descent, predictive, Pratt이다. 문법 클래스로는 각각 LR(k)와 LL(k)에 대응한다.
LL(k) ⊂ LR(k)다. 상향식은 규칙 전체를 다 읽은 뒤에 무엇이었는지 결정하지만, 하향식은 규칙을 고른 뒤에 읽어야 하므로 결정 시점이 이르고 그만큼 볼 수 있는 문법이 좁다. 좌재귀 E → E + T를 LL이 처리하지 못하는 것도 같은 이유다. E를 펼치려고 E를 부르는 무한 재귀가 되므로 좌재귀 제거가 선행되어야 한다. LR은 좌재귀를 그대로 받는다. 오히려 좌재귀 쪽이 스택을 덜 쓴다.
참고