컴퓨터 하드웨어 기술이 빠르게 발전하고 필요한 소프트웨어의 규모와 복잡성이 증가함에 따라 신뢰성이 있고 효율적으로 프로그래밍할 수 있는 프로그래밍 언어의 설꼐 및 이에 따른 컴파일러를 자동적으로 제작하는 것이 중요한 문제로 등장하였다. 프로그래밍 언어와 컴퓨터 구조가 다양해짐에 따라 많은 컴파일러가 필요하게 되었다. 즉, N개의 언어를 M개의 기계에 구현하려 할 때 N*M개의 컴파일러가 필요하다. 이에 따라 컴파일러 제작을 도와주는 도구들이 필요하게 되었고 컴파일러의 전 과정이나 각 단계들을 자동적으로 생상하는 도구들에 대한 연구가 활발하게 진행되었다.
이러한 도구들을 총칭해서 컴파일러 생성기(compiler generator) 또는 컴파일러-컴파일러(compiler-compiler)라 부른다.
1.4 컴파일러 자동화 도구
- 컴파일러-컴파일러는 특정한 프로그래밍 언어를 위한 언어 표현과 목적 기계에 대한 기계 표현을 입력으로 받아 하나의 컴파일러를 출력한다. 이때 생성된 컴파일러는 언어 표현에 기술된 소스 프로그램을 입력으로 받아 목적 기계의 코드로 번역해주는 역할을 수행한다.
위에서 제시된 컴파일러-컴팡리러 모델은 이상적인 경우이고 실제적으로 요사이에 개발된 번역기 제작 시스템은 어휘 분석, 구문 분석, 그리고 코드 생성과 같이 컴파일러의 한 단계만을 취급한다. 이렇게 만들어진 컴파일러의 단계는 다른 자동화 도구에 의해 생성된 단계와 통합하여 구현될 수 있다.
다음은 컴파일러의 각 단계를 생성하는 자동화 도구를 기능적인 면에서 살펴본 그림이다.
[그림1.16]
- 생성기-생성기(generator-generator)는 생성될 단계의 기능을 묘사하는 메타 언어를 입력으로 받아 각 단계가 사용하게 될 테이블 또는 프로그램을 출력한다. 그러면 각 구동기는 이 테이블을 이용하여 그 단계에서 수행해야 할 일을 처리한다. 따라서 필요한 컴파일러 단계를 구현하기 위하여 프로그램을 작성하는 것이 아니라 그 단계에서 처리하는 작업을 메타 언어로 기술하면 되는 것이다.
어휘 분석이나 구문 분석 단계에 대한 자동화 도구는 1970년대에 나타났으나 후단부 작성을 도와주는 도구는 최근에 이르러서야 발표되기 시작했다. 그 이유는 최적화나 코드 생성에 대한 정형화(formalism)가 어려웠기 때문이다.
1.4.1 어휘 분석기 생성기
어휘 분석기 생성기(Lexical Analyzer Generator)는 어휘 분석기를 자동으로 생성하는 도구이다.
- 토큰에 대한 표현을 입력으로 받아 기술된 형태의 토큰을 찾아내는 어휘 분석기를 만든다. 생성된 어휘 분석기는 입력 프로그램에서 토큰들을 구분해 내는 일을 한다.
[그림1.17]
- 일반적으로 토큰의 형태를 기술하는 토큰 표현 방법으로는 정규 표현을 사용한다.
- 어휘 분석기 생성기의 대표적인 예로는 UNIX 운영 체제하에서 수행되는 렉스(Lex)가 있는데, 이는 1975년 벨 연구소에서 근무하는 레스크(M.E.Lesk)에 의해 개발된 소프트웨어 도구로 토큰의 형태를 묘사한 정규 표현들과 각 정규 표현이 매칭되었을 때 처리를 나타내는 액션 코드(action code)로 구성된 입력을 받아 어휘 분석의 일을 처리하는 프로그램을 출력한다.
- 여기서 lex.yy.c가 어휘 분석 작업을 담당하도록 생성된 C 프로그램이다.
1.4.2 파서 생성기
파서 생성기(parser generator)란 언어의 문법 표현으로부터 파서(구문 분석기)를 자동으로 생성하는 도구를 말하며 보통 파서 제작 시스템(PGS: Parser Generating System)이라 부른다.
[그림1.19]
- 언어의 문법 표현으로부터 파서 생성기는 파서를 제어하는 테이블을 생성한다. 파서는 이 테이블을 이용하여 주어진 문장에 대한 문법적인 검사를 하며 다음 단계에서 필요한 의미 정보를 만든다.
- 모든 언어에 대하여 파서 부분은 동일하고 테이블만 다르다. 그러므로, 새로운 언어에 대한 파서를 만들기 위해서는 단지 문법 표현만 바꾸면 된다. 일반적으로 context-free 문법을 문법 표현으로 사용한다.
- 파서 생성기는 컴파일러를 구현한느데 있어서 꼭 필요한 도구로, 대표적인 파서 생성기로는 YACC이 있다.
YACC(Yet Another Compiler-Compiler)는 1975년 벨 연구소에서 근무하는 S.C.Johnson을 중심으로 개발된 파서 생성기로 Lex와 마찬가지로 UNIX 운영 체제하에서 수행되는 유틸리티이다.
- YACC은 문법 규칙과 그에 해당하는 액션 코드를 입력으로 받아 파싱을 담당하는 프로그램을 출력한다. 일반적으로 YACC은 파서만을 생성하고 따라서 필요한 스캐너는 Lex를 사용하여 생성할 수 있다.
- 다음은 Lex와 YACC을 이용하여 컴파일러의 전단부를 구현하는 예이다.
[그림1.20]
- y.tab.c가 YACC으로부터 생성된 프로그램으로 문법 규칙에 의해 기술된 언어의 문장에 대해 구문 검사를 하며 문법 규칙과 결합된 액션 코드를 필요할 때마다 수행한다.
- Lex와 YACC의 액션 코드는 일반적으로 C언어로 작성한다.
1.4.3 코드 생성의 자동화
코드 생성은 중간 언어를 목적 기계 언어로 바꾸는 컴파일러의 과정으로 기계 정형화(machine formalization)를 통하여 자동적으로 구성하려 한다. 목적 기계의 명령어들을 나타낸 테이블을 사용하여 기계 독립적인 코드 생성 알고리즘(CGA: Code Generation Algorithm)을 고안하는 방법이다. 코드 생성 과정을 기계 종속적인 부분과 독립적인 부분으로 나누어 정형화하는데 목적을 두고 있으며 주로 템플릿 매칭 또는 테이블을 이용한 방법에 의해 코드를 생성한다.
[그림1.21]
코드 생성 과정을 자동화한다는 것은 위 그림에서 보는 것과 같이 기계 독립적인 CGA와 CGA가 사용하는 테이블을 기계 표현으로부터 ㅈ동적으로 유도한느 것을 의미한다.
코드 생성에 관한 과거의 연구는 패턴 매칭 코드 생성과 테이블을 이용한 코드 생성으로 나눌 수 있는데, 이들 모두 기계 종속적인 테이블과 코드 생성 알고리즘을 분리해서 코드 생성 과정을 정형화하려는 의도이다. 두 방법은 테이블 구성을 위해 적용되는 알고리즘과 기계 표현의 일반성 면에서 서로 조금씩 다르다.
- 패턴 매칭 코드 생성에서는 목적 코드를 생성하기 위해 경험적인 검색 알고리즘(heuristic search algorithm)을 사용한다.
- 테이블을 이용한 코드 생성에서는 context-free 파싱 이론으로부터 유도된 결정적 파싱 알고리즘(deterministic parsing algorithm)을 사용한다.
1.4.4 컴파일러-컴파일러 시스템
컴파일러의 한 부분만을 자동화하면 그 나머지 부분은 컴파일러 설치자가 제공해야 한다. 그러므로 실질적인 컴파일러 제작 시스템이 되기 위해서는 전과정을 자동화해야 한다. 이와 같은 의도는 PQCC(Production-Quality Compiler Compiler)팀과 ACK(Amsterdam Compiler Kit)팀에 의하여 시도되었다. 이들은 컴파일러 개발 과정을 자동화하기 위한 도구들이다.
- PQCC(Production-Quality Compiler Compiler) :
- 카네기 멜론 대학에서 W. Wulf를 중심으로 개발된 PQCC는 소스 언어와 목적 기계를 정형화하여 컴파일러를 생성하는 시스템이다. 컴파일러의 전단부가 잘 정립된 반면 후단부는 미비한 상태이다. 실질적인 번역기 제작 시스템을 구현하려면 체계적인 후단부가 필요하다. 이와 같이 실질적인 컴파일러-컴파일러 시스템을 구성하려는 연구가 PQCC이다.
- 다음은 PQCC의 전반적인 개요이다.
[그림1.22]- PQCC에서는 트리 형태의 중간 언어인 TCOL(Tree Common Oriented Language)를 사용하였으며 그 시스템의 기능은 언어와 목적 기계에 대한 정형화된 표현을 입력으로 받아 PQC(Production Quality Compiler)라고 부르는 기초 코드 생성기와 최적화기가 사용하는 테이블을 만들어 낸다. 그리고 PQC는 이 테이블을 이용하여 전단부에서 생성한 TCOL을 목적 코드로 번역하는 작업을 한다.
- ACK(Amsterdam Compiler Kit) :
- ACK는 컴파일러의 후단부를 자동화하기 위한 도구의 하나로서 이식성과 재목적성(retargetability)이 매우 높은 컴파일러를 만들기 위한 실질적인 도구이다. 네덜란드 소재 브리제(Vrije) 대학의 Andrew S. Tanenbaum을 중심으로 개발되었다.
- 각 언어에 대한 전단부가 중간 언어인 EM(Encoding Machine) 코드를 생성해 낸다. EM 코드는 가상적인 스택 기계에 근거를 둔 일종의 어셈블리어이다. 그리고 생성된 EM 코드에 대한 최적화 과정(peephole optimization & global optimization)을 거친 후에 후단부에 의해 목적 프로그램으로 변환된다.
[그림1.23]- ACK에서 작동하는 컴파일러는 8개의 단계로 구성되어 있으며 ACK는 각 단계를 효과적으로 생성할 수 있는 방법을 제공하고 있다.
1) 프리프로세서 preprocessor
2) 전단부 front-end
3) 핍홀 최적화기 peephole optimizer
4) 전역 최적화기 global optimizer
5) 후단부 back-end
6) 목적 기계 최적화기 target machine optimizer
7) 범용 어셈블러와 링커 universal assembler/linker
8) 응용 패키지 utility package- 전단부는 각 언어당 하나씩 존재하며 후단부는 각 기계당 하나씩 필요하다. 현재 ACK에서 제공한 전단부에는 Fortran, Algol, Pascal, BASIC, Moduler-2, Occam, C, Ada, C++ 등이 있으며, 후단부는 Intel 8086/80286/80386, Motorola 68000/68020, Zilog Z80/Z8000, Vax 시스템, Sparc 프로세서, Sun2, Sun3 등이 있다.
