Yejin

아자아자 파이팅!!!

7 minute read

💙ref.

  1. kocw 국민대학교 컴파일러(2019)

  2. 형식 언어와 오토마타

  3. Aho et al, “컴파일러: 원리 기법 도구(2판)”, 교보문고(2009)


1. 컴파일러 개요

학습목표

  1. 컴파일러와 인터프리터의 차이점 설명
  2. JIT와 AOT 컴파일을 이해하고 필요성 설명
  3. Preprocessor의 기능과 조건부 컴파일의 필요성 이해
  4. 컴파일러의 일반적인 구조와 주요 기능 설명
  5. 컴파일러 자동화 도구(컴파일러-컴파일러)의 필요성 설명


1.1. 컴파일러란 무엇인가?

1
2
3
4
5
6
7
8
9

#include <stdio.h>

main() 
{
	int i;
	
	for(i=0;i<5;i++)
		printf("Hello World!\n");
}

다음과 같은 c언어 코드를 실행할 때, cpu가 고급 언어를 알아듣지 못하므로 기계어 문장으로 변환해주어야 한다

고급 언어를 기계어로 바꾸어주는 번역기를 컴파일러라고 한다.

c컴파일러를 통해 소스 파일을 컴파일하면 *.obj 형태의 목적파일(object file)이 생성된다 .

기계어나 어셈블리어로 코드를 작성하면 시간이 오래 걸리므로, 빠른 시간 내에 원하는 소프트웨어를 개발하기 위해 고급 언어를 배움

==> 고급 언어를 번역해주는 컴파일러가 필수적이다!


고급언어로 프로그램을 작성할 때는 에디터를 활용함 (통합 개발 환경(IDE)를 사용한다)

통합 환경 중 vs

  • 에디터 기능
  • 컴파일 기능(컴파일 버튼을 클릭하면 소스코드를 컴파일하도록)
  • 디버깅 기능
  • 링킹
  • 로딩

통합 환경에는 소프트웨어에 필요한 여러 가지 툴들이 통합되어 있음

통합 환경을 따로 활용하지 않고 에디터를 통해 코드를 작성하고, gcc혹은 cl.exe를 통해 소스 코드를 cmd에서 컴파일하는 방법도 있음(대표적 OS: Linux)

gcc 따로 설명

cl.exe를 사용하려면 vs 폴더 내부에서 .bat 파일을 별도로 실행해주어야 함

gcc/cl.exe를 활용해 소스 파일을 컴파일했을 때, 실행 속도나 파일의 크기가 다를 수 있음

상업용 소프트웨어를 개발할 때에는(실행용 파일 배포) 가장 효율적인 실행 파일을 판매해야 함

컴파일할 때 최적화할 것인가, 디버깅모드로 컴파일하느냐 릴리즈 모드로 컴파일하느냐

디폴트는 디버깅모드로 컴파일하는 것임

step by step 기능을 통해 어느 부분이 잘못되었는치 차례차례 확인할 수 있다

  • 어떤 값이 어디서 잘못되었는지 실행 단계에서 확인할 수 있음!

릴리즈: 단지 실행하는데만 초점을 두어 훨씬 효율적임

=> 디버깅 모드로 실행 파일을 만들고, 릴리즈 모드로 실행 파일을 만들었을 때, 속도의 차이가 크다


1.2. 컴파일러 소개

컴파일러: 언어 번역기(language translator) 중 하나!

  • input: 고급 언어로 작성된 소스코드(원시 프로그램, source code)
  • output: 목적 프로그램(target code)
    • 저급 언어(기계어, 어셈블리어)로 구성됨
      • 왜 어셈블리어? 어셈블리어에서 기계어로 번역하는 과정은 매우 단순하므로, 고급 언어 입장에서 두 언어에 큰 차이를 두지 않음


모든 언어에 대해 컴파일러가 있는 것은 아니다!

모든 언어에 대해 언어 번역기는 있어야 하지만, 반드시 컴파일러일 필요는 없다

언어 번역기

  • 컴파일러, 인터프리터, 프리프로세서, 어셈블러, 교차 컴파일러 등
    • 컴파일러 언어, 인터프리터 언어가 있음
      • c, cpp, java: 컴파일러 언어
      • python: 일반적으로 인터프리터 언어로써 사용됨
      • 컴파일러와 인터프리터를 모두 제공하는 언어도 있다!
    • 언어 번역기 보조로 프리프로세서(전처리기)를 사용


컴파일러/인터프리터의 장단점

  • 인터프리터 언어인 경우, 소프트웨어를 판매하려면 소스코드를 함께 제공해주어야 함
    • 파이썬으로 개발한 소프트웨어는 파이썬 코드도 제공해야 함
    • 소스코드 제공이 부담스러울 수 있다
  • 실행 효율: 인터프리터는 느리다 ! 한 줄씩 일일히 번역해주어야 하기 때문에, 실행 속도를 고려해햐 함
    • 실행속도를 빠르게 하려면 기계어로 먼저 번역하고, 기계어만 실행시킬 수 있도록 컴파일러도 지원해야 한다
  • 인터프리터 언어가 배우기 쉽다!
    • 파이썬 인터프리터만 실행시키면 코드를 직관적으로 작성한 후 바로 실행할 수 있음
    • 컴파일러 언어는 코드 작성 -> 컴파일 -> 프로그램 실행 등 여러 단계가 필요: 실행 과정이 다소 복잡함


소프트웨어 개발 환경

  • 컴파일러/인터프리터, 전처리기(pre-processor)
  • 어셈블러, 링커(linker), 로더(loader)
  • 편집기(editor), 디버거(debugger), 프로파일러(profiler)
    • Visual Studio, Eclipse, GNU Dev Cpp

프로파일러: 릴리즈 이전에 빠르게 소프트웨어를 실행할 수 있도록 어느 함수에서 지연이 발생하는지 확인해야 함

=> 함수마다 시간이 얼마나 걸리는지 측정하고, 어느 부분이 비효율적인지 확인하기 위해 사용함


프로젝트 관리기(make): 라인 수가 길어지면 여러 개의 파일으로 나누어 실행하는데, make 도구를 통해 여러 개로 나눈 파일을어 사용할 수 있음

make 기능이 없으면 달라진 부분과 연관된 모든 프로그램 코드 파일들을 열어 일일히 수정해주어야 함

make에서 수정된 시간을 파악해 연관된 부분을 자동으로 수정한 후, 다시 *.obj 파일을 만들어 exe 파일 생성함


컴파일러-컴파일러 시스템(compiler-compiler system)

  • 컴파일러 자동화 도구

  • LEX(어휘분석기 생성기), YACC(파서 생성기)


컴파일 과정

  1. 전단부(분석 과정): front-end

    • 어휘 분석(lexical analysis): 토큰 단위로 구분
    • 구문 분석(syntactic analysis, pasing): parse tree 생성
    • 의미 분석(semantic analysis)

  2. 후단부(생성 과정): back-end

    • 중간코드 생성(machine independent)
    • 코드 최적화(code optimization)
    • 목적 코드 생성

소스 코드에 대해 load, compare, jump 등 기계어로 번역하려면 소스코드 내용을 분석해야 함

각 문장들에 대한 기계어 코드를 생성


image

컴파일러의 전반적인 내용을 도식화

분석 및 생성 과정에서 심벌 테이블을 만들어야 함

심벌 테이블: 변수명, 함수명, 상수명 등

기계어로 번역하기 위해 각 변수/함수/상수 의 특징을 알아야 함(타입, 구조체, ,,,) => 심벌들에 대한 테이블 필요

수집된 정보를 바탕으로 기계어 코드 생성

각 분석 단계에서 에러가 발생하기도 한다!(어휘분석 에러, 구문분석 에러, 의미분석 에러 등)

에러가 무엇인지 정보를 수집하고 , 정확한 에러 메시지를 출력할 수 있도록 하는 오류 처리 관련 루틴이 필요하다


어휘 분석(lexical analysis)

  • 어휘 분석기(lexical analyzer) 또는 스캐너
    • 입력: 원시 코드(source code)
    • 출력: 토큰 열(token sequence)

어휘 분석기에서 원시 코드를 토큰 별로 구분해줌

  • 토큰: 의미가 있는 최소 단위(더 이상 분해 x)
    • eg) my_array[index+1] = x + 100 ;
      • my_array, [, index, +, 1, ], =, +, 100, ; 11개의 토큰 추출 가능


각 토큰들을 토대로 문장을 분석해야 한다!

구문 분석(syntax analysis) or 파싱(parsing)

구문 분석기(syntax analyzer) or 파서(parser)


한 문장에서의 구조를 파악함

syntax: 하나의 문장 또는 부분문장의 구조

  • 산술식 문장, 입출력, if, while 등

pasing: 하나의 문장을 파악해 파스 트리 형식으로 출력


입력: 어휘 분석 결과(토큰 열)

출력: 파스 트리(parse tree) 또는 구문 트리(syntax tree)

파스: 여러 갈래로 갈라짐


컴파일러 이론: 문법과 오토마타

파서를 어떻게 만들까?

문법과 오토마타 필요

촘스키: 문법의 복잡도에 따라 4가지로 분류

image

  1. 모든 문법
  2. 어떤 조건을 만족하는 문법
  3. 제약을 더 많이 가함
  4. 제약을 매우 심하게 가함


image

image

오토마타= > 어휘 분석과 파싱을 위해 알아야 한다!


image

각각의 오토마타는 문법과 1대1 대응이 된다!

유한 오토마타를 완벽하게 정규문법으로 기술 가능

정규문법을 완벽하게 유한 오토마타로 만들 수 있다

=> 언어 기술 방법이 문법과 오토마다 두 가지 방법이 있음!

유한 오토마타 -> 튜링 기계(유한 오토마타가 가장 단순, 튜링 기계로 갈수록 오토마타가 복잡해진다 !)


튜링 기계: 이론적인 컴퓨터

  • cf) 인공지능의 튜링 테스트: 인공지능이 정말 사람보다 우월한지를 평가하는 소프트
    • 어떤 것이 사람인지 구분하지 못하면 튜링 테스트가 완벽하다고 한다

고급 언어

  1. 좋은 언어: 언어의 개념이 명확해야 함(의미의 명확)
  2. 개발자의 생각을 ㅈ라 표현
  3. 호환성, 신뢰성, 모듈화, 효율성
  4. 확장성이 우수해야 함
  • 코볼, 포트란, 알골, 파스칼, 에이다, c++ 등


번역기와 컴파일러

크로스 컴파일러

  • pc에서 개발하고 스마트폰에서 실행
    • 개발 환경과 실행 환경이 다를 경우(두 하드웨어가 다를 경우), 개발 환경에서 실행 환경으로 목적 코드를 만들어주기 위한 컴파일러가 필요함


image

프리프로세서

  • c언어: 매크로 확장 기능
  • std 라이브러리 등
  • 조건에 따라 컴파일하지 않아도 되는 경우(조건부 컴파일)
    • 윈도우 전용으로 프로그램을 만들었을 경우, 이러한 부분은 이미 만들어져 있는 라이브러리를 사용하고 별도로 컴파일하지는 않아도 됨
    • include만 하면 된다 ! ==> 언어의 확장성


image

각 토큰을 토큰 넘버로 치환함

각 토큰들을 인식만 하지 말고 토큰 넘버로 치환해야 처리하기 편함


image

문장이 틀렸으면 에러, 문장이 맞았으면 파싱 트리 생성


image

좋은 상품을 만들려면 중간 코드를 만들고, 최적화를 통해 최종 코드 생성

중간코드: 어셈블리어

트리에 대한 중간코드를 생성 => 중간코드 생성기

최적화: 자동으로 코드를 생성하면 비효율적인 부분이 많아짐


image

산술식 단순화, 시간이 많이 걸리는 코드를 짧게 바꿈

(반복문, 루프, 실행되지 않는 조건문 등 없앰)

컴파일러 자동화

2. 형식 언어

2.1. 언어(Language)

언어: 문장들의 집합

문장: 단어들의 집합

언어를 명확하게 기술하려면 단어들의 리스트가 필요함, 이후, 문법 규칙이 필요


image

image

단어들의 집합: T

단어들을 나열해 문장을 만들어야 함

  • 0과 1으로 문장을 만들 경우, 가장 짧은 문장: 0

어휘 집합으로부터 만들어낼 수 있는 모든 문장(string)들을 T* 집합이라고 한다.

  • 어떤 언어는 모든 string 집합을 언어라고 표현할 수도 있고 , 어떤 언어는 string 집합 중 일부 유형만을 언어라고 표현할 수도 있음
  • 만약 , 특정 유형을 언어라고 표현하려는 경우, 제약 조건이 필요함
    • 해당 제약 조건을 만족하는 부분집합들만 언어라고 선언
  • | |: 단어 집합의 길이


image

t*의 부분집합 중에서 어떤 부분만을 언어라고 할 것인가 고민

일반적으로 언어는 무한 개의 문장을 기반으로 하기 때문에, 모든 문장을 나열할 수 x

그렇다면 언어는 어떤 형태로 기술할까?

일반적으로 조건제시법으로 기술할 수 없는 제약 조건이 있음

언어에 문법을 주자!(제약 조건 부여)

문법에는 구성 요소들이 있음(생성규칙)

인식기의 문제

신택스에 맞는 문법이 들어오면 인식기가 옳다고 판정함

정해준 신택스와 다른 문법이 들어오면 인식기가 틀리다고 판정함

인식기를 하나 만들어두면, 모든 문장들을 인식기에 넣어주면 된다!

언어인식기: 오토마타(언어 인식 기계)


image

u, v: t*의 원소 => 원소 간 결합 가능

$a^0: \epsilon$

$\omega^R$: reverse string


image

  1. product
    • 어떤 언어 L과 L’ 두 개의 집합을 Cartesian product 가능 (두 언어의 원소를 가져와 결합)
    • 원소의 개수: L의 원소 개수 * L’의 원소 개수
      • L과 L’의 원소의 개수가 같을 경우 $L^n$
  2. $L^0$: $ \epsilon$의 집합 ?
  3. $L^*$: L의 0집합부터 전부까지 모두 결합


2.2. 문법(Grammar)

image

언어를 정의하고 표현하는 방법

알파벳 t집합

형식 언어에서는 단어를 잘 쓰지 않는다 !

형식 언어 연습 시에는 0/1만 쓰거나, 그 활용도에도 고급 언어의 간단한 단어만 집합으로 사용함


알파벳: 터미널 기호(teminals) => 실질적인 언어 $Vt$

알파벳이 아닌 언어 구조를 정의하는데 필요한 기호: nonterminals => 제약조건을 세우기 위해 필요한 기호$Vn$

teminals과 nonteminals의 합집합: $V$

teminals과 nonteminals의 합집합, 모든 원소: $V^*$

teminals과 nonteminals의 합집합, null 제외 원소: $V^ {\dagger}$


image

임의의 G라는 문법이 있다고 하자.

teminals과 nonteminals의 집합이 있어야 함

생성 규칙이 있어야 한다! : 기호 P, (productrion rules)

  • 이 규칙으로부터 무한대의 문장을 생성함
  • 가장 중요한 요소!
  • 생성 규칙은 $\alpha \rightarrow \beta$ 형식으로 기술됨
    • $\alpha$: $V^ {\dagger}$ (null스트링이면 안됨) “lhs”
    • $\beta$: $V^*$ “rhs”
      • alpha를 beta원소에서 생성함

nonterminals 중 하나를 시작 기호로 사용함: S

==> 문법은 4가지 요소로 구성됨

image

어떤 문법 G가 있을 때,

  • nonterminal 집합이 {S, A}
  • terminal 집합이 {a, b}
  • 시작 기호: S
  • 생성 규칙: P

생성규칙 개수: 5개(화살표 개수만큼!)

  • S 생성규칙 2개(화살표를 | 로 구분하기도 함, 따로 나열 or 함께 나열 정도의 차이임)
  • A 생성규칙 3개

image-20221005093425022

문법으로부터 그 언어에 속하는 모든 문장(string)들을 생성할 수 있어야 한다.

nonterminal은 반드시 시작기호 S로부터 시작해야 한다.

시작기호로부터 문법들을, 생성 규칙을 적용해서 유도할 수 있는 string이 무한대이고, 그 문장들의 집합을 언어라고 함

$\Longrightarrow$: 직접 유도 $\alpha$를 $\beta$로 대치

$\buildrel\ast\over\Longrightarrow$: 0번 이상 반복

$\buildrel\dagger\over\Longrightarrow$: 1번 이상 반복


image-20221005094630158

통상적으로 시작 기호가 무엇인지 아무 얘기가 없으면 첫번째 nonterminal을 시작 기호로 한다

$\omega$: 반드시 sentential form $V^*$

최하단 $\omega$: 반드시 terminal이어야 함. 문장의 sentance


image-20221005094926421


image-20221005094958580


image-20221005095157869


image-20221005095141281

어떤 언어가 주어졌을 때, 문법을 기술할 줄 알아야 한다 !

생성 규칙의 개수: 유한개

스트링의 개수: 무한개

=> 반복 규칙을 사용

만약, a가 0승일 경우, $\epsilon$

화살표 왼쪽을 화살표 오른쪽으로 대치

Leave a comment

You may also enjoy