Lec01. Overview of Compilers (1주차 1강)

1주차 1강 - 9월 2일 월요일, Overview of Compilers

* 제 개인 공부용으로 정리하는 글입니다. 정확한 내용은 꼭 본인이 공부하는 교재를 확인하시길 바랍니다.

 

1. Compiler: Programing Langauge Translator

- Software system은 source language를 target language로 변환함

- source lang: high-level language(C, Java)

- target lang: low-level machine lang(x86, MIPS)

- 인간이 알아들을 수 있는 하이레벨 언어로 코드를 작성하고, 컴파일 과정에서 기계가 알아들을 수 있는 로우레벨로 전환

 

- Transpiler: source-to-source compiler는 source와 target lang이 둘 다 high level language임

   * 수업 외) 검색하니까 토스 테크 블로그 글이 나와서 첨부 https://toss.tech/article/27750

Transpiler, “사용”말고 “활용”하기

   Transpiler는 JS의 ES6 문법을 ES5로 변환하는 등 코드를 변환하는 도구를 의미한다고 함

   궁금한 건, 아래의 기능도 Transpiler일까?(잘 모름)

    Android Studio에서 Java 코드가 인식됐는데, 파일 확장자가 kt면 Kotlin으로 전환하겠냐는 팝업이 뜨는데

    확인 버튼을 누르면 Java <-> Kotlin 언어 사이에 코드 변환을 지원한다

 

2. Structure of Modern Compiler

- Front-end: source program을 이해하고 IR(Intermediate Representation)으로 변환한다

  *수업 외) Intermediate Representation이란? 컴파일러의 전반부와 후반부를 연결해주는 중간 형태의 코드

   최적화나 변환을 위해 작성된 원본 코드의 형태를 변형한 결과...라고 해석된다(아래 프론트엔드 파트에서 더 설명)

- Middle-end: IR program을 가져와서 efficiency(효율성), energy comsumption(에너지 소비) 측면에서 optimizes(최적화)

- Back-end: IR program을 machine-code로 변환함

 

2.1. Front-End 개요

- Lexical Analyzer: character stream(source code)를 token stream으로 변환

- Syntax Analyzer: token stream을 syntax tree로 변환

- Sementic Analyzer: source program이 semantic error가 있는지 아닌지 확인

- IR Translator: syntax tree를 IR로 변환

 

(1) Lexical Analyzer (Lexer, Tokenizer, Scanner)

- lexer는 source program의 lexical structure를 분석한다

- Input: character stream

  pos = init + rate * 10

- Interim Result: lexemes의 sequence ("meaningful(의미있는)" character의 sequence)

  *수업 외) lexical analysis(어휘 분석)을 해서 의미있는 단어 단위로 끊어서 Token을 만든다

  [pos, =, init, +, rate, *, 10]

- Output: token의 sequence

   (token name(토큰 종류), optimal attribute-value(토큰에 대한 속성))쌍 형태

  [(ID, pos), ASSIGN, (ID, init), PLUS, (ID, rate), MULT, (NUM, 10)]

   -> ID, pos: ID 속성이고, 이 ID의 최적 속성 값이 pos라는 뜻

 

- lexer는 invalid token을 가진 프로그램을 reject함

  그림 예시는 C 언어의 변수명 정규 표현식인데, [A-Za-z_]([A-Za-z_]+[0-9])* 이는 숫자로 시작할 수 없다는 뜻

 그래서 12xyz는 숫자로 시작하기 때문에 Lexing Error(어휘 오류)가 발생함

 

(2) Syntax Analyzer (Parser)

- parser는 source program의 grammatical structure를 정의한다

- Input: token의 sequecne(Lexical Anaylzer의 result)

   [(ID, pos), ASSIGN, (ID, init), PLUS, (ID, rate), MULT, (NUM, 10)]

- Output: syntax tree (source program의 grammatical structure)

 -> 문법에 따라 tree를 그린다

 

- parser는 syntatically wrong 프로그램을 reject한다 (program이 context-free-grammer로 표시될 수 없는 경우)

  *수업 외) 오토마타 내용을 가져오자.

   Context-free-grammer란 문법 G에서 모든 생성 규칙이 A->x의 형태를 가질 때를 말한다.

   즉 왼쪽 항에는 하나의 변수, 오른쪽 항에는 Symbol들과 Varialbe로 구성되 String이 위치하는 것을 말함.

   변수 하나를 String으로 번역할 수 있어야 함

   -> 근데 이 문법을 가지고 tree를 그릴 때 어떻게 derivation(트리 분기를 나누냐)에 따라 tree가 여러 개 생기는 경우가 있음

   이걸 ambiguity(애매모호함)라고 하고, 이를 없애기 위해 CFG를 우선순위가 존재하게 만들어야 함

 

- 위 예시에서는 void main 함수 안에 else문만 존재하는 코드가 있다.

void main() {
    else { }
}

 1)) Lexer에서 변환할 때는 else 코드를 token으로 변화하기만 해서 문제가 없다

    [ ..., ELSE, LBRACE, RBRACE, RBRACE ]

  2)) Parser 단계에서 에러가 생긴다

   C언어의 문법 stmt → if exp stmt else stmt | if exp stmt | …

      stmt = statement (프로그램에서 실행 가능한 명령어 단위)

      exp = 표현식, 연산자와 피연산자로 구성된 코드 조각 (x+1, 5*(y-2), a==b)

      - 어쨌든 if문이 먼저 나와야 한다는 규칙을 가지고 있음

   3)) 하지만 현재 코드에서는 else가 if 없이 등장하고 있음 "Parsing Error"

 

 

 (3) Semantic Analyzer

   - semantic analyzer는 semantic error를 감지함

   - 문법적으로는 맞지만, 의미적으로도 오류가 없는지 분석한다

   - 예시

int x = 1;
String y = "hello";
int z = x + y;

     lexically(어휘적), syntatically(구문적)으로는 valid함

      -> Lexer, Parser 단계 통과

     하지만 semantically(의미적)으로 오류가 있음

      -> int z에 int와 string을 더한 값을 할당하려고 하고 있음

      오류 발생 error: incompatible types: String cannot be converted to int

- type 일관성이나 잘못된 연산을 검사해서 실행 도중 발생할 수 있는 오류를 사전에 찾아내는 역할을 함

 

- Source Technology of Semantic Analyzer: Static program analysis(정적 프로그램 분석)

  - 프로그램의 동작을 statically(정적으로), automatically(자동으로) 예측

    static: 실제로 실행하지않고 program text(source code)를 분석한다

    automatatically: SW가 SW를 분석, 사람이 수작업으로 확인하지 않고 분석 도구가 프로그램을 검토

 - 적용 사례

   - Verification(검증): 프로그램이 항상 특정 formal specification을 만족하는가?

      ex) 특정 조건이 항상 참인지, 오류 없이 작동하는지

   - Bug-finding(버그 찾기): 프로그램에 Integer Overflow 같은 버그가 있는지 확인

   - Equivalence Checking(동등성 검사): 두 프로그램이 semantically equivalent한가?

      ex) 서로 다른 코드가 같은 결과를 내는가?

 

(4) IR Translator

- syntex tree를 Intermediate Representation으로 변환한다

- source lang보다는 low level이고, target lang(machine lang)보다는 high level임

ex) three-address code

      어셈블리와 비슷한 형태의 명령어 시퀀스로 표현되며, 각 명령어는 최대 세 개의 피연산자를 가짐

     pos = init + rate * num이 표현된 tree를 아래와 같이 표현

    가장 마지막 leaf부터 역순으로 되짚어서 표현하는 것 같음(추측)

t1 = 10
t2 = rate*t1
t3 = init+t2
pos = t3

 

- 왜 IR이 필요하지? syntax tree를 target lang으로 바로 변환하지 않는 이유가 무엇인가?

  compiler를 빌딩하는 노력을 줄이기 위해

     - IR이라는 공통 문법을 만들어 여러 하이 레벨 언어를 로우 레벨 언어로 변환할 때, 하나의 컴파일러만 설계해도 됨

 

2.2 Middle-End (Optimizer)

- intermediate code가 더 나은 퍼포먼스를 보여주도록 변환한다

예시 보면서 느낀거 = 거지같이 짠 코드를 pr에서 뚜맞 당하고 효율적으로 고치는 기분

최대 3개의 피연산자만 가지도록 하면서도 가장 적게 식을 작성하도록 고침

 

2.3 Back-End

- target machine code 생성

- 최적화된 IR을 기계어로 바꿈

- 예시에서 R1, R2의 두 register가 available하다고 가정

 

t2 =  rate*10

pos = init+t2

 

LOAD R2, rate // R2에 rate값 로드

MUL R2, R2, #10 //R2에 R2와 10을 곱한 값을 할당

LOAD R1, init // R1에 init을 로드

ADD R1, R1, R2 //R1에 R1 값과 R2 값을 더해서 할당

STORE pos, R1 //R1의 값을 pos에 저장

 

컴시이실을 다시 하는 기분이다 젠장...이거 맞나?

최적화 IR을 순서대로 기계어로 번역하면 되는 듯

 

 

3. 요약

- 컴파일러는 프로그래밍 언어 변환기이다

- 현대 컴파일러는 3가지 구조를 포함한다

   프론트엔드: 소스 프로그램의 syntax(문법)와 semantic(의미)를 이해한다

   미들엔드: 프로그램의 효율성을 끌어올린다

   백엔드: target program을 생성한다

 

 

수강 24.09.02. 1주차 1강 월

작성 24.09.07.