컴파일러의 이해

번역기의 종류

번역기는 하나의 프로그래밍 언어로 작성된 프로그램을 그와 동등한 의미를 가진 다른 프로그래밍 언어로 된 프로그램으로 변환하는 프로그램이다.

이때 입력되는 프로그램을 소스 프로그램이라 하고 소스 프로그램을 기술하는 언어를 소스 언어라 한다.

또한 출력되는 프로그램을 목적 프로그램이라 하고 목적 프로그램을 기술하는 언어를 목적 언어라 한다.

 

소스프로그램	번역기	목적프로그램
어셈블리어로 작성된 프로그램	어셈블러	기계어 프로그램
고급 언어로 작성된 프로그램	컴파일러	어셈블리어 또는 기계어 프로그램
고급 언어로 작성된 프로그램	프리프로세서	고급 언어로 작성된 프로그램
고급 언어로 작성된 프로그램	인터프리터	실행 결과

 

* 프리프로세서는 전처리기라고도 불리는데

소스 프로그램과 목적 프로그램이 모두 고급 언어인 번역기로 프로그래밍 언어에 유용한 기능을 추가하여

언어를 확장하는 역할을 한다.

프리프로세서는 일반적으로 코볼 언어로 작성된 프로그램을 가지고 있지만 코볼 컴파일러가 없는 경우에는 실행할 수 없다.

하지만 코볼 컴파일러는 없어도 C 컴파일러가 있다면 실행해볼 수 있다.

코볼 언어로 작성된 프로그램을 C 언어로 작성된 프로그램으로 변환하고 C 언어로 변환된 프로그램을 C 컴파일러에서 컴파일 및 실행하면 된다.

 

프리프로세서의 헤더 파일이 포함된 파일 포함 기능 : C언어에서 사용자가 #include <stdio.h>라는 문장을 작성했다면 프리프로세서가 컴파일하기 전에 #include <stdio.h>를 삭제하고 그 자리를 입출력과 관련된 표준 함수 stdio.h의 내용으로 대체한다.

 

매크로 처리 기능 : 프리프로세서는 매크로로 정의된 부분에 대해 컴파일하기 전에 매크로의 내용으로 확장시킨다.

예를 들어 #define max 45는 이 프로그램에서 max가 나타날 때마다 그것을 45로 바꿔준다.

 

조건부 컴파일 기능 : 조건부 컴파일은 조건에 따라 소스 프로그램의 일부분을 선택적으로 삽입하거나 삭제하는 기능을 말한다.

 

---

다른 번역기들과는 달리 인터프리터는 번역과 동시에 실행된다.

즉 고급 언어를 입력받아 번역과 동시에 실행한 뒤 그 결과를 출력하므로 API 스노볼 등과 같은 대화용 언어를 구현할 때 사용된다.

 

 

언어 처리 시스템

문제가 주어지고 그 문제에 대한 알고리즘을 작성해서 소스 프로그램으로부터 실행 가능한 목적 프로그램을 생성하는 것을 언어 처리 시스템이라 하며 이때 컴파일러 이외에 여러 가지 다른 번역기가 필요할 수도 있다.

언어를 선택하고 나면 그 언어에 맞게 알고리즘을 프로그램으로 바꾸는데 이것을 소스 프로그램이라 한다.

소스 프로그램은 프리프로세서를 통해 확장된 소스 프로그램이 되고 확장된 소스 프로그램은 컴파일러의 입력이 된다.

컴파일러는 목적 어셈블리 프로그램을 출력하는데 이때 두 가지 경우를 생각해 볼 수 있다.

1. 컴파일러가 직접 재배치 가능한 기계 코드로 변환

(효율은 좋지만 이식성이 떨어진다)

2. 컴파일러가 어셈블리어로 번역하고 어셈블리어를 어셈블리가 받아서 재배치 가능한 기계 코드로 변환한다.

(효율은 떨어지지만 이식성이 높아진다)

 

 

대형 프로그램은 가끔 여러 부분으로 컴파일된다. 따라서 재배치 가능한 기계 코드를 다른 재배치 가능한 목적 파일 및 라이브러리 파일과 결합하여 기계에서 실제적으로 실행할 수 있는 코드로 변환해주는 것이 링커이다.

링커가 링킹을 하면 여러 개의 파일이 하나의 파일이 되는 것이다.

마지막으로 로더는 실행 가능한 모든 목적 파일을 통합하여 실행을 위해 레지스터를 할당하고 메모리에 적재한다.

 

---

 

※ 컴파일러의 필요성

인간은 문제를 풀기 위해 컴퓨터를 사용하여 컴퓨터와 의사소통을 하는 데 언어가 필요하다.

컴퓨터는 기계어를 사용하지만 인간은 사람 중심 언어인 고급 언어를 사용한다.

따라서 컴퓨터와 인간이 사용하는 언어를 기계어로 번역해주는 컴파일러가 필요하다.

 

 

컴파일러의 논리적 구조

- 컴파일러의 논리적 구조는 전단부와 후단부로 나눌 수 있다.

전단부 : 목적 기계에 독립적이며 소스 프로그램에 관계되는 부분으로 소스 프로그램을 분석하고 중간 코드를 생성하는 부분

후단부 : 목적 기계에 의존적이며 전단부에서 생성한 중간 코드를 특정 기계에 대한 목적 코드로 번역하는 부분

 

- 어휘 분석(스캐닝) : 소스 프로그램을 읽어들여 토큰이라는 의미 있는 문법적 단위로 분리하여 토큰 스트림을 생성한다.

 

- 구문 분석(파싱) : 토큰 스트림을 받아서 주어진 문법에 맞는지 검사하며 주어진 문법에 맞는 문장의 경우 그 문장에 대한 파스 트리를 출력하고 올바르지 않은 문장의 경우 에러 메시지를 출력한다.

 

- 의미 분석 : 구문 트리와 기호표에 있는 정보를 이용하여 소스 프로그램이 언어 정의에 의미적으로 일치하는지를 검사하고 다음 단계인 중간 코드 생성에 이용하기 위해 자료형 정보를 수집하여 구문 트리나 기호표에 저장한다.

 

- 중간 코드 생성 : 구문 트리를 이용하여 각 구문에 해당하는 중간 코드를 생성하거나 한 문법 규칙이 감축될 때마다 구문 지시적 번역이 이뤄진다.

 

- 코드 최적화 : 주어진 입력 프로그램과 의미적으로 동등하면서 좀 더 효율적인 코드로 바꾸어 코드 실행 시 기억 공간이나 실행 시간을 절약한다.

 

- 목적 코드 생성 : 연산을 수행할 레지스터를 선택하거나 자료에 메모리의 위치를 정해주며 실제로 목적 기계에 맞는 코드를 생성한다.

 

 

컴파일러의 물리적 구조

컴파일러의 물리적 구조는 구현에 관련된 사항으로 설계 문제 컴퓨터 자원 문제 사용자의 요구 사항 컴파일러를 개발하는 인적 자원 등을 고려해야 한다.

 

 

---

 

문법 표기법

정규표현 : 정규 언어를 가장 잘 표현할 수 있는 방법

문법도표 : 초보자가 쉽게 이해할 수 있도록 문법을 도식화하는 방법

BNF 표기법 : 프로그래밍 언어의 형식적 정의를 위해 가장 널리 사용되는 방법

EBNF 표기법 : 반복되는 부분을 BNF 표기법보다 읽기 쉽고 간결하게 표현하는 방법

 

유한 오토마타

유한 오토마타는 형식 언어를 인식하는 시스템의 수학적 모델로 그 시스템에서 변화할 수 있는 상태가 유한개인 것

상태 전이도 : 유한 오토마타의 각 상태를 노드로 표현하고 간선은 전이를 나타낸다.

 

 

어휘분석이란 컴파일러의 첫 번째 단계로 소스 프로그램을 읽어들여 문법적으로 의미 있는 최소 단위인 토큰으로 분리하는 것

어휘 분석을 담당하는 도구는 어휘 분석기 또는 스캐너이다.

 

토큰의 인식

토큰 : 문법적으로 의미 있는 최소 단위

패턴 : 각 문자열을 토큰에 대응시키기 위한 규칙

렉심 : 토큰을 구성하는 소스 프로그램에 있는 문자의 나열

---

 

구문 분석 : 문장 w를 입력받아 w가 정의된 문법에 올바른 문장인지 아닌지를 검사하며 그 문법에 맞는 문장이면 w에 대한 파스 트리를 생성하고 그 문법에 맞지 않은 문장이면 에러 메시지를 내보내는 것이다.

 

구문 분석의 종류 : 파스 트리를 어떤 순서로 만드느냐에 따라 하향식 구문 분석과 상향식 구문 분석으로 나뉜다.

 

하향식 구문 분석 : 시작 기호 S로부터 생성 규칙을 적용하여 좌단 유도에 의해 주어진 문자열 w를 찾아가는 방법이다.

 

감축 : 어떤 문장 형태에서 특정한 생성 규칙의 오른쪽 부분을 찾아 왼쪽 부분으로 바꾸는 것

 

예측 구문 분석 : 문법이 바뀔 때마다 구문 분석기 전체를 바꿔야 하는 재귀적 하강 구문 분석의 단점을 보완한 방법으로 문법이 조금 바뀌더라도 구문 분석기 전체를 바꾸지 않고 파싱표만 수정해서 구문 분석기를 구현하는 것

 

모호한 문법의 사용과 에러 처리 루틴

모호한 문법은 모호하지 않은 문법보다 문법의 표현이 간단하며 사람들이 사용하기에 훨씬 자연스런 문법이다.

모호한 문법은 하나의 식에 대해 여러 가지 결과 값이 계산될 수도 있고 비결정적으로 구문 분석을 함으로써 결정적으로 구문 분석을 하는 경우보다 시간이 많이 걸릴 수 있다. 따라서 모호한 문법을 가지고 파싱표를 작성하면 항상 이동 감축 충돌이나 감축 감축 감축 충돌을 야기한다.

충돌을 없애는 방법은 모호한 문법을 동등한 의미를 가진 모호하지 않은 문법으로 변환하는 방법과

모호한 문법을 가지고 파싱표를 작성한 다음 파싱표에서 발생하는 충돌을 제거하는 방법이 있다.

 

 

의미 분석 : 의미 분석에서는 구문 분석으로 얻은 파스 트리가 입력되고 출력으로는 의미 분석이 이뤄진 파스 트리가 생성된다 또한 의미 분석 단계에서는 구문 지시적 번역을 이용하면 직접 중간 코드를 얻을 수도 있다.

 

기호표

어휘 분석 시 식별자에 대해 기호표를 만들며 이 식별자에 대한 정보는 식별자를 나타내는 문자열 자료의 형을 나타내는 속성 단순 변수나 구조 등을 나타내는 식별자의 형태 메모리에서 식별자의 위치 등이다.

 

기호표를 구성하는 데는 선형 리스트 트리 해시표를 이용하는 방법이 있다.

선형 리스트 방법은 n개의 항목과 m개의 조회가 있을때 구현이 간단하지만 자료의 수가 커지면 이를 모두 조사하여 접근하는 방법을 택하기 때문에 비효율적이다. 이진 탐색 트리 방법은 구현하기가 어렵지만 (n+m)log n의 횟수가 소요되므로 n이 큰 경우에 효율적이며 해싱 방법은 가장 효율적인 방법이다.

 

해시 함수로는 제산법 제곱값 중간법 폴딩법 등이 사용된다.

---

 

속성문법은 속성과 의미 규칙을 사용하여 문맥자유 문법을 확장한 것으로 각각의 논터미널 기호 또는 터미널 기호의 속성을 결합하여 의미 분석에 이용한다.

 

묵시적 형 변환은 강제 형 변환이라고도 하며 많은 언어의 확장 변환에서만 허용한다.

형 변환을 하기 위해 프로그래머가 무언가를 명백하게 서술해야 한다면 이 변환은 명시적이다.

 

중간 코드 생성 : 구문 분석 단계에서 만들어진 구문 트리를 이용하여 생성되거나 한 문법 규칙이 감축될 때마다 구문 지시적 번역으로 생성이 이뤄진다.

 

중간 코드의 장점

소스 프로그램과 목적 기계의 특성에 독립적인 이식성 높은 컴파일러를 개발할 수 있다.

기계 독립적인 최적화를 수행하여 목적 기계 코드로 바뀐 상태에서 행하는 것보다 훨씬 효율적인 최적화 효과를 얻을 수 있다.

 

 

구문 지시적 번역이란 각 생성 규칙에 해당하는 의미 수행 코드를 직접 기술하여 필요한 일을 처리하는 방법이다 따라서 문맥자유 문법의 각 생성 규칙인 컴파일러에 속하는 변수 값 계산 중간 코드 생성 에러 메시지 출력 기호표에 정보 삽입 등과 관련된 부 프로그램이나 의미 수행 코드로 구성되어 있다.

즉 구문 지시적 번역은 생성 규칙과 그에 해당하는 의미 규칙을 결합한 것이다.

---

 

구조적 자료형

- 구조적 자료형과 기본 자료형 : 기본 자료형은 하나의 이름이 하나의 자료 객체를 가진 것으로 정수 실수 문자형을 말하고 구조적 자료형은 하나의 이름에 여러 개의 자료 객체가 있는 것으로 레코드 배열 문자열 집합 트리 등을 말한다.

 

- 레코드 : 이질의 자료 개체들을 하나로 묶고 여기에 그룹 이름을 부여하여 하나의 자료형을 선언할 수 있는데 이러한 형태의 구조적 자료형을 레코드 또는 구조체라고 한다.

 

- 배열 : 동질의 자료 객체들을 묶고 여기에 그룹 이름을 부여하는 것을 말한다.

 

 

메모리의 구성

- 프로시저의 활성 : 프로시저가 실행되는 것을 말한다.

- 존속 시간 : 프로시저 몸체가 실행되는 기간을 말한다.

- 활성 트리 : 제어가 활성에 들어가고 다시 나오는 과정을 트리로 표현한 것이다.

- 활성 레코드 : 프로시저가 한 번 실행되는 데 필요한 정보는 메모리의 연속 블록을 사용하여 관리되는 데 이러한 연속 블록을 말한다.

 

메모리 할당 전략

- 정적 메모리 할당 : 프로그램이 실행될 때 이미 해당 메모리의 크기가 결정되는 방법으로 포트란 77언어에서 사용된다

- 스택 메모리 할당 : 메모리를 스택으로 관리하는 방법으로 C  C++ 파스칼 에이다와 같은 언어에서 사용된다

- 힙 메모리 할당 : 필요할 때마다 동적으로 메모리를 할당하고 해체하는 방법으로 함수 언어에서 사용된다.

 

매개변수 전달 방법

- 값 호출 : 실매개변수와는 별도로 형식 매개변수에 대한 메모리를 할당하는 방법이다. 결국 형식 매개변수는 지역 변수처럼 다뤄지고 호출자는 형식 매개변수에 대한 메모리에 실매개변수의 값을 복사하는 방법으로 구현한다.

 

- 참조 호출 : 매개변수가 참조에 의해 전달될 때 호출자가 피호출자에게 실매개변수의 메모리에 대한 주소를 가리키는 포인터를 전달한다.

 

- 이름 호출 : 형식 매개변수의 이름이 사용될 때마다 그에 대응하는 실매개변수 자체가 사용된 것처럼 매번 다시 계산 및 시행되는 방법이다.

 

 

---

 

코드 최적화 : 주어진 입력 프로그램과 동등한 의미를 가지면서 좀 더 효율적인 코드를 만드는 것이다 따라서 되도록 계산 횟수를 줄이고 보다 빠른 명령을 사용하여 실행 시간이 짧은 코드를 생성하거나 메모리의 요구량을 최소화한다.

 

최적화 기법

- 핍홀 최적화 : 몇 개의 연속적인 명령어를 하나의 명령이나 더 짧은 명령어로 변환

- 지역 최적화 : 부분적인 관점에서 일련의 비효율적인 코드를 구분해내고 좀 더 효율적인 코드를 만드는 방법

- 루프 최적화 : 한 루프 안에서의 최적화 기법으로

- 전역 최적화 : 기본 블록을 넘어서지만 하나의 프로시저 내에서 일련의 비효율적인 코드를 구분해내고 좀 더 효율적인 코드를 만드는 방법

- 프로시저 간 최적화 : 한 프로시저의 한계를 넘어서 전체 프로그램에 적용되는 최적화를 의미한다.

- 기계 종속적 최적화 : 기계의 특성에 따라 아주 달라질 수 있다.

 

 

 

목적 코드 생성의 개념

- 목적 코드 생성은 컴파일러의 마지막 단계로 중간 코드와 기호표의 정보를 받아서 중간 코드 형태의 프로그램을 목적 기계에 맞는 기계어로 생성하거나 어셈블리어로 생성하는 것이다.

 

명령어 선택은 목적 기계에 따라 적절한 명령어를 선택하는 것이다.

명령어 스케줄링은 선택된 명령어들의 실행 순서를 결정하는 것이다

레지스터 할당은 프로그램의 각 명령어가 사용해야 할 레지스터를 결정하는 것이다.