[Compiler] 2. 간단한 컴파일러의 구조

1. 컴파일러의 논리적 구조

1. 개요

1. 문장이 어떤 요소로 구성되어 있는지 파악하기 위해 문장에 사용된 단어를 검사한다.
   • I am a boy라는 문장으로 예를 들면 I, am, a, boy 라는 네 가지 단어가 사용된 것을 알 수 있으며 이를 알아내는 것을 어휘 분석이라고 한다.
2. I, am, a, boy 가 각각 8품사인 명사, 대명사, 동사, 형용사, 부사, 전치사, 접속사, 감탄사 중 어디에 속하는지 확인하고 문장의 5대 요소인 주어, 동사, 목적어, 보어, 수식어 등으로 구분할 것이다.
   • 그리고 주어+동사, 주어+동사+보어, 주어+동사+목적어 등 문장의 형식을 검사하여 이 문장이 주어+동사+보어로 구성되었다는 것을 알아낸다. 이렇게 문장의 형식을 알아내는 것을 구문 분석이라고 한다.
3. 단어 대 단어의 번역이 아니라 한글 문법에 맞게 번역해야 하는에 이를 의미 분석이라고 한다.
4. 마지막으로 한글 단어 가운데 더 알맞은 단어로 번역하는 코드 최적화를 거쳐 한글로 번역한다.

💡 컴파일러도 영어 문장을 한글로 번역하는 것과 비슷한 단계를 거쳐 번역한다.

 

C언어를 기계어로 번역하는 과정은 다음과 같다.

1. 주어진 문장이 어떤 단어들을 포함하고 있는지 확인한다.
   • C언어에서 사용하는 의미 있는 단어를 토큰(token)이라고 한다.
2. C언어에서 어떤 토큰이 사용되었는지 구분한다. → 어휘 분석
3. 문법을 보면서 토큰들이 문법에 맞는지 검사한다. → 구문 분석
4. 형식 언어는 의미를 가지고 있지 않기 때문에 주로 타입을 검사한다. → 의미 분석
5. 의미 분석으로 생성된 코드의 실행 시간을 줄이거나 기억 장소를 줄이기 위한 코드 최적화를 진행한다.
6. 목적 기계의 특성을 고려하여 목적 코드를 생성한다.

전단부

• 1~4단계를 의미한다.
• 목적 기계에 독립적인 부분으로 목적 기계에 관계없이 소스 프로그램을 분석하고 중간 코드를 생성한다.
• 문법 이론에 의해 잘 정립되어 있다.

 

후단부

• 5~6단계를 의미한다.
• 목적 기계에 의존적인 부분으로 전단부에서 생성한 중간 코드를 특정 기계에 대한 목적 코드로 번역한다.
• 아직 연구가 진행 중이다.

2. 논리적 구조

• 아주 간단한 C 문법

<Sub C> ::= <assign-st>
<assign-st> ::= <lhs> = <exp>;
<lhs> ::= <variable>
<exp> ::= <exp> + <term> | <exp> - <term> | <term>
<term> ::= <term> * <factor> | <term> / <factor> | <factor>
<factor> ::= <variable> | <number> | (<exp>)
<variable> ::= <ident>
<ident> ::= (<letter> | _){<letter> | <digit> | _}
<number> ::= {<digit>}
<letter> ::= a | ... | z
<digit> ::= 0 | 1 | ... | 9

2.1 어휘 분석

• 원시 프로그램을 읽어 토큰이라는 의미 있는 문법적 단위(syntactic entity)로 분리라고 토큰 스트림을 생성하는 단계이다.
• 어휘 분석을 담당하는 도구를 어휘 분석기(lexical analyzer) 또는 스캐너(scanner)라고 부른다.
• 일반적인 프로그래밍 언어에서 사용하는 토큰
  • if, for, while 과 같은 예약어
  • 3, 2.5와 같은 상수
  • +, -, *, /, = 와 같은 연산자
  • 프로그래머가 정의한 식별자
  • 괄호나 쉼표, 세미콜론과 같은 구분자 등
• 토큰에 대한 표현은 (토큰 번호, 토큰 값)의 순서쌍으로 표현함
• 주석, 공백 등의 처리도 이 단계에서 처리함

2.2 구문 분석

• 어휘 분석 단계의 결과인 토큰 스트림을 받아 주어진 문법에 맞는지 검사하며, 주어진 문법에 맞는 문장의 경우 그 문장에 대한 파스 트리(parse tree)를 출력하고 올바르지 않은 문장의 경우 에러 메시지를 출력하는 과정이다.
• 이처럼 구문 분석을 담당하는 도구를 구문 분석기(syntax analyzer) 또는 파서(parser)라고 한다.
• 파스 트리는 토큰을 터미널 노드로 하는 트리이다.

2.3 의미 분석

• 원시 프로그램의 의미적 오류를 검사하고 계속되는 중간 코드 생성 단계를 위한 자료형 정보를 수집하여 구문 트리나 기호표에 저장하는 단계이다.
• 이러한 일을 담당하는 도구를 의미 분석기(semantic analyzer)라고 한다.
• 자연 언어에서는 의미 분석이 의미가 있지만 형식 언어는 의미를 가지고 있지 않으므로 의미 분석이 크게 중요하지 않다.
• 따라서 의미 분석에서 가장 중요한 일 중 하나는 형 검사(type checking)이다.
• 자료형 검사 - 각 연산자들이 원시 프로그램의 규칙에 의해 허용된 피연산자를 가졌는지를 검사하는 작업
  • 일반적 연산
    • 피연산자와 연산 결과의 타입이 변할 수 있는 연산
  • 형 고정 연산
    • 피연산자와 연산 결과의 형이 고정되어 있는 연산
  • a + b라는 산술식이 있고 a는 int, b는 float이라고 했을 때 연산을 비교하면 다음과 같다.
    • 일반적 연산 → a나 b의 형을 변환하여 연산 허용
    • 형 고정 연산 → 에러 메시지 출력
  • 형 변환 - 주어진 자료형의 값을 다른 자료형의 값으로 변환하는 것
    • 명시적 형 변환
      • 프로그래머가 명시적으로 형 변환을 요구하는 방법
      • 명시적으로 요구한 형 변환을 캐스트 연산이라고 부름
    • 암시적 형 변환
      • 시스템에서 자동으로 형을 변환하는 방법
      • 시스템에서 자동으로 형을 변환하는 것을 자동 변환 또는 강제 형 변환이라고 부름

2.4 중간 코드 생성

• 구문 분석 단계에서 만들어진 구문 트리를 이용하여 코드를 생성하거나 한 문법 규칙이 감축될 때마다 구문 지시적 번역(syntax-directed translation)이 이루어지는 단계이다.
• 구문 지시적 번역은 문법 규칙이 감축될 때 그 규칙에 알맞은 코드 생성 루틴을 호출함으로써 중간 코드를 생성한다.
• 중간 코드 생성을 담당하는 도구를 중간 코드 생성기(intermediate code generator)라고 부른다.
• 중간 코드를 생성하기 위해서는 중간 언어가 필요하며 역폴란드식 표기법, 폴란드식 표기법이 주로 사용된다.

2.5 코드 최적화

• 같은 기능을 유지하면서 코드를 더 효율적으로 만들어 코드 수행 시 메모리나 수행 시간을 절약하기 위한 단계이다.
• 선택적인 단계로서 생략되는 경우도 있지만 요즘엔 RISC와 같은 컴퓨터 구조의 특성을 활용하기 위해 최적화 단계를 많이 사용하고 있다.
• 최적화 방법
  • 프로그램 영역으로 구분한 경우
    • 지역 최적화
    • 전역 최적화
    • 프로시저 간 최적화
  • 기능적인 측면으로 구분한 경우
    • 실행시간 최적화
    • 메모리 최적화
  • 최적화가 많이 이뤄지는 부분으로 구분한 경우
    • 루프 최적화
    • 단일문 최적화
  • 목적 기계의 의존성에 따라 구분한 경우
    • 기계 독립 최적화
    • 기계 종속 최적화
• 지역 최적화
  • 부분적인 관점에서 일련의 비효율적인 코드들을 구분해내고 더 효율적인 코드로 수정하는 방법
  • 코드가 분기해 나가거나 분기해 들어오는 부분이 없는 기본 블록 내에서 최적화를 수행하기 때문에 상대적으로 쉽게 수행할 수 있다.
  • 기본 블록은 어떠한 제어 흐름도 가지지 않기 때문에 분석이 거의 필요 없다.
  • 공통 부분식 제거, 복사 전파, 죽은 코드 제거, 상수 폴딩, 대수학적 간소화 등
• 전역 최적화
  • 기본 블록을 넘어서지만 하나의 프로시저 내에서 일련의 비효율적인 코드들을 구분해내고 더 효율적인 코드를 만들어내는 방법
  • 지역 최적화보다 더 많은 정보와 비용을 요구해서 수행하기 어렵지만 지역 최적화에 비해 효과가 훨씬 좋다.
  • 일반적으로 자료 흐름 분석 기법이 사용된다.
    • 프로그램 안에서 사용되는 변수의 경로에 관한 정보를 수집해서 처리하는 과정
  • 전역적 공통 부분식 제거, 상수 폴딩, 도달될 수 없는 코드의 제거 등
  • 2.6 목적 코드 생성
  • 연산을 수행할 레지스터를 선택하거나 자료에 메모리의 위치를 정해주며 실제로 목적 기계에 대한 코드를 생성하는 단계

2. 컴파일러의 물리적 구조

• 구현 방법
  • One pass
    • 초창기 컴파일러를 만들 때 사용했던 방법으로 컴파일러의 논리적 단계를 하나의 패스로 구현하는 방법
  • Two pass
    • 중간 코드를 기점으로 앞부분을 전단부, 뒷부분을 후단부로 나누어 구성하는 방법
• 고려 사항
  • 컴파일러의 논리적 구조
  • 컴퓨터 자원
  • 사용자의 요구 사항
  • 개발 인적 자원