[Compiler Design] Lexical Analysis

 

 

 

 

 

컴파일러는 어떤 언어로 쓰여진 프로그램을 읽어 다른 언어로 된 의미가 같은 프로그램으로 번역해주는 프로그램이다.

 

자바에서 애너테이션도 컴파일러가 처리하기도 하고, 애너테이션 프로세서를 통해 추가 작업을 수행하기도 한다.

애너테이션을 만들 때 Retention을 설정하는데, 이 설정값에 따라서 컴파일러 및 애너테이션 프로세서가 어느 정도까지 애너테이션을 처리할 지 결정한다. 

 

다만 자바에서는 Preprocessor를 사용하지 않는다.

#include처럼 Preprocessor가 처리하고 소스코드로 변환하는 과정이 없으니, 컴파일러와 전처리기를 구분해서 생각하자. 

 

컴파일러는 프로그램 실행 전 소스코드를 중간코드로 변환하고, 인터프리터는 실행 중 한줄씩 해석한다.

실제로는 두 가지 해석 방식을 혼합해서 사용하는 경우가 많다. 파이썬도 CPython으로 .pyc 바이트코드를 생성해 최적화 하기도 하고..

 

 

 

<컴파일러의 처리 과정>

 

 

 

 

---

 

 

 

 

Lexical Analysis - 어휘분석

 

프로그램은 그냥 문자열일 뿐이다. 문자열에 의미를 부여하기 위해 문자열의 각 요소를 의미있는 최소 단위로 변환해야 한다.

이 작업을 Lexical Analysis라고 하고, 이 과정에서 Space 개행 등 Redundant한 요소들도 함께 제거한다. 

 

문자열에서 의미 있는 최소단위를 Token이라고 부른다. 이 Token을 잘 처리해보자.

 

어떤 걸 토큰으로 정의할 지를 결정할 때는 정규표현식을 사용한다. 문법은 위키백과에 잘 설명되어있으니 생략.. 

핵심 정규표현식은 그대로 사용하고, 회사마다 정규표현식을 커스텀해서 사용하기도 한다.

 

정의된 토큰을 인식할 때는 Finite State Automata를 사용한다. 

 

 

 

 

FSA는 정규표현식과 같은 표현력을 가지며 상호치환이 가능하다. 

최종 목표는 토큰을 인식하는 소스코드를 작성하는 것. 그러니 이 작업을 위해 몇 가지 과정을 거쳐야 한다.

 

RegExp - Non-Deterministic Finite Automata - Deterministic Finite Automata - Java

 

DFA에서 자바 소스로 변환하는건 그냥 읽고 그대로 구현하면 되니까 문제 없고.. 

RegExp - NFA / NFA - DFA 간 변환 방식은 이미 알고리즘이 확립되어있다. 

 

FSA로 표현할 때 상태전이도가 간단하다고 최선이 아니다.

상태 고립을 고려해 직관적이고, 이해하기 쉬운 상태전이도를 작성하자. 

 

상태전이도 작성 시 Top-Down 방식으로 작성하는게 도움이 된다. 

정규표현식이 큰 단위의 반복임을 확인하고, 다른 상태들 끼리의 간섭을 최소화하자. 

 

Lexical Analysis 분석 결과 안에서 토큰들은 Lexeme = <토큰번호, 토큰값> 방식으로 표현된다. 

그냥 키-값 매핑으로 문자열 비교 대신 정수 비교를 할 수 있고, 토큰 값을 분리해 메모리를 효과적으로 사용한다고 이해하자. 

 

 

 

 

 

RegExp - Non-Deterministic Finite Automata - Deterministic Finite Automata - Java

Lex / ANTLR 은 정규표현식 ~ DFA 까지의 과정을 처리해 준다.

 

 

.l 확장자 파일에 정규표현식 기반의 토큰 규칙을 정의하고 Lex에 넣으면 

Lex는 DFA 기반의 어휘분석기 함수인 yylex() 를 포함하는 lex.yy.c 파일을 반환한다.

lex.yy.c를 컴파일하면 입력 스트림을 받아서 토큰을 반환하는 프로그램이 만들어진다. 

 

토큰이 중복되서 인식되는 경우에는 가장 긴 토큰을 우선으로 하고, 길이가 같다면 가장 먼저 나타난 규칙의 정규 표현으로 인식한다. 

 

즉, Lex는 어휘분석기 때문에 도입된 어휘분석기를 생성하는 도구라고 생각하자.

지금까지 FSA를 어떻게 그리고 DFA를 어떻게 그리는지를 공부한 이유는 Lex가 내부적으로 어떻게 동작하는지 알기 위해서이다.

 

 

 

 

lex로 만들어진 어휘분석기는 스캐너라고도 부른다.

구문분석기는 프로그램의 구조를 분석하기 위해 어휘분석기에게 다음 토큰을 요구하고, 어휘분석기는 프로그램을 읽다가 규칙에 맞는 lexeme을 찾고 토큰으로 변환해 구문분석기에게 전달한다.