Chapter5 컴파일러 개요
5.1 서론
번역 기법 : 고급 프로그래밍 언어로 작성된 프로그램을 기계 코드로 번역하는 컴파일러라 불리는 번역 프로그램을 사용한다.
인터프리터 기법 : 번역을 수행하지 않는 대신, 프로그램이 소프트웨어 인터프리터로 의해서 소스 형태에서 해석되어 실행된다.
하이브리드 구현 시스템 : 고급 수준 언어로 작성된 프로그램을 중간 형태로 번역하여, 이 번역한 중간 형태를 인터프리터로 실행
구문분석기(파서) -> 프로그램 구문의 형식적 기술에 기초. 가장 일반적 구문 기술의 형식적 방법 -> BNF
BNF의 사용이 비형식적으로 구문 서술을 사용하는 경우보다 3가지 이상의 중요한 장점을 가짐
- ①명확하고 간결
- ②구문 분석기에 대한 기초로서 사용 가능
- ③BNF에 기반한 구현은 그 명확한 모듈 기반 작성으로 인하여 유지보수가 상대적으로 쉽다
컴파일러가 구문을 분석하는 작업 -> 어휘분석 / 구문분석
어휘 분석기 : 이름이나 수치 리터럴 같은 작은 규모의 언어 구조를 다룸 구문 분석기 : 식, 문장, 프로그램 단위와 같은 큰 규모의 언어 구조를 다룸
어휘 분석을 구문 분석으로 분리하여 처리하면 얻을 수 있는 이득 ① 단순성 제공 ② 효율성을 제공
어휘 분석기는 입력 프로그램 파일을 읽어 들이는데, 흔히 이러한 입력을 버퍼에 저장하는 과정이 포함되기 때문에 다소 플랫폼에 종속적 그러나 구문 분석기는 플랫폼에 독립적. 어떠한 소프트웨어 시스템이든지 기계에 종속적인 부분을 따로 떼어내어 분리하는 것은 이식성을 제공하며 항상 좋은 방법
5.2 컴파일러 일반적 구성
컴파일러 -> 고급 언어로 쓰여진 프로그램을 어떤 특정한 컴퓨터에서 직접 실행 가능한 형태의 프로그램으로 번역해 주는 컴퓨터 프로그램.
컴파일러의 구조 -> 크게 전단부(front-end) / 후단부(back-end)
- 전단부 : 소스 언어에 관계되는 부분으로 소스 프로그램을 분석하고 중간 코드를 생성하는 부분
- 후단부 : 소스 언어보다는 목적 기계(target machine)에 의존적이며 전단부에서 생성한 중간 코드를 특정 기계를 위한 목적 코드로 번역하는 부분
전단부 : 각 언어마다 하나씩 필요 / 문법 이론에 의해 잘 정립 후단부 : 목적 기계당 하나씩 필요 / 경험적인 방법을 통하여 연구 진행 중
전단부가 소스 프로그램을 읽어 들이는 어휘 분석 단계로부터 중간 코드를 생상하는 중간 코드 생성 단계까지이기에, 전단부의 출력은 중간 코드가 된다. 후단부는 중간 코드에 대한 목적 프로그램이 생성된다.
컴파일러의 일반적 구조
소스 프로그램 —> 전단부(어휘 분석 -> 구문 분석 -> 중간 코드 생성) –중간 코드–>** 후단부(코드 최적화 -> 목적 코드 생성)** —> 목적 프로그램
해당하는 어휘분석, 구문분석, 중간코드생성,코드최적화,목적코드생성 모두 테이블 관리와 데이터 교환이 일어남.
어휘 분석 : 어휘 분석기에 의해 이루어지며, 이는 소스 프로그램을 읽어 들여 일련의 토큰(token)을 생성하는 일을 함.
토큰이란 문법적으로 의미를 갖는 최소의 단위로 프로그램은 토큰의 열로서 구성되어 있다고 생각할 수 있다. 토큰의 종류 -> 특수 형태와 일반 형태로 분류.
특수 형태 : 언어를 정의할 때 언어 설계자가 결정하는 지정어, 연산자 기호, 구분자 등이며 일반 형태 : 프로그래머가 프로그래밍할 때 사용한 명칭과 상수들
ex) a = b + 10
어휘 분석 단계에서 a, =, b, +, 10, 그리고 ;의 여섯 개의 토큰으로 위 문장을 분리.
여기서 =,+,;은 특수 형태의 토큰이며 a, b, 10은 일반 형태의 토큰에 해당된다.
각 토큰들은 효율적인 처리를 위해서 고유의 내부번호를 정수 형태로 갖는데, 이것을 토큰번호(token number)라 부른다.
주석과 공백은 이 과정에서 모두 제거
구문분석기 : 파서라고도 하는데, 어휘 분석 단계의 출력인 토큰들을 받아 소스 프로그램에 대한 에러를 체크하고(error checking) 올바른 문장에 대한 구문 구조 (syntactic structure)를 만든다. 즉 소스 프로그램에 대한 에러가 있으면 그에 해당하는 에러 메시지를 출력하고, 그렇지 않으면 프로그램에 대한 구문 구조를 트리 형태로 만들어 출력한다. 프로그램의 구문 구조를 트리 형태로 표현하는 방법에는 파스 트리(parse tree)와 추상 구문트리(abstract syntax tree)가 있으나 요즘 대부분의 컴파일렁서는 추상 구문트리를 사용한다.
중간 코드 생성과정 에서는 파서의 출력인 추상 구문 트리를 입력으로 받아 의미 검사(semantic checking)를 행하고 그에 해당하는 중간 코드를 생성한다.
컴파일러에 따라 독립된 의미 분석 단계를 가질 수 있다. 왜냐하면 컴파일러는 언어의 특성과 목적 기계, 그리고 컴파일러를 구현하는 사람에 따라 다른 구조를 가질 수 있기 때문이다. 그리고 컴파일러를 구현하는 사람에 따라 다른 구조를 가질 수 있기 때문이다.
의미 분석 단계에서 가장 중요한 것은 중 하나 -> 형검사(type checking)이다. 형검사란 각 연산자(operator)가 사용 언어의 정의에 맞는 피연산자(operand)를 가지는 가를 검사하는 것이다. ex) 실수가 배열의 첨자로 사용된 것 에러, 어떤 언어는 실수와 정수의 혼합 연산 허용. 그 때 정수를 실수로 바꿔주는 작업 필요) 이와 같은 기능을 형 변환(type conversion)이라 부르며 모두 의미 분석 단계에서 처리한다.
중간 코드의 생성은 구문 분석 단계에서 만들어진 구문 구조를 이용하여 코드를 생성 -> 구문 트리를 운행하면서 각 구문에 해당하는 중간 코드를 생성.
ex) lod 1 2 //load b
ldc 10 // load constant 10
add // addition
str 1 1 // store a
즉 b의 값과 상수 10을 스택에 적재한 다음 덧셈을 해서 a에 저장을 한다. 참고로 여기서 사용한 중간 언어는 U-코드다.
중간 코드 생성 단계에서 생성된 중간 코드들은 다음 과정인 코드 최적화(code optimization)의 단계의 입력으로 사용될 수 있다. 최적화 과정은 선택적인 단계(optional phase)로 생략되는 경우도 있다. 그 기능은 같은 의미를 유지하면서 코드를 보다 더 효율적으로 만들어 코드 실행시 기억 공간이나 실행 시간을 절약하는데 있다.
최적화는 최적화되는 관점에 따라 지역 최적화(local optimization 또는 people optimization)와 전역 최적화(global optimization)로 구분할 수 있다. 지역 최적화는 기본 블록 내에서 행해지며 부분적인 관점에서 일련의 비효율적인 코드들을 구분해 내고 좀더 효율적인 코드로 개선하는 방법이다.
지역 최적화 방법으로 얻을 수 있는 효과 (1) 컴파일 시간 상수 연산(constant folding) (2) 중복된 load,store 명령문 제거 (3) 식(expression)의 대수학적 간소화(algebraic simplification) (4) 연산 강도 경감(strengh reduction) (5) 불필요한 일련의 코드 블록(null sequence) 삭제
전역 최적화 -> 흐름 분석 기술을 이용하여 기본 블록들 사이에 최적화를 행하는 것. 여기에서 행할 수 있는 것 -> 곹오 부분식의 축약, 루프 내에서 갑이 변하지 않는 코드를 루프 밖으로 이동, 그리고 도달될 수 없는 코드 제거 등이 있다.
또한, 최적화는 그 위치에 따라 precode optimization과 postcode optimization으로 나눌 수 있다. Precode optimization은 중간 코드를 이용하여 최적화를 수행하며 그 위치는 목적 코드 생성 전에 행해진다. postcode optimization은 목적 코드 생성 후에 코드를 최적화 하는 방법으로 기계 의존적인 최적화 방법
목적 코드 생성기는 중간 코드를 입력으로 받아 그와 의미적으로 동등한 목적 기계에 대한 코드를 생성하는 일을 한다.
목적 코드 생성기가 목적 코드를 생성하기 위하여 행하는 일 -> 크게 4가지
① 목적 코드 선택 및 생성
② 레지스터의 운영
③ 기억 장소 할당
④ 기계 의존적인 코드 최적화
목적 코드 생성기 : 각 변수들에 대한 기억 장소를 할당해야 하며 중간 코드의 의미와 일치하는 기계 명령어들을 효과적으로 선택하는 코드 생성 알고리즘을 사용
우수한 목적 코드 생성기 -> 레지스터들을 효율적으로 사용할 수 있어야. 레지스터의 사용 -> 임시 변수의 사용을 줄일 수 있을 뿐만 아니라 전체적인 실행 속도 향상.
기계 의존적인 최적화 -> 연속적인 명령어들을 의미적으로 동등한 하나의 명령어 또는 처리 속도가 빠른 명령어로 대체하여 기계어 코드의 성능을 향상시키는 방법
컴파일러는 소스 프로그램에 나타난 모든 자료들에 대한 정보들을 가지고 있어야 한다. 예를 들어, 어떤 변수가 정수를 나타내는지 실수를 나타내는지, 배열의 크기가 얼마나 되는지, 함수의 인수가 몇 개 필요한지 알아야 한다. 이런 자료에 대한 정보는 컴파일러의 전단부인 어휘 분석 단계와 구문 분석 단계에서 수집되어 심벌테이블(symbol table) 이라는 곳에 저장된다. 테이블 관리는 이러한 정보들을 관리하는 부분이며 여기에서 사용되는 자료 구조를 심벌 테이블이라 한다.
컴파일러에서 중요한 기능 한가지는 소스 프로그램의 에러를 발견하여 사용자에게 알려주는 것 ex) 어휘 분석 단계에서 소스 프로그램의 토큰이 철자가 틀리는 경우가 발생할 수도 있고, 구문 분석 단계에서 괄호가 빠지는 것과 같은 문법 규칙에 대한 에러가 발생할 수도, 이와 같은 에러에 대한 처리 기술은 컴파일러를 실제로 구현하는데 있어 매우 중요. 컴파일러는 이런 에러들을 처리하여 주는 루틴을 가지고 있다.
컴파일러 구현 시 하나 이상의 단계들을 모아 패스라고 하는 하나의 모듈로 묶을 수 있다. 한 패스는 소스 프로그램이나 그 전 패스의 출력을 읽어 들여 그 패스를 이루고 있는 단계들의 기능에 따라 입력을 변환해서 중간 파일에 출력한다. 그러면 이 출력은 다음 패스의 입력이 된다. 만약 여러 단계가 모여 하나의 패스를 이룬다면, 서로간의 제어에 따라 각 단계들은 상호간의 수행을 할 수 있다. 어휘 분석 단계와 구문 분석 단계를 대표적인 예로 들 수 있는데, 어휘 분석기에서 무조건 토큰들을 생산하는 것이 아니라 구문 분석 단계에서 토큰이 필요할 때마다 어휘 분석 단계에게 토큰을 요구하게 하여 마치 부프로그램과 같은 역할을 할 수 있게 한다.
※ **부프로그램(subprogram) **: 프로그램의 한 부분으로서 특정한 일을 여러 번 실행할 필요가 있을 때 이를 실행하기 위해 논리적으로 별개의 프로그램으로 작성된 프로그램. 특정한 일을 부차적 프로그램이 담당하게 함으로써 프로그램 작성에 드는 노력을 절약하고 프로그램이 차지해야 할 기억장소를 절약할 수 있다. 그리고 독립적으로 번역할 수 있는 주 프로그램의 나머지 부분에 상관없이 기계어로 변환될 수 있다.
초창기 컴파일러는 전단부, 후단부 구분 없이 전과정을 하나의 패스로 구성한 단일 패스 컴파일러였다. (single pass compiler) 컴파일러에서 패스의 개수는 사용하는 목적 기계나 프로그래밍 언어에 따라 결정된다. 여러 개의 패스로 구성된 컴파일러를 다중 패스 컴파일러라 부른다.
다중 패스 컴파일러는 기능에 따라 여러 패스로 구성되어 있기 때문에 컴파일러의 부분적인 기능을 개선하고 다른 기종으로 이전하기에도 편리하다. 또한 다른 패스 컴파일러는 단일 패스 컴파일러보다 작은 기억 공간을 요구한다. 왜냐하면 하나의 패스가 사용했던 공간을 다음 패스가 다시 사용할 수 있기 때문이다.
많은 장점을 갖고 있기에 대부분 다중 패스로 구성된 컴파일러이지만 단일 패스 컴파일러보다 컴파일 속도가 느리다는 것이 단점이다.
참고자료
프로그래밍 언어 개념 - 원유헌 저