컴파일러 개요

 

 

Chapter 5. 컴파일러 개요

“컴파일러 일반적 구성”

Compiler: 컴파일러는 특정 고급 프로그래밍 언어로 작성된 프로그램을 특정 대상 컴퓨터에서 실행 가능한 코드로 변환하는 컴퓨터 프로그램으로 작성된 프로그램을 변환하는 컴퓨터 프로그램이다.

.cpp → 컴파일러 → .obj → 링커 → .exe

: CPU에 따라 사용하는 기계어가 다르기 때문에 컴파일러에서는 기계 독립적인 .obj 파일까지만 만든다.

 

Compiler Structure

• Front-end: 언어 의존적인 부분 (기계 독립적)
• Back-end: 기계 의존적

(Front-end Part)

1. Lexical Analyzer (Scanner)

컴파일러 내에서 효율적이며 다루기 쉬운 정수로 바꿈

소스코드를 읽어 문장을 토큰으로 나누고 토큰 스트림(토큰 번호와 토큰 필드)을 아웃풋으로 함

• token number: 예약어, 변수 등과 같은 값을 문자열보다 정수로 표현하는 것이 효율적
• token 표현: <Token number, Token value>와 같이 순서쌍으로 표현

예시) if X < Y then X := 10;

Token	if	X	<	Y	then	X	:=	10	;
Token 번호	3	1	4	1	5	1	6	2	7
Token 표현	<3, 0>	<1, X>	<4, 0>	<1, Y>	<5, 0>	<1, X>	<6, 0>	<2, 10>	<7, 0>

변수는 같지만 표현이 달라지기 때문에 Token 번호로 구분하지 않고 모든 변수에 1을 부여

⇒ 순서쌍에 표현된 토큰 필드를 그대로 쓰는 것이 아니라 Symbol table에 변수를 저장하고 인덱스 번호로 표현

 

2. Syntax Analyzer (Parser)
   • 기능: 문법 검사, 트리 생성
   •  출력
     • 잘못된 문장: 에러 메시지 출력
     • 정확한 문장: 프로그램 구조를 트리로 바꿔 출력

3. Intermediate Code Generator (중간코드 생성기)
• 기능: 의미검사, 중간코드 생성
• 의미 검사: 의미 분석은 정확성으로도 10%밖에 차지하지 않으며 정확하지 않기 때문에 따로 구성하지 않고 중간 코드 생성에 기능 중 일부로 구성됨
• 예) if (a > 10) a = 1.0;

⇒ a가 int type인 경우 semantic error가 생김

(Back-end Part)

4. Code Optimizer (코드 최적화기): 비효율적인 코드를 구분해 더 효율적인 코드로 바꿈 (선택적 페이즈)
   • 최적화의 뜻 (meaning of optimization)
   • 주요 파트: 실행시간 최적화 (improve running time)
   • 작은 파트: 코드 사이즈 줄이기 (reduce code size)

ex) LDC R1, 1
LDC R1, 1(x)
하드웨어가 고사양이 아닌 시기에 중요했었지만 지금은 하드웨어 성능이 좋아져 선택사항이 됨

최적화 기준 (criteria for optimization)

• 최적화 후 의미 유지
• 평균 속도 향상
• 노력의 가치가 있어야 함

• Local optimization / Global optimization
  • Local optimization프로그램 소스 중 일부 작은 것에 대한 최적화
  • ex) a = 10 + 3 + b → a = 13 + b
    c = c + 1 ⇒ c++
  • Global optimization프로그램 전체에 대한 최적화
  • ex) 소스코드 안의 함수에 대해 만들어지고 한번도 사용되지 않은 함수를 제거

5. Target Code Generator (목적코드 생성기)

중간 코드로부터 기계 명령어(machine instruction)를 생성

• 코드 생성기 역할
  • instruction selection & generation — 기계어 명령 선택 & 생성
  • register management — 레지스터 관리
  • storage allocation — 메모리 관리
  • code optimization (Machine-dependent optimization) — 코드 최적화 (기계 종속적 최적화)

⇒ 앞 단계 code optimizer에서는 달리 CPU와 더 연관된 기계 종속적 최적화 진행

 

Error Recovery

• Error Recovery: 에러가 다른 문장에 영향을 미치지 않도록 수정
• Error repair: 에러가 발생하면 복구하는 것
• Error handling
  • Error detection (에러 감지)
  • Error recovery (에러 회복)
  • Error reporting (에러 보고)
  • Error repair (에러 수정)
• 에러 종류
  • Syntax Error (문법 에러)
  • Semantic Error (의미 에러)
  • Run-time Error (런타임 에러) 문법 에러는 비교적 발견하기 쉽고, 고치지 쉽지만 의미 에러와 런타임 에러는 고치기 쉽지 않음

 

“컴파일러 자동화 도구”

Compiler Generating Tools (Compiler – Compiler)

  언어와 기계가 발전할수록 많은 컴파일러가 필요

        ⇒ 새로운 언어를 개발하는 이유: 컴퓨터의 응용 분야가 넘어지기 때문

  N개의 언어를 M개의 컴퓨터에서 구현하기 위해서는 (N x M)개의 컴파일러가 필요

 

Compiler – compiler Model

Machine architecture와 programming language의 발전에 따라 automatic compiler generation이 연구됨

• Language Description : grammar theory(문법 이론)를 이용

• Machine Description : 정형화가 이루어져있지 않은 상태

1. LEX (Scanner 생성기)
   • 1975년 M.E.Lesk가 고안함
   • 입력 스트림에서 정규표현(RE)으로 기술된 토큰들을 찾아내는 프로그램을 작성하는데 유용한 도구
2. Parser Generator (PGS: Parser Generating System)
   • 종류
     • Stanford PGS
     • Wisconsin PGS
     • YACC(Yet Another Compiler Compiler): 가장 유명하며 많이 쓰임
3. Automatic Code Generation
   • 3가지 측면
     • Machine Description: ISP, ISPS, HDL
     • Intermediate Language (중간 언어)
     • Code generating algorithm (코드 생성 알고리즘)
   • CGA(code generation Automata)
     • Pattern matching code generation (패턴매칭 코드 생성)
     • Table driven code generation
4. Compiler – Compiler System
   • PQCC (Production Quality Compiler – Compiler System)
     • W.A. Wulf (Carnegie–Mellon University)
     • input: language description, target machine description
     • output: PQC, table
     • Pattern Matching Code Generation에 의해 code를 생성
   • ACK (Amsterdam Compiler Kit)
     • Vrije대학의 Andrew S. Tanenbaum을 중심으로 개발된 Compiler의 Back-End 자동화 도구
     • UNCOL개념에서 출발 (N*M ⇒ N + M)
     • EM이라는 Abstract Machine Code를 중간 언어로 사용
     • Portable Compiler를 만들기에 편리

1. •  

 

“어휘 분석 (Lexical Analysis)”

Lexical Analysis: 컴파일러가 특정 문자열을 개별 토큰으로 그룹화하는 프로세스

 - 토큰: 문법적으로 의미있는 최소단위

• 토큰 넘버: 문자열 처리의 효율성을 위한 정수
• 토큰 필드(값): 숫자 값, 문자열 

 - Special form (Language designer)

• Keyword(키워드): const, if, else, int, ...
• Operator symbol(연산자): +, -, *, /, ++, --, ...
• Delimiters(구분자): ;, (, ), [, ], ...

ex)

if	else	for	…
<1, 0>	<2, 0>	<3, 0>	…
+	-	*	…
<11, 0>	<12, 0>	<13, 0>	…
;	,	(	…
<21, 0>	<22, 0>	<23, 0>	…

: 키워드, 연산자, 구분자는 각각 다른 Token number를 가지며 Token value는 갖지 않는다.

 

 - General form (programmer)

• identifier: stk, ptr, sum, …
• constant: 526, 3.0, 0.1234e-10, ‘c’, “string”, …

: identifier를 나타내는 Token number = n, constant를 나타내는 Token number = m이라고 하면 모든 identifier과 constant는 Token number로 n과 m을 가지며 Token value로 구분한다.

 

Symbol Table

: 어휘분석과 구문분석 시 식별자에 관한 정보 수집, 저장

  Semantic analysis와 Code generation시에 사용

  name + attributes로 구성

  Hashed Symbol Table로 되어있음

 

Token 인식

• Character set
  • letter → a | b | c | … | z | A | B | … | Z ⇒ l
  • digit  → 0 | 1 | 2 | … | 9 ⇒ d
  • special_char → + | - | * | / | …
• Recognizing of Identifier (: 세 가지 상태는 서로 변환 가능)
  • Finite Automata: 유한한 상태를 자동으로 변경
  • Regular Grammar
  • Regular Expression

 

Chomsky hierarchy

Type 0	제한 없는 문법(unrestricted Grammar)     → 생성규칙 표현에 대한 제약이 없음
Type 1	CSG(Context Sensitive Grammar) - deQueue를 사용해 구현 제약사항: ex) = 의 길이를 나타냄     → 구현의 어려움 (deQueue를 만들기 어려움)
Type 2	CFG(Context Free Grammar) - stack을 사용해 구현 제약사항: =1 이면서 (Type 1에서 의 길이에 대한 제약이 더해짐) stack anbn: a가 n번 나오면 b가 n번 나오는 것을 셀때 사용 ex) ()의 짝을 셀 때  BUT  anbncn에 대해서는 표현할 수 없음 ex) if-then, else (그래서 else 생략 가능) deQueue를 사용해서 표현 가능하지만 deQueue의 구현이 어려움	⇒ Parser를 만들 때 사용
Type 3	RG(Regular Grammar) AB : B는 1) Terminal Symbol              2) Terminal S + non-terminal S 표현 순서에 대한 제약이 생김 ex) AaX, BYb: RG가 아님     AaX, BbY: RG	⇒ Scanner를 만들 때 사용