1.1
다음 괄호에 알맞은 말을 쓰시오.
(1) 한 프로그래밍 언어로 쓰여진 프로그램을 입력으로 받아 그와 동등한 의미를 갖는 다른 프로그래밍 언어로 된 프로그램을 출력하여 주는 시스템 프로그램을 (번역기)라 말한다.
해설) 컴파일러란 언어의 번역기 중 하나로 고급 언어 프로그램을 입력으로 받아 의미적으로 동등하면서 직접 기계에서 실행될 수 있는 형태로 번역하는 작업을 한다.
(2) 좋은 프로그래밍 언어는 (Symentic)과 Semantics가 명료해야 한다.
해설) 좋은 프로그래밍 언어의 요건은
(1) 언어의 개념이 명로해야 한다. 문법적인 구조(syntax)와 그에 따른 의미(semantic)가 일관성이 있으며 단순해야 한다.
(2) 프로그래머의 생각을 자연스럽게 표현할 수 있어야 한다.
(3) 프로그램의 호환성, 신뢰성, 모듈화, 효율성 등이 좋아야 한다.
(4) 언어의 확장성이 우수해야 한다.
(5) 좋은 프로그래밍 환경을 갖고 있어야 한다.
(3) Ada란 1980년 미 국방성(DoD)에서 발표한 언어로 (실시간) 응용에 적합한 언어이다.
해설) 에이다의 개발 목적은 신뢰성, 단순성, 모듈화, 효율성 등으로 요약될 수 있으며 에이다가 갖는 언어의 특징으로는 패키지, 포괄 구조, 분리 컴파일, 다중 처리 등이 있다.
(4) 인터넷 프로그래밍 언어는 크게 (서버사이드) 언어와 (클라이언트사이드) 언어로 구분할 수 있다.
해설) 인터넷 프로그램이란 웹 브라우저에서 실행될 수 있는 프로그램을 의미하며 인터넷 프로그램을 작성하는 일을 인터넷 프로그래밍이라 한다. 서버사이드 언어에 속하는 언어로는 PERL, PHP, ASP, JSP 등이 있고 후자에 속하는 언어로는 HTML, DHTML, 자바스크립트, 자바 애플릿 등이 있다.
(5) 한 기종에서 작동하는 컴파일러를 다른 기종으로 그대로 이전하면 (크로스 컴파일러)가 된다.
해설) 크로스 컴파일러란 소스 프로그램을 컴파일러가 실행회고 있는 기계에 대한 기계어로 번역하는 것이 아니라 다른 기종에 대한 기계어로 번역하는 컴파일러를 말한다. 크로스 컴파일러의 출력 프로그램을 실행하기 위해서는 그 기종으로 프로그램을 가져가서 실행시키거나 또는 그 기종에 대한 코드 인터프리터(또는 에뮬레이터)가 있어야 한다. 주로 새로운 기종에 필요한 컴파일러를 설치할 때 사용하는 기술이다. ex) A 컴퓨터에서 작동하는 컴파일러가 B 컴퓨터를 위한 실행 코드를 생성하는 경우, 썬사의 워크스테이션(SPARC 프로세서)에서 수행되는 C 언어 컴파일러가 펜티엄 프로세서를 위한 목적 코드를 생성하는 경우
(6) 컴파일러의 일반적인 구조는 어휘 분석, 구문 분석, 중간코드 생성, (코드 최적화), 그리고 목적코드 생성 과정으로 나눌 수 있다.
해설) 컴파일러의 구조는 크게 전단부(어휘 분석, 구문 분석, 중간코드 생성)와 후단부(코드 최적화, 목적코드 생성)로 나눌 수 있다. 전단부는 소스 언어에 관계되는 부분으로 소스 프로그램을 분석하고 중간 코드를 생성하는 부분이다. 후단부는 소스 언어보다는 목적 기계에 의존적이며 전단부에서 생성한 중간 코드를 특정 기계를 위한 목적 코드로 번역하는 부분이다.
(7) 어휘 분석기를 간단히 (스캐너 Scanner)라 부르며 구문 분석기를 (파서 Parser)라 부른다.
해설) 어휘 분석기는 소스 프로그램을 읽어 들여 일련의 토큰을 생성하는 일을 한다. 구문 분석기는 어휘 분석 단계의 출력인 토큰들을 받아 소스 프로그램에 대한 에러를 체크하고 올바른 문장에 대해서는 구문 구조를 만든다.
(8) 중간 코드 생성기의 입력은 (추상 구문 틀)이고 출력은 중간 코드이다.
해설) 중간 코드 생성 과정에서는 파서의 출력인 추상 구문 트리를 입력으로 받아 의미 검사를 행하고 그에 해당하는 중간 코드를 생성한다.
(9) 최적화는 그 위치에 따라 (precode optimization)와 (postcode optimization)으로 나눌 수 있다.
해설) precode optimization은 중간 코드를 이용하여 최적화를 수행하며 그 위치는 목적 코드 생성 전에 행해진다. postcode optimization은 목적 코드 생성 후에 목적 코드를 최적화하는 방법으로 기계 의존적인 최적화 방법이다.
(10) N개의 언어를 M개의 기종에 설치하려 할 때, (N*M)개의 컴파일러가 필요하다.
해설) 프로그래밍 언어와 컴퓨터 구조가 다양해짐에 따라 많은 컴파일러가 필요하게 되었다. 즉, N개의 언어를 M개의 기계에 구현하려 할 때 N*M개의 컴파일러가 필요하다. 이에 따라 컴파일러 제작을 도와주는 도구들이 필요하게 되었고 컴파일러의 전 과정이나 각 단계들을 자동적으로 생성하는 도구들에 대한 연구가 활발히 진행되었다.
(11) 언어 표현과 목적 기계에 대한 기계 표현을 입력으로 받아 하나의 컴파일러를 생성하는 도구를 (컴파일러-컴파일러)라 부른다.
해설) (10)과 같은 도구들을 총칭해서 컴파일러 생성기 또는 컴파일러-컴파일러라 부른다. 컴파일러-컴파일러는 특정한 프로그래밍 언어를 위한 언어 표현과 목적 기계에 대한 기계 표현을 입력으로 받아 하나의 컴파일러를 출력한다. 이때 생성된 컴파일러는 언어 표현에 기술된 소스 프로그램을 입력으로 받아 목적 기계의 코드로 번역해 주는 역할을 수행한다.
(12) 어휘 분석기 생성기의 입력은 (토큰 표현)이고 출력은 (어휘 분석기)이다.
해설) [그림 1.17 참고] 어휘 분석 생성기는 어휘 분석기를 자동으로 생성하는 도구이다. 토큰에 대한 표현을 입력으로 받아 기술된 형태의 토큰을 찾아내는 어휘 분석기를 만든다. 생성된 어휘 분석기는 입력 프로그램에서 토큰들을 구분해 내는 일을 한다.
(13) 파서 제작 시스템의 입력은 (언어의 문법 표현)이고 출력은 (파싱 테이블)이다.
해설) 파서 생성기란 언어의 문법 표현으로부터 파서(또는 구문 분석기)를 자동으로 생성하는 도구를 말한다. [그림 1.19 참고] 보통 파서 생성기를 파서 제작 시스템(PGS: Parser Generating System)이라 부른다. 언어의 문법 표현으로부터 파서 생성기는 파서를 제어하는 테이블을 생성한다. 파서는 이 테이블을 이용하여 주어진 문장에 대한 문법적인 검사를 하며 다음 단계에서 필요한 의미 정보를 만든다.
(14) 생성기-생성기는 생성될 단계의 기능을 묘사하는 (메타 언어)를 입력으로 받아 각 단계가 사용하게 될 테이블(또는 프로그램)을 출력한다.
해설) [그림 1.16 참고] 각 구동기는 이 테이블을 이용하여 그 단계에서 수행해야 할 일을 처리한다. 따라서 필요한 컴파일러 단계를 구현하기 위하여 프로그램을 작성하는 것이 아니라 그 단계에서 처리하는 작업을 메타 언어로 기술하면 되는 것이다.
(15) 일반적으로 YACC는 파서만을 생성하기 때문에 스캐너는 (렉스)를 사용하여 생성해야만 한다.
해설) 렉스는 어휘 분석기 생성기의 대표적인 예로, 토큰의 형태를 묘사한 정규 표현들과 각 정규 표현이 매칭되었을 때 처리를 나타내는 액션 코드로 구성된 입력을 받아 어휘 분석의 일을 처리하는 프로그램을 출력한다. YACC은 파서 생성기의 대표적인 예로, 문법 규칙과 그에 해당하는 액션 코드를 입력으로 받아 파싱을 담당하는 프로그램을 출력한다.
(16) PQCC에서 사용한 중간 언어는 (TCOL)이고 ACK에서 사용한 중간 언어는 (EM)이다.
해설) PQCC(Production-Quality Compiler Compiler)는 소스 언어와 목적 기계를 정형화하여 컴파일러를 생성하는 시스템이다. PQCC에서는 트리 형태릐 중간 언어인 TCOL(Tree Common Oriented Language)을 사용하였으며 그 시스템의 기능은 언어와 목적 기계에 대한 정형화된 표현을 입력으로 받아 PQC(Production Quality Compiler)라고 부르는 기초 코드 생성기와 최적화기가 사용하는 테이블을 만들어 낸다. 그리고 PQC는 이 테이블을 이용하여 전단부에서 생성한 TCOL을 목적 코드로 번역하는 작업을 한다. ACK(Amsterdam Compiler Kit)는 컴파일러의 후단부를 자동화하기 위한 도구의 하나로서 이식성과 재목적성이 매우 높은 컴파일러를 만들기 위한 실질적인 도구이다. 각 언어에 대한 전단부가 중간 언어인 EM(Encoding Machine) 코드를 생성해 낸다. EM 코드는 가상적인 스택 기계에 근거를 둔 일종의 어셈블리어이다. 그리고 생성된 EM 코드에 대한 최적화 과정(peephole optimization & global optimization)을 거친 후에 후단부에 의해 목적 프로그램으로 변환된다.
(17) Java 언어의 중간 코드는 ()이고 실행 환경은 ()이다.
해설)
(18) C# 언어의 중간 코드는 (MSIL)이고 실행 환경은 (CLR)이다.
해설) MSIL(Microsoft Intermediate Language), CLR(Common Language Runtime)
1.2
다음 약어에 대한 원어를 쓰시오.
(1) PGS : Parser Generating System
(2) YACC : Yet Another Compiler-Compiler
(3) PQCC, TCOL : Production-Quality Compiler Compiler, Tree Common Oriented Language
(4) ACK, EM : Amsterdam Compiler Kit, Encoding Machine
(5) JIT : Just In-Time Compilation
1.3
컴파일러의 일반적인 구조를 어휘 분석기, 구문 분석기, 중간 언어 생성기, 코드 최적화기, 그리고 목적 코드 생성기로 나누어 설명하고 특히, 각 단계의 입력과 출력을 설명하시오.
1) 어휘 분석기 : 소스 프로그램을 읽어 들여 일련의 토큰을 생성하는 일을 한다.
2) 구문 분석기 : 어휘 분석 단계의 출력인 토큰들을 받아 소스 프로그램에 대한 에러를 체크하고 올바른 문장에 대해서는 구문 구조를 만든다.
3) 중간 언어 생성기 : 파서의 출력인 추상 구문 트리를 입려으로 받아 의미 검사를 행하고 그에 해당하는 중간 코드를 생성한다.
4) 코드 최적화기 : 선택적인 단계이며 생략할 수 있다. 기능은 같은 의미를 유지하면서 코드를 보다 더 효율적으로 만들어 코드 실행시 기억 공간이나 실행 시간을 절약하는데 있다.
5) 목적 코드 생성기 : 중간 코드를 입력으로 받아 그와 의미적으로 동등한 목적 기계에 대한 코드를 생성하는 일을 한다.
1.4
코드 최적화는 관점에 따라 지역 최적화와 전역 최적화로 구분할 수 있다. 지역 최적화(핍홀 최적화)에 의해 얻을 수 있는 효과를 열거하시오.
1) 컴파일 시간 상수 연산
2) 중복된 load, store 명령문 제거
3) 식의 대수학적 간소화
4) 연산 강도 경감
5) 불필요한 일련의 코드 블록 삭제 등
1.5
목적 코드 생성기가 목적 코드를 생성하기 위하여 행하는 작업을 크게 4가지로 나누어 설명하시오.
1) 목적 코드 선택 및 생성 : 중간 코드의 의미와 일치하는 기계 명령어들을 효과적으로 선택하는 코드 생성 알고리즘을 사용해야 한다.
2) 레지스터의 운영 : 대부분의 컴퓨터들이 빠른 시간 내에 계산을 할 수 있는 소수의 고속 레지스터들을 가지고 있다. 그러므로 우수한 목적 코드 생성기는 이러한 레지스터들을 가능한 한 효율적으로 사용할 수 있어야 한다. 효율적인 레지스터의 사용은 임시 변수의 사용을 줄일 수 있을 뿐만 아니라 전체적인 실행 속도를 빠르게 할 수 있다. 레지스터 할당 문제는 효율적인 코드 생성을 위해서 매우 중요한 문제이며 많은 알고리즘이 개발되어 있다.
3) 기억 장소 할당 : 각 변수들에 대한 기억 장소를 할당해야 한다.
4) 기계 의존적인 코드 최적화 : 목적 코드 생성기에서 행하는 기계 의존적인 최적화는 연속적인 명령어들을 의미적으로 동등한 하나의 명령어 또는 처리 속도가 빠른 명령어로 대체하여 기계어 코드의 성능을 향상시키는 방법이다. 일반적으로 코드 생성기에 의해 생성된 코드들은 잘 훈련된 어셈블리 프로그래머들이 손으로 작성한 코드들보다 훨씬 효율적이어야 한다.
1.6
렉스와 YACC의 기능을 간단히 설명하시오. 그리고 렉스와 YACC을 이용하여 컴파일러의 전단부를 구현하는 방법을 설명하시오.
렉스는 토큰의 형태를 묘사한 정규 표현들과 각 정규 표현이 매칭되었을 때 처리를 나타내는 액션 코드로 구성된 입력을 받아 어휘 분석의 일을 처리하는 프로그램을 출력한다.(코드를 해석하고 토큰으로 분해, YACC에 yylex() 함수를 제공) YACC은 문법 규칙과 그에 해당하는 액션 코드를 입력으로 받아 파싱을 담당하는 프로그램을 출력한다.(기술 파일의 main() 함수에서 yyparse()라는 YACC에 의해 만들어지는 구문 분석기를 부르고, yyparse() 함수는 yylex()라는 렉스가 만들어 주는 해석기(lexer)를 이용해서 입력열에서 처리단위의 토큰을 뽑아오게 된다.)
YACC로부터 생성된 프로그램인 y.tab.c가 문법 규칙에 의해 기술된 언어의 문장에 대해 구문 검사를 하며 문법 큐칙과 결합된 액션 코드를 필요할 때마다 수행한다.
1.7
컴파일 과정을 어휘 분석, 구문 분석, 중간 코드 생성, 코드 최적화, 목적 코드 생성 단계로 나누어 설명하고 각 단계를 자동적으로 구성하기 위한 컴파일러 제작 도구에 관하여 논하시오.
1) 어휘 분석 : 어휘 분석기를 통해 토큰에 대한 표현을 입력으로 받아 기술된 형태의 토큰을 찾아내어 입력 프로그램에서 토큰들을 구분해 낸다.
2) 구문 분석 : 언어의 문법 표현으로부터 파서 생성기는 파서를 제어하는 테이블을 생성한다. 파서는 이 테이블을 이용하여 주어진 문장에 대한 문법적인 검사를 하며 다음 단계에서 필요한 의미 정보를 만든다.
3) 중간 코드 생성 :
4) 코드 최적화
5) 목적 코드 생성
- 각 단계를 자동적으로 구성하기 위한 컴파일러 제작 도구
(1) PQCC(Production-Quality Compiler Compiler)는 소스 언어와 목적 기계를 정형화하여 컴파일러를 생성하는 시스템이다. PQCC에서는 트리 형태릐 중간 언어인 TCOL(Tree Common Oriented Language)을 사용하였으며 그 시스템의 기능은 언어와 목적 기계에 대한 정형화된 표현을 입력으로 받아 PQC(Production Quality Compiler)라고 부르는 기초 코드 생성기와 최적화기가 사용하는 테이블을 만들어 낸다. 그리고 PQC는 이 테이블을 이용하여 전단부에서 생성한 TCOL을 목적 코드로 번역하는 작업을 한다.
(2) ACK(Amsterdam Compiler Kit)는 컴파일러의 후단부를 자동화하기 위한 도구의 하나로서 이식성과 재목적성이 매우 높은 컴파일러를 만들기 위한 실질적인 도구이다. 각 언어에 대한 전단부가 중간 언어인 EM(Encoding Machine) 코드를 생성해 낸다. EM 코드는 가상적인 스택 기계에 근거를 둔 일종의 어셈블리어이다. 그리고 생성된 EM 코드에 대한 최적화 과정(peephole optimization & global optimization)을 거친 후에 후단부에 의해 목적 프로그램으로 변환된다.
