이론에서 실제로

지금까지 유한 오토마타, 정규 표현식, 문맥 자유 문법, 푸시다운 오토마타를 다루었다. 이 이론들이 컴파일러의 특정 단계에 대응된다는 점을 간간이 언급했는데, 이제 전체 그림을 살펴볼 차례이다. 컴파일러는 소스 코드를 기계어로 변환하는 프로그램이지만, 이 변환은 단일 과정이 아니라 여러 단계가 체계적으로 결합된 파이프라인이다. 각 단계가 왜 필요하고, 왜 이런 순서로 배치되어 있는지를 이해하면 컴파일러 설계의 논리가 분명해진다.

컴파일러의 전체 구조

컴파일러의 처리 과정은 크게 프런트엔드(Frontend)와 백엔드(Backend)로 나뉘며, 그 사이를 중간 표현(Intermediate Representation, IR)이 연결한다.

소스 코드
  │
  ▼
┌─────────────────────────┐
│       프런트엔드          │
│  ┌───────────────────┐  │
│  │  어휘 분석 (Lexing) │  │
│  └────────┬──────────┘  │
│  ┌────────▼──────────┐  │
│  │  구문 분석 (Parsing)│  │
│  └────────┬──────────┘  │
│  ┌────────▼──────────┐  │
│  │  의미 분석          │  │
│  └────────┬──────────┘  │
└───────────┼─────────────┘
  ┌─────────▼─────────┐
  │   중간 표현 (IR)    │
  └─────────┬─────────┘
┌───────────┼─────────────┐
│       백엔드            │
│  ┌────────▼──────────┐  │
│  │  최적화             │  │
│  └────────┬──────────┘  │
│  ┌────────▼──────────┐  │
│  │  코드 생성          │  │
│  └───────────────────┘  │
└─────────────────────────┘
  │
  ▼
목적 코드

이 구조가 임의로 정해진 것이 아니다. 각 단계는 이전 단계의 출력을 입력으로 받아 더 높은 수준의 분석을 수행하며, 이렇게 단계를 분리함으로써 각 단계를 독립적으로 설계하고 최적화할 수 있게 되는 것이다.

어휘 분석 — 렉서

컴파일러가 소스 코드를 처리하는 첫 번째 단계는 어휘 분석(Lexical Analysis)이다. 렉서(Lexer)라고 불리는 이 단계에서는 문자 스트림을 토큰(Token)이라는 의미 있는 단위로 분리한다. 예를 들어 int x = 42;라는 소스 코드는 int(키워드), x(식별자), =(연산자), 42(정수 리터럴), ;(구분자)라는 다섯 개의 토큰으로 분해된다.

이전 포스트에서 다룬 것처럼, 렉서는 본질적으로 유한 오토마타이다. 각 토큰 종류를 정규 표현식으로 정의하고, 이를 DFA로 변환하여 입력을 스캔한다. 공백이나 주석 같은 의미 없는 문자는 이 단계에서 제거되어 이후 단계의 부담을 줄인다. 렉서가 별도의 단계로 분리되어 있는 이유는 문자 수준의 처리와 구조 수준의 처리를 혼합하면 복잡도가 급격히 증가하기 때문이다.

구문 분석 — 파서

렉서가 생성한 토큰 스트림을 입력으로 받아 프로그램의 구조를 분석하는 단계가 구문 분석(Syntax Analysis)이다. 파서(Parser)는 토큰 시퀀스가 프로그래밍 언어의 문법에 맞는지 검증하고, 맞다면 파스 트리 또는 추상 구문 트리(Abstract Syntax Tree, AST)를 생성한다.

파서는 본질적으로 푸시다운 오토마타이다. 문맥 자유 문법을 기반으로 동작하며, 스택을 사용하여 중첩된 구조를 추적한다. 파싱 전략은 크게 두 가지로 나뉜다. 하향식(Top-Down) 파싱은 시작 기호에서 출발하여 입력을 유도해 나가는 방식으로, LL 파서가 여기에 해당한다. 상향식(Bottom-Up) 파싱은 입력 토큰에서 출발하여 시작 기호를 향해 축약해 나가는 방식으로, LR 파서가 대표적이다. 어떤 방식이든 파서가 수행하는 작업은 토큰의 선형 시퀀스를 계층적 구조로 변환하는 것이다.

의미 분석

구문적으로 올바른 프로그램이라고 해서 반드시 의미적으로도 올바른 것은 아니다. int x = "hello";는 C 언어의 문법에는 부합하지만 타입이 맞지 않는다. 이런 검사를 수행하는 것이 의미 분석(Semantic Analysis) 단계이다.

의미 분석에서는 심볼 테이블(Symbol Table)을 구성하여 변수와 함수의 선언 정보를 관리하고, 타입 검사(Type Checking)를 수행하며, 변수가 선언되기 전에 사용되었는지, 함수 호출의 인자 수가 맞는지 같은 문맥 의존적 규칙을 검증한다. 이전 포스트에서 문맥 자유 문법의 범위를 넘어서는 규칙이 있다고 언급했는데, 그 규칙들이 바로 이 단계에서 처리되는 것이다.

중간 표현의 역할

프런트엔드와 백엔드 사이에 중간 표현(IR)을 두는 이유는 무엇인가? 이 설계 결정은 컴파일러 공학에서 가장 중요한 아이디어 중 하나이다.

만약 IR 없이 소스 언어에서 직접 목적 코드를 생성한다면, M개의 소스 언어와 N개의 목적 기계에 대해 M×N개의 컴파일러를 만들어야 한다. 그러나 공통 IR을 도입하면 M개의 프런트엔드와 N개의 백엔드, 총 M+N개의 모듈만 구현하면 된다. 새로운 소스 언어를 지원하려면 프런트엔드만 추가하면 되고, 새로운 목적 기계를 지원하려면 백엔드만 추가하면 되는 것이다.

LLVM이 이 원리의 가장 성공적인 구현 사례이다. LLVM IR이라는 공통 중간 표현을 기반으로 C, C++, Rust, Swift 등 다양한 언어의 프런트엔드가 존재하며, x86, ARM, RISC-V 등 다양한 아키텍처의 백엔드가 존재한다. 새로운 언어나 아키텍처를 추가할 때 전체 컴파일러를 처음부터 만들 필요가 없는 것이다.

최적화

최적화(Optimization) 단계에서는 IR 수준에서 프로그램의 성능을 개선하는 변환을 수행한다. 상수 폴딩(컴파일 시점에 계산 가능한 수식을 미리 계산), 죽은 코드 제거(실행되지 않는 코드 삭제), 루프 최적화(반복문의 효율 개선), 인라이닝(함수 호출을 함수 본문으로 대체) 등이 대표적인 최적화 기법이다.

최적화가 IR 수준에서 수행되는 이유는 소스 언어에도 목적 기계에도 의존하지 않는 변환을 한 곳에서 구현할 수 있기 때문이다. 물론 목적 기계에 의존하는 최적화(레지스터 할당, 명령어 스케줄링 등)도 있으며, 이는 코드 생성 단계에서 수행된다. 이처럼 최적화를 기계 독립적 최적화와 기계 의존적 최적화로 분리할 수 있는 것도 IR을 중심으로 한 단계 분리의 장점인 셈이다.

코드 생성

컴파일러의 마지막 단계는 최적화된 IR을 실제 목적 기계의 명령어로 변환하는 코드 생성(Code Generation)이다. 이 단계에서는 레지스터 할당(어떤 변수를 어떤 레지스터에 배치할 것인가), 명령어 선택(IR 연산을 어떤 기계 명령어로 변환할 것인가), 명령어 스케줄링(파이프라인 효율을 위한 명령어 순서 재배치) 같은 작업이 수행된다.

코드 생성기의 출력은 어셈블리 코드이거나 직접적인 기계어 바이너리이며, 이것이 최종적으로 운영체제에서 실행 가능한 프로그램이 된다.

단일 패스와 다중 패스

컴파일러의 구현 방식에 따라 단일 패스(Single-Pass)와 다중 패스(Multi-Pass)로 나눌 수 있다. 단일 패스 컴파일러는 소스 코드를 한 번만 읽으면서 렉싱, 파싱, 코드 생성을 동시에 수행한다. 메모리가 제한되었던 초기 컴퓨팅 시대에 유리했으며, 초기 C 컴파일러와 파스칼 컴파일러가 이 방식을 사용했다. C에서 함수를 사용하기 전에 선언해야 하는 규칙은 단일 패스 컴파일러의 제약에서 비롯된 것이다.

다중 패스 컴파일러는 소스 코드나 IR을 여러 번 순회하면서 각 패스에서 특정 작업을 수행한다. 현대의 대부분의 컴파일러는 다중 패스 방식을 채택한다. 각 패스가 하나의 관심사에 집중할 수 있으므로 구현이 깔끔해지고, 더 정교한 분석과 최적화가 가능해지기 때문이다.

컴파일러와 인터프리터

컴파일러와 인터프리터는 프로그래밍 언어를 실행하는 두 가지 접근 방식이다. 컴파일러가 소스 코드 전체를 목적 코드로 번역한 후 실행하는 반면, 인터프리터는 소스 코드를 한 문장씩 읽으며 즉시 실행한다. 컴파일러는 실행 전에 번역 시간이 필요하지만 실행 속도가 빠르고, 인터프리터는 즉시 실행할 수 있지만 실행 속도가 상대적으로 느리다.

현대의 많은 언어 구현체는 이 두 방식을 결합한다. Java는 소스 코드를 바이트코드로 컴파일하고, JVM이 바이트코드를 인터프리트하거나 JIT(Just-In-Time) 컴파일하여 실행한다. Python도 내부적으로 바이트코드로 컴파일한 후 가상 머신에서 실행한다. 순수한 컴파일러나 순수한 인터프리터보다는, 둘의 장점을 취하는 하이브리드 방식이 현대 언어 구현의 주류인 셈이다.

다음 포스트에서는 컴파일러의 첫 번째 실질적 구현 단계인 어휘 분석, 즉 렉서의 구체적인 구현 방법을 살펴본다.