[CS] 컴파일러 compiler
컴파일러(compiler)란 특정 프로그래밍 언어로 쓰여 있는 문서를 다른 프로그래밍 언어로 옮기는 언어 번역 프로그램 이다.
컴파일러의 개요
컴퓨터에서 실행되는 모든 sw는 프로그래밍 언어로 작성된다. 하지만 프로그래밍 언어는 사람이 이해할 수 있는 수준의 언어라 기계어만 이해할 수 있는 컴퓨터는 프로그래밍 언어를 이해할 수가 없다.
즉, 프로그래밍 언어로 작성된 프로그램을 기계어만 이해할수있는 컴퓨터를 위해 번역(변환) 하는 것이 컴파일러이다.
(컴파일러는 컴퓨터구조 수업을 듣고 들으면 생각보다 이해가 될 수도 있다.)
그럼 전반적인 측면에서 컴파일이 되는 과정을 간단하게 알아보자
1. 전처리기(#include 등 #이 붙은 전처리기 구문을 처리)
2. 컴파일러로 컴파일
3. 어셈블러(assembler) 컴파일러를 통해 번역된 기계코드를 완전한 기계어로 바꾸어주는 역할 (컴퓨터 구조 내용)
4. 링커(Linker) 여러 개의 오브젝트 파일을 하나로 합치거나, 라이브러리를 합친다.
컴파일러 과목에서는 2번 컴파일러로 컴파일이 되는 과정을 배울 수가 있다.
컴파일러의 기능
1. 고급언어를 직접 기계어로 변환
2. 자바의 경우 바이트 코드로 변환. 중간단계의 코드를 생성하고 이를 해석하여 실행
자바는 마이크로프로세서에서 실행되도록 개발되어서 이러한 과정을 거치는데
장점은 한번 컴파일된 바이트 코드는 다른 플랫폼에서 재컴파일 없이 실행 가능하다
단점은 바이트 코드를 해석해서 실행할 프로그램 구조가 필요하여 기계어 코드 실행보다는 느리다.
3. c/c++는 기계어 코드로 변환해 준다.
4. 마이크로 프로세서는 각각 다른 기계어 코드를 가지고 있어서, 다른 기계어 코드를 생성해야 한다.
마이크로프로세서에 맞는 컴파일러를 사용해야 함
컴파일러의 필수조건
1. 컴파일러는 번역(변환) 과정에서 프로그램의 뜻을 보존하여야 한다
즉, 프로그램의 의도와 의미가 그대로 보존되어야 한다는 의미이다.
2. 컴파일러는 입력으로 들어온 프로그램을 실용적으로 개선을 하여야 한다.
컴파일러의 구성요소
컴파일러는 밑에 그림처럼 이루어져 있는데
밑에 그림처럼 총 3가지의 analyzer와 1가지의 generator를 통하여 소스코드를 기계코드로 번역을 해주어 컴퓨터에서 실행가능한 컴파일러가 동작하는 것이다.
(컴파일러에 따라서는 선택적으로 구문 및 의미 분석과 코드 생성 단계 사이에 중간 코드를 생성하거나 코드를 최적화하기도 한다.) ex: java(바이트 코드로 변환. 중간단계의 코드를 생성하고 이를 해석하여 실행)
1. 어휘 분석기 (Lexical analysis) : 소스 코드를 정규 문법 (regular grammar)에 따라 토큰(token)의 집합으로 변환하는 어휘 분석 또는 스캐닝(scanning)이다. ->scanner 구현
그럼 analysis를 예시로 들어보자 'a', 'n', 'a', 'l', 'y' 's', 'i', 's'를 따로 놓으면 어떠한 의미도 없지만 "analysis" 한 개의 문자열로 합쳐서 본다면 "분석"이라는 의미를 가지게 된다.
어휘 분석 단계에서 검출되는 의미 있는 조각을 어휘항목 (lexeme)이라고 하며, 어휘 분석기는 검출된 어휘항목을 참조하여 토큰(token)을 생성한다.
example = analysis + lexical이라는 코드 한 줄이 있다고 가정을 하자
그럼 아래와 같은 token이 생성된다.
<id,1> <assign, NULL> <id,2> <plus, NULL> <id,3>
2. 구문 분석기 (Syntax analysis) : 소스 코드의 문법을 검사하는 구문 분석 또는 파싱 (parsing)이라 한다. ->paser 구현
어휘분석기(Lexical analysis)에서 생성한 token으로 문법 구조를 서술하는 추상 구문 트리를 생성한다.
문법 구조를 서술한다는 의미는 영어로 비유를 하자면 주어 동사 목적어 등을 구분 지어 서술하는 것과 비슷하다.
구문 분석기(Syntax analysis) 과정에서 (예외처리) 문법에 맞지 않는 소스 코드는 사용자에게 알리는 것, 즉 token 간의 관계가 올바르게 생성되었는지를 검사하는 것이다.
요약하자면 토큰 간의 관계를 서술하고, 소스 코드에 잘못된 토큰 간의 관계가 있는지를 검사하는 것이 구문 분석의 목적이다.
3. 의미 분석기 (Semantic analysis)
의미 분석 단계에서는 구문 트리와 심볼 테이블에 있는 정보를 이용하여 소스 코드가 언어 정의에 의미적으로 부합하는지를 검사한다. 의미 분석의 중요한 기능은 타입 검사 (type checking)이다. 컴파일러는 타입 검사를 수행하면서 피연산자가 연산자에 부합하는지를 검사한다. 의미 분석기는 정수와 문자열의 덧셈, 값을 0으로 나누는 행동 등과 같이 의미적으로 올바르지 않은 코드의 존재 유무를 검사한다. 예를 들어, "The earth revolves around the moon"라는 문장은 영어라는 인간언어에 존재하는 어휘항목만을 사용하였고, 주어와 동사가 일치하며 "revolve" 다음에 올 수 있는 "around"라는 부사까지 올바르게 사용하였지만, 의미적으로는 "지구가 달을 공전한다"는 틀린 문장이다.
이전의 어휘 분석기나 구문 분석기는 독립적으로 실행되어 출력을 만들어냈지만, 의미 분석기는 이러한 난해함 때문에 이전 단계에서 생성한 구문 트리와 심볼 테이블을 참조하면서 의미 분석을 수행해야 한다.
4. 코드 생성기 (Code generation): 목적 코드 생성, 기계어 번역의 경우 여러 라이브러리의 목적 코드를 묶어 하나의 실행파일을 생성한다.
요약하자면 이전 단계를 통해 분석된 소스 코드를 목표 기계에 맞는 어셈블리어나 기계어로 변환하는 단계이다.
번외)
상용 컴파일러에서는 의미 분석(Semantic analysis) 단계와 코드 생성(Code generation) 단계 중간에 코드 최적화 단계가 추가되는데, 코드 최적화 단계는 해당 언어의 성능이나 자원 소모를 결정짓는 중요한 단계이다.
그러나 코드 최적화 단계는 컴파일러보다는 컴퓨터 구조에 대한 지식을 요구하는 단계로써, 컴파일러의 원리를 배우는 입장에서는 코드 최적화 단계라는 것의 중요성과 이것이 의미 분석 단계와 코드 생성 단계 사이에 있다는 사실 정도만 인지하고 있어도 충분하다.
앞에까지는 전반적인 흐름이라면 아래는 각 단계마다 자세한 방법을 서론 할 것이다.
1. 어휘 분석 (Lexical analysis) : 컴파일러의 첫 번째 단계는 소스 코드를 정규 문법 (regular grammar)에 따라 토큰 (token)으로 분류하는 어휘 분석 또는 스캐닝 (scanning)이다.
- 어휘항목 (lexeme): 소스 코드에 존재하는 의미 있는 문자열, 식별자, 숫자, 키워드 등을 의미한다.
- 패턴 (pattern): 토큰이 어휘항목을 서술하는 규칙으로써, 정규문법에 따라 표현된다.
- 토큰 (token): 토큰이름과 속성값으로 구성되는 데이터쌍으로써, 각 토큰은 토큰의 패턴에 부합하는 어휘항목을 갖는다.
어휘 오류라는 것은 소스 코드상에서 정의되지 않은 어휘항목이 발견되었을 때 발생하는 오류이다. 그러나 어휘 분석기가 독립적으로 어휘 오류를 검출하는 것은 매우 어렵거나 많은 비용이 소모된다. 예를 들어, 아래와 같은 코드가 있다.
if2(var == 5)
이 코드에서 어휘 분석기가 if2를 if의 잘못된 입력인지, if2라는 함수를 호출하는 구문인지 판단하는 것은 심볼 테이블을 참조해야 가능하다. 그렇기 때문에 어휘 분석기가 독립적으로 어휘 오류를 검출하기보다는 어휘 분석기는 심볼 테이블을 생성하고, 어휘 분석의 다음 단계인 구문 분석 (syntax analysis)에서 구문 분석기가 어휘 오류를 검출하는 것이 더욱 일반적이다.
정규 표현식 (Regular expression)
정규 표현식은 수학적으로 정의된 기호와 연산을 이용하여 언어를 귀납적으로 정의하기 위한 방법이다. 정규 표현식에서 정의되는 연산은 접합, 클린 클로저, OR이 있으며, 피연산자는 기호의 유한 집합인 알파벳이나 기호가 된다. 접합 연산의 기호는 따로 표기하지 않으며, 클린 클로저 연산은 *, OR 연산은 |로 표기한다. 연산자 우선순위는 클린 클로저(*)가 가장 높으며, 그 다음으로 접합 연산, OR연산 순서이다. C언어에서 정의된 식별자의 집합을 정규 표현식으로 서술하면, 아래와 같은 정규 표현식으로 정의된다.
정규 정의 (Regular definition)
위의 정의에서 ri는 어떠한 기호의 집합 L과 di를 합집합 하여 생성된 집합에서 생성될 수 있는 정규식 중 하나이고, di는 L에 없는 새로운 기호이며 각각의 di는 서로 다르다. 위에서 언급한 C언어의 식별자는 아래와 같은 정규 정의에 의해 서술된다.
2. 구문분석 (Syntax analysis) : 토큰 스트림으로부터 파스 트리 (parse tree)를 생성한다.
보편적 (universal), 하향식 (top-down), 상향식 (bottom-up)이 있다. 보편적 파싱 방법은 어떠한 문법도 파싱 할 수 있지만, 파싱 과정이 매우 비효율적이기 때문에 상용 컴파일러에는 적용될 수 없다. 따라서, 컴파일러에서는 하향식과 상향식 파서가 이용되며, 주로 상향식 파서가 많이 이용된다.
우리가 영어 문장에서 문법적 오류를 검출하기 위해서는 영어 문법을 이해하고 있어야 하는 것이 당연하듯이 파서 또한 프로그래밍 언어 정의에 이용된 문법을 이해하고 있어야 한다. 현재까지 개발된 있는 대부분의 프로그래밍 언어는 문맥 자유 문법을 기반으로 정의되어 있다. 문맥 자유 문법은 촘스키 위계 (Chomsky hierarchy)의 type-2에 해당하는 문법이다.
문맥 자유 문법 G는 G=(V,T,P,S)의 순서쌍으로 정의되며, 각 원소의 의미는 아래와 같다.
- V: nonterminal의 유한집합으로써 nonterminal은 언어에 대한 계층적 구조를 부여하는 역할을 한다.
- T: terminal의 유한집합으로써 terminal은 더 이상 다른 terminal이나 nonterminal로 유도가 불가능하다. V와 T는 서로소이다.
- P: 생성규칙 (production)의 유한집합. 문법의 생성규칙은 nonterminal과 terminal들의 조합되어 문자열을 생성할 수 있는 방법을 명시한다.
- S: 문법에서는 한 개의 nonterminal을 시작 기호 (start symbol)로 갖는다. S는 해당 문법의 시작 기호를 나타내며, 문법은 항상 시작 기호로부터 시작된다.
유도 (Derivation) :구문 분석에서 유도라는 것은 문법의 생성규칙에 따라 특정한 문자열을 도출해 나가는 과정이다
파스 트리 (Parse tree) : 파서의 주목적은 소스 코드라는 문자열에서 파스 트리를 생성하는 것이다. 파스 트리를 생성하는 것은 문법의 생성규칙과 유도를 통해 서술될 수 있다.
모호성 (ambiguity) : 어떤 문자열에 대해 두 개 이상의 서로 다른 파스 트리를 생성하는 문법을 "모호하다"라고 한다.
즉, 모호한 문법은 동일한 문자열에 대해서 2개 이상의 최좌단 유도나 2개 이상의 최우단 유도를 생성하는 문법이다. 예를 들어, 아래와 같은 문법이 있는 경우,
문자열 id + id * id이 입력된다고 가정하면, 해당 문법은 동일한 문자열에 대해 아래의 [그림 3]과 같은 두 개의 서로 다른 파스 트리를 생성한다.
[그림 3] 동일 문자열에 대한 두 개의 서로 다른 파스 트리 (parse tree)
따라서, 위의 문법은 모호하다.
대부분의 파서에서 문법은 모호하지 않은 것이 바람직하다. 문법이 모호할 경우에는 파서가 어떠한 생성규칙을 선택할지를 유일하게 결정할 수 없기 때문이다. 문법을 정의할 때는 모호한 문법이 되지 않도록 하는 것이 중요하며, 좌재귀 제거와 좌인수분해 등 문법의 모호성을 제거하기 위한 다양한 방법들이 있다.
하향식 파싱 (Top-down parsing)
재귀적 하강 파싱 (Recursive descent parsing)
LL(1) 파서
상향식 파싱 (bottom-up parsing)
이동-감축 파싱 (shift-reduce parsing)
단순 LR 파싱 (Simple LR parsing, SLR parsing)