0. 개요
🤔 이후 강의들을 듣는 데 필요한 최소한 Compile의 전반적인 과정을 알아보자.
1. Compile 전반적인 과정
* 일련의 phase로 구성되어 있다.
- Front-End : 의미분석까지의 단계는 소스 프로그램의 의미를 이해하고 분석하는 역할을 한다.
- Back-End : 나머지 단계는 중간 형태를 사용하여 동일한 target program을 생성하는 역할을 한다.
- 궁극적으로 token화를 하기 위한 것이다.
우리가 흔히 개발에서 말하는 front-end, back-end와 같은 의미로 쓰이는 것은 아니다.
Compiler의 앞면과 뒷면이라고 이해하면 편할 것이다.
cf) interpreter는 compiler의 frontend 과정은 공유하지만,
compiler와 같이 중간 형태를 직접 해석하여 기계어로 번역하지 않는다.
중간 형태를 실행하는 방식으로 프로그램을 실행한다.
2. Pass란?
"패스(pass)"는 컴파일 과정의 일련의 단계 중 하나이며, 나머지 컴파일 과정과 이어져 실행된다.
그냥 쉽게 말해서 Compile을 몇 번 하느냐에 따라
one pass compiler / two pass compiler 등으로 나뉜다.
pass를 사용하는 이유는 다음과 같다. :
- pass를 사용하면 여러 기계어(target language)에 대한 컴파일러에서 프론트 엔드를 공유할 수 있다.
- 백 엔드 측은 컴파일러에 의해 하나 이상의 소스 코드를 공유할 수 있다.
ex. Gcc는 프런트 엔드측이 언어가 서로 달라도, 뒷단을 공유할 수 있다. - 메모리 사용량 감소
3. 문자열 분석 및 구문 분석 (Lexical and Syntax Analysis)
3-1. Scanner
스캐너(Scanner) 또는 렉서(Lexical Analysis)로 불린다.
스캐너는 문자들('i', 'n', 't', ' ', 'm', 'a', 'i', 'n', '(', ')', ...)을 읽고, 이를 프로그램의 가장 작은 의미 있는 단위인 "토큰"으로 그룹화한다.
=> Token화
// 식별자 ( 함수, 변수 ) 등은 이후에 체크하는 과정이 필요하다.
Scanner의 목적은 다음과 같다.
1. parser의 작업을 단순화한다. 입력의 크기를 줄여 parser의 처리를 쉽게 만든다.
2. 공백, 주석 제거
3. 토큰에 행 및 열 번호를 태그하여 이후 단계에서 좋은 진단 정보를 생성하기 쉽도록 한다.
(debugging을 위한 줄 numbering)
3-2. Parsing
구문 분석(Parser)은 token을 a parse tree로 구성하여 더 높은 수준의 구조(서브루틴 등)를 그 구성 요소로 표현한다.
트리의 루트는 "program"이며, 왼쪽에서 오른쪽으로 token들을 leaf로 가진다.
이 트리는 토큰들이 유효한 프로그램을 만들기 위해 어떻게 결합되는지를 보여준다.
이 구조는 Context-Free Grammar 라고 알려진 일련의 잠재적인 재귀 규칙에 의존한다.
* Context-Free Grammar
: 언어의 Syntax 문법을 정리해 놓은 것.
3-3. Scanning과 Passing 과정에서 Compiler or Interpreter가 하는 일
- 프로그램의 모든 토큰이 올바르게 형성되었는지를 검사한다.
ex. "123abc"나 "$@foo"와 같이 형식에 맞지 않는 토큰이 발견되면, scanner는 오류 메시지를 생성한다. - 토큰의 순서가 문법에 따라 정의된 구문에 부합하는지를 확인한다.
ex. "A = X Y Z"와 같이 문법적으로 올바르지 않은 토큰 순서가 발견되면 parser는 오류 메시지를 생성한다.
이러한 검사를 통해 컴파일러나 인터프리터는 프로그램의 토큰이 올바르게 형성되고, 문법적으로 유효한 순서로 배치되는지 확인한다. 만약 형식에 맞지 않는 토큰이나 문법적으로 잘못된 토큰 순서가 발견되면 컴파일러나 인터프리터는 오류 메시지를 생성하여 사용자에게 알려주어 디버깅과 수정을 도울 수 있다.
4. Semantic Analysis(의미 분석)
의미 분석은 프로그램의 의미를 파악하는 과정이다.
- 동일한 식별자의 의미를 파악하고, 변수, 타입 등의 올바른 사용을 검증한다.
// 식별자 ( 함수, 변수 ) 등은 이후에 체크하는 과정이 필요하다. -> 이 과정에서 체크한다.
논리적 오류를 검증하는 것. - 식별자와 표현식의 유형을 추적하여, 일관성을 유지한다.
- symbol table을 사용하여 Context-Free Grammer나 Parse-Tree로 잡아내지 못한 다양한 규칙을 적용시킨다.
아래는 예시이다.
X = "a"
Y = 3
A = X/Y // 문자열을 상수로 나누어 Error 발생
4-1. C언어에서의 의미 분석기
- 모든 식별자는 사용되기 전에 선언되어야 한다.
- 적절하지 않은 문맥에서 식별자를 사용하지 않아야 한다.
ex. 정수를 subroutine으로 호출하거나 문자열을 정수로 나누는 등 - 서브루틴 호출은 올바른 개수와 유형의 인수를 제공해야한다.
- 스위치 문법의 분기 lable ( Case 1 : 과 같은 것 ) 은 고유한 상수여야 한다.
- non-void return 타입을 가진 함수는 명시적으로 값을 반환해야 한다.
그러나 모든 의미론적인 규칙을 모두 확인할 수는 없다.
C언어에서 수행되는 것은 "Static Semantic analysis"이며, 컴파일 타임에 이해할 수 있는 의미이다.
다른 사항들은 실행 시간(Run Time)이 될 때까지 확인할 수 없다.
(물론 아예 동적 check (Run을 돌린 후에 결정되는 것들)이 없는 것은 아니다.)
#. 정적 의미 분석, 동적 의미 분석
Static Semantic analyis : Compile Time에 문법, 문법 등을 검증
Dynamic Semantic analyis : Run Time에 변수 초기화, 포인터 유효값, 배열 overflow, 타입 overflow 등을 검증 ex. Java
배열 overflow의 대표적인 예시 : 배열 bound가 넘쳤는지.. 이는 실행 중에 확인한다. // C 언어는 이런 검증이 거의 없다.
4-2. 다른 언어의 Compiler에서는?
많은 컴파일러에서는 주석이 달린 구문 트리가 프론트 엔드에서 백 엔드로 전달되는 중간 형태(intermediate form)로 사용된다.
다른 컴파일러에서는 의미론적 분석이 트리를 순회 <중간 재검토>하면서(일반적으로 단일 패스) 다른 중간 형태를 생성하는 것으로 끝난다.
이의 일반적인 형태 중 하나는 제어 흐름 그래프(control flow graph)이다.
이 그래프의 노드는 간단한 이상적인 머신의 어셈블리 언어 조각과 유사한 구조를 가진다.
5. Target Code Generation의 역할
이는 중간 형태(the intermediate form)를 목표 언어(target language)로 변환시키는 역할을 한다.
- 변수에 위치를 할당하기 위해 심볼 테이블을 탐색한다.
- 프로그램의 중간 표현을 탐색하면서 변수 참조에 대한 로드(load)와 저장(store)을 생성한다.
- 적절한 산술 연산, 조건 검사 및 분기 명령을 생성한다.
또한, 코드 생성기는 가끔 symbolt table을 저장하여, 나중에 심볼릭 디버거가 사용할 수 있도록 해준다.
이는 대상 코드의 실행되지 않는 부분에 숨겨져 포함되어 저장된다. 마치 자료구조처럼 사용된다.
6. 최적화(optional)의 역할
코드 개선은 컴파일 과정의 선택적인 과정이지만, 요즘은 거의 다 포함되어 있다.
목표 언어로 변환된 코드를 최적화해준다.
효율성 UP
예시 :
- 변수를 레지스터에 저장
- 명령어를 재배열하여 no-ops(아무 동작을 하지 않는 명령어) 제거
- 최신 프로세서의 다중 파이프라인을 활용
