Skip to content

태그: 컴파일러

총 16개의 글이 있습니다.

객체 표현과 GC

객체 표현은 언어의 값을 메모리에 어떤 모양으로 담을지를 정하는 설계이고, 값의 수명을 누가 어떻게 끝낼지가 그 설계에 딸려 나온다. 값의 종류가 닫혀 있는지 열려 있는지가 두 선택을 함께 결정한다. 정적 타입 언어는 정수를 기계 워드 하나로 담는다. 컴파일 시점에 이게 정수라는 걸 알기 때문에 타입 정보를 실행 중에 들고 다닐 필요가 없다. 동적 타입 언어는 그럴 수 없다. 값이 어디로 흘러가든 자기가 무엇인지 스스로 알고 있어야 한다. CPython은 모든 값을 힙 객체로 만들고 `PyObject *` 하나로 가리킨다. 아래는 main(3.16.0a0) 기준이고 측정은 3.14.6에서 했다. 모든 값이 객체다 객체의 머리는 참조 카운트와 타입 포인터다. c struct _object {

컴파일러 생성기

컴파일러 생성기는 명세를 입력으로 받아 컴파일러의 한 단계를 코드로 만들어 내는 도구다. 사람은 "무엇을 인식할 것인가"만 적고, "어떻게 인식할 것인가"에 해당하는 표와 루프는 기계가 채운다. 이런 도구가 성립하려면 그 단계가 기계적으로 유도 가능한 형태여야 한다. 정규표현에서 DFA를 만드는 절차가 있고 문법에서 파싱표를 만드는 절차가 있기 때문에 렉서와 파서에 생성기가 있는 것이지, 컴파일러의 모든 단계에 있는 것이 아니다. 명세와 산출물 주요 생성기의 입출력을 실제로 재 보면 규모의 차이가 드러난다. flex와 bison은 직접 돌린 결과이고, 나머지는 CPython main(3.16.0a0) 저장소의 파일이다. | 생

펌핑 보조정리

펌핑 보조정리는 어떤 언어가 정규언어가 아님을 보이는 도구다. 유한한 상태로는 무한한 구별을 할 수 없다는 사실을, 문자열을 늘려 보는 절차로 바꿔 놓은 것이다. DFA(Deterministic Finite Automaton, 결정적 유한 오토마타)의 상태는 말 그대로 유한하다. 그러므로 충분히 긴 문자열을 읽는 동안에는 같은 상태를 두 번 지날 수밖에 없다. 상태가 `p`개면 `p`개보다 긴 문자열을 읽는 사이에 반드시 하나가 반복된다. q₀ ──x──▶ q ──y──▶ q ──z──▶ (종료상태) └────────┘ 같은 상태로 돌아온다 `y`가 상태를 제자리로 되돌리므로, 기계는 `y`를 몇 번 돌았는지 알지 못한다. `xz`, `xyz`, `

Context-sensitive Lexing

문맥 의존 렉싱은 토큰의 경계나 종류가 앞뒤 문맥에 따라 달라지는 경우를 처리하는 것이다. 렉서는 정규표현으로 기술되고 유한 오토마타로 구현된다는 것이 원칙이지만, 실제 언어에는 그 전제가 깨지는 곳이 많다. CPython의 토크나이저 상태 구조체가 얼마나 커졌는지를 보면 그 규모가 드러난다. c struct tok_state { char *buf, *cur, *inp; const char *end, *start; int done, tabsize, indent; int indstack[MAXINDENT]; // 들여쓰기 스택 int atbol, pendin; // 줄 시작 여부, 밀린 INDEN

렉서(어휘분석기, 스캐너)는 원시 프로그램을 문자 단위로 읽어 토큰이라는 문법 단위로 자르는 단계이다. 토큰의 형태는 정규표현으로 기술되고 정규표현이 나타내는 언어는 유한 오토마타가 인식하므로, 렉서의 실체는 DFA 하나를 돌리는 일이다. 구현이 갈리는 지점은 그 DFA를 사람이 짜느냐 생성하느냐다. 일반적인 프로그래밍 언어가 쓰는 토큰은 크게 다섯 종류가 있다. 식별자(`sum`, `a`, `b`), 상수(`1`, `3.14`, `"abc"`), 예약어(`if`, `while`, `return`), 연산자(`+`, `-`, `*`, `==`), 구분자(`(`, `[`, `;`, `,`)다. 전부 정규표현으로 적을 수 있다. 중첩 괄호처럼 세는 능력이 필요한 것은 여기 없다. 그래서 렉서는 스택 없이 상

LR 파싱은 입력을 왼쪽에서 오른쪽(Left to right)으로 읽으면서 우단유도(Right parse)를 역순으로 복원하는 상향식 구문분석 기법이다. 하향식 파싱은 시작기호에서 출발해 문법규칙을 적용하며 입력 문자열까지 내려온다. LR은 반대로 간다. 입력 토큰에서 출발해 규칙의 오른쪽을 왼쪽으로 되돌리며 시작기호까지 올라간다. 이 되돌리는 동작을 reduce라고 한다. E → E + T | T 입력: id + id * id T → T * F | F F → ( E ) | id 하향식은 `E`부터 시작해 `E + T`, `T + T`… 로 펼쳐 나가고, 상향식은 `id`부터 시작해 `F`, `T`, `E`… 로 접어 나간다. handle과 shif

유한 오토마타는 유한한 개수의 상태만으로 문자열을 인식하는 기계이고, 정규표현이 나타내는 언어와 정확히 같은 범위를 인식한다. DFA와 NFA는 그 두 가지 형태로, 표현력은 같지만 실행 비용과 만들기 쉬운 정도가 다르다. 렉서 생성기가 정규표현을 받아 스캐너를 뱉는 과정이 결국 이 둘 사이의 변환이다. 정규표현 → ε-NFA → DFA → 최소화된 DFA 만들기 쉽다 실행이 싸다 표가 작다 유한 오토마타 형식적으로는 다섯 개의 구성원소로 정의한다. M = (Q, Σ, δ, q₀, F) Q : 상태들의 유한집합 Σ : 입력기호들의 유한집합 δ : 상태전이함수 q₀ : 시작상태, q₀ ∈ Q F : 종료상태들의 집합, F ⊆ Q `

Pratt 파싱(top-down operator precedence)은 연산자 우선순위를 문법 규칙의 계층이 아니라 토큰에 붙은 정수 하나로 표현하는 하향식 파싱 기법이다. 무엇이 문제였는지부터 보는 게 빠르다. 재귀 하강으로 표현식을 파싱하면 우선순위 단계마다 함수를 하나씩 만들어야 한다. expression → equality equality → comparison (('==' | '!=') comparison)* comparison → sum (('') sum)* sum → term (('+' | '-') term)* term → factor (('*' | '/') factor)* factor → ('-' | '!') factor | primary prima

문법 변환은 같은 언어를 생성하면서 구문분석하기 좋은 형태로 문법을 고치는 작업이다. 사람이 읽기 좋게 쓴 문법과 파서가 처리하기 좋은 문법이 다르기 때문에 필요하다. 무엇이 문제인지는 산술식 문법 하나로 다 드러난다. E → E + E | E E | E * E | E / E | 0 | 1 | 2 | 3 | 4 | 5 읽기에는 이보다 자연스러울 수 없다. 그런데 `3+4*5`를 좌단유도해 보면 유도트리가 두 개 나온다. (a) E ⇒ E+E ⇒ 3+E ⇒ 3+E*E ⇒ 3+4*E ⇒ 3+4*5 → 3+(4*5) = 23 (b) E ⇒ E*E ⇒ E+E*E ⇒ 3+E*E ⇒ 3+4*E ⇒ 3+4*5 → (3+4)*5 = 35 같은 문장인데 계산 결과가 다

오토마타 계층

오토마타 계층은 형식언어를 표현력에 따라 층으로 나누고, 각 층을 인식하는 기계를 대응시킨 것이다. 문법에 제약을 얼마나 두느냐가 층을 정하고, 그 층을 인식하려면 기계에 무엇이 필요한지가 따라 나온다. 컴파일러의 단계가 이 계층 위에 놓인다. 렉서와 파서가 나뉘는 이유도 여기서 나온다. 형식언어와 촘스키 계층 글자 `a`와 `b`만 쓸 수 있다고 하자. 둘을 아무렇게나 늘어놓으면 나오는 경우의 수는 끝이 없을 것이다. ε, a, b, ab, ba, aab, bba, abab, aaabb, ... 쓸 수 있는 기호의 집합 `T = {a, b}`를 알파벳이라 하고, 그 기호를 0개 이상 나열해 만들 수 있는 모든 문자열의 집합을 `T*`라고 한다면, 위의 나열이 `T*`이다. `ε`은

인라인 캐싱과 특수화

인라인 캐싱은 어떤 연산이 지난번에 무엇이었는지를 그 명령어 자리에 기록해 두고 다음번에 재사용하는 기법이고, 특수화는 그 기록을 근거로 명령어 자체를 전용 명령으로 바꿔치기하는 것이다. 동적 타입 언어의 비용은 연산 자체가 아니라 매번 무엇을 해야 하는지 다시 알아내는 데 있다. python def add(a, b): return a + b `a + b` 한 줄을 실행하려면 `a`의 타입을 보고, 그 타입의 덧셈 구현을 찾고, 없으면 `b`의 타입에서 역방향 연산을 찾고, 정수라면 크기를 확인해 알맞은 경로로 간다. `a`와 `b`가 언제나 작은 정수인 함수에서도 이 과정을 매 호출마다 반복한다. 정적 타입 언어라면 컴파일 시점에 `add` 기계어 명령 하나로 끝났을 일이다. 출

코드 최적화

코드 최적화는 프로그램의 의미를 바꾸지 않으면서 계산 횟수를 줄이거나 실행시간을 짧게, 기억용량을 적게 만드는 변환이다. 코드 최적화를 하기 위해선 두 가지 조건이 요구된다. 중간 결과에 이름이 있어야 한다. `T2 := C + D`처럼 결과에 이름이 붙어 있어야 그 줄을 다른 곳으로 옮길 수 있다. 스택 위 익명의 자리에 있으면 옮길 수 없다. 3-주소 코드가 최적화용 중간언어인 이유다. 제어 흐름이 그래프여야 한다. 분기 없이 순차 실행되는 최대 구간을 기본 블록이라 하고, 블록을 노드로 흐름을 간선으로 만든 것이 흐름 그래프라 한다. 최적화를 하기 위해선 이 값이 여기까지 살아 있는가, 이 코드에 도달할 수 있는가? 같은 질문에 답할 수 있어야 하고, 그래프 구조에선

클로저와 셀

클로저는 함수와 그 함수가 정의된 환경을 함께 묶은 것이고, 셀은 그 환경을 구현하는 한 칸짜리 상자다. 자유 변수를 어떻게 붙잡아 두느냐가 클로저 구현의 전부다. 문제가 어디서 생기는지부터 봐야 한다. python def outer(a): def inner(b): return a + b return inner `inner` 안의 `a`는 자기 지역변수도 전역변수도 아니다. 바깥 함수의 지역변수이고, 이런 변수를 자유 변수(free variable)라고 한다. `a`는 `outer`의 스택 프레임에 있는데, `outer`는 `inner`를 반환하면서 사라진다. 없어진 프레임의 변수를 어떻게 읽을 것인가. 함수가 탈출하지 않는다면 이 문제는 함수가 정

트리 순회와 바이트코드

같은 AST를 실행하는 방법은 크게 둘이다. 트리를 재귀적으로 순회하며 노드마다 값을 계산하거나, 트리를 한 번 훑어 바이트코드로 바꿔 놓고 평평한 루프로 돌리거나. 파싱까지는 완전히 같다. 갈라지는 것은 AST를 손에 쥔 다음부터다. 소스 → 렉서 → 파서 → AST ─┬─ 트리 순회 : AST를 그대로 재귀 순회 └─ 컴파일 → VM : AST → 바이트코드 → 루프 트리 순회 노드 타입으로 분기해 자식을 재귀 호출하고 결과를 합친다. go func Eval(node ast.Node, env *object.Environment) object.Object { switch no

opcode는 가상머신이 실행하는 명령어 하나를 가리키는 코드다. 명령어 집합을 어떻게 설계하느냐가 가상머신의 성능과 컴파일러의 복잡도를 함께 결정한다. 설계에서 정해야 할 것은 크게 셋이다. 피연산자를 어디에 두는가(스택이냐 레지스터냐), 명령어를 어떻게 인코딩하는가, 명령어를 몇 개나 둘 것인가. 스택 머신과 레지스터 머신 피연산자의 위치가 갈림길이다. 스택 머신은 피연산자를 암묵적으로 스택 top에서 가져온다. 중간언어의 후위표현이 그대로 명령어가 된다. a + b * c LOAD_NAME a LOAD_NAME b LOAD_NAME c BINARY_OP * ← 스택에서 둘 pop, 결과 push BINARY_OP + `BINA

중간언어는 원시언어와 목적코드 사이에 두는 표현으로, 컴파일러를 앞단과 뒷단으로 나누는 경계다. 앞단은 소스를 중간언어로 바꾸고 뒷단은 중간언어를 기계어로 바꾼다. 왜 한 단계를 더 두는지는 언어 `m`개를 기계 `n`종에 올리는 상황을 생각하면 분명하다. 직접 번역하면 번역기가 `m × n`개 필요하지만, 중간언어를 거치면 앞단 `m`개와 뒷단 `n`개, 합쳐서 `m + n`개로 끝난다. 이것 말고도 얻는 것이 있다. 컴파일러를 기능적으로 독립적인 모듈로 나눌 수 있다 원시 프로그램의 이식성이 올라간다 고급언어와 저급 목적코드 사이의 의미적 간극을 이어 준다 기계와 독립적인 최적화를 할 수 있다. 기계코드로 바뀐 뒤에 하는 것보다 훨씬 효율적이다 중간코드를 인터프리터로 직접 실행할 수 있다 대가도 있