프로그래밍언어론 강의 6화 :: 언어 구현, 인터프리터, 컴파일러

프로그래밍언어론 6화를 듣고 배운내용

 

 

프로그래밍 언어 정의

구문 규칙

문맥 자유 문법과 EBNF로 주로 사용

 

의미 규칙

자연어 주로 사용

 

 

프로그래밍 언어 정의 예시: 로봇 제어 언어

구문 규칙

EBNF 사용: <program> ::= { forward | left | right }

 

의미규칙

forward: 로봇이 앞으로 1만큼 이동

left: 로봇이 왼편으로 90도 회전

right: 로봇이 오른편으로 90도 회전

 

 

프로그래밍 언어 구현

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

 

CPU의 함수 모형

M[Pm](in) = out

M: CPU 기계어

Pm: 기계어로 작성된 프로그램

in: 입력 데이터

out: 출력 데이터

 

 

프로그래밍 언어 구현 형태

인터프리터 함수 모형

lntL[PL](in) = out

IntL: 연어 L의 명령어를 해석하는 인터프리터

 

컴파일러 함수 모형

CompL[PL] = Pm

CompL: 언어 L의 컴파일러

그 다음 CPU 함수로 보내서 값을 얻어낸다.

 

 

전통적인 프로그래밍 언어 구현

기계어를 확장하는 형태로 구현

 

명령형:
저급언어의 연산과 명령어를 확장하는 형태로 구현

 

절차형:
명령형 + 함수, 사용자 정의 명령어(프로시저) 지원 형태로 구현

 

객체지향:
절차형 + 사용자 정의 자료형

 

 

 

새로운 패러다임의 언어

저급언어와 연관성을 직접 파악하기 어렵다

계산 모델과 하드웨어 사이에 중간 기계(추상 기계)를 징검다리 삼아 구현

프로그램을 추상기계가 이해하는 형태로 변경

 

함수형:

람다 계산법

 

논리:

연역 논리

 

추상기계

함수: CPS, G-machine

논리: WAM

 

가상기계

구체적인 구현물로 제시, 코드를 독자적으로 수행

JVM

WORA

 

 

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

구문 트리: 구현 단계의 중심

 

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

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

 

환경(인터프리터 구현)

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

 

 

실행 환경

메모리 구조 - 실행 지원

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

동적 세그먼트: 스택, 힙

 

레지스터 - 실행 상태 관리

전용 레지스터: PC, SP, FP

여러 범용 레지스터

 

 

실제 언어 구현

1. 어휘 분석기 구현

프로그램 어휘 구별하고 속성을 구해서 구문 분석기에 전달

 

2. 구분 분석기 구현

토큰 열로부터 구문 트리 생성

구문 트리 형태: 파스 트리, 추상 구문 트리(파스트리를 단순화)

예) 순환 하강 구문 분석기

 

 

프로그래밍 언어 Koch를 만들어 보자

코크(Koch) 곡선을 그리는 로봇 제어 언어를 만들어보자

코크 곡선

스웨덴 수학자 코크가 제안한 프렉탈 곡선

눈송이와 유사 형태

 

 

로봇 제어 언어 - 세 가지 명령어

forward: 로봇이 앞으로 1만큼 이동

left: 로봇이 왼편으로 60도 회전

right: 로봇이 오른편으로 120도 회전

 

구문 규칙

<program> ::= { F | L | R }

 

코드

FRFRFR

 

 

Koch 인터프리터

Koch 프로그램을 입력 받아서 실행

코크 곡선 생성

 

두 부분으로 나뉜다

1. 드라이버 코드: 환경 설정, 인터프리터 엔진 호출

2. 인터프리터 엔진: 원시 프로그램의 구문을 분석 및 수행

 

파이썬으로 만든다면

Koch 인터프리터: kint.py

Koch 프로그램: example.kch

 

 

Koch 컴파일러

Koch 프로그램을 입력으로 받아서 코크 곡선을 그릴 수 있는 파이썬 프로그램(a.py)을 생성하는 프로그램

1. 드라이버 코드: 설정 코드 생성, 컴파일러 엔진 호출

2. 컴파일러 엔진: 구문 분석, 코드 구현

 

Koch 컴파일러: kc.py

Koch 프로그램: example.kch