컴파일 과정을 수행하는 프로그램. 소스 코드 전체를 목적 코드로 번역해 그 결과를 한 번에 실행하고, 번역과 실행이 따로 진행되므로 번역은 오래 걸려도 실행은 빠르다. 내부는 여섯 단계로 나뉜다.
Front-End와 Back-End
앞쪽 절반은 언어에 의존하고 기계에 독립적인 Front-End, 뒤쪽 절반은 언어에 독립적이고 기계에 의존하는 Back-End다. 이렇게 갈라두면 언어 하나를 여러 기계로 옮길 수 있고 기계 하나가 여러 언어를 받을 수 있다. PSA와 같은 발상이다.
어휘 분석과 구문 분석
첫 단계인 어휘 분석기(Lexical Analyzer, Scanner)는 소스 프로그램을 토큰의 나열로 바꾼다. 문자의 나열을 컴파일러 내부에서 다루기 쉬운 정수로 바꿔주는 일이다. if (a > 10)이 있다면 if, (, a, >, 10, ) 여섯 개의 토큰이 생성된다. 대표적인 토큰 분석기가 Lex다.
토큰의 나열은 구문 분석기(Syntax Analyzer, Parser)로 넘어간다. 구문(Syntax)을 체크하고 트리를 생성하는 단계다. 문법에 맞지 않으면 오류 메시지를 내고, 맞으면 프로그램 구조를 트리 형태로 출력한다. 대표적인 구문 분석기는 Yacc이며, 이후의 모든 단계가 이 트리 위에서 돈다.
중간 코드와 의미 검사
중간 코드 생성기는 의미(Semantic)를 체크한다. 문법은 맞는데 뜻이 틀린 경우를 잡아내는 자리다.
if (a > 10) a = 1.0; // a가 정수라면 semantic error
a = b + 1;코드 최적화
코드 최적화기는 선택적 단계(optional phase)다. 비효율적인 코드를 구분해내서 더 효율적인 코드로 바꿔준다. LDC R1, 1이 연달아 두 번 나오면 load가 중복이니 하나를 없애는 식이다. 주된 목표는 실행 시간 개선이고 코드 크기 축소는 부차적이다. 최적화에는 지켜야 할 기준이 붙는다. 프로그램의 의미를 보존할 것, 평균 속도가 올라갈 것, 그리고 들이는 노력이 값어치할 것.
최적화는 보는 범위에 따라 갈린다. 지역 최적화는 좁은 범위만 들여다보고(local inspection) 고치는 방법으로, 컴파일 시점에 계산할 수 있는 것을 미리 계산하는 상수 접기(constant folding), 중복된 적재와 저장 명령 제거, 대수적 간소화, 비싼 연산을 싼 것으로 바꾸는 강도 감소가 여기 든다. 전역 최적화는 값이 프로그램 전체를 어떻게 흐르는지 분석하는 기법(flow analysis technique)을 써서 공통 부분식을 없애고, 반복문 안에서 변하지 않는 계산을 밖으로 빼고, 도달할 수 없는 코드를 지운다.
목적 코드 생성
목적 코드 생성기는 중간 코드로부터 실제 기계 명령어(machine instruction)를 생성한다. 명령어를 고르고, 레지스터를 관리하고, 저장 공간을 할당하고, 기계에 의존적인 최적화를 한다.
오류 처리
마지막은 오류 처리다. 오류가 다른 문장에 영향을 미치지 않도록 수정하는 것이 error recovery이고, 오류를 복구해주는 것이 error repair다. 한 번 컴파일에 여러 오류가 한꺼번에 보고되는 것은 recovery가 있어서다. 오류 처리 전체는 검출, 수습, 보고, 복구로 이루어진다. 오류는 구문 오류, 의미 오류, 실행 시간 오류로 나뉘는데 앞의 둘은 컴파일러가 잡고 마지막은 못 잡는다. Checked와 Unchecked의 구분과 통한다.
Lex와 Yacc
앞의 두 단계를 만들어주는 도구인 Lex와 Yacc은 보통 같이 구현한다. Lex(A Lexical Analyzer Generator)는 입력 스트림에서 정규 표현식으로 기술된 토큰들을 찾아내는 프로그램을 작성하는 데 쓰는 도구다. Lex 소스는 정규 표현식과 해당하는 프로그램 조각의 테이블이고, 그 테이블이 입력 스트림을 읽어 출력 스트림으로 복사하면서 입력을 주어진 표현식에 매칭되는 문자열로 분할하는 프로그램으로 변환된다. Yacc(Yet Another Compiler-Compiler)은 유닉스 시스템의 표준 파서 생성기다. 파스 트리를 생성할 때 Bottom-up(LR)을 채택하고 그중에서도 단순 LR에 선행 예측을 더한 LALR(Look-Ahead LR) 방식을 쓴다.
둘 사이에는 위아래가 있다. Yacc이 Lex의 상위에서 구현된다.
main() → yyparse() Yacc이 만든 구문 분석기
↓ 토큰이 필요하면
yylex() Lex가 만든 어휘 분석기
Lex는 입력 문자열에 대한 일차적인 검색을 하고 실제적인 분석은 Yacc이 한다. 1단계와 2단계의 분업이 도구 수준에서 그대로 나타난다.
문법을 적는 BNF
구문 분석기가 판단의 근거로 삼는 문법은 BNF로 적는다. 문법을 형식적으로 기술하는 표기법이고, 반복과 선택 표기를 더해 간결하게 만든 것이 EBNF다. 자세한 내용은 구문 표기법에 있다.
패스 수에 따른 갈래
소스를 몇 번 읽느냐로도 갈린다. 단일 패스 컴파일러는 초창기의 컴파일러이고 컴파일 속도가 빠르다.
다중 패스 컴파일러는 컴파일 속도가 느린 대신 얻는 것이 있다. 부분적인 기능 개선이 가능하고, 다른 기종으로 이전하기 편리하며, 요구하는 기억 공간이 작다.