오토마타와 컴파일러 10 - 의미 분석과 타입 검사

파서가 잡지 못하는 것들

지금까지 다룬 구문 분석은 프로그램이 문법적으로 올바른지를 판별하는 과정이었다. 파서가 구문 트리를 성공적으로 만들어냈다면, 해당 프로그램은 문법 규칙에 부합하는 셈이다. 그런데 문법적으로 올바른 프로그램이 반드시 의미적으로도 올바른 것일까? 그렇지 않다.

int x = "hello";라는 코드를 생각해 보자. 변수 선언과 초기화라는 문법 구조를 완벽하게 따르고 있으므로 파서는 아무런 문제 없이 구문 트리를 생성한다. 그러나 정수형 변수에 문자열을 대입하는 것은 의미적으로 모순이다. 선언되지 않은 변수를 사용하거나, 함수에 잘못된 수의 인자를 전달하거나, 호환되지 않는 타입끼리 연산하는 경우도 마찬가지이다. 이러한 오류들은 문맥 자유 문법의 범위를 벗어나기 때문에 파서가 아닌 별도의 단계에서 검출해야 한다. 그 단계가 바로 의미 분석(Semantic Analysis)이다.

의미 분석기는 구문 트리를 순회하면서 프로그램의 의미적 일관성을 검증한다. 구체적으로 변수가 사용되기 전에 선언되었는지, 타입이 서로 호환되는지, 함수 호출의 인자 수와 타입이 정의와 일치하는지 등을 확인하는 것이다.

심볼 테이블과 스코프

의미 분석의 핵심 자료 구조는 심볼 테이블(Symbol Table)이다. 심볼 테이블은 프로그램에 등장하는 모든 식별자(변수, 함수, 타입 등)에 대한 정보를 저장하는 사전이다. 각 항목은 이름, 타입, 스코프, 메모리 위치 같은 속성을 포함한다.

심볼 테이블 예시:
┌──────────┬──────────┬────────┬──────────┐
│   이름   │   타입   │ 스코프 │   종류   │
├──────────┼──────────┼────────┼──────────┤
│ x        │ int      │ main   │ 변수     │
│ y        │ float    │ main   │ 변수     │
│ add      │ int→int  │ global │ 함수     │
│ i        │ int      │ for    │ 변수     │
└──────────┴──────────┴────────┴──────────┘

프로그래밍 언어에서 스코프(Scope)는 식별자가 유효한 범위를 결정한다. 대부분의 언어는 중첩된 스코프를 지원하며, 안쪽 스코프에서 바깥쪽 스코프의 식별자에 접근할 수 있다. 이를 처리하기 위해 심볼 테이블은 체인 구조나 스택 구조로 구현되는 것이 일반적이다.

새로운 블록에 진입하면 새 스코프를 생성하고, 블록을 빠져나오면 해당 스코프를 제거한다. 변수를 참조할 때는 현재 스코프에서 먼저 찾고, 없으면 바깥 스코프를 순서대로 탐색한다. 이 과정을 스코프 해석(Scope Resolution)이라고 부른다.

global scope
├── int g = 10
└── function main()
    ├── int x = 5          ← main scope
    ├── if (x > 0)
    │   └── int y = x + g  ← if scope (x는 main에서, g는 global에서 해석)
    └── print(y)           ← 오류: y는 if 블록 안에서만 유효

위 예시에서 y는 if 블록 내부에서 선언되었으므로, 블록 밖에서 y를 참조하면 의미 분석기가 "선언되지 않은 변수" 오류를 발생시킨다. 파서는 print(y)의 구문 자체에는 문제가 없다고 판단하지만, 의미 분석기는 y가 해당 스코프에서 보이지 않는다는 사실을 심볼 테이블을 통해 감지하는 것이다.

타입 검사

의미 분석에서 가장 중요한 작업은 타입 검사(Type Checking)이다. 타입 검사는 프로그램의 각 식과 문장에서 타입이 일관되게 사용되고 있는지를 검증한다.

타입 검사는 크게 정적 타입 검사(Static Type Checking)와 동적 타입 검사(Dynamic Type Checking)로 나뉜다. 정적 타입 검사는 컴파일 시점에 수행되며, C, Java, Rust 같은 언어가 이 방식을 채택한다. 동적 타입 검사는 실행 시점에 수행되며, Python, JavaScript, Ruby 같은 언어에서 사용된다.

과연 정적 타입 검사가 동적 타입 검사보다 항상 우월한 것일까? 반드시 그렇지는 않다. 정적 타입 검사는 실행 전에 많은 오류를 잡아낼 수 있어서 프로그램의 안전성을 높이지만, 표현력에 제약이 따른다. 동적 타입 검사는 유연성이 높지만 런타임에서야 오류를 발견하게 되는 비용이 있다. 각 접근 방식은 서로 다른 트레이드오프를 가지고 있으며, 컴파일러 설계자는 이를 인식한 위에서 선택을 내리는 것이다.

타입 검사기는 구문 트리를 아래에서 위로 순회하면서 각 노드의 타입을 결정한다. 리프 노드(상수, 변수)의 타입은 직접 알 수 있고, 내부 노드(연산자, 함수 호출)의 타입은 자식 노드들의 타입으로부터 추론한다.

    [+] : int              ← 자식이 모두 int이므로 결과도 int
   / \
  /   \
[x]:int  [3]:int           ← 리프 노드의 타입은 심볼 테이블과 리터럴에서 결정

    [+] : 오류!            ← int와 string은 더할 수 없음
   / \
  /   \
[x]:int  ["hi"]:string

타입 추론

모든 변수에 명시적으로 타입을 적어야 하는 것은 번거로운 일이다. 현대 언어들은 타입 추론(Type Inference)을 통해 프로그래머가 타입을 생략해도 컴파일러가 스스로 타입을 결정할 수 있게 한다. auto x = 42;라고 쓰면 컴파일러는 42가 정수 리터럴이므로 x의 타입을 int로 추론하는 것이다.

단순한 타입 추론은 초기화 식의 타입을 그대로 변수에 부여하는 것으로 충분하지만, 제네릭이나 고차 함수가 관여하면 상황이 복잡해진다. Hindley-Milner 타입 추론 알고리즘은 ML, Haskell 같은 언어에서 사용되며, 유니피케이션(Unification)이라는 기법을 통해 타입 변수들 사이의 관계를 풀어나간다. 이 알고리즘은 프로그래머가 타입 어노테이션을 전혀 쓰지 않아도 모든 식의 타입을 결정할 수 있다는 점에서 이론적으로도 매우 중요한 결과이다.

속성 문법과 파싱 중 의미 처리

의미 분석을 구문 분석과 완전히 분리하여 별도의 패스로 수행할 수도 있지만, 실제 컴파일러에서는 구문 분석 도중에 의미 처리를 함께 수행하는 경우가 많다. 이를 체계화한 것이 속성 문법(Attribute Grammar)이다.

속성 문법에서는 문법의 각 기호에 속성을 부여하고, 생성 규칙에 의미 규칙을 추가한다. 속성은 합성 속성(Synthesized Attribute)과 상속 속성(Inherited Attribute)으로 나뉜다. 합성 속성은 자식 노드에서 부모 노드로 전파되고, 상속 속성은 부모 노드에서 자식 노드로 전파된다.

생성 규칙:     E → E₁ + T
의미 규칙:     E.type = if (E₁.type == int && T.type == int) then int
                        else if (E₁.type == float || T.type == float) then float
                        else error

위 규칙은 덧셈 식의 타입을 결정하는 의미 규칙이다. 양쪽 피연산자가 모두 정수이면 결과도 정수이고, 하나라도 실수이면 결과는 실수이며, 그 외의 조합은 타입 오류가 된다. 이런 방식으로 파싱과 동시에 타입 정보를 계산할 수 있는 것이다.

Yacc/Bison 같은 파서 생성기에서는 생성 규칙에 의미 동작(Semantic Action)을 삽입하여 이를 구현한다. $$ = check_type($1, $3);과 같은 코드가 생성 규칙에 포함되며, 파서가 해당 규칙을 적용할 때마다 이 코드가 실행되어 심볼 테이블을 업데이트하거나 타입을 검사한다.

흔한 의미 오류들

의미 분석기가 검출하는 대표적인 오류들을 정리하면 다음과 같다.

오류 유형	예시	설명
미선언 변수	`x = 5;` (x 미선언)	심볼 테이블에 없는 식별자 참조
중복 선언	`int x; int x;`	같은 스코프에서 동일 이름 재선언
타입 불일치	`int x = "hello";`	대입 양변의 타입 불일치
인자 수 불일치	`add(1, 2, 3)` (add는 2인자)	함수 정의와 호출의 인자 수 차이
반환 타입 불일치	`int f() { return "hi"; }`	선언된 반환 타입과 실제 반환 값 불일치
잘못된 연산	`"hello" - "world"`	해당 타입에 정의되지 않은 연산

이 오류들은 모두 구문적으로는 합법적이지만 의미적으로는 잘못된 프로그램에서 발생한다. 파서만으로는 이들을 걸러낼 수 없으며, 심볼 테이블과 타입 규칙이라는 추가 정보가 있어야 비로소 감지할 수 있는 것이다.

의미 분석은 프런트엔드의 마지막 관문이다. 이 단계를 통과한 프로그램은 문법적으로도, 의미적으로도 올바르다고 판단된 것이며, 컴파일러는 이제 이 프로그램을 안전하게 변환할 수 있다. 다음 포스트에서는 그 변환의 첫 단계인 중간 표현과 최적화를 살펴본다.