AP 과목 A 33 — 컴파일러와 언어 처리: 어휘·구문·의미 분석에서 최적화까지

AP 과목 A 제33편 · 2026년도·실라버스 Ver.7.2 기준의 독립 학습 자료입니다. IPA와 제휴하지 않으며 합격을 보장하지 않습니다. 시리즈 허브 보기

2026년 IPA 응용정보기술자시험(AP) 과목 A, Syllabus Ver.7.2 기준이며 2026-10-22 확인했다. Motitory의 독립 학습 자료로 IPA와 제휴하거나 IPA의 승인·검토를 받지 않았다. Ver.7.2 전 범위를 빠짐없이 다루지 않으며 합격을 보장하지 않는다. 본문의 예제와 문제는 모두 Motitory가 만든 오리지널이며 IPA 기출이 아니다.

이 글은 고정된 마무리 계획 AP33–38 가운데 **AP33(보충편)**이며 시리즈의 마지막 글이 아니다. 전체 목록은 시리즈 허브에 있다. 트리·스택 같은 자료구조는 AP5, 상태 전이표 추적은 AP6, 개발 방법과 테스트는 AP23에서 다뤘으므로 여기서는 다시 설명하지 않고 컴파일러 고유의 내용만 다룬다.

1. 컴파일러의 역할과 처리 흐름

**컴파일러(コンパイラ)**는 고급 언어로 쓴 **원시 프로그램(ソースプログラム)**을 의미를 바꾸지 않고 대상 기계용 **목적 프로그램(目的プログラム)**으로 번역한다. 목적 프로그램은 보통 링크를 거쳐 실행 파일이 된다. 시험에서 쓰는 표준 모델은 다음 순서다.

원시 프로그램(문자열)
 → ① 어휘 분석   : 문자 → 토큰 열
 → ② 구문 분석   : 토큰 열 → 구문 트리(파스 트리/AST)
 → ③ 의미 분석   : 선언·형·문맥 검사, 기호표 갱신
 → ④ 중간 코드 생성: AST → 중간 표현(예: 3번지 코드)
 → ⑤ 최적화      : 관측 가능한 동작을 유지한 채 중간 코드 개선
 → ⑥ 코드 생성   : 대상 기계의 목적 코드
목적 프로그램

실제 컴파일러는 단계를 합치거나 최적화를 여러 번 수행하기도 하므로, 이 순서는 “각 단계가 무엇을 입력받아 무엇을 내놓는가”를 구분하는 학습용 모델로 기억한다.

2. 어휘 분석

**어휘 분석(字句解析)**은 문자의 나열을 **토큰(トークン)**으로 자른다. 공백과 주석은 이 단계에서 버려진다. 토큰 종류(식별자, 숫자, 연산자, 구분자)는 보통 정규 표현으로 정의하고 **유한 오토마톤(有限オートマトン)**으로 인식한다. 예: 식별자 = 영문자(영문자|숫자)*. 유한 오토마톤의 상태 전이표를 손으로 따라가는 방법은 AP6에서 다뤘다.

최장 일치: <=는 <와 = 두 토큰이 아니라 하나의 토큰으로 읽는다.
어휘 오류의 예: 어떤 토큰 패턴에도 맞지 않는 문자(언어가 허용하지 않는 # 등).

풀이 예제 1 — 토큰화와 구문 트리

원시 코드 total = price * 3 + tax;

순서	토큰 종류	실제 문자열
1	식별자	`total`
2	대입 연산자	`=`
3	식별자	`price`
4	곱셈 연산자	`*`
5	수치	`3`
6	덧셈 연산자	`+`
7	식별자	`tax`
8	구분자	`;`

공백 6개는 토큰이 되지 않으므로 결과는 토큰 8개다. 구문 트리는 다음 절에서 이어서 만든다.

3. 구문 분석과 문법

**구문 분석(構文解析)**은 토큰 열이 문법에 맞는지 확인하고 구조를 트리로 만든다. 프로그래밍 언어의 문법은 보통 **문맥 자유 문법(文脈自由文法)**으로 쓰며 BNF로 표기한다.

stmt   → id = expr ;
expr   → expr + term   | term
term   → term * factor | factor
factor → id | num | ( expr )

*를 더 아래 층(term)에 두었으므로 *가 +보다 먼저 묶인다(우선순위).
expr → expr + term처럼 왼쪽 재귀이므로 같은 층 연산자는 왼쪽부터 묶인다(좌결합). -를 +와 같은 층에 추가하면 a - b - c는 (a - b) - c가 된다.
E → E + E | E * E | id처럼 층을 나누지 않은 문법은 a + b * c에 트리가 두 개 생기는 모호한 문법이다.

예제 1의 추상 구문 트리(AST):

        =
       / \
   total   +
          / \
         *   tax
        / \
    price   3

**파스 트리(구문 트리)**는 expr, term 같은 비단말 기호를 모두 노드로 남기고, AST는 연산과 피연산자만 남긴 요약이다. 괄호와 ;는 구조가 트리에 반영되었으므로 AST에서 사라진다.

형식 언어와 오토마타의 대응(시험 단골):

언어 클래스	정의 수단	인식 기계	컴파일러에서
정규 언어	정규 표현·정규 문법	유한 오토마톤	어휘 분석(토큰)
문맥 자유 언어	문맥 자유 문법(BNF)	푸시다운 오토마톤(스택)	구문 분석

유한 오토마톤은 상태 수가 유한해 임의 깊이의 중첩 괄호 짝을 셀 수 없다. 중첩 구조에는 스택이 필요하므로 구문 분석은 문맥 자유 문법을 쓴다.

4. 의미 분석

**의미 분석(意味解析)**은 문법상 올바른 트리가 언어의 의미 규칙을 지키는지 검사한다. 선언 정보는 **기호표(記号表)**에 기록한다.

선언되지 않은 이름의 사용, 같은 범위의 이중 선언
형(型) 검사: 정수 변수에 문자열 대입, 인수 개수·형 불일치
필요한 경우 암시적 형 변환(예: 정수 → 실수)을 트리에 삽입

“사용 전에 선언되어야 한다”는 조건은 앞뒤 문맥에 달려 있어 문맥 자유 문법만으로 표현하기 어렵기 때문에 구문 분석이 아닌 의미 분석에서 검사한다. 반대로 문법과 형은 맞지만 알고리즘이 틀린 논리 오류는 컴파일러가 보통 찾지 못하며 테스트의 영역이다(AP23).

5. 중간 표현과 최적화

중간 언어(中間言語)·중간 표현은 원시 언어와 대상 기계 사이의 형태로, 대개 특정 CPU에 묶이지 않는다. 그래서 같은 중간 표현에서 여러 기계용 코드를 만들거나, 기계와 무관한 최적화를 한 번 구현해 재사용할 수 있다. 대표 형식은 명령 하나에 연산자 하나와 주소 최대 세 개(결과 주소 하나, 입력 피연산자 주소 최대 둘)를 쓰는 **3번지 코드(3番地コード)**다.

풀이 예제 2 — 3번지 코드와 안전한 최적화

b, c는 정수 입력이고 x, y, z는 정수 지역 변수다. 표시된 모든 계산은 오버플로하지 않으며 호출·입출력·volatile 접근도 없다고 가정한다.

x = 4 * 2;
y = (b + c) * (b + c) - x;
z = y + 1;      // z는 이후 어디서도 쓰지 않는다
return y;

① 3번지 코드(10줄)

t1 = 4 * 2
x  = t1
t2 = b + c
t3 = b + c
t4 = t2 * t3
t5 = t4 - x
y  = t5
t6 = y + 1
z  = t6
return y

② 상수 폴딩(定数畳み込み)과 상수 전파: 4 * 2는 컴파일 시점에 8로 계산할 수 있다. x가 바뀌지 않으므로 t5 = t4 - 8로 바꿀 수 있다.

③ 공통 부분식 제거(共通部分式の除去): t2와 t3 사이에 b, c가 바뀌지 않고 정수 +에 부작용이 없으므로 t3 = b + c를 지우고 t2를 재사용한다. 식이 f()처럼 출력·상태 변경을 하는 호출이면 횟수가 바뀌므로 합칠 수 없다.

④ 불필요 코드 제거(デッドコード除去): z와 t6은 이후에 읽히지 않고 계산에 부작용이 없으므로 지운다. ② 이후 x, t1도 읽히지 않으므로 지운다. 출력, 예외처럼 언어가 정의한 동작을 만드는 코드는 결과를 쓰지 않아도 지울 수 없다.

⑤ 결과(4줄)

t2 = b + c
t4 = t2 * t2
y  = t4 - 8
return y

검산: b = 1, c = 2이면 원래 코드는 (3) * (3) - 8 = 1, 최적화 후도 9 - 8 = 1로 같다.

최적화의 원칙: 최적화는 언어가 정의한 관측 가능한 동작(출력, 반환값, 입출력 순서 등)을 유지해야 한다. 또한 모든 프로그램을 반드시 빠르게 만든다는 보장은 없다. 인라인 전개·루프 전개처럼 코드가 커지는 변환은 캐시 효율을 떨어뜨릴 수 있고, 컴파일 시간도 늘어난다. 효과는 측정으로 확인한다. 그 밖의 이름: 루프 불변식 이동(ループ内不変式の移動), 강도 경감(x * 2 → x + x 등).

6. 코드 생성과 목적 프로그램

**코드 생성(コード生成)**은 중간 표현을 대상 기계의 명령으로 바꾼다. 명령 선택과 레지스터 할당이 핵심이다. 출력인 목적 프로그램은 보통 그대로 실행되지 않고 **링커(リンカ)**가 다른 목적 모듈·라이브러리와 결합해 실행 가능한 로드 모듈을 만든다.

인터프리터(インタプリタ): 목적 프로그램을 만들지 않고 원시 프로그램(또는 중간 코드)을 해석하며 실행한다.
크로스 컴파일러: 컴파일러가 동작하는 기계와 다른 기계용 목적 코드를 만든다.

7. 용어 대조표

한국어	日本語	English	한 줄 정의
컴파일러	コンパイラ	compiler	원시 프로그램을 목적 프로그램으로 번역
어휘 분석	字句解析	lexical analysis	문자 → 토큰
토큰	トークン	token	식별자·숫자·연산자 같은 최소 의미 단위
구문 분석	構文解析	syntax analysis (parsing)	토큰 → 문법에 따른 트리
추상 구문 트리	抽象構文木	abstract syntax tree	연산과 피연산자만 남긴 트리
문맥 자유 문법	文脈自由文法	context-free grammar	구문 정의에 쓰는 문법, BNF로 표기
형식 언어	形式言語	formal language	문법·기계로 정의되는 기호열 집합
오토마톤	オートマトン	automaton	입력을 읽어 상태를 바꾸는 추상 기계
의미 분석	意味解析	semantic analysis	선언·형·문맥 규칙 검사
기호표	記号表	symbol table	이름과 형·범위 정보 저장
중간 언어	中間言語	intermediate language	원시 언어와 기계어 사이의 표현
3번지 코드	3番地コード	three-address code	명령당 연산 하나, 결과 주소 하나와 입력 주소 최대 둘
최적화	最適化	optimization	동작을 유지하며 코드 개선
코드 생성	コード生成	code generation	중간 표현 → 대상 기계 명령
목적 프로그램	目的プログラム	object program	컴파일러의 출력

8. 퀵 시트와 함정

어휘 = 문자→토큰(정규·유한 오토마톤) / 구문 = 토큰→트리(문맥 자유·스택) / 의미 = 선언·형 / 코드 생성 = 대상 기계 명령.
오류 분류: 허용되지 않는 문자 → 어휘, 괄호 누락 → 구문, 미선언·형 불일치 → 의미, 결과가 틀림 → 논리 오류(테스트).
우선순위는 문법의 층, 결합성은 재귀 방향으로 정해진다.
3번지 코드 = 명령당 연산자 1개. 임시 변수 t1, t2, …가 생긴다.
상수 폴딩은 컴파일 시점 계산, CSE는 부작용·중간 갱신이 없을 때만, 불필요 코드 제거는 관측 가능한 효과가 없을 때만.
함정: “최적화는 항상 빠르게 한다”, “중간 언어는 특정 CPU 기계어다”, “목적 프로그램 = 원시 프로그램”, “유한 오토마톤으로 중첩 괄호를 검사할 수 있다”.

9. 오리지널 진단 5문제

아래 문제는 Motitory가 만든 원문이며 IPA 기출을 사용하거나 번안하지 않았다.

Q1 — 처리 단계

원시 프로그램의 문자열에서 공백과 주석을 건너뛰고 count, <=, 10 같은 단위로 나누는 단계는?

A. 구문 분석

B. 의미 분석

C. 어휘 분석

D. 코드 생성

A: 오답. 구문 분석은 이미 나뉜 토큰 열을 문법에 따라 트리로 묶는다.
B: 오답. 의미 분석은 토큰화와 구문 분석 뒤에 선언·형을 검사한다.
C: 정답. 문자 → 토큰이며 <=는 최장 일치로 한 토큰이 된다.
D: 오답. 코드 생성은 중간 표현에서 대상 기계 명령을 만드는 후반 단계다.

Q2 — 문법과 우선순위

3절의 문법으로 a + b * c를 분석한 AST로 옳은 것은?

A. 루트가 *, 왼쪽 자식이 a + b, 오른쪽 자식이 c

B. 루트가 +이고 a, b, c가 모두 그 자식

C. 이 문법은 모호하므로 두 트리 모두 정당한 결과

D. 루트가 +, 왼쪽 자식이 a, 오른쪽 자식이 b * c

A: 오답. (a + b) * c의 트리다. 괄호 없이는 이 문법에서 나오지 않는다.
B: 오답. 이항 연산 노드는 자식 둘을 가진다. 셋을 한 노드에 두면 연산 순서가 사라진다.
C: 오답. 이 문법은 expr/term/factor 층으로 모호성을 없앴다. 층이 없는 E → E + E | E * E | id라면 모호했다.
D: 정답. *가 아래 층 term에서 먼저 묶인다.

Q3 — 오류 검출 단계

다음 중 전형적으로 의미 분석에서 검출되는 것은?

A. if (x > 0 {처럼 닫는 괄호가 빠졌다.

B. 선언되지 않은 변수 totl을 오타로 사용했다.

C. 식별자에 언어가 허용하지 않는 문자 #이 있다.

D. 반복 조건이 하나 어긋나 합계가 1 작게 나온다.

A: 오답. 문법 위반이므로 구문 분석에서 검출한다.
B: 정답. totl은 올바른 식별자 토큰이고 문법에도 맞지만 기호표에 선언이 없다.
C: 오답. 토큰 패턴에 맞지 않는 문자이므로 어휘 분석에서 검출한다.
D: 오답. 언어 규칙 위반이 아닌 논리 오류로, 컴파일러가 아니라 테스트로 찾는다. AP23 테스트 복습

Q4 — 안전한 최적화

정수 지역 변수만 쓰는 함수다. log()는 화면에 출력하는 함수일 때, 동작을 바꾸지 않는 변환은?

A. t = 6 * 7을 t = 42로 바꾼다.

B. log(x) + log(x)를 2 * log(x)로 바꾼다.

C. 반환값을 쓰지 않으므로 log(x); 호출문을 지운다.

D. 최적화하면 모든 프로그램이 빨라지므로 측정 없이 최대 최적화를 기본값으로 한다.

A: 정답. 상수 폴딩이다. 컴파일 시점에 같은 값을 계산할 뿐 관측 가능한 동작은 그대로다.
B: 오답. 출력이 두 번에서 한 번으로 줄어든다. 부작용이 있는 식은 공통 부분식으로 합칠 수 없다.
C: 오답. 출력은 관측 가능한 동작이므로 반환값을 쓰지 않아도 불필요 코드가 아니다.
D: 오답. 코드 증가·컴파일 시간 등 비용이 있고 모든 프로그램이 빨라진다는 보장이 없으므로 측정해야 한다.

Q5 — 형식 언어와 오토마타

옳은 설명은?

A. 임의 깊이의 중첩 괄호 ((())) 짝 검사는 유한 오토마톤만으로 충분하다.

B. 중간 언어는 항상 특정 CPU의 기계어이므로 다른 기계용으로 바꿀 수 없다.

C. 정규 언어는 유한 오토마톤으로 인식해 어휘 분석에 쓰고, 문맥 자유 문법은 스택을 쓰는 푸시다운 오토마톤에 대응해 구문 분석에 쓴다.

D. 목적 프로그램은 어휘 분석에 들어가기 전의 원시 프로그램을 말한다.

A: 오답. 상태가 유한하므로 깊이에 제한이 없는 중첩을 셀 수 없고 스택이 필요하다. 자료구조로서의 스택은 AP5에서 복습한다.
B: 오답. 중간 언어는 대개 기계에 독립적이며, 그래서 여러 대상 기계와 공통 최적화에 쓰인다.
C: 정답. 언어 클래스·인식 기계·컴파일러 단계의 대응이다. 상태 전이 추적은 AP6에서 복습한다.
D: 오답. 목적 프로그램은 컴파일러의 출력이고, 원시 프로그램이 입력이다.

정답: C, D, B, A, C

10. 셀프 체크와 복습 일정

여섯 단계의 입력과 출력을 순서대로 말할 수 있다.
total = price * 3 + tax;의 토큰 8개와 AST를 다시 그릴 수 있다.
문법의 층과 재귀 방향으로 우선순위·결합성을 설명할 수 있다.
오류 네 가지(어휘·구문·의미·논리)를 예로 분류할 수 있다.
예제 2의 10줄을 4줄로 줄이고 각 변환이 안전한 이유를 말할 수 있다.
정규 언어–유한 오토마톤, 문맥 자유 문법–푸시다운 오토마톤을 짝지을 수 있다.

권장 복습 주기(발행 일정과 별개): 당일 예제 1·2를 보지 않고 다시 풀기 → 1일 후 Q1–Q5 → 3일 후 퀵 시트만 보고 용어표 빈칸 채우기 → 7일 후 3번지 코드를 새 식으로 직접 만들어 최적화 → 14일 후 틀린 문항만 재확인.

11. 공식 출처

IPA 응용정보기술자시험 Syllabus Ver.7.2 — 대분류 1 / 중분류 1 / 3. 情報に関する理論 / (10) コンパイラ理論, PDF p.10 (인쇄 쪽 -6-). 컴파일러의 역할과 처리 과정, 어휘 분석, 구문 분석, 의미 분석, 코드 생성, 최적화와 용어(문맥 자유 문법, 중간 언어, 목적 프로그램, 형식 언어, 오토마톤)를 확인했다. 2026-10-22 확인.
IPA 실라버스 허브 — 2026-10-22 확인.

이 글은 AP33–38 마무리 계획의 첫 회차다. 다음으로 예정된 주제는 AP34 무선 LAN이며, 시리즈는 AP38에서 끝난다.