JANGUN


컴파일러 구성


지음 : 김강현



목차

제1장 컴파일러의 개요
제2장 형식언어와 오토마타
제3장 어휘분석
제4장 Context-free 언어와 푸시다운 오토마타
제5장 구문분석
제6장 의미분석과 기호표
제7장 중간언어와 중간코드 생성
제8장 코드 최적화
제9장 목적코드 생성


제1장 컴파일러의 개요

1. 컴파일러와 인간이 의사전달을 하기 위해서는 BASIC, FORTRAN, COBOL, PASCAL, C, C++, JAVA, Delphi와 같은 고급언어가 필요하고, 이러한 고급언어로 작성된 프로그램을 컴퓨터가 인식할 수 있도록 저급언어로 번역해 주기 위해서는 번역기가 필요하다.
번역기에는 어셈블러, 컴파일러, 인터프리터, 프리프로세서 등이 있는데, 이 중 가장 대표적인 번역기가 컴파일러이다.
2. 번역기 중에서 고급언어로 작성된 프로그램을 입력자료로 하여 번역하는 가장 대표적인 번역기는 컴파일러와 인터프리터이다.
컴파일러는 일반적으로 어휘분석(lexical analysis) 단계, 구문분석(syntax analysis) 단계, 의미분석(semantic analysis) 단계, 중간코드 생성(intermediate code generation) 단계, 코드최적화(code optimization) 단계, 목적코드 생성(code generation) 단계를 거쳐 저급언어로 번역되며,
인터프리터는 컴파일러와는 달리 원시 프로그램을 입력 프로그램의 논리적인 순서에 따라 문장단위로 번역한 후 곧바로 실행된다. 이러한 차이로 번역기는 각각의 특성을 갖게 된다.
3. 어휘분석 단계에서 원시 프로그램을 읽어 들여 토큰 단위로 분리하여 출력하며, 구문분석 단계에서 이 토큰들이 주어진 문법에 맞는지를 검사하고, 구문분석 단계의 결과인 구문트리에 대하여 어떠한 의미와 기능을 하는 것인지를 분석하고, 이러한 기능이 올바르게 수행될 수 있도록 환경을 조성하는 일을 하는 것이 의미분석이다.
4. 의미분석 단계까지의 내용으로 코드를 생성해도 되지만 좀 더 효율적으로 만들어 실행 시 기억공간이나 실행시간을 절약하는 것이 필요한데, 이를 수행하는 것이 코드최적화이고, 코드최적화가 되기 위하여 중간코드가 먼저 생성되어야 한다.
마지막 단계인 목적코드 생성 단계에서는 최적화된 코드를 그대로 레지스터나 기억장소 위치를 정해서 목적코드로 생성해 준다.
5. 컴파일러는 위에서 말한 6단계의 논리적인 구조를 가지고 있다. 논리적인 구조를 실제 구현하게 되는 경우 1-패스 컴파일러 또는 2-패스 컴파일러 방법을 이용한다.
1-패스 컴파일러는 초창기에 컴파일러를 마들 때 사용하였던 방법으로 컴파일러의 전 과정을 하나의 패스로 구현하는 방법이고, 2-패스 컴파일러는 컴파일러의 구성을 중간코드를 기점으로 하여 앞 단계를 전반부, 뒤 단계를 후반부로 구성하는 방법이다.
6. 컴파일러를 구현하는 것은 일반 소프트웨어 구현과 비슷하지만, 설계상의 문제, 컴퓨터의 소프트웨어 시스템, 사용자의 요구사항 및 개발에 참여하는 인적 자원 등을 고려하여 구현해야 한다.



제2장 형식언어와 오토마타

1. 형식언어란 어떤 알파벳에서 얻은 기호들로 구성되는 문자열들의 집합을 말하며 이러한 형식언어를 생성하기 위해 여러 규칙을 이용하는데 이것을 형식문법이라 한다.
형식문법을 표현하기 위해 정규표현(regualar expression), 문법도표(syntax diagram), BNF(Backus-Naur Form), EBNF(Extended BNF) 등의 방법을 사용한다.
2. 형식언어를 인식하기 위해 유한 오토마타를 이용하는데 크게 결정적 유한 오토마타(Deterministic Finite Automata : DFA)와 비결정적 유한 오토마타(Nondeterministic FA : NFA)로 구분짓는다.
DFA란 하나의 입력문자열에 대하여 오직 하나의 다음 상태가 결정되는 유한 오토마타이며, NFA는 어떤 상태에서 주어진 하나의 입력기호를 보고, 갈 수 있는 다음 상태가 하나 이상 존재할 수 있는 유한 오토마타이다.
3. NFA는 언어의 구조를 쉽게 표현할 수 있지만 DFA보다 프로그램으로 구현하기 힘들다. 반면 DFA는 NFA보다 프로그램으로 구현하였을 때 효율면에서 좋다.
이러한 이유로 NFA가 언어의 구조를 표현하고 일반적인 구현은 DFA로 해야 효율적이다. 따라서 DFA에서 NFA로, NFA에서 DFA로의 변환을 필요로 하며 서로 변환 가능하다.
4. 정규표현, 정규문법, 유한 오토마타는 서로 동치관계에 있으며 서로 변환 가능하다.



제3장 어휘분석

1. 어휘분석(lexical analysis)이란 원시 프로그램을 읽어 들여 토큰(token)이라는 의미 있는 문법단위로 분리하는 것을 말하며, 어휘분석을 담당하는 도구를 어휘분석기(lexical analyzer) 또는 스캐너(scanner)라고 한다.
2. 토큰이란 의미 있는 문법적 단위로서 일반적으로 식별자(identifier), 상수(constant), 예약어(reserved word), 연산자(operator), 구분자(delimiter) 등이 사용된다.
토큰의 종류와 형태는 프로그래밍 언어 설계자나 컴파일러 설계자에 의해 결정된다.
3. 어휘분석기를 설계하기 위해서 우선 정규문법이 주어져야 하며 (이 정규문법은 일반적으로 정규표현으로 표시된다.), 주어진 문법에 대한 토큰표(token table)를 작성한다.
다음으로 문법을 보고 NFA를 구성하고, NFA를 DFA로 변환한 다음, DNF를 최소화시키면 어휘분석기가 된다.
4. 어휘분석기를 구현할 때에는 문법이 어떻게 주어지는지 명확하게 정의되어야 하며, 어떤 토큰들이 많이 사용하는지 확률개념을 도입해야 한다.
또한 구문분석을 하면서 부프로그램처럼 어휘분석기를 호출할 것이냐 아니면 어휘분석기를 먼저 수행시킨 다음 그 결과를 구문분석기에 전달할 것이냐 하는 것도 구현 시 고려되어야 한다. 이외에 예약어의 처리 및 실수의 내부 표현 등도 고려해야 한다.
5. 어휘분석기 생성기는 컴파일러 생성기 또는 컴파일러-컴파일러의 일부분으로서 어휘분석기를 자동으로 생성하는 도구이다.
어휘분석기의 종류에는 LEX, FLEX, ScanGen, PCLEX, POISON, JLEX 등이 있다.



제4장 Context-free 언어와 푸시다운 오토마타

1. context-free 언어는 자연언어(natural language)를 표현하기 위해 도입되었으며, 정규언어보다 표현범위가 넓어서, 이것을 인식하는 푸시다운(push-down) 오토마타를 구현하는 일은 유한 오토마타를 구현하는 일보다 훨씬 복잡하고 어렵다.
2. 유도과정의 각 단계에서 문장형태의 가장 왼쪽에 있는 논터미널 기호를 계속해서 대체하는 경우를 좌단유도(leftmost derivation)라 하며, 반대로 가장 오른쪽에 있는 논터미널 기호를 계속해서 대체하는 경우는 우단유도라 한다.
3. 구문분석의 방법은 크게 두 종류가 있으며, 하나는 top-down 구문분석이고 다른 하나는 bottom-up 구문분석이다.
또한 구문분석을 하는 과정은 문장이 유도되는 과정을 트리 형태로 표현하는데, 이를 유도 트리(derivation tree) 또는 파스트리(parse tree)라고 한다.
4. 문장이 효율적으로 인식되기 위하여 context-free 문법이 가지고 있는 비효율적인 부분들인 모호성, ε-생성규칙, 단일 생성규칙, left-factoring, left-recursion 등을 제거해야 한다.
5. 푸시다운 오토마타는 유한 상태 제어(finite state control)와 입력 테이프 외에 무한정의 용량을 가진 스택으로 구성되며, 비결정적 푸시다운 오토마타와 결정적 푸시다운 오토마타의 두 종류가 있다.



제5장 구문분석

1. 구문분석 방법은 크게 top-down 방법과 bottom-up 방법의 두 종류로 나누어 볼 수 있다.
top-down 방법은 시작기호로부터 시작하여 정의된 문법의 규칙(rule)들을 적용하여 유도에 의한 주어진 문자열을 찾아가는 방법이고, 반대로 bottom-up 방법은 입력된 문자열에서 감축(reduce)에 의해 시작기호를 찾아가는 방법이다
2. 순위문법(precedence grammar)들에는 연산자순위 문법(operator precedence grammars), 단순순위 문법(simple precedence grammars), 확장순위 문법(extended precedence grammars), 한정순위 문법(weak precedence grammars), 혼합순위 문법(mixed strategy precedence) 등이 있다.
3. Bottom-up 구문분석에는 스택과 입력버터 등을 사용하는 shift-reduce 구문분석, 여러 가지의 순위 구문분석이 있다.
4. LR 파싱표를 구성하는 방법은, SLR, CLR, LALR 방법이 있으며, SLR은 구현하기 쉽지만 완전하지 못하고, CLR은 가장 적당하지만 구현하기가 매우 힙들다.
그래서 SLR과 CLR의 중간을 취하는 방법이 LALR이고 이 방법이 가장 많이 사용되고 있다.
5. top-down 구문분석 중 backtracking을 하지 않은 것을 LL 구문분석이라고 하며, top-down 구문분석의 종류에는 recursive-descent 구문분석과 predictive 구문분석이 있다.
recursive-descent 구문분석은 재귀적 프로시저 집합을 사용하고 생성규칙이 바뀌면 프로그램 자체를 수정해야 한다.
반면에 predictive 구문분석은 파싱표를 이용하여 생성규칙이 바뀌었을 때 파싱표만 수정하면 된다.



제6장 의미분석과 기호표

1. 의미분석을 통하여 구문분석 단계에서 얻은 파스트리를 중심으로 의미를 부여하여 중간코드 생성이 가능하게 한다.
의미분석 과정에서는 상수정의, 유형정의, 변수의 유형선언, 프로시저 선언 등이 이루어진다.
2. 기호표는 의미분석 단계에서 기호표에 수집된 속성과 참조된 식별자의 사용이 타당한지를 검사하는 역할을 한다.
기호표에서 식별자와 관련될 수 있는 자료는 식별자 이름, 유형, 레벨, 오프세트, 차원수 등이며, 특히 기호유형은 의미분석 시 유형검사를 위해 중요한 요소이다.
3. 기호표 구성은 전체적인 컴파일 시간에 많은 영향을 끼치며 기호표는 크게 선형 리스트, 트리, 해시표의 세 가지 방법을 이용하여 구성할 수 있다.
이 중에서 해시기호표 구성방법이 가장 효율이 좋은 검색법을 갖는 것으로 알려져 있다.



제7장 중간언어와 중간코드 생성

1. 중간코드를 이용하면 기계와 독립적인 최적화가 가능하고, 기계코드로 바뀐 상태에서 행하는 것보다 훨씬 효율적인 최적화를 수행할 수 있다.
이러한 중간코드로는 후위표현, 3-주소 코드, 트리구조, 가상적인 기계코드 등 여러 종류가 있다.
2. 후위표현은 산술연산자를 관호 사용 없이 표현할 수 있는 형식으로 구문트리의 선형화된 표현방법이다.
인터프리터를 사용하는 언어의 중간언어로 적합하지만 최적화를 위해서는 부적합한 중간언어이다.
3. 3-주소 코드는 상용 컴파일러에서 가장 많이 사용하는 중간언어로서 코드를 재구성할 때 편리하기 때문에 코드를 최적화하는 컴파일러에서 주로 사용된다.
이 3-주소 코드는 연산자와 피연산자를 위한 필드와 함께 레코드로 구현될 수 있는데, triple, quadruple 혹은 간접 triple의 형태로 구현된다.
4. 구문지시적 변환(syntax-directed translation)은 구문분석을 하면서 중간코드를 생산하는 방법이다.
이는 context-free 문법의 각 생성규칙과 그와 결합하여 쓰여지는 부프로그램이나 의미수행(semantic action) 코드로 구성된다.
구문지시적 변환의 장점은 컴파일러의 설계자가 원시언어의 구문구조에 따라 직접 중간언어 생성을 표현할 수 있다는 점이다.



제8장 코드 최적화

1. 코드최적화란 보다 효율적인 실행코드를 만드는 것으로 최적화 과정은 최적화 관점에 따라 여러 가지로 분류된다.
이 장에서는 실행시간을 짧게 하기 위한 최적화와 소요 기억용량을 작게 하는 최적화의 관점으로 나누어 살펴보았다.
2. 실행시간을 짧게 하기 위한 최적화 방법으로는 공통 부분식의 제거, 상수전파, 코드이동, 루프의 융합, 루프전개, 프로시저 호출의 전개, 불필요한 코드의 제거, 복사전파, 식의 연산순서 변경, 중복된 로드, 저장 명령문 제거, 식의 대수학적 간소화, 연산의 세기 경감, 결합변경, 귀납변수 최적화 및 기타 방법이 있다.
3. 소요 기억용량의 최적을 위한 방법으로는 상수전파, 루프의 융합, 복사전파, 중첩된 로드, 저장 명령문 제거, 연산의 세기 경감, 레지스터 할당 등의 방법 이외에도 부프로그램화와 부분식 끌어올리기 등의 방법이 있다.



제9장 목적코드 생성

1. 컴파일러의 마지막 단계는 목적코드 생성이다. 목적코드 생성은 중간코드를 입력으로 받아 그 기계에 맞는 기계어로 생성할 수 있으며, 어셈블리어로도 생성할 수 있다.
좋은 코드를 생성하려면 해당되는 기계의 하드웨어나 운영체제에 대해서 잘 알아야 한다.
2. 산술식에 대한 목적코드 생성은 레지스터(accumulator, 누산기)의 개수에 따라 생성하는 방법이 다르다.
3. 논리식은 ∧ (AND), ∨ (OR), ¬ (NOT) 등의 논리연산자를 사용한다.
또한 논리식의 값은 특별한 기능을 갖는데 논리식에 대한 목적코드를 생성할 때 이러한 특성을 이용하면 목적코드를 좀 더 효율적으로 생성할 수 있다.