공부 배경 및 동기
어린이 날을 맞아, CS 공부 파트를 파고 따로 공부를 기록하려고 한다.
그동안 휘발된 기록이 너무 많고 성공한 기록은 대부분 블로그란걸 깨달았다.
컴파일러 설계를 배우기 위한 선수과목으로 언어론을 치고 있다.
근-본이 부족한 나에게 맞게, 최대한 기반 지식을 미리 언급하거나 잡아두고, 키워드나 용어도 도움이 될 것 같아 잘 남겨두려고 한다.
읽고 있는 책은 PEARSON 출판사 , Sebesta 지음 , Concepts of Programming Languages (프로그래밍 언어론 제 10 판)
IEEE 로는
R. W. Sebesta, Concepts of Programming Languages, 10th ed. Boston, MA, USA: Pearson, 2012.
배경지식 정리
컴퓨터의 2가지 요소는 내부 기억 장소와 프로세서로 나눌 수 있다.
(물론 4가지로 나누면 입력, 출력장치도 포함된다.)
내부 기억장소에는 프로그램과 데이터를 저장하게 된다.
프로세서에는 산술 + 논리 연산같은 기본 연산, 즉 기계 명령어들의 집합을 구현하는 회로들의 모임이다.
(여기서 기본연산은 매크로 명령어, 기계 명령어들은 마이크로 명령어라고 한다.)
기계어란, 컴퓨터가 ‘이해하는’ 유일한 언어로 명령어들의 집합이다.
이론적으로 특정 고급언어가 기계어인 컴퓨터가 개발이 가능하지만, 복잡성이 높고 유연성은 낮은데다 비용이 매우 높다.
따라서, 기본 연산을 제공하는 매우 낮은 수준의 언어로 구현 시스템 소프트웨어가 고급언어로 작성된 프로그램에 대한 인터페이스를 생성하도록 요구한다.
추가로, 언어 구현 시스템이 컴퓨터의 유일한 소프트웨어일 수 없다.
기계어보다 높은 수준의 기본연산들을 제공하는 프로그램들의 큰 규모의 모임인 운영체제가 필요한 이유다.
운영체제의 기능을 간단하게 뽑자면,
- 시스템 자원 관리
- 입출력 연산
- 파일관리 시스템
- 텍스트 편집기
- Etc..
언어 구현 시스템이 운영체제의 많은 기능들을 필요로 한다.
그러므로, 언어 구현 시스템은 기계어를 이용해 프로세서와 직접 인터페이스를 갖기보다는 운영체제와 인터페이스를 갖는다.
운영체제와 언어구현 시스템은 컴퓨터 기계어 인터페이스에 대한 상부 층을 형성한다.
이 층은 더 높은 수준에 위치한 사용자에 대한 인터페이스를 제공하는 가상 컴퓨터로 고려될 수 있다.
사용자 프로그램은 가상 컴퓨터의 층의 상단에 위치한 또 다른 상부층을 형성한다.
예를 들어, 자바의 가상머신이나 씨샵의 CLR 같은 친구들을 이야기하는 것이다.
물론 일반적인 언어의 구현 방식에 대한 이야기라, C 언어도 C 가상 컴퓨터와 C 컴퓨터로 구성한다고 하는데 이 부분 나중에 정확히 찾아보자.
내용의 구조
교과에서 소개된, 언어 구현 시스템의 방식에는 3개 정도가 있다.
- 컴파일러 구현
- 순수 인터프리터 구현
- 1+2 혼합형
컴파일러 구현
원시 프로그램을 컴퓨터에서 직접 실행될 수 있는 기계어로 번역한다.
여기서 원시 프로그램은 (Source Language) 로, 컴파일러가 번역하는 언어이다.
다음의 프로세스를 거쳐서 언어가 컴파일 된다.
원시 프로그램 → 어휘 분석기 → 구문 분석기 → 중간 코드 생성기 → 의미 분석기 → 최적화 → 기계 프로그램
어휘 분석기
원시 프로그램에 포함된 문자들을 어휘 단위로 모은다.
프로그램에 포함된 어휘 단위는 식별자, 특수어, 연산자, 구분자 기호가 있다.
어휘 분석기는 원시 프로그램에 포함된 주석은 무시한다.
(컴파일러는 주석을 사용하지 않는다!)
구문 분석기
어휘 분석기로부터 어휘 단위들을 가져오고, 이들을 이용하여 파스트리라 불리는 계층적 구조를 형성한다.
파스트리는 프로그램의 구문구조를 표현한다.
대부분의 경우에, 실제 파스트리가 구성되지는 않고 이를 구성하는 데 필요한 정보가 생성 및 직접 사용 된다.
중간 코드 생성기
원시 프로그램과 컴파일러의 최종 출력인 기계 프로그램 간의 중간 수준에 위치하는 다른 언어로 표현된 프로그램을 생성한다.
중간 언어는 어셈블리어 이거나 이에 준하는 유사한 것이다.
참고로 중간 코드는 직역하면 중간 표현인데 번역은 IR, Intermediate Representation 으로 한다.
코드가 아니고 표현인 이유는 텍스트 뿐 아니라 트리나 그래프 형태로도 쓰기 때문이라고 한다.
어셈블리어
어셈블리어는 기계어에 1:1로 대응되는 사람이 읽을 수 있는 형태의 저급언어다.
참고로 CPU 아키텍쳐에 종속적이다.
의미 분석기
중간 코드 생성기 이후에 타입 오류 등을 검사한다.
최적화
프로그램의 크기를 줄이거나 실행속도를 더 빠르게 해서 프로그램을 향상 시키는 것을 의미한다.
알고리즘이라면 시간 복잡도를 줄이고, 공간 복잡도도 줄이는 것이라고 할 수 있겠다.
많은 종류의 컴파일러 최적화는 기계어 상에서 수행하기 어려우므로, 대부분의 최적화는 중간 코드 상에서 이루어진다.
기계어 상에서 컴파일러 최적화가 수행하기 어려운 이유는 의미 정보가 손실된 상태이고, CPU 아키텍쳐 의존성도 있는데다 사이드 이펙트가 너무 많으며 레지스터 할당이 이미 정해져있기 때문이다.
순수 해석 (순수 인터프리터)
컴파일러와는 정반대의 구현 방법으로, 어떠한 번역과정 없이 인터프리터라 불리는 프로그램이 해석한다.
인터프리터 프로그램
기계어에 대한 소프트웨어 모의실험(시뮬레이션)으로 동작한다. 인출-실행 사이클이 기계명령어가 아닌 고급 언어 프로그램을 직접 다룬다.
언어에 대한 가상기계를 분명히 제공한다.
인터프리터 방식의 장점
많은 원시-수준 디버깅 연산을 쉽게 구현한다.
이유는 모든 실행-시간(런타임의 번역) 오류 메시지가 원시-수준 프로그램 단위를 참조 가능하기 때문이다.
예를 들어, 배열 첨자 범위를 벗어나면 (OOI, Out of Index) 그 원시 코드들과 그 배열의 이름을 쉽게 나타낼 수 있다.
인터프리터 방식의 단점
더 많은 기억공간이 필요하다. 심볼 테이블이 해석과정에 존재해야 한다.
느리다. 10배, 100배 느리다.
실행 횟수 관계 없이 매번 해석.
따라서, 문장 해석이 병목이다. 컴파일러 구조는 폰 노이만 병목이라 불리는 프로세스 - 기억장소간 연결이 병목이지만, 인터프리터는 문장 해석 자체가 병목이다.
혼합형 구현 시스템
컴파일러와 순수 인터프리터의 절충.
고급 언어 프로그램을 용이한 해석이 가능하도록 설계된 중간언어로 번역한다.
원시 언어 문장이 단지 한번만 해석되므로 순수해석보다 빠르다. (여기서 해석은 decode)
프로세스는
원시 프로그램 → 어휘 분석기 → 구문 분석기 → 중간 코드 생성기 → 인터프리터 → 결과
예시
Perl 은 혼합형 시스템으로 구현되어 있다. 해석 전에 오류를 탐지하고 인터프리터를 단순화 하기 위해 부분적으로 컴파일 한다.
Java의 초창기 구현에서, 바이트코드는 바이트코드 인터프리터와 연관된 실행-시간 시스템을 갖는 어떠한 기계에도 이식성을 제공한다.
JIT 구현 시스템은 먼저 프로그램을 중간언어로 번역한다. 프로그램 실행중에, 중간 언어 메소드 호출 시 메소드를 기계코드로 번역하여 보관하다가 재사용한다.
때때로, 모든 구현방식을 제공하기도 하는데, 이는 보통 개발과 디버깅에서는 인터프리터를 쓰고 디버깅이 완료되면 컴파일 하는 식으로 활용한다.
핵심 키워드 정리
#원시프로그램 #SourceProgram
#어휘단위 #Token
#어휘분석기 #Lexer #LexicalAnalyzer
#구문분석기 #Parser
#파스트리 #ParseTree
#중간표현 #IR #IntermediateRepresentation
#의미분석 #SemanticAnalysis
#최적화 #Optimization
#인출실행사이클 #FetchExecuteCycle
#폰노이만병목 #VonNeumannBottleneck
#즉시컴파일 #JIT #JustInTime