목차
1 컴파일러 개론 = 1
1.1 소개 = 1
1.2 컴파일러 구현을 공부하는 이유는 무엇인가? = 3
1.3 컴파일러의 기초 원칙 = 4
1.4 컴파일러 구조 = 4
1.5 번역의 high-level view = 7
1.5.1 입력의 이해 = 7
1.5.2 동작 환경의 생성과 관리 = 11
1.5.3 성능향상 = 13
1.5.4 출력 프로그램의 생성 = 14
1.6 컴파일러의 요구사항 = 20
1.7 요약과 전망 = 21
기타 = 22
2 스캐닝 = 25
2.1 소재 = 25
2.2 단어 인식 = 27
2.2.1 인식기를 공식화하기 = 29
2.2.2 더 복잡한 단어의 인식 = 31
2.2.3 스캐너 생성의 자동화 = 33
2.3 정규 표현 = 33
2.3.1 표기법의 공식화 = 35
2.3.2 예 = 36
2.3.3 re의 특성 = 39
2.4 정규 표현에서 스캐너로 = 41
2.4.1 비결정적 유한 오토마타 = 42
2.4.2 정규 표현을 nfa로: Thompson 구조 = 45
2.4.3 nfa에서 dfa로: 부분 집합 구조 = 47
2.4.4 dfa에서 최소화된 dfa로: Hopcroft의 알고리즘 = 52
2.4.5 dfa에서 정규 표현으로 = 55
2.4.6 dfa를 인식기로 사용하기 = 57
2.5 스캐너 구현하기 = 58
2.5.1 테이블 기반 스캐너 = 58
2.5.2 직접 만들어진 스캐너 = 59
2.5.3 키워드 다루기 = 61
2.5.4 동작 명시 = 61
2.6 고급 주제 = 63
2.7 요약과 전망 = 66
기타 = 67
3 파싱 = 69
3.1 소개 = 69
3.2 구문 표현 = 70
3.2.1 Context-Free 문법 = 71
3.2.2 문장 구조 형성 = 75
3.2.3 의미를 구조로 나타내기 = 79
3.2.4 특정 전개 살펴보기 = 81
3.2.5 Context-Free 문법과 정규 표현 = 84
3.3 Top-Down 파싱 = 85
3.3.1 예 = 86
3.3.2 Top-Down 파싱에서의 복잡성 = 89
3.3.3 Left Recursion 없애기 = 89
3.3.4 Backtrack의 필요성을 없애기 = 92
3.3.5 Top-Down Recursive-Descent 파서들 = 96
3.4 Bottom-Up 파싱 = 101
3.4.1 Shift-Reduce 파싱 = 103
3.4.2 Handle 발견하기 = 107
3.4.3 Ir(1) 파서들 = 109
3.5 Lr(1) 테이블 만들기 = 114
3.5.1 Ir(1) 항목들 = 115
3.5.2 정규 모음 만들기 = 116
3.5.3 테이블 채우기 = 121
3.5.4 테이블 생성시 오류 = 123
3.6 실제 이슈들 = 127
3.6.1 에러 복원 = 127
3.6.2 Unary 연산자 = 128
3.6.3 문맥 의미의 모호성 취급 = 130
3.6.4 Left versus Right Recursion = 131
3.7 고급 주제 = 134
3.7.1 문법 최적화 = 134
3.7.2 Ir(1) 테이블의 크기 줄이기 = 136
3.8 요약과 전망 = 140
기타 = 141
4 문맥 의미 분석 = 143
4.1 서론 = 143
4.2 자료형 시스템의 소개 = 146
4.2.1 자료형 시스템의 목적 = 146
4.2.2 자료형 시스템의 구성 요소들 = 152
4.3 속성 문법 기본구조 = 160
4.3.1 평가 방법들 = 166
4.3.2 순환형 = 167
4.3.3 확장된 예제 = 168
4.3.4 속성 문법 접근이 가지고 있는 문제들 = 175
4.4 애드 혹 구문 주도형 번역 = 178
4.4.1 애드 혹 구문 주도형 번역 구현 = 180
4.4.2 예제 = 182
4.5 고급 주제들 = 191
4.5.1 자료형 추론의 난해한 문제들 = 191
4.5.2 우선순위의 변화 = 193
4.6 요약과 전망 = 195
기타 = 196
5 중간 표현(IR) = 199
5.1 서론 = 199
5.2 분류법 = 200
5.3 그래픽 IR = 203
5.3.1 구문 관련 트리들 = 203
5.3.2 그래프 = 208
5.4 선형 IR = 212
5.4.1 스택 기계 코드 = 213
5.4.2 3-주소 코드 = 214
5.4.3 선형 코드로 표현하기 = 215
5.5 정적 단일 배정 형식(ssa) = 218
5.6 이름에 값 할당하기 = 221
5.6.1 임시 값 이름 짓기 = 222
5.6.2 메모리 모델 = 224
5.7 심볼 테이블 = 227
5.7.1 해시 테이블 = 228
5.7.2 심볼 테이블 만들기 = 229
5.7.3 내포된 스코프 다루기 = 231
5.7.4 다수의 심볼 테이블 사용 = 235
5.8 요약과 전망 = 237
기타 = 237
6 프로시저 추상화 = 239
6.1 소개 = 239
6.2 제어 추상화 = 241
6.3 이름 공간 = 244
6.3.1 Algol과 같은 언어에서의 이름 공간 = 245
6.3.2 구동 레코드 = 249
6.3.3 객체 지향 언어의 이름 공간 = 254
6.4 프로시저 간의 값 교환 = 261
6.4.1 매개변수 전달 = 261
6.4.2 값 반환 = 265
6.5 주소 계산 = 266
6.5.1 단순한 기본 주소 = 266
6.5.2 다른 프로시저의 지역 변수 = 267
6.6 표준화된 링키지 = 271
6.7 메모리 관리 = 275
6.7.1 메모리 배치 = 276
6.7.2 힙 관리를 위한 알고리즘 = 280
6.7.3 묵시적 해제 = 284
6.8 요약과 전망 = 289
기타 = 290
7 코드 형태 = 293
7.1 서론 = 293
7.2 저장 공간의 할당 = 295
7.2.1 데이터 영역 배치 = 296
7.2.2 레지스터에 값의 저장 = 297
7.2.3 목표 시스템의 특성들 = 299
7.3 산술 연산자 = 300
7.3.1 적은 레지스터의 사용 = 301
7.3.2 매개변수의 접근 = 303
7.3.3 함수 호출 표현 = 305
7.3.4 다른 산술 연산자들 = 305
7.3.5 혼합 형태 표현식 = 306
7.3.6 연산자로서의 할당 = 307
7.3.7 교환법칙, 결합법칙, 그리고 수 체계 = 307
7.4 불리언 연산자와 관계 연산자 = 308
7.4.1 표현 = 309
7.4.2 관계 연산자를 위한 하드웨어 지원 = 313
7.4.3 표현의 선택 = 317
7.5 배열의 저장과 접근방법 = 318
7.5.1 벡터 요소의 접근 = 318
7.5.2 배열의 저장 방법 = 320
7.5.3 배열 요소의 참조 = 322
7.5.4 범위 확인 = 327
7.6 문자열 = 328
7.6.1 문자열의 표현 = 329
7.6.2 문자열 할당 = 329
7.6.3 문자열 연결 = 333
7.6.4 문자열의 길이 = 334
7.7 구조체 참조 = 335
7.7.1 익명의 값들의 load와 store = 335
7.7.2 구조체 배열의 이해 = 337
7.7.3 구조체 배열 = 338
7.7.4 공용체와 런타임 태그들 = 339
7.8 제어 흐름의 구성 = 340
7.8.1 조건문 실행 = 341
7.8.2 루프와 반복 = 344
7.8.3 Case 문장들 = 349
7.8.4 Break 문장들 = 353
7.9 프로시저 호출 = 353
7.9.1 매개변수의 평가 = 354
7.9.2 함수 매개변수 = 355
7.9.3 레지스터 저장과 복원 = 356
7.9.4 리프 프로시저를 위한 최적화 = 357
7.10 객체지향 언어의 구현 = 358
7.10.1 단위 클래스, 비상속 = 358
7.10.2 단일 상속 = 361
7.11 요약과 전망 = 367
기타 = 367
8 코드 최적화 개론 = 369
8.1 소개 = 369
8.2 기초 = 372
8.2.1 INPACK 코드로부터 예 = 373
8.2.2 최적화를 위한 고려사항들 = 374
8.2.3 최적화 기회 = 378
8.3 중복된 표현들 = 378
8.3.1 비순환 그래프 = 379
8.3.2 Value Numbering = 383
8.3.3 중복 제어로부터 교훈 = 388
8.4 최적화의 범위 = 389
8.4.1 Local 방법들 = 390
8.4.2 Superlocal 방법들 = 390
8.4.3 Regional 방법들 = 391
8.4.4 Global 방법들 = 392
8.4.5 전체 프로그램 방법들 = 393
8.5 기본 블록보다 큰 영역에서의 value numbering = 393
8.5.1 Superlocal Value Numbering = 393
8.5.2 Dominator를 기반으로 한 value numbering = 398
8.6 전역 중복 제거 = 402
8.6.1 유효한 표현(Available Expression)의 계산 = 404
8.6.2 불필요한 연산의 대체 = 406
8.6.3 혼합 = 407
8.7 고급주제 = 409
8.7.1 문장의 복사 = 410
8.7.2 인라이닝 방법 = 412
8.8 요약과 전망 = 415
기타 = 416
9 자료 흐름 분석 = 417
9.1 소개 = 417
9.2 반복적인 자료 흐름 분석법 = 419
9.2.1 Live 변수들 = 419
9.2.2 반복적 LIVEOUT 계산법의 속성 = 428
9.2.3 자료 흐름 분석법의 한계 = 431
9.2.4 다른 자료 흐름 문제들 = 434
9.3 정적 단일-할당 형태 = 438
9.3.1 SSA 형태를 만드는 간단한 방법 = 440
9.3.2 우위 = 441
9.3.3 ø-함수의 위치 선정 = 447
9.3.4 이름 재정의 = 450
9.3.5 SSA 형태로부터 실행 가능한 파일을 재 생성하기 = 458
9.4 고급 주제들 = 463
9.4.1 구조적인 자료 흐름 알고리즘과 감소성 = 463
9.4.2 함수간의 분석 = 467
9.5 요약과 전망 = 471
기타 = 472
10 스칼라 최적화 = 475
10.1 소개 = 475
10.2 변환을 위한 용어 = 478
10.2.1 기계-독립적 변환 = 478
10.2.2 기계-종속적 변환 = 480
10.3 최적화의 예제 = 482
10.3.1 쓸모없고 도달 불가능한 코드 제거 = 482
10.3.3 특성화 = 499
10.3.4 다른 변환을 가능케 하기 = 502
10.3.5 중복 제거 = 506
10.4 고급 주제 = 507
10.4.1 최적화의 조합 = 507
10.4.2 강도 감소 = 511
10.4.3 최적화의 다른 목적 = 522
10.4.4 최적화 시퀀스 선택 = 524
10.5 요약과 전망 = 525
기타 = 526
11 명령어 선택 = 529
11.1 소개 = 529
11.1.1 목표 변환 컴파일러 구성하기 = 533
11.2 간단한 트리 탐색 기법 = 536
11.3 트리 패턴 매칭을 통한 명령어 선택 = 542
11.3.1 법칙의 재구성 = 543
11.3.2 타일링 찾기 = 549
11.3.3 도구들 = 552
11.4 핍홀 최적화를 통한 명령어 선택 = 553
11.4.1 핍홀 최적화 = 554
11.4.2 핍홀 변환기 = 562
11.5 급 주제들 = 564
11.5.1 핍홀 패턴 배우기 = 564
11.5.2 명령어 시퀀스 생성하기 = 566
11.6 요약과 전망 = 567
기타 = 568
12 명령어 스캐줄링 = 271
12.1 소개 = 571
12.2 명령어 스케줄링 문제 = 573
12.2.1 스케줄의 질을 측정하는 다른 방법 = 579
12.2.2 무엇이 스케줄링을 어렵게 만드는가? = 579
12.3 리스트 스케줄링 = 581
12.3.1 효율성 고려 = 584
12.3.2 다른 우선순위 기법 = 586
12.3.3 전방, 후방 리스트 스케줄링 = 587
12.3.4 왜 리스트 스케줄링을 사용하는가? = 589
12.4 고급 주제들 = 591
12.4.1 지역적 스케줄링 = 591
12.4.2 문맥 복제 = 600
12.5 요약과 전망 = 603
기타 = 603
13 레지스터 할당 = 605
13.1 소개 = 605
13.2 배경 = 606
13.2.1 메모리와 레지스터 = 606
13.2.2 할당과 지정 = 607
13.2.3 레지스터의 분류 = 609
13.3 지역 레지스터 할당과 지정 = 610
13.3.1 하향 지역 레지스터 할당 = 611
13.3.2 상향 지역 레지스터 할당 = 612
13.4 기본 블록보다 큰 경우 = 615
13.4.1 Liveness와 생존 범위 = 616
13.4.2 블록 경계에서의 복잡성 = 618
13.5 전역 레지스터 할당과 지정 = 619
13.5.1 전역 생존 범위 분석 = 622
13.5.2 전역 스필 비용 평가 = 623
13.5.3 추론과 간섭 그래프 = 625
13.5.4 하향 컬러링 = 628
13.5.5 상향 컬러링 = 630
13.5.6 Degree를 줄이기 위한 생존 범위의 coalescing = 632
13.5.7 복습과 비교 = 634
13.5.8 간섭 그래프에서 기계의 특이한 속성 표현 = 635
13.6 고급 주제 = 637
13.6.1 그래프 컬러링 할당의 변형 = 637
13.6.2 레지스터 할당에서 더욱 어려운 문제들 = 640
13.7 요약과 전망 = 643
기타 = 643
부록 ILOC = 647
A.1 소개 = 647
A.2 이름 부여 법칙 = 650
A.3 연산들 = 650
A.3.1 산술 연산 = 651
A.3.2 시프트 = 652
A.3.3 메모리 연산 = 652
A.3.4 레지스터에서 레지스터로의 복사 연산 = 653
A.4 예제 = 654
A.5 제어 흐름 연산 = 655
A.5.1 비교와 조건문 = 656
A.5.2 점프 = 657
A.6 SSA의 표현 = 658
부록 B 데이터 구조 = 661
B.1 소개 = 661
B.2 집합의 표현 = 662
B.2.1 순차 리스트를 이용한 집합 표현 = 663
B.2.2 비트 벡터를 이용한 집합 표현 = 665
B.2.3 성긴 집합의 표현 = 665
B.3 IR의 구현 = 667
B.3.1 그래픽한 IR 표현 = 667
B.3.2 선형 IR 형태 = 672
B.4 해시 테이블의 구현 = 673
B.4.1 해시 함수의 선택 = 675
B.4.2 오픈 해싱 = 676
B.4.3 오픈 어드레싱 = 378
B.4.4 심볼 레코드의 저장 = 680
B.4.5 내포된 어휘 스코프의 추가 = 681
B.5 유연한 심볼 테이블의 설계 = 684
기타 = 686
참고문헌 = 689
찾아보기 = 709
