학습개요
앞서 우리는 프로그래밍 언어의 구문론과 의미론, 구문 분석 이론에 대해 살펴보았습니다. 그렇다면 구체적으로 프로그래밍 언어는 어떻게 구현할 수 있을까요? 다시 말해서 프로그래밍 언어의 인터프리터나 컴파일러를 어떻게 작성할 수 있을까요? 프로그래밍 언어 구현이 복잡하긴 하지만 실제로는 우리에게 잘 알려진 자료 구조를 사용합니다. 구문 분석을 위해서는 조금 복잡한 알고리즘이 사용되는데, 성능을 크게 고려하지 않는다면 사람이 이해하기 쉬운 구문 분석 알고리즘을 선택할 수도 있습니다. 이번 강의에서는 프로그래밍 언어의 구현 방법을 알아보고 간단한 예에 대한 어휘 분석기와 구문 분석기를 살펴봅니다.
학습목표
- 프로그래밍 언어 구문과 의미를 구체적으로 정의하는 방법을 설명할 수 있다.
- 프로그래밍 언어 구현에 필요한 자료 구조와 기능을 설명할 수 있다.
- 어휘 분석기와 구문 분석기를 구현하는 방법을 살펴본다.
정리하기
- 프로그래밍 언어를 구현하기 위해서는 먼저 언어를 정의해야 하며, 이는 프로그램의 형태를 정의하는 구문론과 프로그램의 수행 의미를 정의하는 의미론으로 정의할 수 있다.
- 프로그래밍 언어 구현은 함수 모델로 해석할 수 있다.
- 전통적인 프로그래밍 언어는 기계의 단순한 명령어를 확대하는 형태로 구현한다. 그러나 새로운 패러다임의 프로그래밍 언어는 구현 모델을 추상기계로 만들고 이를 징검다리로 삼는 형태로 구현한다.
- 추상기계와 가상기계의 차이는 해당 기계의 구체적인 구현물이 있는지 여부이다.
- 컴파일러의 구현 단계는 크게 분석 단계와 생성 단계로 나눌 수 있다. 프로그래밍 언어에 의존적인 분석 단계를 전단부, 목적 기계에 의존적인 생성 단계를 후단부라고 부른다.
- 인터프리터를 구현할 때도 컴파일러의 전단부에 해당하는 분석 단계는 그대로 거친다. 하지만 전단부에서 생성된 중간 표현을 목적 코드로 바꾸는 대신 중간 표현을 순회하며 프로그램을 실행한다.
- 구문 트리와 중간 표현 외에 프로그래밍 언어 구현에 필요한 자료 구조로는 심볼 테이블과 환경을 들 수 있다.
- 언어 구현 시에는 프로그램이 실행되는 환경인 실행 환경도 고려해야 한다.
- 어휘 분석기는 어휘의 토큰과 속성을 분석하며, 구문 분석기는 토큰을 이용하여 구문 트리를 구성한다. 구문 트리는 파스 트리와 추상 구문 트리의 두 가지 형태가 있다.