서류 양식에 “무엇을 / 누구와 / 누구로 / 결과는 어디에” 네 칸이 인쇄되어 있고, 명령 하나마다 양식 한 장을 채우는 것과 같다. 한 번에 계산 하나씩만 하도록 풀어 쓴 코드의 한 줄을 이렇게 칸 네 개짜리 기록으로 담고, 기록들을 실행 순서대로 줄줄이 이어 둔다. 모든 줄이 같은 모양이라 프로그램으로 다루기 쉽고, 중간에 줄을 끼우거나 빼기도 쉽다. 대신 칸을 다 쓰지 않는 줄이 많아 빈칸이 생기고, 어느 칸에 무엇을 넣는지는 명령 종류마다 외워야 한다.
예시로 보기
3주소 코드를 t1 = b * t0 같은 글자로만 들고 있으면, 컴파일러가 그 줄을 볼 때마다 글자를 다시 쪼개 읽어야 한다. 미리 칸으로 나눠 담아 두면 “연산자 칸이 *인가”, “결과 칸이 t1인가”를 바로 물을 수 있다.
다음 다섯 줄을 담는다.
t0 = -a
t1 = b * t0
t2 = b * t1
t3 = t1 + t2
c = t3
HEAD
│
▼
┌─────┬────┬────┬────┐ ┌─────┬────┬────┬────┐
│ - │ a │ │ t0 │──▶│ * │ b │ t0 │ t1 │──┐
└─────┴────┴────┴────┘ └─────┴────┴────┴────┘ │
┌───────────────────────────────────────────────┘
▼
┌─────┬────┬────┬────┐ ┌─────┬────┬────┬────┐
│ * │ b │ t1 │ t2 │──▶│ + │ t1 │ t2 │ t3 │──┐
└─────┴────┴────┴────┘ └─────┴────┴────┴────┘ │
┌───────────────────────────────────────────────┘
▼
┌─────┬────┬────┬────┐
│copy │ t3 │ │ c │
└─────┴────┴────┴────┘
op arg1 arg2 result
한 줄이 네 칸짜리 기록 하나다. 첫 줄 t0 = -a는 피연산자가 하나뿐이라 셋째 칸이 비었다. 마지막 줄 c = t3도 그렇다. HEAD가 첫 기록을 가리키고, 기록마다 다음 기록을 가리킨다.
a = 2, b = 3으로 차례대로 실행하면 t0 = −2, t1 = −6, t2 = −18, t3 = −24, c = −24다1.
-가 arg2 유무로 단항·이항으로 갈림 — 38_quadruples_verify.py정의
쿼드러플은 네 칸 (op, arg1, arg2, result)을 가진 기록이고, 연결 리스트에 담는다. 쿼드러플(quadruple)은 “넷이 한 벌”이라는 뜻이다.
| 칸 | 담는 것 |
|---|---|
| op | 연산자나 명령의 종류. +, *, goto, param 등 |
| arg1 | 첫째 피연산자 |
| arg2 | 둘째 피연산자. 없으면 비운다 |
| result | 결과를 받는 변수. 없으면 비운다 |
3주소 코드의 줄마다 칸을 채우는 법은 다음과 같다.
| 3주소 코드 | op | arg1 | arg2 | result |
|---|---|---|---|---|
복사 a = b |
= |
b | a | |
이항 연산 a = b - c |
- |
b | c | a |
단항 연산 a = -b |
- |
b | a | |
L: |
label |
L | ||
goto L |
goto |
L | ||
if x goto L |
if |
x | L | |
param x |
param |
x | ||
call f, n |
call |
f | n | |
x = call f, n |
call |
f | n | x |
return x |
return |
x | ||
x[i] = y |
[]= |
i | y | x |
x = y[i] |
=[] |
y | i | x |
눈여겨볼 곳이 셋이다.
- 이항 뺄셈과 단항 부호 바꾸기가 둘 다 op
-다. arg2가 차 있으면 뺄셈, 비어 있으면 부호 바꾸기다. - 흐름을 바꾸는 줄은 result가 비고, 갈 곳의 레이블이 arg 칸에 들어간다.
goto는 arg1에,if는 조건 다음인 arg2에 둔다.ifnot x goto L도if와 같은 자리를 쓴다. - 배열 연산은 op가
[]=(넣기)와=[](꺼내기)로 다르고, 배열 이름이 들어가는 칸도 다르다. 넣기는 배열이 result, 꺼내기는 배열이 arg1이다.
복사 줄의 op는 위 그림처럼 copy로 적기도 하고 아래 표처럼 =로 적기도 한다. 둘은 같은 것이다2.
하는 일. 새 쿼드러플을 리스트 맨 끝에 붙인다. 처음부터 차례로 읽는다. 중간 코드 생성기는 붙이기만 하고, 최적화 단계는 읽으면서 고치거나 뺀다.
| 일 | 비용 |
|---|---|
| 맨 끝에 붙이기 | 끝을 가리키는 포인터를 따로 두면 \(O(1)\), 없으면 처음부터 따라가야 해서 \(O(n)\) |
| 처음부터 끝까지 읽기 | \(O(n)\) |
| 읽던 자리에서 한 줄 끼우기·빼기 | \(O(1)\) |
\(n\)은 쿼드러플의 개수다2.
활용
- 구현: 38_quadruples_verify.py의
QuadList. 연습: 3주소 코드 변환 연습 - 최적화가 줄을 빼는 일이 잦다. 죽은 코드 제거는 쓸모없는 대입을 통째로 뺀다. 연결 리스트는 뺄 때 뒤의 줄을 당기지 않아도 된다.
- 흔한 실수:
if x goto L에서 L을 result 칸에 넣는다.x[i] = y의 칸 순서를=[]와 섞는다. 단항 연산에서 arg2 대신 arg1을 비운다.
연결
- 선수: 3주소 코드
- 담는 그릇: 연결 리스트
- 트리에서 쿼드러플을 만들어 붙이는 과정: AST에서 3주소 코드 만들기
확인 문제
C1 쿼드러플의 네 칸을 순서대로 쓰고, a = b - c와 a = -b를 각각 쿼드러플로 쓰라. 둘은 어떻게 구별되는가?
답: (op, arg1, arg2, result). a = b - c는 (-, b, c, a), a = -b는 (-, b, 빈칸, a). op가 같으므로 arg2가 차 있는지로 구별한다.
C2 예시의 다섯 쿼드러플을 a = 2, b = 3으로 차례로 실행할 때 result 칸의 변수에 들어가는 값을 순서대로 쓰라.
답: t0 = −2, t1 = 3 × (−2) = −6, t2 = 3 × (−6) = −18, t3 = −6 + (−18) = −24, c = −24.
C3 다음 3주소 코드를 쿼드러플 표로 옮기라. L0: / t0 = x < y / ifnot t0 goto L1 / x = t1 / goto L0
답: (label, L0, , ), (<, x, y, t0), (ifnot, t0, L1, ), (=, t1, , x), (goto, L0, , ).
이유: 흔한 오답은 x = t1을 (=, x, , t1)로 뒤집는 것이다. 값을 받는 쪽이 result다.
C4 x[i] = y와 x = y[i]의 쿼드러플에서 배열 이름은 각각 어느 칸에 들어가는가? 왜 다른가?
답: x[i] = y는 ([]=, i, y, x)로 배열 x가 result에, x = y[i]는 (=[], y, i, x)로 배열 y가 arg1에 들어간다. result는 값이 바뀌는 쪽이다. 넣기에서는 배열 x가 바뀌고, 꺼내기에서는 변수 x가 바뀌고 배열 y는 읽기만 한다.