컴파일러 1장

1.서론

프로그램이 실행될 수 있기전에 먼저 컴퓨터에서 실행될 수 있는 형태로 번역되어야 한다.

컴파일러는 이러한 번역을 수행하는 소프트웨어 시스템을 의미한다.

컴파일러 작성에 관한 학습은 프로그래밍 언어, 기계구조, 언어학이론, 알고리즘, 소프트웨어 공학을 언급한다.

원시언어:컴퓨터가 자동으로 프로그램을 번역하는 과정에서 입력으로 주어지는 프로그래밍언어.

컴파일러: 원시언어의 프로그램을 읽어들여 의미가 같은 다른 목표 언어로 번역하는 프로그램이다.

컴파일러의 중요한 역할은 번역과정에서 탐지되는 원시 프로그램의 오류를 보고하는 것이다.

인터프리터는 사용자가 제공한 입력에 대해서 원시 프로그램에서 명기된 연산을 직접 실행한다.

컴파일러는 인터프리터보다 빠르다.

인터프리터는 컴파일러보다 더 좋은 오류 진단 메시지를 제공한다. 문장단위로 원시프로그램을 실행하기 때문에.

자바 언어 처리기는 컴파일 방법과 인터프리터 방법을 결합한다.

자바 원시 프로그램은 바이트코드라는 중간코드로 컴파일된다. 그리고 바이트코드는 가상머신에 의해 인터프리팅된다. 장점은 다른 기계에서도 인터프리팅이 가능하다는 것이다.

입력을 출력으로 더 빨리 하기위해 JIT컴파일러는 중간 프로그램을 실행하기 전에 바이트코드를 기계어로 변환하여 입력을 처리한다.

원시프로그램을 별도의 모듈에 분할되어 다른 파일에 저장될 수 있다. 원시 프로그램을 모으는 작업은 전aa처리기라고 불리는 별도의 프로그램에 위탁된다.

전처리기(preprocessor):컴파일을 하기전에 필요한 것들에 대해 사전처리나 사전준비적인 계산을 하는 프로그램.

전처리기는 매크로라 불리는 축약을 원시언어문장으로 확장한다.

어셈블리 언어는 출력이 용이하고 디버깅하고 쉽기 때문에 컴파일러는 출력으로 어셈블리언어 프로그램을 만든다.

어셈블리 언어는 어셈블러라는 프로그램에 의해 처리된다.

어셈블리어:기계어의 명령부와 번지부를 사람이 이해하기 쉬운 기호와 일대일 대응시켜 기호화한 프로그램 언어

어셈블:어셈블러 언어를 기계어로 번역하는 것

어셈블러:어셈블리어 언어를 기계어로 번역하는 프로그램

재배치 가능한(relocatable):거의 프로그램이나 루틴이 주기억장치 상의 어느 영역에서든 로드할 수 있고, 또 로드된 상태로 실행할 수 있는 형태로 되어있는 것을 표시할 때 사용.

대형 프로그램은 가끔 여러부분으로 컴파일 된다.따라서 리로케이터블 코드는 다른 리로케이터블 목적파일과 라이브러리 파일들과 결합되어 기계에서 실제로 실행가능한 목적파일로 변환된다.

링커는 외부 메모리 주소(한 파일의 코드가 다른 파일에 있는 위치를 참조하는 경우)를 해결한다.

로더는 모든 실행 가능한 목적 파일을 통합하여 실행을 위해 기억장소에 적재한다.

 

1.2 컴파일러의 구조

컴파일러의 맵핑에는 두 부분이 있다(분석과 통합)

분석 부분은 원시 프로그램을 구성 요소들로 분리하고 이 구성요소에 문법적인 구조를 해석한다. 그런 후 이 구조를 이용하여 원시 프로그램의 중간 표현을 생성한다.

만약 원시 프로그램이 구문적으로 잘못되었거나 의미적으로 불합리하다는 것을 탐지하면 분석부분은 유익한 메시지를 제공해야한다. 이를 통해 사용자는 조치를 취할 수 있다.

또 분석부분은 원시프로그램의 정보를 수집하고 그 정보를 심볼 테이블이라는 데이터 구조에 저장한다. 이 테이블은 중간표현과 더불어 통합부분으로 전달된다.

 

 

중간코드(중간표현): 컴파일러가 원시 언어로 된 프로그램을 목적 코드로 번역하는 과정에서 생성되는 내부적인 코드. 컴파일 과정에서 중간코드를 사용함으로써 번역 단계를 세분화된 모듈로 구성할 수 있으며, 각 단계별로 사용되는 중간 코드들은 일반적으로 다른 형태를 갖는다.

 

통합부분은 중간코드와 심볼테이블을 통해 바람직한 목표 프로그램을 생성한다. 분석 부분은 전단부라 불리고 통합부분은 후단부라 불린다.

 

 

컴파일러의 첫 번째 단계를 어휘 분석 또는 스캐닝이라 한다.

어휘 분석기는 원시 프로그램을 형성하는 문자의 스트림을 읽어서 문자들을 어휘항목(lexeme)이라 불리는 의미 있는 문자의 나열로서 묶는다.

어휘분석기는 각 어휘항목에 대해서 출력으로써 다음 형태의 토큰을 출력한다.토큰은 구문 분석기로 전달된다.

<토큰-이름, 속성-값>

토큰에서 첫 요소인 토큰-이름은 구문 분석 중에 사용되는 추상 기호이고 두 번째 요소인 속성-값은 토큰을 위한 심볼테이블에 있는 한 항목을 가리킨다.

심볼테이블 항목에 있는 정보는 의미 분석과 코드생성에서 요구된다.

예를 들어 원시 프로그램이 다음 코드를 갖는다고 하자.

position=initial+rate*60

이 코드에서 문자들은 어휘항목으로 분류되어 구문 분석으로 전달되는 토큰으로 사상된다.

position은 토큰<id,1>로 사상되는 어휘항목이다. id는 식별자를 의미하는 추상기호이고, 1은 position의 심볼 테이블 항목을 가리킨다.

기호 =은 토큰<=>으로 사상하는 어휘항목이다. 이 토큰은 속성-값이 필요없기 때문에 두 번째 요소는 생략되었다.

initial은 토큰<id,2>로 사상하는 어휘항목이다.

+는 토큰<+>로 사상하는 어휘항목이다.

rate는 토큰<id,3>으로 사상하는 어휘항목이다.

*는 토큰<*>로 사상하는 어휘항목이다.

60은 토큰 <60>으로 사상하는 어휘항목이다.

최종 분석후 코드이다.

<id,1><=><id,2><+><id,3><*><60>

 

 

1.2.2 구문 분석

컴파일러의 두 번째 단계를 구문 분석 또는 파싱이라 한다.파서는 어휘 분석기에서 생성된 토큰의 첫 번째 요소를 사용하여 토큰 스트림의 문법 구조를 나타내는 트리 모양의 중간 표현을 만든다.

전형적인 표현은 구문 트리이며 이 트리에서 각 내부 노드는 연산을 나타내고 그 노드의 자식 노드는 연산의 피연산자를 나타낸다.

 

1.2.3 의미 분석

의미 분석기는 구문 트리와 심볼 테이블에 있는 정보를 이용하여 프로그램이 언어 정의에 의미적으로 일치하는지를 검사한다.

중간 코드 생성에 이용하기 위해 타입 정보를 수집하여 구문 트리나 심볼 테이블에 저장한다.

의미 분석의 중요한 부분이 타입검사이다. 타입 검사에서 컴파일러는 각 연산자가 부합되는 피연산자를 갖는지를 검사한다. 예를 들면 많은 프로그래밍 언어 정의에서 배열첨자는 정수여야 한다. 컴파일러는 부동소수점 수가 배열을 접근하기 위해서 사용되면 오류라고 보고해야 한다.

언어 명세가 강제변환이라고 불리는 타입 변환을 허용할 수도 있다.

 

1.2.4 중간 코드 생성

구문 트리는 중간표현의 한 형태이다.

구문트리는 구문 분석과 의미 분석에서 가장 일반적으로 사용된다.

원시코드의 구문 분석과 의미 분석이 있은 직후 많은 컴파일러는 저수준 중간 표현이나 기계어 같은 중간 표현을 생성한다. 이 표현은 추상기계에 대한 프로그램으로 생각할 수 있다.

추상기계: 컴퓨터 하드웨어나 소프트웨어의 이상적인 모형이다.

이 중간 표현은 두가지 특성을 갖는다. 즉 생산하기 쉬워야 하고 목표 기계어로 번역하기도 쉬워야 한다.

3주소코드:컴퓨터를 동작시키기 위한 명령 코드의 일종으로, 주소를 3개 포함하는 것이다.

그림 16의 중간 코드 생성기의 출력은 3주소 코드 나열로 구성된다.

t1=inttofloat(60)

t2=id3*t1

t3=id2+t2

id1=t3

 

1.2.5 코드 최적화

기계 독립코드 최적화 단계는 보다 좋은 목표 코드를 생성하도록 중간 코드를 개선한다. (저전력 혹은 고속)

 

t1=id3*60.0

id1=id2+t1

 

코드가 더 짧아졌다.

 

1.2.6 코드 생성

코드 생성은 원시프로그램의 중간 표현을 입력으로 사용하여 이를 목표언어로 나타낸다.

예를 들면 레지스터 R1과 R2를 이용하여 중간 코드를 다음과 같이 기계어 코드로 변환할 수 있다.

LDF R2,id3

MULF R2,R2 #60.0

LDF R1,id2

ADDF R1,R1,R2

STF id1,R1

 

1.2.7 심볼테이블 관리

컴파일러의 중요한 기능은 원시프로그램에서 사용되는 변수이름을 저장하고 각 이름의 여러 가지 속성에 관한 정보를 수집하는 것이다.

심볼테이블은 각 변수 이름에 대해 하나의 레코드를 갖는 데이터 구조이다.

이 데이터 구조는 컴파일러가 각 이름에 대한 레코드를 빨리 찾고 레코드에 대한 데이터를 빨리 저장하고 추출하는 것이 가능하도록 설계되어야 한다.

 

1.2.8 단계를 패스로 통합

실질적인 구현에서 여러 단계의 동작들은 입력 파일을 읽고 출력파일을 작성하는 패스로 통합된다. 예를 들면 전단부 단계인 어휘분석, 구문분석, 의미분석과 중간 코드 단계는 한 개의 패스로 통합될 수 있다. 코드 최적화는 선택적 패스이다.

 

1.2.9 컴파일러-구성 도구

파서 생성기:프로그래밍 언어의 구문적인 서술로부터 구문 분석기를 자동적으로 생성한다.

스캐너 생성기:언어의 토큰의 정규식으로부터 어휘 분석기를 생성한다.

구문지시 번역 엔진:파스 트리를 순회하고 중간 코드를 생성하는 루틴의 집합을 생성한다.

코드 생성기 생성기:중간 코드의 각 연산을 목표기계의 기계어로 변환하는 규칙의 집합으로부터 코드생성기를 생성한다.

데이터흐름 분석엔진:값들이 프로그램의 한 부분에서 각기 다른 부분에 전달되는 방법에 관한 정보를 수집하는 작업을 수월하게 한다. 데이터흐름 분석은 코드 최적화의 중요한 부분이다.

컴파일러-구성 도구 키트:컴파일러의 여러 단계를 구성하는 루틴의 통합적인 집합을 제공한다.

 

 

1.4 컴파일러를 구성하는 기술

컴파일러는 언어의 명세를 따르는 모든 원시 프로그램을 수락하여야 한다.

1.4.2 코드 최적화 기술

컴파일러 설계에서 최적화라는 용어는 최적의 코드보다는 더 효율적인 코드를 생성하려는 시도를 언급하는 용어이다. 그러므로 최적화는 잘못된 용어이다. 왜냐하면 컴파일러에서 생상된 코드가 동일한 작업을 수행하는 다른 어떤 코드보다 빠르다는 것을 보장하는 방법이 없기 때문이다.

컴파일러 최적화는 다음 설계 목적을 만족해야 한다.

최적화는 정확해야 한다. 즉 컴파일된 프로그램의 의미를 유지해야 한다.

최적화는 많은 프로그램의 성능을 개선하여야 한다.

컴파일 시간은 타당해야 한다.

공학적 노력의 요구는 관리할 수 있어야 한다.

 

1.5.1 고급 프로그래밍 언어의 구현

일반적으로 고급 프로그래밍 언어는 프로그래밍하기가 쉽지만 덜 효율적이다. 즉 목표 프로그램은 더 느리게 실행된다.