[프로그래밍 언어론] 6강 - 프로그래밍 언어의 구현

📌 개요

🔑 학습 키워드

┗  프로그래밍 언어 구현 모형: 컴파일러, 인터프리터 구조적 차이를 수학적 모형으로 설명

┗  컴파일러, 인터프리터 구현 단계

┗  언어 구현에 필요한 자료 구조: 구문 트리, 심볼 테이블, 환경(인터프리터), 실행 환경

┗  실행 환경 -> 메모리 구조: 정적 세그먼트(코드, 정적 데이터), 동적 세그먼트(힙, 스택)

┗  실행 환경 -> 레지스터: 전용 레지스터(PC, SP, FP), 범용 레지스터

┗  어휘 분석기, 구문 분석기

 

💡 1. 프로그래밍 언어 정의와 구현

[ 프로그래밍 언어 정의 ]

┗  구문 규칙 + 의미 규칙:

- '구문 규칙': 어떤 프로그램이 올바른 형태인지 규정하는 것
- '의미 규칙': 올바른 형태의 프로그램을 실행하였을 때 어떻게 실행되는 것이 올바른 것인이 규정하는 것

 

┗  프로그래밍 언어 정의 방법: 구문 규칙 정의 방법, 의미 규칙 정의 방법

[구문 규칙 정의 방법]: 문맥 자유 문법, BNF, EBNF, 구문 도표 등
-> '문맥 자유 문법'과 'EBNF'를 주로 사용함.

[의미 규칙 정의 방법]: 기능적 의미론, 표기적 의미론, 공리적 의미론 등
-> '자연어'를 많이 사용함.

 

[ 프로그래밍 언어 구현 ]

┗  프로그래밍 언어 구현: 그 프로그래밍 언어로 작성된 프로그램을 수행하는 프로그램

┗  프로그래밍 언어 L의 구현:

- 프로그래밍 언어 'L'로 작성된 프로그램 'Pʟ'이 'L'의 구문 규칙을 따르는 올바른 프로그램인지 검사
- 올바른 경우, 'Pʟ'을 입력으로 받아서 L의 의미 규칙에 따라 실행

┗  프로그래밍 언어 구현은 대개 프로그램을 입력으로 받는 프로그램 형태로 주어짐

┗  CPU의 함수 모형:

- 'M': CPU가 받아들이는 기계어
- 'Pᴍ': 기계어 M으로 작성된 프로그램
-> M ⟦ Pᴍ ⟧(in) = out
-> 이 프로그램의 수행은 입력 데이터 in을 받아 출력 데이터 out을 내는 형태

┗  프로그래밍 언어 구현의 함수 모형:

- 'L': 어떤 프로그래밍 언어
- 'Pʟ': L로 작성된 어떤 프로그램
-> L ⟦ Pʟ ⟧(in) = out
-> 입력 데이터 in을 받아 출력 데이터 out을 내는 형태

┗  프로그래밍 언어 구현 형태:

[ '인터프리터'의 함수 모형 ]
- 'Intʟ': 프로그래밍 언어 L의 명령어를 해석하는 인터프리터
-> Intʟ ⟦ Pʟ ⟧(in) = out
-> 인터프리터 L로 작성된 프로그램 Pʟ을 해석하며 CPU와 비슷한 기능을 수행함

[ '컴파일러'의 함수 모형 ]
- 'Compʟ': 프로그래밍 언어 L의 컴파일러
-> 고수준 언어 프로그램 'Pʟ'을 CPU가 수행할 수 있는 저수준 언어 프로그램 'Pᴍ'으로 변환
-> Compʟ ⟦ Pʟ ⟧ = Pᴍ
-> 이렇게 생성된 프로그램 'Pᴍ'은 CPU가 수행할 수 있음
-> M ⟦ Pᴍ ⟧(in) = out

 

💡 2. 프로그래밍 언어 구현 개요

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

┗  대상: 명령형 언어, 절차형 언어, 객체지향 언어

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

- '명령형 언어': '저급언어'의 '연산'과 '명령어'를 확장하는 형태로 구현
- '절차형 언어': 명령형 언어 + 사용자정의연산(함수)과 사용자정의 명령어(프로시저)를 지원하는 형태로 구현
- '객체지향 언어': 절차형 언어 + 사용자정의 데이터 타입을 지원하는 형태로 구현
-> 객체지향 상속 관련: '부분형 관계', 'IS-A 관계', '가상함수 테이블(Vtab)'

 

[ 새로운 패러다임의 프로그래밍 언어 구현 ]

┗  "함수형 언어", "논리 언어" 등 새로운 패러다임의 언어는 기계어를 확대한 형태로는 한계가 있음.

┗  (1) 언어의 계산 모델과 하드웨어 사이에 추상기계를 놓음 

┗  (2) 해당 언어의 프로그램을 추상기계가 이해하는 프로그램으로 변경

[ '함수형' 언어 ]
- '계산 모델': 람다 계산법
- '추상기계': CPS, G-machine, SGM, STGM, TIM 등

[ '논리' 언어 ]
- '계산 모델': 연역 논리
- '추상기계': WAM 등

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

┗  참고: "추상기계"는 모델일뿐, 구현한 실제 프로그램은 -> "가상기계"

 

[ 컴파일러 구현 단계 ]

┗  분석 단계 (전단부):

- 주어진 프로그램을 구성 요소로 나누어 구조 파악
- 중간 표현(중간 코드) 생성
- '세부 단계': 어휘 분석, 구문 분석, 의미 분석
- '프로그래밍 언어에 종속적임.'

┗  중간 표현(중간 코드): 전단부와 후단부를 구별하는 자료 구조

┗  생성 단계 (후단부):

- 목적 기계에 적합한 명령어 생성
- 효율적인 목적 코드 생성
- '세부 단계': 중간 코드 최적화, 코드 생성, 목적 코드 최적화
- '목적 기계에 종속적임'

 

[ 인터프리터 구현 단계 ]

┗  "컴파일러 구현 단계"의 "분석 단계"를 그대로 거침

┗  중간 표현을 순회하며 프로그램을 수행

┗  인터프리터 엔진: 프로그래밍 언어의 "문장 단위"로 해석하여 수행

 

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

┗  구문 트리:

- 언어 구현 단계의 중심을 차지하는 자료 구조
- '분석 단계'의 '전 과정'을 '관통'

┗  심볼 테이블:

- 컴파일러 구현에 사용됨
- 프로그램에서 '정의'하거나 '선언한 식별자 정보(타입, 선언 위치 등)'를 저장

┗  환경:

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

┗  실행 환경:

- 언어를 구현할 때 사용되지는 않지만 프로그램 실행 시 반드시 필요
- 메모리 구조와 레지스터를 포함

- 메모리 구조: 실행 지원
-> '정적 세그먼트': 코드, 정적 데이터
-> '동적 세그먼트': 스택, 힙

- 레지스터: 메모리 및 실행 상태를 관리
-> '전용 레지스터': PC, SP(Stack Pointer), FP(Frame Pointer) 등
-> '범용 레지스터': 기타 여러 목적으로. 사용되는 레지스터

 

💡 3. 언어 구현 실제

[ 어휘 분석기 구현 ]

- 어휘 분석기는 프로그램의 어휘(예약어, 리터럴, 연산자 등)를 구별해 냄
- 필요에 따라 속성을 구하여 구문 분석기에 전달
- 대부분 유한 상태 기계(FSM)를 구성하여 구현

[ 구문 분석기 구현 ]

┗  구문 분석기: 어휘 분석기의 분석 결과인 "토큰 열"로부터 "구문 트리"를 구성함

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

- 파스 트리: 문법 기호 정보를 모두 포함
- 추상 구문 트리(AST): 번역에 필요한 정보만 포함

         '파스 트리 (Parse Tree)'                '추상 구문 트리 (AST)'

             <assignment>                             =
            /     |       \                          / \
 <identifier>     =     <expression>                x   +
      |                  /    |    \                   / \
      x        <identifier>   +   <identifier>        a   b
                     |               |
                     a               b

┗  때로는 구문 트리를 순회하는 여러 프로시저로 구성된 프로그램을 "구문 분석기"라고 부르기도 함.

┗  순환 하강 구문 분석기: 문법 규칙을 그대로 코드로 바꾼 형태 -> 구문 분석기 구현 방법 중 하나

- 각 비단말 기호의 문법 규칙에 대해 하나의 프로시저를 만들되, 우변을 모사하도록 프로시저를 만듦
- 우변을 모사할 때 단말 기호라면 일치하는지 검사하고, 비단말 기호라면 해당 프로시저를 호출함
- 즉, BNF 같은 문법 규칙을 함수 구조로 거의 그대로 옮긴 거라고 보면됨.