Compiler 1 - Compiler structure & Tokens

 high level language를 low level language로 번역해 주는 것이 compiler. 예를 들어 source.c로 작성한 소스코드를 source.exe인 target program으로 만들어 주는 것이 컴파일러의 역할이다.

language translation : translate the source code into semantically equivalent target code. 서로 다른 언어로 번역할 지더라도 의미적으로 동일한 코드로 변환되어야 한다. 또한 소스코드의 error도 판독하는 능력도 추가되어 있다. 이런 활동을 하는 것이 language processor이다.

이런 번역을 하는 방식은 compilation과 interpretation의 두 가지가 있다.

compilation은 전체 소스코드를 타겟 코드로 실행 전에 모두 변환하는 것이다. C/C++ 등은 이런 방식을 채택한다. Compiler는 input으로 src code를 받아 target pgm이나 error msg를 결과로 낸다.

반대로 Interpretation은 interpreter가 실행되는 statement 단위로 번역을 한다. 그리고 이 과정이 모두 런타임에 발생한다. 즉, 해당 문장이 실행될 때 즉시 번역된다는 것이다. python, javascript가 이 방식으로 작동한다. 실제로 파이썬 소스코드는 .py로 이루어진 소스코드를 바로 실행하는 방식이고 따로 .exe 등 target pgm을 만들어 내지 않는다.

쉬운 예를 들어보면, 어떤 나라의 대통령의 연설을 그 나라 언어로 할 때, 이를 실시간 통역사가 번역하는 것은 interpretation 방식이고, 연설 전에 연설문 전체를 번역하여 배포하는 것은 compilation 방식이 된다.

일반적으로 compilation은 실시간 번역의 오버헤드가 없어 실행속도가 빠르지만, 소스코드가 타겟 프로그램으로 번역되어 실행되므로 이식성은 떨어진다. (target program으로 번역된 .exe은 해당 CPU에 맞는 ISA로 번역되므로 다른 컴퓨터에서 실행 불가능할 수 있다) 그리고 디버깅에 있어서 긴 소스코드를 매번 전체 다 컴파일 해야만 수정을 할 수 있다는 것 또한 컴파일 방식의 단점이다. 그러나 만약 매번 수정할 시 수정하는 부분이 산재해 있다면 컴파일 방식이 더 좋을 수도 있다.

자바/파이썬 등의 언어는 compiler와 interpreter를 모두 사용하여 하이브리드 언어라 한다. 이는 compiler를 이용해 전체 소스 코드를 intermediate pgm으로 번역을 하고, 각 라인이 실행될 때 마다 intermediate pgm을 다시 기계어로 번역하는 방식이다. 이 intermediate pgm은 ISA에 독립적이고, 실행시간이 더 빠르므로 두 방식의 이점을 모두 가질 수 있다.
language processing = preprocessor + compiler + assembler + linker
requirements for compiler : correctness (semantically equivalent, mandatory), performance improvement, reasonable compilation time.

lexical/syntax analysis 등의 과정에서 중요한 것들은 모두 symbol table에 저장되어 각 컴포넌트가 상호작용할 수 있게 된다.

1) Lexical analyzer (scanner)
소스 코드를 token sequence로 분리해내는 과정.

2) Syntax analyzer (parser)
위의 token set을 이용해 grammatical structure (syntax tree)를 만들어 냄.

3) semantic analyzer
위에서 만들어진 syntax tree를 가지고 type checking과 type conversion, scope checking을 시행. (semantic consistency를 확인)

위 세 개의 결과에 이상이 없으면 intermediate level code를 만들어 낸다. 이런 과정은 code optimizer가 코드를 효율적으로 바꾸기 위해서 존재한다. 해당 과정을 거친 뒤에 target machine code(기계어/어셈블리 코드)를 만들어낸다.
이 과정이 컴파일러가 작동하는 간략한 전체 과정이다.


1. Lexical Analyzer : meaningful sequence of token으로 input string을 분리해 내는 과정.

소스코드의 캐릭터를 읽고, 캐릭터를 의미 있는 순서집합(lexemes)로 그룹화 한다. 그리고 sequence of token을 생산하고 이를 symbol table에 저장한 뒤, token을 syntax analyzer로 보내는 역할을 맡는다.

- Token : syntactic category (예를 들어 noun, verb, adjective, identifier, number, operator ....  등)
일반적으로 token category - value 쌍으로 저장되며 이것이 lexical analysis의 결과물이 된다.

- Lexemes : sequence of characters that matches the patterns for a token
pattern : set of rules that defines token.

즉, 카테고리로 나누어지고 정의된 class (token)의 instance (lexeme)인 소스코드를 읽어 분해하는 것이다.

Class of token : Keyword(if/else), operator(+, -), Identifier(count, i, j), constants, punctuation symbols(Lparen, Rparen, 쉼표), Whitespace(공백)
일반적으로 공백은 각 lexeme을 분리하는데 사용되므로 lexical analyzer가 token을 분리해내고 나면 쓸모가 없으므로 lexical analyzer가 이를 제외한다.


이를 위해서는 각 token의 pattern을 정의하는 것 부터 시작해야 한다. 이는 regular language를 사용하여 이루어지며, 이 패턴에 따라 input stream의 token을 인식하는 것은 finite automata를 이용하여 이루어진다.