컴파일러 컴파일러

3. 종류

파서 생성기는 파싱 알고리즘에 따라 다양한 종류로 나뉜다.

1964년 최초의 컴파일러 컴파일러 중 하나인 META II는 스택 머신 코드를 생성하고 자체 소스 코드 및 기타 언어를 컴파일할 수 있었다.

벨 연구소의 초기 유닉스 버전에는 C 프로그래밍 언어 코드를 출력하는 lex 및 yacc 시스템이 있었다. 이들의 현대 GNU 버전은 flex와 bison이다.

컴파일러 컴파일러는 코드 생성을 위한 문법에 따라 구문 트리를 타일링하는 데 사용되는 하향식 재작성 기계 생성기([http://jburg.sourceforge.net/ JBurg] 참조) 및 속성 문법 파서 생성기(예: ANTLR)를 포함하여 다양한 형태로 존재한다.^[3]

META I과 META II는 UCLA의 D. 발 쇼르에 의해 개발되었다. 이후 Schorre 기반 메타컴파일러들이 등장했으며, 각 메타컴파일러는 언어 분석 및/또는 코드 생성에 대한 개선 사항을 추가했다.

프로그래밍에서 프로그래밍 언어 이름을 컴파일러와 프로그래밍 언어 모두를 지칭하는 데 사용하는 것이 일반적이며, 문맥에 따라 그 의미가 구별된다. 예를 들어, META II는 컴파일러이자 언어이다.

Schorre 계열 메타컴파일러의 메타언어는 내장된 출력 변환 구문을 가진 하향식 문법 분석 구문을 사용하는 함수형 프로그래밍 언어이다. 구문 방정식은 다음과 같다.

```

= ;

```

여기서 ``은 함수 이름이고, ``는 그룹화, 대안 및 출력 생성을 가질 수 있는 테스트로 구성된 일종의 논리 표현식이다.

프로그래밍 언어를 분석적으로 하향식으로 정의하는 것은 자연스럽다. 예를 들어, 프로그램은 다음과 같이 정의할 수 있다.

```

program = $declaration;

```

이는 프로그램을 0개 이상의 선언 시퀀스로 정의한다.

초기 컴파일러의 문자 집합은 제한적이었다. 문자 '/'는 대체(또는) 연산자에 사용되었고, "A 또는 B"는 A / B로 작성되었다. 괄호 ( )는 그룹화에 사용되었다.

```

A (B / C)

```

위는 A 다음에 B 또는 C가 오는 구문을 설명한다.

Generators Language는 Lisp과 유사한 의미 체계를 가지고 있었다. 구문 분석 트리는 재귀적인 리스트로 간주되었다. Generator Language 함수의 일반적인 형태는 다음과 같다.

```

함수이름(첫번째_구문분석_규칙) => 첫번째_생성_코드_생성기

(두번째_구문분석_규칙) => 두번째_생산_코드_생성기

(세번째_구문분석_규칙) => 세번째_생산_코드_생성기

...

```

생성기 호출은 구문분석_규칙에서 사용될 수 있다. 예를 들면 다음과 같다.

```

expr_gen(ADD[expr_gen(x),expr_gen(y)]) =>

<AR + (x*16)+y;>

releasereg(y);

return x;

(SUB[expr_gen(x),expr_gen(y)])=>

<SR + (x*16)+y;>

releasereg(y);

return x;

(MUL[expr_gen(x),expr_gen(y)])=>

.

.

.

(x)=> r1 = getreg();

load(r1, x);

return r1;

...

```

즉, 구문 분석 트리가 (ADD[,])처럼 보이면 expr_gen(x)가 과 함께 호출되어 x를 반환한다.

프로그래밍 언어의 컴파일러를 개발하는 데에는 기술과 노력이 필요하다. 이를 지원하기 위해, 언어의 구문 등 정의로부터 컴파일러를 생성하는 컴파일러 생성기(컴파일러 컴파일러)가 연구되었다. 그 과정에서 입력을 처리하는 구문 분석기를 자동 생성하는 프로그램(파서 생성기)이 개발되어 널리 실용화되었다.

3. 1. LL 파서 생성기

3. 2. LR 파서 생성기

• yacc
• GNU Bison
• SableCC

3. 3. 파서 콤비네이터

• Parsec - Haskell용 파서 컴비네이터 라이브러리
• Scala Standard Parser Combinator Library

3. 4. Packrat 파서 생성기

• PackCC - C용 (좌재귀 지원)
• XPEG - C++용

4. 메타컴파일러

메타컴파일러는 컴파일러의 모든 측면을 설명하는 특수 메타프로그래밍 언어를 입력으로 받아 컴파일러를 생성하는 도구이다. 이는 컴파일러 작성을 위한 도메인 특화 언어의 주요 예시이며, 특정 문제의 사양에 적합한 도메인 특화 대상 언어에 대한 번역기 제작 비용을 줄여준다.

메타컴파일러의 메타언어는 일반적으로 강력한 문자열 및 기호 처리 언어이므로, 광범위한 기타 소프트웨어 엔지니어링 및 분석 도구 생성을 포함하여 범용 애플리케이션에 강력하게 적용될 수 있다.

메타컴파일러는 ''일반적으로 자체 메타언어로 작성된'' 메타프로그램이거나 기존 컴퓨터 프로그래밍 언어로 작성된 메타프로그램이다. 자체 메타언어로 작성된 메타컴파일러가 자체를 컴파일하는 과정은 셀프 호스팅 컴파일러와 동일하다.

대표적인 메타컴파일러로는 META II, TREE-META, CWIC 등이 있다.

초기 Schorre 메타컴파일러인 META I과 META II는 UCLA의 D. 발 쇼르에 의해 개발되었다. 이후 다른 Schorre 기반 메타컴파일러들이 등장했으며, 각 메타컴파일러는 언어 분석 또는 코드 생성에 대한 개선 사항을 추가했다.

Schorre 계열 메타컴파일러의 메타언어는 내장된 출력 변환 구문을 가진 하향식 문법 분석 구문을 사용하는 함수형 프로그래밍 언어이다. 구문 방정식은 다음과 같다.

` = ;`

이는 '성공' 또는 '실패'를 반환하는 컴파일된 ''테스트'' 함수이다. ``은 함수 이름이고, ``는 그룹화, 대안 및 출력 생성을 가질 수 있는 테스트로 구성된 일종의 논리 표현식이다.

4. 1. META II

4. 2. TREE-META

4. 3. CWIC

CWIC 저자들은 메타컴파일러가 컴파일러 구축의 비창의적인 측면을 자동화하여 컴파일러 구축 작업을 돕는다고 설명한다. 이를 통해 특정 문제 사양에 적합한 언어를 설계할 수 있으며, 이러한 언어에 대한 처리기 생산 비용을 줄여 문제 해결을 언어 설계로 시작하는 것이 경제적으로 가능하게 된다.

5. 결론

프로그래밍 언어의 컴파일러 개발에는 많은 기술과 노력이 필요하다. 이러한 과정을 돕기 위해, 언어의 구문 정의로부터 컴파일러를 자동으로 생성하는 컴파일러 생성기(컴파일러 컴파일러라고도 함)가 연구되었다. 이 과정에서 입력값을 처리하는 구문 분석기를 자동으로 생성하는 프로그램, 즉 파서 생성기가 개발되어 널리 사용되고 있다.^[1]

참조

_[1] 서적 Compilers : principles, techniques, & tools https://www.worldcat[...] 2007
_[2] 논문 A Syntax Directed Compiler for ALGOL 60 1961-01
_[3] 간행물 SIS: A Compiler-Generator System Using Denotational Semantics Dept. of Computer Science, University of Aarhus, Denmark 1978-06
_[4] 웹사이트 Tony Brooker and the Atlas Compiler Compiler http://curation.cs.m[...] 2016-04
_[5] 학회자료 The genesis of attribute grammars https://www.dcs.warw[...] Springer-Verlag
_[6] 학술지 Eli: A complete, flexible compiler construction system
_[7] 학술지 A syntax improving program
_[8] 웹사이트 ANTLR http://www.antlr.org[...]
_[9] 웹사이트 JavaCC https://javacc.dev.j[...]
_[10] 웹사이트 Coco/R http://www.ssw.uni-l[...]
_[11] 웹사이트 SableCC http://sablecc.org/