4장. 문맥 의존 분석

"이 문장 문법은 맞는데, 말이 되나?" — 타입 시스템과 의미 검사의 세계.

4.1 들어가며 — 문법은 맞는데 말이 안 되는 코드

2장과 3장을 거쳐 컴파일러는 입력 텍스트를 토큰으로 잘게 썰고, 토큰 스트림을 파스 트리로 엮는 데까지 왔다. 이제 컴파일러는 한 가지 사실은 보장할 수 있다 — 문법적으로 정당한 문장이다. 하지만 그게 끝이 아니다. 다음 코드를 보자.

x = y + z;

이 한 줄은 x ← y나 x ← z의 파스 트리와 모양이 거의 똑같다. 다른 점은 오른쪽에 어떤 이름이 들어가느냐 뿐. 그런데 만약 x와 y는 정수이고 z는 문자열이라면? 또는 z가 한 번도 선언된 적 없는 이름이라면? 파서는 이 차이를 잡아내지 못한다. 파스 트리만 보고는 "정수 더하기 문자열"이 안 된다는 사실을 알 길이 없다.

그래서 필요한 것이 문맥 의존 분석(context-sensitive analysis)이다. 다른 이름으로는 의미 정교화(semantic elaboration)라고도 부른다. 결국 IR(중간 표현)에 의미라는 살을 붙여나가는 작업이라는 뜻이다.

이런 검사는 문맥 자유 문법(CFG)으로는 깔끔하게 표현되지 않는다. 가능은 하지만 가능한 모든 변수 조합을 문법에 박아넣어야 하는데, 현실적인 언어의 이름 공간 크기를 생각하면 사실상 불가능에 가깝다. 그래서 컴파일러 작성자는 파서 옆에다 "이건 따로 처리하겠습니다"의 영역을 만든다. 이 장은 그 영역을 두 가지 방식으로 다룬다.

1. 속성 문법(attribute grammar) — 함수형, 자동화, 우아한 명세.
2. 임시방편 구문 주도 번역(ad hoc syntax-directed translation) — 파싱 도중에 코드 조각을 끼워넣는 실전형 접근.

4.2 타입 시스템 입문

모든 값에는 타입(type)이 있다. 타입이란 같은 부류 값들이 공통으로 가지는 성질의 집합이다. 정수 타입은 "−2³¹ ≤ i < 2³¹ 범위의 정수"라는 멤버십으로 정의되고, 열거형 colors = {red, orange, yellow, ...}처럼 명시적 멤버 나열로 정의되기도 한다. 구조체처럼 규칙으로 만들어지는 타입도 있다. 언어 안의 모든 타입과 그 타입들을 사용하는 규칙을 묶어서 타입 시스템(type system)이라고 부른다.

4.2.1 타입 시스템은 왜 있는가

언어 설계자가 타입 시스템을 도입하는 이유는 셋이다. 안전성, 표현력, 효율.

(1) 런타임 안전 보장

잘 만들어진 타입 시스템은 실행되면 망할 프로그램을 실행 전에 골라낸다. 컴파일러는 (a) 모든 식의 타입을 추론하고, (b) 각 연산자 자리에 들어간 피연산자 타입이 규칙에 맞는지 검사한다. FORTRAN 77의 + 연산자가 실제로 어떤 식으로 작동하는지 표로 보면 직관적이다.

표를 외우는 게 아니라, 표가 있다는 사실이 중요하다. 컴파일 타임에 표를 참조해서 위반을 잡으면, 런타임에 일일이 태그(tag)를 붙여 검사할 필요가 없다.

(2) 표현력 — 연산자 오버로딩

강타입 언어가 누리는 호사 중 하나가 연산자 오버로딩(operator overloading)이다. + 하나로 정수 더하기, 실수 더하기, 복소수 더하기를 다 표현할 수 있다. 무타입 언어 BCPL에서는 그렇게 못한다 — 정수 덧셈은 +, 부동소수 덧셈은 #+처럼 별도의 연산자를 줘야 한다. 모든 값이 그냥 "셀"(cell)일 뿐이니까.

(3) 더 나은 코드 생성

컴파일러가 모든 식의 타입을 알면 iADD, fADD, dADD처럼 정밀도별로 다른 ILOC 명령을 직접 박을 수 있다. 만약 타입을 런타임에 검사해야 한다면 어떻게 될까?

// "a+b ⇒ c" 의 일부 코드 (런타임 타입 검사)
if (tag(a) = integer) then
    if (tag(b) = integer) then
        value(c) ← value(a) + value(b);
        tag(c)   ← integer;
    else if (tag(b) = real) then
        temp     ← ConvertToReal(a);
        value(c) ← temp + value(b);
        tag(c)   ← real;
    else ...
else if (tag(a) = real) then
    ...
else
    signal runtime type fault

덧셈 한 번이 if-else 사다리가 된다. 각 값에 타입 태그를 붙이고, 메모리도 더 먹고, 캐시도 망가진다. 컴파일 타임에 끝낼 수 있다면 언제나 그쪽이 빠르다. 단, 언어 설계가 그것을 허용해야 가능한 이야기다.

4.2.2 타입 시스템의 구성 요소

현대 언어의 타입 시스템은 보통 네 부분으로 이뤄진다.

1. 기본 타입(base types) — 숫자(정수/실수), 문자, 불리언. 하드웨어가 직접 지원하는 것들.
2. 구성 규칙(constructors) — 기본 타입에서 배열, 레코드, 포인터, 합집합 같은 복합 타입을 만드는 법.
3. 등가 판정(equivalence) — 두 타입이 같은가? 호환 가능한가?
4. 추론 규칙(inference rules) — 식의 타입을 피연산자 타입으로부터 어떻게 계산하는가.

등가 판정 두 학파: 이름 vs 구조

C에서 다음을 보자.

struct Tree {
  struct Tree *left;
  struct Tree *right;
  int          value;
}
struct STree {
  struct STree *left;
  struct STree *right;
  int           value;
}

Tree와 STree는 같은 타입인가?

• 이름 등가(name equivalence): 이름이 같아야 같은 타입. 프로그래머가 다른 이름을 골랐다면 그건 의도다. → 둘은 다른 타입.
• 구조 등가(structural equivalence): 구조가 똑같으면 같은 타입. → 둘은 같은 타입.

대규모 프로젝트에서 이름 등가는 같은 이름이 우연히 충돌할 위험이 있고, 구조 등가는 의미는 다른데 모양만 같은 두 타입(파일 I/O 블록 vs 화면 비트맵 정보)을 섞어버릴 수 있다. 트레이드오프다.

타입 시그니처 — 함수의 명함

함수도 타입을 가진다. C의 strlen은

unsigned int strlen(const char *s);

인데, 추상 표기로는 strlen : const char * → unsigned int로 적을 수 있다. Scheme의 filter처럼 다형성이 들어가면

filter : (α → boolean) × list of α → list of α

"불리언을 반환하는 α 함수와 α의 리스트를 받아 α의 리스트를 돌려준다"는 뜻. 반환 타입이 인자에 따라 결정되는 이런 성질을 매개변수 다형성(parametric polymorphism)이라고 한다.

4.3 속성 문법(Attribute Grammar) 프레임워크

지금까지 살펴본 검사들을 어떻게 체계적으로 자동화할까? 한 가지 답이 속성 문법이다. 이름 그대로 문법 + 속성 규칙으로, 각 문법 기호에 "속성"이라는 라벨을 붙이고, 그 속성을 다른 속성들의 함수로 정의하는 함수형 명세다.

구체적으로 보자. 부호 있는 이진수 문법 SBN을 예로 든다.

Number → Sign List
Sign   → + | -
List   → List Bit | Bit
Bit    → 0 | 1

이 문법이 만든 트리에 "이 트리는 십진수로 얼마인가?"를 라벨로 붙이고 싶다. 각 비기호에 다음 속성을 둔다.

그리고 각 생성 규칙(production)에 그 속성을 어떻게 계산하는지 적는다.

1  Number → Sign List   List.position ← 0
                        if Sign.negative
                            then Number.value ← -List.value
                            else Number.value ←  List.value
2  Sign → +              Sign.negative ← false
3  Sign → -              Sign.negative ← true
4  List → Bit            Bit.position ← List.position
                         List.value   ← Bit.value
5  List₀ → List₁ Bit     List₁.position ← List₀.position + 1
                         Bit.position   ← List₀.position
                         List₀.value    ← List₁.value + Bit.value
6  Bit → 0               Bit.value ← 0
7  Bit → 1               Bit.value ← 2^Bit.position

"-101"이 들어오면 트리의 각 노드에 위 규칙들이 인스턴스화되어 값이 흐르고, 결국 루트의 Number.value에 -5가 박힌다.

합성 속성 vs 상속 속성

SBN 예에서 value와 negative는 합성, position은 상속이다. 첫 규칙이 루트에서 List.position ← 0으로 박아주고, 그 값이 트리 아래로 흘러내려간다. 비트 자릿수는 위에서 알려줘야 하니까 어쩔 수 없이 상속이다.

4.3.1 평가 방법(Evaluation Methods)

속성 문법은 명세일 뿐 — 실제로 평가하는 평가기가 필요하다. 세 부류로 나뉜다.

1. 동적(dynamic) 방법 — 의존성 그래프를 만들고 데이터플로우 방식으로 흘려보낸다. Knuth의 원래 논문이 제안한 방식.
2. 둔감한(oblivious) 방법 — 그래프 모양과 무관하게 좌→우, 우→좌, 또는 교차 패스를 반복. 단순하지만 트리 구조를 못 활용한다.
3. 규칙 기반(rule-based) 방법 — 문법을 정적 분석해서 평가 순서를 미리 짜둔다. 빠르고 우아하지만 비순환 문법이어야 한다.

4.3.2 순환성(Circularity) — 닭이 먼저냐 알이 먼저냐

속성 규칙이 자기 자신에 의존하면(직접·간접) 의존성 그래프에 사이클이 생긴다. 이렇게 생긴 문법은 잘못 짜인 것이다 — 컴파일러가 무한 루프에 빠지거나 답을 못 낸다. 대처법은 두 가지.

• 회피(avoidance) — 합성 속성만 쓰는 등 사이클이 절대 안 생기는 부분집합으로 제한. strongly noncircular 문법은 다항 시간에 검사 가능.
• 평가 시 처리 — 사이클을 만나면 기본값을 넣고 반복(iterate)으로 수렴.

4.3.3 확장 예제 — 식의 타입 추론

고전 식 문법에 type 속성을 붙여, a - 2 × c(a는 정수, c는 실수)의 타입을 추론해보자. 각 산술 연산자에 대해 두 피연산자 타입을 받아 결과 타입을 돌려주는 함수 𝓕₊, 𝓕₋, 𝓕×, 𝓕÷를 가정한다(그림 4.1의 표가 이 함수들이다).

Expr₀ → Expr₁ + Term    Expr₀.type ← 𝓕₊(Expr₁.type, Term.type)
      | Expr₁ - Term    Expr₀.type ← 𝓕₋(Expr₁.type, Term.type)
      | Term            Expr₀.type ← Term.type
Term₀ → Term₁ × Factor  Term₀.type ← 𝓕×(Term₁.type, Factor.type)
      | Term₁ ÷ Factor  Term₀.type ← 𝓕÷(Term₁.type, Factor.type)
      | Factor          Term₀.type ← Factor.type
Factor → ( Expr )       Factor.type ← Expr.type
       | num            num.type 는 이미 정의됨
       | name           name.type 는 이미 정의됨

모든 속성이 합성이다 — 자식의 type으로 부모의 type을 만든다. 이런 문법을 S-속성 문법(S-attributed grammar)이라고 부르고, 상향식 파서와 궁합이 좋다(reduce 시점에 바로 평가). 짧고, 우아하고, 빠른 평가기가 나온다.

실행 시간 추정기 — 요구가 늘면 규칙도 늘어난다

이번엔 직선 코드의 실행 사이클 수를 추정해보자. cost 속성을 만들고, 각 노드에서 ILOC 명령어 비용을 합한다. 처음에는 단순하다 — 모든 변수에 대해 매번 load 비용을 매기면 된다.

그런데 더 현실적으로 만들고 싶다면? "한 블록 안에서 같은 변수를 여러 번 쓰면 첫 번째만 load 비용이 든다"고 모델링하고 싶다. 이를 위해 Before(이 노드 도달 전에 이미 로드된 이름 집합)과 After(노드 처리 후의 집합) 속성을 도입한다.

여기서 속성 문법의 약점이 드러난다 — 속성 규칙은 가까운 이웃(부모, 자식, 형제)밖에 못 본다. 정보를 트리 멀리 보내려면 복사 규칙(copy rules)을 잔뜩 만들어 한 노드에서 다음 노드로 전달해야 한다. 그림 4.10의 규칙은 그래서 그림 4.7보다 세 배 이상 길다. 한 줄짜리 명세가 한 페이지짜리 명세로 부풀어오른다.

4.3.4 속성 문법의 골치들

4.4 임시방편 구문 주도 번역

속성 문법의 핵심 통찰 — "문맥 의존 검사는 문법 구조 주위로 조직될 수 있다" — 만 살리고, 함수형의 제약은 버려보자. 그러면 임시방편 구문 주도 번역(ad hoc syntax-directed translation, ad hoc SDT)이 된다.

방식은 단순하다. 각 생성 규칙(production)에 코드 조각(action)을 매단다. 파서가 그 규칙으로 reduce할 때마다(또는 top-down 파서면 그 노드를 처리할 때마다) 그 코드를 실행한다. 임의의 코드를 끼워넣을 수 있고, 전역 자료구조(심볼 테이블 등)를 자유롭게 건드릴 수 있다.

SBN 예제를 ad hoc SDT로 다시 써보자. Yacc 표기법을 빌려, $$는 현재 reduce의 결과 자리, $1, $2, ...는 우변 i번째 기호의 값을 가리킨다.

1  Number → Sign List      $$ ← $1 × $2
2  Sign   → +              $$ ← 1
3  Sign   → -              $$ ← -1
4  List   → Bit            $$ ← $1
5  List₀  → List₁ Bit      $$ ← 2 × $1 + $2
6  Bit    → 0              $$ ← 0
7  Bit    → 1              $$ ← 1

속성 문법 버전(그림 4.5)이 7개 규칙에 13~14줄의 속성 규칙이었다면, 이 버전은 7줄. 각 기호당 한 개의 값만 허용하고, 값은 잎에서 루트로만 흐른다. 이 두 가지 단순화가 LR(1) 파서와 자연스럽게 맞물린다 — 파서 스택에 값 슬롯 하나씩만 더 두면 된다.

4.4.1 구현 — 스택과 심볼 테이블

shift-reduce 파서는 각 기호에 대해 (symbol, state)를 스택에 쌓는다. 여기서 한 칸 더 늘려 (value, symbol, state)를 쌓으면, 액션은 자동으로 스택 맨 위로부터 일정 오프셋의 값을 읽고 쓰면 된다. $1은 스택 맨 위에서 3×|β|개 슬롯 아래의 값, $i는 3×(|β|−i+1) 아래의 값을 가리킨다.

액션 사이의 통신 — 심볼 테이블

속성 문법에서 가장 골치 아팠던 비국소 정보 전달이 여기서는 자명해진다. 심볼 테이블(symbol table)을 하나 만들고 액션이 그것을 자유롭게 읽고 쓰면 끝이다.

아까 손이 많이 갔던 "한 블록 안에서 변수당 load는 한 번만"을 ad hoc SDT로 다시 쓰면 이렇게 짧아진다.

Block₀ → Block₁ Assign
       | Assign
Assign → name = Expr ;     { cost ← cost + Cost(store) }
Expr   → Expr + Term       { cost ← cost + Cost(add) }
       | Expr - Term       { cost ← cost + Cost(sub) }
       | Term
Term   → Term × Factor     { cost ← cost + Cost(mult) }
       | Term ÷ Factor     { cost ← cost + Cost(div) }
       | Factor
Factor → ( Expr )
       | num               { cost ← cost + Cost(loadI) }
       | name              { if name 의 심볼테이블 필드가 아직
                                로드되지 않았다고 표시하면
                              cost ← cost + Cost(load)
                              필드를 true 로 설정 }

cost는 전역 변수, "이미 로드되었는지"는 심볼 테이블 필드. 속성 문법 버전에서 Before·After 집합을 트리 따라 복사하던 그 모든 수고가 두 줄의 if문으로 사라진다.

4.4.2 활용 예 — AST 만들기, ILOC 내뿜기, 선언 처리

ad hoc SDT의 진짜 가치는 한 번의 파스로 여러 일을 동시에 한다는 점이다. 같은 액션 안에서

• AST 노드를 만들고(MakeNode₂(Plus, $1, $3)),
• 타입을 추론해 노드에 저장하며($$.type ← 𝓕₊($1.type, $3.type)),
• 심볼 테이블을 갱신하고,
• ILOC 명령을 즉석에서 출력할 수도 있다(Emit(add, $1, $3, $$)).

C 선언문 처리의 예를 보자. int *p, q[10]; 같은 문장은 문맥 자유 문법으로 큰 줄기는 잡되, "StorageClass는 한 선언당 하나만"같은 세밀한 제약은 ad hoc 액션이 처리한다. 액션이 속성 구조체를 채워나가다가 변수 이름이 등장하는 순간 심볼 테이블 항목을 만들고, 다음 변수가 오면 일부 필드만 리셋한다. 문법은 자유롭게 두고, 의미 검사는 코드로 직접 박는다.

4.5 고급 주제

4.5.1 더 어려운 타입 추론

지금까지 예제는 모두 "변수와 함수가 선언되어 있다"는 가정 위에 있었다. 그게 깨지면 타입 추론은 한 단계 어려워진다.

(가) 선언 없이 일관 사용 + 함수 반환 타입 고정

Smalltalk처럼 변수는 선언 안 하지만 같은 이름은 같은 타입으로 일관되게 쓰여야 하는 언어. a ← b × 3.14159를 보면 b는 숫자이고 a는 소수를 담을 수 있는 타입임을 추론할 수 있다. 함수 반환 타입이 항상 같다는 보장이 있다면, 타입의 격자(lattice) 위에서 고정점 반복(iterative fixed-point)으로 풀린다.

(나) 함수 반환 타입이 인자에 따라 달라질 때

Scheme의 map: (α → β) × list of α → list of β 같은 매개변수 다형성이 들어오면 단순 고정점 반복으로는 부족하다. 고전적 접근은 유니피케이션(unification, 5장에서 다시 등장)이다.

(다) 동적 타입 변경

APL처럼 같은 식이 한 번은 정수 곱셈, 다음은 다차원 부동소수 배열 연산일 수 있다면 컴파일러는 사실상 인터프리터 모드로 떨어진다. 다만 똑똑한 APL 시스템은 "이 지점에서 타입이 바뀔 수 있는가?"를 정적으로 분석해 불필요한 검사를 제거(check elimination, check motion)한다.

4.5.2 결합법칙 바꾸기 — 좌재귀 vs 우재귀

3장에서 봤듯 좌재귀 문법은 자연스럽게 좌결합 트리를, 우재귀 문법은 우결합 트리를 만든다. 같은 다섯 원소 리스트라도

좌재귀:  ((((elt₁ elt₂) elt₃) elt₄) elt₅)
우재귀:  (elt₁ (elt₂ (elt₃ (elt₄ elt₅))))

구문 주도 액션을 영리하게 짜면 좌재귀 문법으로 우결합 트리를 만들거나 그 반대도 할 수 있다. 트릭 하나는 ε-생성으로 리스트 헤더 노드를 잠깐 만들어 두고, 끝에서 헤더를 제거하는 방식이다.

List → ε             { $$ ← MakeListHeader() }
     | List elt      { $$ ← AddToEnd($1, $2) }
Quux → List          { $$ ← RemoveListHeader($1) }

좌재귀 문법으로 LR(1) 파싱을 하면서 결과는 우결합(또는 정해진 순서) 리스트로 만들 수 있다. ε-생성 한 번의 작은 비용으로 결합법칙을 자유롭게 바꾼다.

4.6 정리

2장과 3장이 보여줬던 깔끔한 자동화 — 정규 표현 → 스캐너, CFG → 파서 — 가 4장에서는 약간 흐트러진다. 문맥 의존 분석에서는 형식주의가 임시방편을 완전히 대체하지 못했다. 두 갈래가 공존한다.

현실의 컴파일러는 보통 ad hoc SDT를 골라 한 번의 파스에서 IR 만들기, 타입 추론, 심볼 테이블 채우기, 저장소 할당까지 동시에 처리한다. 이유는 단순하다 — 컴파일 시간이 빠르고, 이미 yacc/bison 같은 툴이 그 모델을 강력히 지원하기 때문이다.

속성 문법은 학술적으로 풍부하고 깔끔한 부분 문제(완전 합성, 또는 완전 상속만 쓰는)에 잘 맞지만, 실무에서는 그 우아함이 비국소 정보 전달과 저장 관리 비용으로 빠르게 침식된다. 이론과 실전의 갈등을 가장 솔직하게 보여주는 장이다.