ysw's blog

    C Compiler

    03 Jan 2019 | C

    포스팅

    C 프로그래밍


    프로그래밍이란 목적에 맞는 알고리즘으로부터 프로그래밍 언어를 사용하여 구체적인 프로그램을 작성하는 과정을 의미합니다. 이렇게 작성된 프로그램은 먼저 실행 파일(executable file)로 변환되어야 실행할 수 있습니다.


    <실행파일 생성>

    1. 소스 파일(Source file)의 작성

    프로그래밍에서 가장 먼저 해야 할 작업은 프로그램을 작성하는 것 입니다. C언어를 문법에 맞게 논리적으로 작성된 프로그램을 원시 파일 또는 소스파일이라고 합니다. C언어를 통해 작성된 소프파일의 확장자는 .c가 됩니다.

    2. 선행처리기(Preprocessor)에 의한 선행 처리

    선행처리란 소스 파일 중에서도 선행처리 문자(#)로 시작하는 선행처리 지시문의 처리 작업을 의미합니다. 코드를 생성하는 것이 아닌, 컴파일하기 전 컴파일러가 작업하기 좋도록 소스를 재구성해주는 역할만을 합니다.

    3. 컴파일러(Compiler)에 의한 컴파일

    소스 코드를 컴파일하는 이유는 대부분 사람들에게 이해하기 쉬운 형태의 고수준 언어로부터 실행가능한 기계어 프로그램을 만들기 위해서이다. 좁은 의미의 컴파일러는 주로 고수준 언어로 쓰인 소스 코드를 저수준 언어로 번역하는 프로그램을 가리킨다. 컴퓨터는 0과 1로 이루어진 이진수로 작성된 기계어만을 이해할 수 있습니다. 소스 파일은 개발자에 의한 C언어로 작성되므로, 컴퓨터는 그것을 바로 이해할 수 없습니다. 따라서 소스 파일을 컴퓨터가 알아볼 수 있는 기계어로 변환시켜야 하는데, 그 작업을 컴파일(Compile)이라고 합니다. 주로 다른 프로그램이나 하드웨어가 처리하기에 용이한 형태로 출력되지만 사람이 읽을 수 있는 문서 파일이나 그림 파일 등으로 옮기는 경우도 있다.

    컴파일은 컴파일러에 의해 수행되며, 컴파일이 끝나 기계어로 변환된 파일을 오브젝트 파일(Object file)이라고 합니다. 이러한 오브젝트 파일의 확장자는 .o나 .obj가 됩니다.

    4. 링커(Linker)에 의한 링크

    컴파일러에 의해 생성된 오브젝트 파일은 운영체제와의 인터페이스를 담당하는 시동 코드(start-up code)를 가지고 있지 않습니다. 또한, 대부분의 C 프로그램에서 사용하는 C 표준 라이브러리 파일도 포함되어 있지 않습니다. 이때 하나 이상의 오브젝트 파일과 라이브러리 파일, 시동 코드 등을 합쳐 하나의 파일로 만드는 작업을 링크라고 합니다.

    링크는 링커(linker)에 의해 수행되며, 링크가 끝나면 하나의 새로운 실행 파일이나 라이브러리 파일이 생성됩니다. 이처럼 여러 개의 소스 파일을 작성하여 최종적으로 링크를 통해 하나의실행 파일로 만드는 것을 분할 컴파일이라고 합니다.

    5. 실행 파일(Executable file)의 생성

    소스 파일은 선행처리기, 컴파일러 그리고 링커에 의해 위와 같은 과정을 거쳐 실행 파일로 변환됩니다. 최근 사용되는 개발 툴은 대부분 위에서 소개한 선행처리기, 컴파일러, 링커를 모두 내장하고 있으므로, 소스 파일에서 한 번에 실행 파일을 생성해 줍니다. 이렇게 생성된 파일의 확장자는 .exe가 됩니다.



    원리

    컴파일러는 옮김의 과정에서 프로그램의 뜻을 보존하여야 한다. 입력받은 프로그램의 의미를 충실히 따라야한다.
    -이 조건이 없다면 컴파일러를 사용하는 사용자가 컴파일러를 믿고 프로그램을 작성할 수도 없고, 잘못된 옮김을 인정한다면 컴파일러를 올바르게 하기 위한 노력을 들일 필요가 없을것이다.

    실용적인 면에서, 컴파일러는 입력으로 들어온 프로그램을 어떤 면에서든지 개선해야 한다.
    - 소스코드를 기계어로 옮긴다면 기계가 이해할 수 없었던 언어를 기계가 이해할 수 있게 개선한 것이 된다.



    기능

    고급언어를 직접 기계어 코드를 변환한다. 자바의 경우 바이트 코드로 변환한다. 중간단계의 코드를 생성하고 이것을 해석해서 실행한다.

    C/C++언어와 같은 고급언어는 직접 기계어 코드로 변환한다. 마이크로프로세서는 각각 다른 기계어 코드를 가지고 있기 때문에 같은 고급언어라도 다른 기계어 코드를 생성해야 한다. 따라서 개발자는 해당 마이크로프로세서에 맞는 컴파일러 사용해야 한다. 그러나 자바는 다양한 마이크로프로세서에서 실행되도록 하는 철학을 가지고 개발되었기 때문에 바이트 코드를 가지고 해석을 해서 실행하는 방식이다. 장점은 한번 컴파일된 바이트 코드는 다른 플랫폼에서 재컴파일없이 실행할 수 있다. 그러나 단점은 바이트 코드를 해석해서 실행할 프로그램 구조가 필요하고, 직접 기계어 코드를 실행하는 것 보다 속도에서 늦다.


    컴파일러의 실행 단계


    <컴파일 과정>

    1. 어휘 분석(lexical analyze) or 스캔(scan)

    - 모듈 : 어휘 분석기(lexical analyzer) or 스캐너(scanner)
    - 내용 : 문자열을 의미있는 토큰(token)으로 변환
    - 결과물 : 토큰(token)

    2. 구분 분석(syntax analyzing)

    - 모듈 : 파서(parser) or 구문 분석기(syntax analyzer)
    - 내용 : 토큰(token)을 구조를 가진 구문트리(syntax tree)로 변환
    - 결과물 : 구문 트리(syntax tree), parser 에 따라 추상 구문 트리(abstract syntax tree)를 바로 생성하기도 함
    ※ 구문트리(syntax tree) 와 추상구문트리(abstract syntax tree)의 차이는, 구문트리에는 세미콜론(;)이나 괄호 등이 모두 포함된다. 하지만 추상구문트리에는 이러한 불필요한(의미가 없는) 것들이 생략된다.

    3. 의미 분석(semantic analysis)

    - 모듈 : 의미 분석기(semantic analyzer)
    - 내용 : 프로그램의 의미(semantic)에 따라 필요한 정보를 유추/분석
    - 결과물 : 추상 구문 트리(abstract syntax tree) / 장식구문(decoration syntax tree)

    4. 중간 표현의 생성(intermediate representation)

    - 내용 : 좀 더 코드 생성이 편하고, 여러 종류의 언어나 기계어(CPU 종속)에 대응하기 위해서, 중간에 공통의 중간표현으로 변환

    5. 코드 생성(code generation)

    - 모듈 : 코드 제너레이터(code generator)
    - 내용 : 어셈블리어나 기계가 이해하기 쉬운 명령으로 변환
    - 결과물 : 어셈블리어

    6. 최적화(optimization)

    - 내용 : 좀더 질 좋은 프로그램으로 변환

    7. 어셈블러

    - 내용 : 기계어로 변환
    - 결과물 : 기계어

    위 컴파일 단계에서 구문 분석(syntax analyzing) ~ 중간표현(intermediate representation) 생성까지를 컴파일러의 프론트-엔드(front end) 라고 합니다. 나머지 과정을 백-엔드(back end)라고 합니다.



    단계라는 것의 중요성과 이것이 의미 분석 단계와 코드 생성 단계 사이에 있다는 사실 정도만 인지하고 있어도 충분하다.


    <실행파일 생성>

    컴파일러를 만들때, 어휘분석을 위해서 스캐너(scanner)가 필요하고, 어휘분석을 통해 만들어진 토큰(token)열을 구문분석 하기 위해서는 파서(parser)가 필요합니다. 이러한 스캐너와 파서를 일일이 직접 작성하는 일은 만만치가 않습니다. 아마도 정규표현식으로 도배가 되어, 나중에는 어디가 어딘지 분간이 안되겠지요. "여긴 어딘가. 나는 누구인가?"

    이런 이유로 스캐너(scanner)와 파서(parser)를 자동으로 생성해 주는 제너레이터(generator)가 있으면 참 편리할 것입니다. 그리고 예상하셨겠지만, 이런 제너레이터(generator)가 이미 존재합니다. 각각을 스캐너 제너레이터(scanner generator), 파서 제너레이터(parser generator)라고 부릅니다.

    그런데, 실제로 스캐너 제너레이터(scanner generator) 라는 말 대신 어휘 분석기 제너레이터(lexical analyzer generator) 라고 더 많이 쓰는 것 같습니다. 그리고 이 어휘분석기 제너레이터는 줄여서 렉서 제너레이터(lexer generator)라고 합니다. 어찌되었건, 렉서 제너레이터(lexer generator)는 일반적으로 대부분 비슷합니다. 이에 반해, 파서 제너레이터(parser generator)는 몇 가지 타입으로 나누어 집니다.



    LL 파서 제너레이터 (지원문법이 비교적 적음 / 속도 비교적 빠름)
    http://en.wikipedia.org/wiki/LL_parser#Concrete_example

    LR 파서 제너레이터 (지원문법이 넓음 / 속도 느림)
    http://en.wikipedia.org/wiki/LR_parser#Concrete_example

    Canonical LR 파서 제너레이터 (지원문법이 넓음 / 속도 느림)
    http://en.wikipedia.org/wiki/Canonical_LR_parser

    LALR 파서 제너레이터 (지원문법이 비교적 넓음 / 속도는 평균적)
    http://en.wikipedia.org/wiki/LALR_parser



    각 파서(parser)마다 파싱하는 방식이 다르기 때문에, 취급할 수 있는 문법의 범위와 속도가 달라집니다. 자세한 내용은 아래에서 다시 설명하도록 하겠습니다.

    렉서 제너레이터(lexer generator)와 파서 제너레이터(parser generator)의 종류는 많이 있습니다. 각 렉서 제너레이터(lexer generator), 파서 제너레이터(parser generator)마다 생성하는 파서의 언어와 취급하는 파서 제너레이터 타입이 다르므로, 자신의 상황에 맞게 적절히 사용하면 될 것 같습니다.

    개인적으로 제가 학교 다닐때, 컴파일러 수업에서 사용했던 렉서 제너레이터(lexer generator)로는 렉스(Lex)라는 녀석을 사용했습니다. 그리고 파서 제너레이터(parser generator)로는 YACC(Yet Another Compiler Compiler)였던걸로 기억합니다. YACC 는 생성하는 파서의 언어는 C 이고, 취급문법은 LALR(1) 이라고 하네요.

    이쯤되면, 어휘 분석기 제너레이터(lexical analyzer generator)는 뭐고 파서 제너레이터(parser generator)는 뭐고 파서랑 무슨관계고, 정신이 없으신 분들이 게실것 같습니다. 정리를 해 드리면 간단합니다.

    우리가 정의한 언어의 어휘분석(lexical analysis)과 구문분석(syntax analysis)을 해야 합니다. 그러기 위해서는 어휘분석을 해 주는 어휘분석기가 필요합니다. 이를 스캐너(scanner) 라고 부릅니다. 그리고 구문분석을 해 주는 구문분석기가 필요합니다. 이를 파서(parser)라고 부릅니다.

    그런데, 문제는 이런 렉서(lexer)와 파서(parser)를 일일이 직접 코딩해서 만드는건 너무나 힘이 듭니다. 양이 방대하고 복잡합니다. 실수가 생길수 밖에 없지요.

    그렇기 때문에, 이 스캐너(scanner)와 파서(parser) 소스코드를 자동으로 생성해 주는 제너레이터(generator)라는 녀석을 사용하는 것입니다. 이를 각각 렉서 제너레이터(lexer generator)와 파서 제너레이터(parser generator) 라고 합니다. 즉, 스캐너(scanner)와 파서(parser)의 소스코드를 자동으로 만들어 주는 프로그램인 것입니다. 참고로 왜 스캐너 제너레이터(scanner generator) 라고 안하고 렉서 제너레이터(lexer generator)라고 하는지는 저도 모르겠습니다.

    가져온곳: URL