[컴파일러개론] 중간고사 정리 - Lexical Analysis

Lexical Analysis

소스코드는 전처리기(preprocessor)를 통해 #include, #defines, #ifdef등 전처리 과정을 거치고,

전처리된 소스코드는

- Lexical(어휘) Analysis

- Syntax(구문) Analysis

- Semantic(의미) Analysis

세 가지 분석을 통해 추상 구문 트리(중간 코드)가 된다.

 

Lexical Analysis

어휘분석기의 대표적인 예로는 Scanner가 있다.

문자열을 차례대로 검사하여, 의미 있는 최소 단위(토큰)로 쪼개주는 것을 어휘 분석이라고 한다.

어휘 분석 과정에서 space 같은 것들을 제거하여 코드의 크기도 줄일 수 있다.

 

토큰(Token)

문법적으로 의미 있는 최소단위

- 식별자, 키워드, 상수, 연산자, 문자열

식별자는 특히 조금 더 처리가 필요하며, 어디까지가 토큰인지 알아보기가 어렵다.

 

Token과 관련된 질문들

1) 토큰 하나하나를 기술하는 방법

2) 토큰을 인식하는 방법

3) 여러 토큰 중 결정하는 방법

4) 토큰이 컴퓨터에서 표현되는 방법

 

---

1) 토큰을 기술하는 방법

정규표현식(RE)을 사용하여 토큰을 설명한다.

정규표현식은 패턴을 나타내는 것

ex) 2진수 집합 => 1(0|1)* | 0 

 

정규표현식을 쓰는 곳

- unix 명령 중 grep (파일을 찾는 명령어)

- javascript에서 exec, test, match, search 등의 메소드

 

var myRe = /d(b+)d/g;
var myArray = myRe.exec("cdbbdbsbz");

위 코드에서 두 개의 / 문자 사이에 주어진 식이 정규표현식을 의미하며,

맨 뒤에 g는 문자열에서 match되는 것을 전부 찾으라는 것을 의미한다.

 

exec은 문자열에서 매치된 문자열을 반환한다.

test는 true/false만 반환한다.

 

 

식별자중 a와 b의 갯수가 동일하게 나타나는 것의 정규표현식을 작성해보시오.

위 문제가 정규표현식 작성이 불가능 한 이유는 유한상태오토마타로 표현할 수 없기 때문이다.

정규표현식은 유한상태오토마타로 표현이 가능해야 한다.

 

 

2) 토큰을 인식하는 방법

유한 상태 오토마타(FSA)

상태를 유한한 갯수까지만 가지며, 상태 간의 전이를 정의한다.

시작 상태 한 개와 끝 상태 여러 개를 가진다.

 

FSA는 정규표현식과 동일한 표현력을 가지기 때문에 어휘 분석의 기초가 되는 이론적 기반이다.

 

DFA(Deterministic finite automata)

FSA의 한 종류로, 나가는 edge가 레이블 문자에 의해 유일하게 결정되는 것을 말한다.

널이 붙은 edge도 없다.

 

토큰 인식은

사용자가 정의한 정규표현식을 NFA(Non-DFA)로 변환하고,

NFA를 DFA로 변환하고, 이 DFA를 따라 인식한다.

FSA를 통해 switch case로 구현할 수 있다.

 

 

3) 여러 토큰 중 결정하는 방법

두 개 이상의 정규표현식이 매치될 때, 긴 토큰을 우선으로 처리한다.

 

4) 토큰이 컴퓨터에서 표현되는 방법

전통적인 방법 : Lexeme = <토큰번호, 토큰값>

 

토큰번호

- 각 토큰들을 효율적으로 처리하기 위해서 부여한 번호

토큰값

- 명칭의 토큰값은 자신의 스트링 값

- 상수의 토큰값은 자신의 상수 값

 

if x < y then x :=10;

(1, X) (1, Y) => 1은 식별자를 의미하며, 토큰값으로 자신의 스트링 값을 가짐

(2, 10) => 2는 상수를 의미하며, 토큰값으로 자신의 상수 값을 가짐

---

도구를 이용한 어휘분석기 만들기

Lex

C 기반 어휘분석기 생성기

정규표현과 실행코드를 입력받아 C언어로 쓰여진 프로그램을 출력

 

lex는 프로그램을 만들어내는 프로그램이다.

 

test.l ->  lex  -> lex.yy.c ->  cc  -> 어휘분석기 실행파일

 

lex는 가장 길게 인식된 토큰을 우선으로 한다.

인식된 토큰의 길이가 같은 경우 먼저 나타난 규칙의 정규 표현으로 인식한다.

 

%{

 <정의 부분>

 자료구조, 변수, 상수 등

}%

%%

  <규칙 부분>

  정규표현과 그 토큰이 인식되었을 때 처리할 행위를 기술하기 위한 부분

%%

  <사용자 부 프로그램 부분>

  렉스 입력 작성 시 사용되는 부 프로그램들을 정의

 

yyleng : 매칭된 토큰의 문자열의 길이를 저장하고 있는 변수

yytext : 매칭된 토큰의 문자열을 담은 변수

yylval : 매칭된 토큰값을 담은 변수

yywrap : 입력의 끝에서 호출하는 함수, 정상적인 경우 복귀값은 1이다.

 

---

정리

- 토큰은 정규표현식(RE)을 이용하여 기술한다.

- 토큰은 유한상태오토마타(FSA)를 이용하여 인식한다.

- 토큰은 긴 토큰을 우선으로 결정한다.

- 토큰은 (토큰번호, 토큰값) 쌍으로 표현된다.

 

문제

Q. 다음 lex 정규표현식들의 차이는?
1. [^abc]와 [abc^]와 ^abc

[^abc]는 abc를 제외한 문자
[abc^]는 a, b, c, ^ 중 하나
^abc는 abc로 시작을 의미한다.