프로그래밍 언어의 구현

프로그래밍 언어 구문과 의미를 구체적으로 정의하는 방법을 살펴본다.

 

프로그래밍 언어 구현에 필요한 자료 구조와 기능을 이해한다.

 

간단한 프로그래밍 언어 정의에 따라 인터프리터를 작성하는 방법을 살펴본다.

 

간단한 프로그래밍 언어 정의에 따라 컴파일러를 작성하는 방법을 살펴본다.

---

프로그래밍 언어 정의

• 구문규칙 : 형태에 대한 규정 문법
• 의미규칙 : 실행결과에 대한규정

정의방법

• 구문 규칙 정의 : 문맥자유 문법, BNF, EBNF, 구문도표가 있으나 실제론 문맥자유문법과 EBNF를 주로 사용
• 의미 규칙 정의 : 기능적 의미론, 표기적 의미론, 공리적 의미론등이 있으나 실제로 의미를 정의할 때, 난해하므로 자연어를 주로 사용한다.

정의 예 : 로봇 제어 언어(방향지시)

구문규칙

<program> : :={ forward | Left | right }  *중괄호는 0번 이상반복이다 명령이 없어도 된다.

의미규칙
forward : 로봇이 향하고 있는 방향으로 1만큼 이동
Left : 로봇이 왼편으로 90도 회전
right : 로봇이 오른편으로 90도 회전

프로그래밍 언어 구현

그 언어로 작성된 프로그램을 수행하는 프로그램

(쉽게 언어의 구현이란 프로그램을 동작시키기 위해 사용되는 더 큰 프로그램을 의미한다.)

 

프로그래밍 언어 L의 구현

▶다음을 수행하는 프로그램

1. P_L이 L의 구문규칙을 따르는 올바른 프로그램인지 검사( P_L:언어 L로 작성된 프로그램)
2. 올바른 경우, P_L을 입력받아서 L의 의미 규칙에 따라 실행

하는  프로그램을 L의 구현이라고 한다.

 

CPU의 함수 모형

• M : CPU가 받아들이는 기계어
• P_M : 기계어 M으로 작성된 프로그램
• in : 입력 데이터
• out : 출력 데이터

함수로 표현

• L : 프로그래밍 언어
• P_L : L로 작성된 프로그램
• in : 입력 데이터
• out : 출력데이터

※인터프리터의 함수모형

Int : 언어 L의 명령어를 해석하는 인터프리터

 

※컴파일러 함수모형

Comp : 언어 L의 컴파일러

P : CPU M이 이해하는 프로그램

컴파일러는 out이 없다 이는 통번역을 한 뒤에 앞서 배웠던 CPU에 함수모형과 같이 넘겨준다.

즉 첫 번째 아래의 것을 실행하고

이를 다시 

넘겨주어서 실행하는 것이 컴파일러이다.

---

프로그래밍 언어의 구현방법

전통적인 프로그래밍 언어구현(기계어를 확장하는 형태)

• 명령형 언어 : 저급언어의 연산과 명령어를 확장하는 형태로 구현
• 절차형 언어 : 명령형 언어 + 사용자 정의 연산(함수)과 사용자 정의 명령어(프로시저)를 지원하는 형태로 구현
• 객체지향 언어 : 절차형 언어 + 사용자 정의 자료형을 지원하는 형태로 구현

새로운 패러다임의 언어구현 (구현 모델을 추상기계로 만들어 징검다리 삼아 구현)

• 언어별 계산 모델

함수형 언어 : 람다 계산법

논리형 언어 : 연역논리

• 저급언어와의 연관성을 직접 파악하기 어렵다.
• 계산 모델과 하드웨어 사이에 중간기계인 추상기계를 하나 더 놓은 형태로 구현(프로그램을 추상기계가 알아듣는 형태로 변
• 추상기계 :

함수형 언어 : CPS. G-machine, Tim 등

논리 언어 : WAM 등

• 가상기계 : 추상기계가 구체적인 구현물로 제시되고 코드를 독자적으로 수행할 수 있는 경우

컴파일러 구현 단계

분석단계

▷프로그램의 구조 파악

▷중간 표현 생성

→프로그램이 언어에 종속적

생성 단계

▷ 목적 기계에 적합한 명령어 생성

▷ 효율적인 목적 코드 생성

→ 목적 기계에 종속적

인터프리터 구현단계

▷ 컴파일러 구현단계의 분석단계는 그대로 포함된다.

▷ 중간 표현을 순회하며 프로그램을 수행하고 프로그래밍 언어의 문장 단위로 해

 

언어 구현에 필요한 자료구조

구문트리

▷언어 구현 단계의 중심 차지

▷분석 단계의 전 과정을 관통

※컴파일러 분석단계는 결국 원시 코드로부터 구문 트리를 생성하며, 생성 단계는 구문트리로부터 목적 코드를 생성한다. 따라서 전 과정을 관통하는 단계라고 할 수 있다.

심벌 테이블(컴파일러 구현)

▷식별자 정보(타입, 선언 위치등)를 저장

 

환경(인터프리터 구현)

▷값 정보를 포함한 식별자 정보를 저장

 

실행환경

실행을 지원하기 위한 메모리구조

▷정적 세그먼트 : 코드, 정적 테이터

※정적 데이터는 주소가 미리 결정되어 있는 변수 공간으로 이루어짐

▷동적 세그먼트 : 스택, 힙

※스택은 서브프로그램의 활성레코드 관리에, 힙은 수동 할당 변수 공간으로 사용됨

메모리 및 실행 상태를 관리하기 위한 레지스터

▷PC, SP, FP 등 전용 레지서터

※코드세그먼트를 가리키는 PC, 스택을 가리키는 SP 및 FP

▷여러 범용 레지스터

---

언어 구현 실제

어휘 분석기 구현

▷프로그램의 어휘를 구별해 내고 속성을 구하여 구문 분석기에 전달 

어휘 : 예약어, 리터럴, 연산자등

※어휘를 구별한다는 거는 거는 결국 토큰별로 잘라낸다는 것을 말한다.

 

유한 상태 기계(FSM)를 구성하여 구현

※ 어휘 분석기는 어휘와 토큰과 속성을 분석하며, 구문 분석기는 토큰을 이용하여 구문 트리를 구성한다. 구문트리는 파스트리와 추상 구문트리 두 가지 형태가 있다.

 

구문 분석기 구현

▷ 구문 분석기는 토큰열로부터 구문트리를 생성

▷ 구문 트리의 형태 : 파스트리, 추상 구문 트리

 

▷ 구문 트리를 순회하는 여러 프로시저로 구성된 프로그램

순환하강 구문 분석기

▷ 문법 규칙 그대로 코드를 바꾼 형태

1. 각 비단말 기호를 문법 규칙에 대해 하나의 프로시저 생성
2. 우변을 모사할 때 단말 기호는 일치 검사, 비단말 기호는 해당 프로시저 호출

---

용어정리

 

프로그래밍언어 정의

프로그램이 올바른 형태인지, 올바른 형태의 프로그램을 실행하였을 ㄸ 어떻게 실행되는 것이 올바른 것인지 규정하는 것을 뜻한다.

 

함수모형

가상함수 테이블

객체지향언어에서 상속기능을 자연스럽게 지원하기 위해 객체 자체의 자료형에 따라 메서드를 호출할 수 있어야 하는데 이를 위해 객체 지향언어는 각 객체에 메서드에 대한 참조구조를 두고 있다 이를 일반적으로 가상함수테이블이라고 부른다.

 

추상기계 / 가상기계

다양한 패러다임 프로그래밍 언어구현, 함수형 언어 논리언어등을 구현할 때 징검다리를 놓는 것과 유사하게 복잡한 계산모델과 하드웨어 사이의 중간기계를 놓는 형태를 말한다. 즉 정형화된 추상기계를 가정하고 이 추상기계가 알아듣는 형태로 해당언어의 프로그램을 변경하는 방식으로 구현한다. 하드웨어기계사이의 간극은 컴파일러가 담당하기도 하고 인터프리터가 하기도 하며 추상기계 형태의 중간 기계가 구체적인 구현물로 제시되고 중간기계상에서 코드를 독자적으로 수행할 수 있는 경우에는 추상기계라는 용어대신 가상기계라는 용어를 사용한다.

 

전단부

분석단계를 마하고 프로그래밍언어에 종속적인 단계이다. 어휘분석, 구문분석, 의미분석 순으로 나뉘며 컴파일러와 인터프리터 모두 동일하다.

후단부

생선단계로 기계에 종속적인 단계이다.

컴파일러는 목적 기계에 적합한 형태의 명령어로 변환하는 것이 기능의 첫 번째이고 두 번째로 수행성능 향상을 두고 있다 2개의 최적화 단계를 제공한다. 인터프리터에서는 후단부는 중간표현부터 코드를 생성하는 대신 중간표현을 순회하며 프로그램 의미대로 수행한다.                                                                                                                                                                                                                                                                 

중간표현

의미분석 후 나타내는 형태를 말한다. 특별히 구분되는 가상기계가 있는 경우에는 가상기계 코드 바이트 코드라고 부름

대게 정형화된 트리형태인 경우는 중간표현이라고 하며 의미분석 후 파트 별로 나누어서 최적화를 한다.

 

중간코드

중간표현과 유사하고 어셈블리어와 유사한 선형코드인 경우에는 중간코드라고 부르기도 한다.

 

심벌테이블

프로그램에서 정의하거나 선언한 식별자 정보를 저장하고 있는 표를 말한다. 컴파일러 구현에 사용

 

환경

인터프리터 구현에 사용되고 심벌테이블보다 확장되어 식별자의 값 정보도 알 수 있는 테이블

실행환경

인터프리터가 환경을 필요로 하듯이 컴파일러도 실행 시 환경을 필요로 하고 이를 실행환경이라고 부른다. 구현할 때가 아니라 실행할 때 반드시 필요

메모리 : 정적세그먼트, 동적세그먼트

레지스터: 수행 중인 명령어 스택 힙등을 관리하기 위해 필요

 

유한 오토마타

어휘구조가 복잡하여 어휘 분석기를 구현하려면 한문자 한문자 읽어가며 상태를 파악해야 하는데 때문에 대부분 유한 상태기계를 구성하여 구현하는데 어휘 분석기에 사용되는 유한상태기계를 말한다.

 

추상구문 트리

구문트리의 형태인 파스트리(번여과 문법에 대한 정보 모두포함) , 추상구문트리 중 하나로 번역에 필요한 정보만 포함한다.

 

순환 하강 구문 분석기

문법 규칙을 그대로 코드로 바꾼 형태

각 비단말 기호의 문법 규칙에 대해 하나의 프로시저를 만들되, 우변을 모사하도록 프로시저를 만든다. 우변을 모사할 때 단말 기호라면 일치하는지 검사하고, 비단말기호라면 해당 프로시저를 호출한다.