1. 인터프리터 구현 with Java

게시 2024/05/01

By Gyu Hwan 6 분읽는 시간

이번 글은 서적을 참고하여 자바를 이용한 인터프리터 구현 및 정리이다.

언어의 구성 요소

프로그래밍 언어를 구현하는 과정은 복잡하지만, 몇 가지 기본적인 단계로 나눌 수 있다. 이 과정은 원시(raw) 소스 텍스트에서 시작하여, CPU가 이해할 수 있는 로우레벨 코드로 변환하는 것을 목표로 합니다. 아래는 자바 소스 코드의 간단한 예시이다

  
class Foods {
  private int count; 
}

1. 렉싱(lexing) or 스캐닝(scanning)

렉싱(lexing)이란, 원시 소스 텍스트를 토큰(token)이라는 더 작은 단위로 분리하는 과정이다. 토큰으로 분리함으로써 식별자, 예약어, 리터럴 값을 구분할 수 있게 된다. 자바 예시 코드를 토큰으로 분류한다면 다음과 같다.

토큰 : class, Foods, {, private, int, count, ;, }

일반적으로 공백문자는 무시한다. 공백 문자도 처리하도록 할 수 있는데. 코드 스타일 분석 도구나 들여쓰기가 중요한 경우, 공백 문자도 토큰으로 표현한다.

2. 파싱(Parsing)

다음 단계는 파싱으로 분류된 토큰을 하나의 표현식이나 문장으로 만드는 과정이다. 파서는 일련의 토큰을 받아 트리 구조로 만든다. 위의 예시로는 class 를 루트로 하고 Foods 를 클래스 이름으로, { .. } 내부를 클래스 바디로 갖는 구조로 생성할 수 있다.

3. 정적 분석

파싱으로 만들어진 구문 트리를 검사하여 의미적 오류가 없는지 확인하는 단계다. 정적 타입 언어는 이 단계에서 타입 검사(type checking) 를 실시한다.

4. 중간 표현(IR, Intermediate Representation)

인터프리터는 최적화와 실행을 위해서 중간 표현을 생성하는데. 중간 표현은 원시 소스나 타깃 아키텍처 어느 쪽에도 속하지 않는다. 이 단계가 징검다리 역할을 하여 다양한 아키텍처를 지원할 수 있는데. 이를테면 x86, ARM, SPARC 아키텍처에서 실행되는 컴파일러를 개발하는데 IR이 있음으로서 이전 단계를 생략 가능해진다.

5. 최적화

최적화란 컴파일러 성능을 향상시키기 위한 작업을 의미하는데. 이 과정은 선택적이다. 성공한 언어들은 대부분 컴파일 타임 최적화를 하지 않는다. 그럼에도 최적화를 한다면 다음과 같은 방법들이 있다.

상수 폴딩(constant folding)

다음과 같은 코드가 여러 개라고 해보자

  
pennyArea = 3.14159 * (0.75/2) * (0.75/2)

컴파일러는 이 산술식을 계산하여 모두 변경한다.

  
pennyArea = 0.4417860938;

루프 언롤링(Loop Unrolling)

  
for(int i = 0; i < n; i++) {
 array[i] = 0;
}

한 번에 여러 단계를 동시에 처리해서 반복 횟수를 줄인다.

  
for (int i = 0; i < n; i += 4) {
    array[i] = 0;
    array[i + 1] = 0;
    array[i + 2] = 0;
    array[i + 3] = 0;
}

공통 서브식 제거

  
int a = b * c + g;
int d = b * c * e;

이 코드는 b * c 식이 동일하게 포함된 것을 확인할 수 있는데. 미리 계산하여 최적화를 진행할 수 있다.

  
int temp = b * c;
int a = temp + g;
int d = temp * e;

6. 코드 생성

이 단계에서는 소스 코드를 기계가 실핼할 수 있는 형태로 변환한다. 이는 CPU가 직접 실행할 수 있는 기계어 코드나 어셈블리 언어와 유사한 형태를 말한다.

코드는 크게 두 가지 형태로 변환될 수 있다.

실제 CPU 명령어: 이는 특정 하드웨어 아키텍처에 맞춰진 명령어로, 각 아키텍처에 대한 별도의 컴파일러가 필요
가상 CPU 명령어: 이는 실제 하드웨어와는 독립적인 가상 머신용 코드를 생성한다. 이러한 코드를 바이트코드(bytecode)라고 하며, 자바 가상 머신(JVM)이 대표적인 예이다.

자바를 기준으로 바이트코드는 가상 머신이나 JIT 컴파일러(Just-In-Time Compiler)에 의해 실행 시점에 네이티브 코드로 변환된다. 이 과정을 통해 동일한 바이트코드로 다양한 플랫폼에서 실행이 가능해진다. (이식성)

Interpreter, Java

Interpreter