[PLT] Semantic Analysis (의미 분석)

Semantic Analysis, 의미 분석, symbol table, 심볼 테이블, scope resolution, name resolution, type checking, lexical scope, dynamic scope, shadowing

정의

Semantic Analysis (의미 분석) 는 파서가 생성한 AST 를 검사하여 문법적으로 올바르지만 의미상 오류인 경우 를 발견하고, 각 이름 (identifier) 이 무엇을 가리키는지 결정하는 단계입니다.

한 줄 요약: “코드가 문법적으로 맞는 건 알겠는데, 말이 되나?”

무엇을 검사하는가

파서가 통과시킨 것들:

undefinedVar + 1        // 정의되지 않은 변수
"hello" * 3             // 잘못된 타입 (문자열 * 숫자? 파이썬은 가능, JS 는?)
myFunc()                // 함수 없음
const x = 1; x = 2;     // const 재할당
return 42;              // 함수 밖 return

파서는 이런 것을 발견 못 함. Semantic analyzer 가:

• 이름 해석: 각 identifier 가 어떤 declaration 을 가리키는지
• Scope 규칙: 어느 변수가 여기서 보이는지
• 타입 검사: 값의 타입이 문맥에 맞는지
• 컨트롤 흐름: return 이 함수 안에 있는지, break 가 루프 안에 있는지
• 접근 제어: private 필드 접근 금지, immutable 재할당 금지

Symbol Table

이름 → 정보 매핑. Semantic analyzer 의 핵심 자료구조.

각 심볼의 정보:

• 이름
• 종류 (variable, function, class, module)
• 타입
• 선언 위치
• 가시성 (scope)
• 속성 (const, static, private)

interface Symbol {
  name: string;
  kind: 'variable' | 'function' | 'class' | 'parameter';
  type: Type;
  declLocation: SourceLocation;
  isConst: boolean;
  isExported: boolean;
}

class SymbolTable {
  private scopes: Map<string, Symbol>[] = [new Map()];

  enterScope() { this.scopes.push(new Map()); }
  exitScope() { this.scopes.pop(); }

  declare(sym: Symbol) {
    const current = this.scopes[this.scopes.length - 1];
    if (current.has(sym.name)) {
      throw new Error(`Duplicate declaration: ${sym.name}`);
    }
    current.set(sym.name, sym);
  }

  lookup(name: string): Symbol | undefined {
    for (let i = this.scopes.length - 1; i >= 0; i--) {
      if (this.scopes[i].has(name)) {
        return this.scopes[i].get(name);
      }
    }
    return undefined;
  }
}

Scope (범위)

Scope: 한 이름이 유효한 코드 영역.

Lexical Scope (정적 스코프)

소스 코드의 위치로 결정. 대부분 언어 (JavaScript, Python, Rust, Java, C).

function outer() {
  const x = 1;
  function inner() {
    console.log(x);   // ← outer 의 x
  }
  inner();
}

inner 안의 x 는 정의 시점의 outer 를 가리킴 (lexical).

Dynamic Scope (동적 스코프)

호출 시점의 스택 으로 결정. 초기 Lisp, Emacs Lisp, Perl local 등.

(defun outer () (let ((x 1)) (inner)))
(defun inner () (print x))    ; ← 호출한 outer 의 x

대부분 언어는 lexical scope. Dynamic scope 는 예측 어려워 지양.

Nested Scope

Scope 는 중첩 가능. 안쪽 scope 가 바깥 참조 가능:

Global scope
  └── Module scope
        └── Function scope
              └── Block scope
                    └── (nested block)

이름 해석: 가장 안쪽부터 바깥으로 확인.

Shadowing (섀도잉)

내부 scope 가 외부 이름을 가림:

const x = 1;
{
  const x = 2;    // 바깥 x 를 가림
  console.log(x); // 2
}
console.log(x);   // 1

Rust 는 shadowing 을 명시적 언어 기능 으로:

let x = 5;
let x = "hello";   // 다른 타입도 가능

Python 은 함수 scope 안에서만 shadowing.

이름 해석 알고리즘

각 identifier 참조를 declaration 에 연결.

resolve(node, symbolTable):
    switch node.kind:
        case Identifier:
            sym = symbolTable.lookup(node.name)
            if sym is None:
                error(f"Undefined: {node.name}")
            node.resolvedSymbol = sym

        case VariableDeclaration:
            resolve(node.init, symbolTable)
            sym = Symbol(name=node.name, type=...)
            symbolTable.declare(sym)

        case Block:
            symbolTable.enterScope()
            for stmt in node.statements:
                resolve(stmt, symbolTable)
            symbolTable.exitScope()

        case Function:
            fn = FunctionSymbol(...)
            symbolTable.declare(fn)
            symbolTable.enterScope()
            for param in node.params:
                symbolTable.declare(param)
            resolve(node.body, symbolTable)
            symbolTable.exitScope()

Hoisting (호이스팅)

일부 언어 (JavaScript) 는 선언을 scope 상단으로 끌어올림:

console.log(foo());   // OK, 호이스팅
function foo() { return 1; }

console.log(x);       // undefined (var 는 호이스팅되지만 값 아님)
var x = 5;

console.log(y);       // ReferenceError (let 은 TDZ)
let y = 5;

Semantic analyzer 는 두 pass:

1. 선언 수집 pass: block 전체를 훑어 선언 등록
2. 참조 해석 pass: 표현식의 identifier 해석

TypeScript, Rust 는 이 방식 (선언 순서와 무관하게 참조 가능).

Type Checking

각 표현식의 타입 을 결정하고 문맥에 맞는지 확인.

const x: number = "hello";   // 오류: string 을 number 에
add("hello", 1);              // 오류 여부는 언어 나름

간단한 규칙:

• NumberLiteral: type = number
• StringLiteral: type = string
• BinaryOp(+):
  • number + number → number
  • string + string → string
  • number + string → 언어별 (JS 는 coercion, Python 은 오류, Rust 는 오류)

Type inference (Hindley-Milner, TypeScript, Rust): 명시 없이도 타입 추론. 자세한 것은 Type Systems 참조.

Control Flow Check

• return 이 함수 안?
• break / continue 가 loop / switch 안?
• 모든 경로가 return 하는가? (noImplicitReturns)
• 예외 처리 (throws 선언 vs actual throw)

checkReturn(node, insideFunction=false):
    switch node.kind:
        case ReturnStatement:
            if not insideFunction:
                error("'return' outside function")
        case FunctionDeclaration:
            checkReturn(node.body, insideFunction=True)
        case Block:
            for stmt in node.statements:
                checkReturn(stmt, insideFunction)

상수 검사

const 는 재할당 금지:

const x = 1;
x = 2;    // 오류

const arr = [];
arr.push(1);   // OK (내부 변경, 재할당 X)

Semantic analyzer 는 const 변수의 재할당 사이트 를 검사.

Symbol Table 구현 전략

Chained Hash Tables

각 scope 가 별도 map, 안쪽 → 바깥 순회.

Flat + Depth

하나의 map 에 (name, depth) 키. 스코프 depth 로 shadowing.

Persistent (Immutable)

각 scope 변화가 새 map. 함수형 언어에 자연스러움.

오류 메시지 개선

좋은 semantic error:

error[E0425]: cannot find value `undefined_var` in this scope
  --> src/main.rs:5:9
   |
 5 |     let x = undefined_var + 1;
   |             ^^^^^^^^^^^^^ not found in this scope
   |
   = help: did you mean `undefined_val`?

• 유사 이름 제안 (Levenshtein distance)
• Import 제안
• 정의 위치 표시

Rust 컴파일러가 이 방면 최상.

두 언어의 대비

JavaScript (동적 타입, hoisting)

• 대부분 검사는 런타임
• undefined_var 는 파싱/semantic 통과, 런타임 ReferenceError
• Static analysis 는 ESLint, TypeScript 가 담당

Rust (정적 타입, ownership 검사)

• 매우 엄격한 semantic 분석
• Ownership + borrow checking (semantic 안)
• 컴파일 오류가 대부분 실제 버그

Semantic Analysis 결과

AST 에 정보 주석 (annotated AST):

interface AnnotatedIdentifier extends Identifier {
  resolvedSymbol: Symbol;   // 이 identifier 가 가리키는 declaration
  inferredType: Type;
}

이후 단계 (IR 생성, 최적화, 코드 생성) 가 이 정보 활용.

함정

관련 위키

• PLT 개요
• Lexical Analysis
• Parsing
• AST
• Type Systems
• Interpreter vs Compiler
• IR & Code Gen
• TypeScript Strict Mode
• JavaScript Lexical Environment