프로그래밍 언어 정의
어떤 프로그램이 올바른 형태인지, 올바른 프로그램을 실행했을 때 어떻게 실행되는 것이 올바른 것인지 규정하는 것을 "프로그래밍 언어 정의"라고 한다. 프로그래밍 언어의 형태에 관한 규정인 "구문(Syntax) 규칙"과 실행 결과에 관한 규정인 "의미(Semantics) 규칙"을 합쳐 프로그래밍 언어의 정의가 된다.
프로그래밍 언어 구현
프로그래밍 언어로 작성된 프로그램을 수행하는 프로그램을 "프로그래밍 언어 구현"이라고 한다. "함수 모형(Functional Model)"을 통해 프로그래밍 언어의 구현을 쉽게 이해할 수 있다.
어떤 프로그래밍 언어 $L$의 구현은 $L$로 작성된 어떤 프로그램 $P_L$이 주어졌을 때, 입력 데이터 $in$을 받아 출력 데이터 $out$을 내야한다.
이를 수식으로 나타내면 다음과 같다.($P_L$을 받는 수행함수 $L[..]$이 프로그래밍 언어 $L$의 구현이다.)
$$ L[P_L](in) = out $$
프로그래밍 언어 구현 모델은 다음 세 가지가 있다.
- 인터프리터: 프로그램을 받아서 해석하며 실행한다. 컴퓨터 하드웨어 CPU의 수학적 모형과 거의 일치한다.
- 컴파일러: 고수준 언어로 작성된 프로그램을 CPU가 수행 가능한 저수준 프로그램으로 번역하여 실행한다.
- 하이브리드 구현: 인터프리터와 컴파일러가 결합된 형태이다.
프로그래밍 언어의 구현은 크게 두 갈래로 나누어진다.
- 전통적인 프로그래밍 언어 구현: 명령형 언어, 절차형 언어, 객체지향 언어의 형태로 발전되어 온 주류 프로그래밍 언어로, 앞에 제시된 패러다임을 확대하는 형태로 제시된다.
- 새로운 패러다임의 언어 구현: 함수형 언어, 논리 언어와 같은 언어들은 기존의 패러다임과 다른 개념을 제시하기에 색다른 방식으로 구현된다. (다만, 주류 프로그래밍 언어의 구현 방법과 완전히 다른 것이 아니라 주류 프로그래밍 언어 구현에 한 단계 수준을 더 추가하는 형태로 구현된다.)
전통적인 프로그래밍 언어 구현
전통적인 프로그래밍 언어의 구현은 단순한 기계어를 확장하는 형태로 구현된다. 기계어나 어셈블리어에서 가정하는 순차적 제어 흐름을 유지한 채, 명령어 집합을 더 추가하는 형태로 구현한다.
- 명령형 언어: 저급 언어(기계어, 어셈블리어)의 연산과 명령어를 확장하는 형태로 구현한다.
- 절차형 언어: 함수, 프로시저 개념을 추가하여 사용자 정의 연산, 사용자 정의 명령어를 지원하는 형태로 구현한다.
- 객체지향 언어: 자료형에 함수 및 프로시저를 연관시켜 사용자 정의 자료형을 지원하는 형태로 구현한다.
다양한 패러다임의 언어 구현
다양한 패러다임의 언어는 단순히 확정으로 구현하기 어렵기에, 대부분 언어가 가정하는 복잡한 계산 모델과 현재 하드웨어 사이에 하나의 정형화된 추상기계를 더 놓는 형태로 구현한다. 이 추상기계가 알아들을 수 있는 형태로 해당 언어의 프로그램을 변경하는 방식으로 구현하는 것이다. 따라서 새로운 패러다임의 언어 구현을 이해하기 위해서는 추상 기계를 잘 이해하는 것이 중요하다.
컴파일러 구현 단계
컴파일러 구현 단계는 크게 "분석 단계(Analysis Phases)"와 "생성 단계(Synthesis Phases)"로 나뉘어진다.
- 분석 단계(Analysis Phases): 컴파일러 구현 단계에서 "전단부"에 해당하며, 주어진 프로그램을 구성 요소로 나누어 구조를 파악한다. 구현할 프로그래밍 언어에 종속적인 단계이다. 구문 분석 단계를 거치면 프로그램은 트리 형태로 바뀌고 이를 "구문 트리(Syntax Tree)"라고 한다.
- 생성 단계(Synthesis Phases): 컴파일러 구현 단계에서 "후단부"에 해당하며, 해당 트리가 올바른 형태인지 파악한다. 트리가 올바르면 이후에 처리할 수 있는 정형화된 형태의 트리로 구문 트리를 변경하며 올바르지 않으면 오류를 발생시킨다. 분석 단계를 거치면 컴파일러가 다룰 수 있는 정형화된 형태의 트리가 생성되고 컴파일러는 이를 변형하여 최종 목적의 코드 형태로 변환한다. 목적 기계에 종석적인 단계이다.
생성 단계에서 코드를 변형하는 것은 "목적 기계에 적합한 형태의 명령어로 변환"하고, "생성될 목적 코드의 수행 성능을 향상"시키기 위함이다. 결국 이들이 컴파일러의 가장 기본적인 기능(첫 번째 기능)이며 컴파일러의 차이를 구분하는 척도(두 번째 기능)이다.
인터프리터 구현 단계
인터프리터 구현 단계는 컴파일러 구현 단계의 "분석 단계"를 그대로 표현한다. 다만 의미 분석 단계 후에 나타나는 형태인 "중간 표현"으로부터 코드를 생성하는 대신, 중간 표현을 순회하며 프로그램 의미대로 수행한다. 이때, 중간 표현을 받아 해석하는 부분을 인터프리터 엔진이라고 한다.
인터프리터 엔진은 입력된 원시 프로그램에 대해 독자적인 입력을 받아 수행하고 결과를 출력으로 내기에, "해석 단위(Interpreting Unit)"를 규정하는 것이 필요하다. 인터프리터의 해석 단위는 일반적으로 프로그래밍 언어의 문장 단위가 된다.
언어 구현에 필요한 자료구조
컴파일러나 인터프리터 구현 단계 과정을 도와주는 자료구조가 있다. 이에 대해 알아보도록 하겠다.
- 구문 트리(Syntax Tree): 언어 구현 단계의 중심을 차지하는 자료구조로, 컴파일러의 분석 단계는 원시코드로부터 구문 트리를 생성하고 생성 단계는 구문 트리로부터 목적 코드를 생성한다.
컴파일러 분석 단계에서 분석에 필요한 다른 정보들은 다른 전역 자료구조에 저장된다.
- 심볼 테이블(Symbol Table): 프로그램에서 정의하거나 선언한 식별자 정보를 저장하고 있는 표를 말한다. 컴파일러 구현에 사용되며, 식별자의 자료형 정보, 선언 위치 등을 포함한다.
- 환경(Environment): 인터프리터 구현에서 사용되며, 식별자의 값 정보를 알아야 하기에 확장된 형태의 테이블이다.
인터프리터가 환경을 필요하듯, 컴파일러도 실행 시 환경을 필요로 한다. 이를 실행환경(Run-Time Environment)이라 하며, 통상 실행을 지원하기 위한 메모리 구조, 이들 메모리 및 실행 상태를 관리하기 위한 레지스터를 포함한다. 메모리는 레지스터와 함께 실행 환경의 주요 구성 요소가 되고, 일반적으로 "코드(Code", "정적 데이터(Static Data)", "스택(Stack)", "힙(Heap)" 등 4가지 구획(Segment)으로 구성된다.
- 정적 세그먼트(Static Segment): 코드와 정적 데이터로 구성되며, 정적 데이터는 주소가 미리 결정된 변수 공간으로 이루어진다.
- 동적 세그먼트(Dynamic Segment): 스택과 힙으로 구성되며, 스택은 서브프로그램의 활성 레코드 관리에 힙은 수동 할당 변수 공간으로 사용된다.
- 레지스터(Register): 코드 세그먼트를 가리키는 프로그램 카운터(PC, 실행 환경에서 가장 중요한 요소로, 현재 실행해야 할 명령어를 가리킨다.) 스택을 가리키는 스택 포인터(SP), 프레임 포인터(FP)를 비롯한 전용 레지스터와 더불어 범용 레지스터로 구성된다.
이때, 실행 환경은 언어 구현에 필수적이나 언어 구현 시 사용되는 자료구조는 아니다. 그러나 "실행할 때" 필수적으로 사용하는 자료구조이다.
언어 구현 실제
프로그래밍 언어를 구현하는 것은 매우 복잡하고 어렵기에 실제 언어 구현이 어떤 방식으로 이루어지는 이론적으로 살펴보도록 하겠다.
어휘 분석기 구현
어휘 분석기는 프로그램의 어휘(예약어, 리터럴, 연산자 등)를 구별해 내고 필요에 따라 속성을 구하여 구문 분석기에 전달하는 기능을 한다. 어휘 분석기를 구현하기 위해서는 당연히 단어를 먼저 구별해야 한다. 어휘 구조가 복잡한 경우 어휘 분석기를 구현하려면 한 문자씩 읽으며 상태를 파악해야 한다.
따라서 대부분의 경우 "유한 상태 기계(FSM: Finite State Machine)"을 구성하여 구현하고, 어휘 분석기에 사용되는 유한 상태 기계를 "유한 오토마타(Finite Automata)"라고 한다.
구문 분석기 구현
구문 분석기는 어휘 분석기의 분석 결과인 토큰 열로부터 트리를 구성하는 일을 한다. 이때, 구문 분석기의 실행 결과로 생성된 트리를 "구문 트리"라고 한다. 구문 트리는 "파스 트리"와 "추상 구문 트리" 두 가지 형태 중 하나로 결정된다. 추상 구문 트리의 크기가 훨씬 작기에 실제로 트리를 구성할 때 추상 구문 트리를 주로 사용한다.
- 파스 트리(Parse Tree): 문법에 대한 정보를 모두 포함하는 트리
- 추상 구문 트리(AST: Abstract Syntax Tree): 번역에 필요한 정보만 간추려 포함하는 트리
때로는 구문 트리 자체를 생성하는 프로그램보다, 구문 트리를 순회하는 여러 프로시저로 구성된 프로그램을 구문 분석기라고도 한다.
