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

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

프로그래밍 언어 정의

• 어떤 프로그램이 올바른 형태인지, 또 올바른 형태의 프로그램을 실행하였을 때 어떻게 실행되는 것이 올바른 것인지 규정하는 것
  • 구문(syntax): 형태에 대한 규정
  • 의미(semantics): 실행 결과에 대한 규정
• 프로그래밍 언어 정의 방법
  • 구문 정의: 문맥 자유 문법, BNF, EBNF, 구문 도표
  • 의미 정의: 기능적 의미론, 표기적 의미론, 공리적 의미론 등
  • 실제로 의미를 정의할 때, 여러 의미론은 매우 난해하므로 대신 자연어를 사용함

프로그래밍 언어 구현

• 프로그래밍 언어 L로 작성된 어떤 프로그램 P_L이 주어졌을 때, P_L이 L의 구문 규칙을 따르는 올바른 프로그램인지 검사하고, 올바른 경우에 P_L을 L의 의미 규칙에 따라 실행하는 프로그램을 L의 구현이라고 부름
• 프로그래밍 언어 구현은 대개 프로그램을 받는 프로그램 형태로 주어짐
• 프로그래밍 언어 구현 모델
  • CPU가 받아들이는 기계어를 M, 기계어로 작성된 프로그램을 P_M이라고 하면, 이 프로그램의 수행은 입력 데이터 in을 받아 출력 데이터 out을 내는 형태임
  • 어떤 프로그래밍 언어 L의 구현은 L로 작성된 어떤 프로그램 P_L이 주어졌을 때, 입력 데이터 in을 받아 출력 데이터 out을 내야 함
• 프로그래밍 언어 구현 형태
  • 인터프리터(interpreter)
    • 프로그래밍 언어 L명령어를 해석하는 프로그램 Int_L을 인터프리터라고 함
    • 인터프리터는 L프로그램 P_L을 해석하며 CPU와 비슷한 기능을 수행함
  • 컴파일러(compiler)
    • 고수준 언어 프로그램 P_L을 CPU가 수행할 수 있는 저수준 언어 프로그램 P_M으로 변환하는 프로그램 Comp_L을 컴파일러라고 함
    • 이렇게 생성된 프로그램 P_M은 기계 M이 수행할 수 있음

프로그래밍 언어 구현 방법

프로그래밍 언어 구현 개요

• 전통적인 프로그래밍 언어 구현
  • 명령형 언어와 여기서 발전한 절차형 언어는 기계어를 확대한 형태를 가정함
  • 명령형 언어: 저급언어의 연산과 명령어를 확장하는 형태로 구현
  • 절차형 언어: 사용자 정의 연산(함수)과 사용자 정의 명령어(프로시저)를 지원하는 형태로 구현
  • 객체지향 언어: 자료형에 함수 및 프로시저를 연관시킴으로써 사용자 정의 자료형을 지원하는 형태로 구현

다양한 패러다임의 프로그래밍 언어 구현

• 함수형 언어나 논리 언어 등 새로운 패러다임의 언어는 기계어를 확대한 형태로는 한계가 있음
• 따라서 언어가 기초하고 있는 구현 모델을 추상기계로 만들고 추상기계가 이해하는 프로그램으로 번역함
• 가상기계(virtual machine): 추상기계 현태의 중간 기계가 구체적인 구현물로 제시되며 중간 기계 상에서 코드를 독자적으로 수행할 수 있는 경우

컴파일러 구현 단계

• 분석 단계와 생성 단계
  • 분석 단계: 원시 프로그램 구조를 파악하고 맞는 구조인지 판단하는 단계
  • 생성 단계: 프로그램 구조에 따라 목적 프로그램을 생성하는 단계
  • 분석 단계를 Front-End(어휘 분석, 구문 분석, 의미 분석), 생성 단계를 Back-End(중간 코드 최적화, 코드 생성, 목적 코드 최적화)라고 부름

인터프리터 구현 단계

• 분석 단계와 수행 단계
  • 인터프리터도 분석 단계는 그대로 거침
  • 그러나 기계어 코드를 생성하는 대신 분석된 코드를 해석하여 수행함
• 중간 표현
  • 분서된 코드를 중간 표현, 중간 코드라고 부름
  • 특별히 구별되는 가상기계가 있는 경우에는 가상기계 코드, 바이트 코드(byte code)라고 부름

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

• 구문 트리(syntax tree)
  • 언어 구현 단계의 중심을 차지하는 자료 구조
  • 전단부를 거치면 구문 트리가 생성됨
• 심볼 테이블(symbol table)
  • 컴파일러 구현에 사용됨
  • 프로그램에서 정의하거나 선언한 식별자 정보(타입, 선언 위치 등)를 저장
• 환경(environment)
  • 인터프리터 구현에 사용됨
  • 심볼 테이블보다 확장되어 식별자의 값 정보도 알 수 있는 테이블
• 실행 환경(run-time environment)
  • 컴파일러를 구현할 때 사용되지는 않지만 프로그램 실행 시 반드시 필요
  • 메모리 구조와 레지스터를 포함
  • 메모리: 정적 세그먼트(코드, 정적 데이터), 동적 세그먼트(스택, 힙)
  • 레지스터(register): 수행 중인 명령어, 스택, 힙 등을 관리하기 위해 필요

언어 구현 실제

어휘 분석기 구현

• 어휘 분석기는 프로그램의 어휘(예약어, 리터럴, 연산자 등)를 구별해 냄
• 대개 유한 상태 기계(FSM)를 구성하여 구현

구문 분석기 구현

• 구문 분석기는 어휘 분석기의 분석 결과인 토큰 열로부터 구문 트리를 구성함
• 구문 트리의 형태: 파스 트리, 추상 구문 트리
  • 파스 트리: 문법 기호 정보를 모두 포함
  • 추상 구문 트리(AST): 번역에 필요한 정보만 포함
• 때로는 구문 트리를 순회하는 프로그램을 구문 분석기라고 부르기도 함
• 순환 하강 구문 분석기: 문법 규칙을 그대로 코드로 바꾼 형태
  • 각 비단말 기호의 문법 규칙에 대해 하나의 프로시저를 만들되, 우변을 모사하도록 프로시저를 만듦
  • 우변을 모사할 때 단말 기호라면 일치하는지 검사하고, 비단말 기호라면 해당 프로시저를 호출함