제4장 어휘 분석

컴파일러 구성론

강 승 식

4.1 서론

□ 어휘분석(lexical analysis)

- 입력 : source program ( character string )

- 기능 : string을 scan하여 문법적으로 의미있는 최소의 단위로 분할

- 출력 : list of tokens

※ 어휘분석기(lexical analyzer) or scanner

□ token의 종류

일반형태 : 프로그래머가 사용하는 명칭

1. 명칭(identifier) --- 변수 이름, 함수 이름 등

2. 상수(constant) --- 정수, 실수, string 등

특수형태 : 고급언어에서 정의된 symbol

3. 지정어(keyword 또는 reserved word) --- begin, end, for, while, if 등

4. 연산 기호(operator symbol) --- +, -, *, /, <, > 등

5. 구분자(delimiter) --- ;, :, (, ), [, ] 등

□ token에 대한 정보 : (token_number, token_value) 쌍이 parser에 전달됨

. token number : 각 token에 대한 고유번호

. token value : 일반형태의 token에 대해서 string(명칭) 또는 constant(상수)

예) if X < Y then X := 10;

□□□ (29, 0) (1, X) (18, 0) (1, Y) (35, 0) (1, X) (9, 0) (2, 10) (7, 0)

예 1) 문장 a:=b+3; 에 대한 토큰 및 토큰번호, 토큰값

(토큰번호는 4.3절에 C언어의 enumeration type에 정의된 것을 따름)

토큰	a	:=	b	+	3	;

토큰#	0	11	0	5	1	12

토큰값	a	0	b	0	3	0

※ Symbol Table

명칭에 대한 token, token value, 속성(type, 차원 등)을 보관하는 자료구조

- 명칭에 대한 어휘분석 결과를 parser에 전달 방법

예: 변수 a, b의 경우 --- (0, a), (0, b)

symbol table의 index (0, 10), (0, 20)을 파서에 전달

- 스캐너(어휘분석기)와 파서의 관계

스캐너는 파서가 토큰이 필요할 때 호출하는 서브루틴

4.2 Token 인식

□ token의 기술 : 정규문법, 정규표현, 유한자동

□ 명칭, 정수, 실수, string 상수, comment의 인식

토큰 인식기를 위해 문자를 아래와 같이 정의

letter → a | b | c | ... | z | A | B | C | ... | Z

digit → 0 | 1 | 2 | ... | 9

special_char → + | - | * | / | . | , | ...

4.2.1 명칭 인식

명칭의 정규표현

4.2.2 정수 인식

4.2.3 실수 인식

S → dA

A → dA | .B

B → dC

C → dC | eD | [eqn: epsilon]

D → dE | +F | -G

E → dE | [eqn: epsilon]

F → dE

G → dE

4.2.4 스트링 상수 인식

예: □This is a string□, □I don''t know□ , □□ (null string), □''□ 등

C 프로그램

do {

while (getchar() != '\'')

;

ch = getchar();

} while (ch == '\'');

4.2.5 Comment 인식

4.3 어휘분석기의 구현

- 특수 심벌

+	-	*	,	;

:	:=	.	..	(

)	[	]	=	<>

<	<=	>	>=

- 단어 심벌(예약어: reserved word)

array	begin	const	div	do

end	if	mod	of	procedure

program	integer	then	var	while

어휘분석기 프로그램 소스

(1) 토큰번호 tsymbol 정의

enum tsymbol {

tnull,    tident,     tnumber,   tplus,     tminus,   ttimes,

tcomma,   tsemicolon, tcolon,    tassign,   tdot,     tddot,

tlparen,  trparen,    tlbracket, trbracket, tequal,   tnequal,

tless,    tlesse,     tgreat,    tgreate,   teof,

arraysym, beginsym,   constsym,  divsym,    dosym,    endsym,

ifsym,    intsym,     modsym,    ofsym,     procsym,  progsym,

thensym,  varsym,     whilesym

};

(2) 명칭 길이와 예약어 개수 정의

#define ID_LENGTH	12

#define NUMKEYWORD	15

(3) 파서에게 전달하는 토큰 정보

struct tokentype {

int number;	/* token number */

union {

char id[ID_LENGTH];

int num;

} value;	/* token value */

};

(4) 예약어(지정어) 스트링 배열과 토큰번호

char *keyword[] = {	/* keyword table */

"array",     "begin",   "const",   "div",  "do",

"end",       "if",      "integer", "mod",  "of",

"procedure", "program", "then",    "var",  "while"

};

enum tsymbol tnum[] = {

arraysym,    beginsym, constsym,   divsym,  dosym,

endsym,      ifsym,    intsym,     modsym,  ofsym,

procsym,     progsym,  thensym,    varsym,  whilesym

};

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <ctype.h>

#include "scanner.h"	/* (1), (2), (3), (4)에 대한 header file */

struct tokentype scanner()

{

struct tokentype token;

int i, j, k, num;

char ch, id[ID_LENGTH];

token.number = tnull;

do {

while ((ch = getchar()) == ' ');	/* skip blanks */

if (isalpha(ch)) {	/* identifier or keyword */

i = 0;

do {

if (i < ID_LENGTH) id[i++] = ch;

ch = getchar();

} while (isalnum(ch));

id[i] = '\0';

ungetc(ch, stdin);

/* find the identifier in th ekeyword table */

i = 0; j = NUMKEYWORD-1;

do {	/* binary search */

k = (i + j) / 2;

if (strcmp(id, keyword[k]) >= 0) i = k + 1;

if (strcmp(id, keyword[k]) <= 0) j = k - 1;

} while (i <= j);

if ((i-1) > j)	/* found: keyword exit */

token.number = tnum[k];

else {	/* not found: identifier exit */

token.number = tident;

strcpy(token.value.id, id);

}

} else if (isdigit(ch)) {	/* number */

num = 0;

do {

num = 10 * num + (int)(ch - '0');

ch = getchar();

} while (isdigit(ch));

ungetc(ch, stdin);	/* retract */

token.number = tnumber;

token.value.num = num;

} else switch (ch) {	/* special characters */

case '(':	/* state 7 */

ch = getchar();

if (ch == '*') {	/* comment */

do {

while (ch != '*') ch = getchar();

ch = getchar();

} while (ch != ')');

} else {

token.number = tlparen;

ungetc(ch, stdin);	/* retract */

}

break;

case '<':	/* state 11 */

ch = getchar();

if (ch == '>') token.number = tnequal;

else if (ch == '=') token.number = tlesse;

else {

token.number = tless;

ungetc(ch, stdin);	/* retract */

}

break;

case '>':	/* state 15 */

ch = getchar();

if (ch == '=') token.number = tgreate;

else {

token.number = tgreat;

ungetc(ch, stdin);	/* retract */

}

break;

case ':':	/* state 18 */

ch = getchar();

if (ch == '=') token.number = tassign;

else {

token.number = tcolon;

ungetc(ch, stdin);	/* retract */

}

break;

case '.':	/* state 21 */

ch = getchar();

if (ch == '.') token.number = tddot;

else {

token.number = tdot;

ungetc(ch, stdin);	/* retract */

}

break;

case '=': token.number = tequal; break;

case ')': token.number = trparen; break;

case '+': token.number = tplus; break;

case '-': token.number = tminus; break;

case '*': token.number = ttimes; break;

case ';': token.number = tsemicolon; break;

case ',': token.number = tcomma; break;

case '[': token.number = tlbracket; break;

case ']': token.number = trbracket; break;

case EOF: token.number = teof; break;

}	/* switch end */

} while (token.number == tnull);

return token;

}	/* end of scanner */

4.4 Lex

□ 정규표현으로 기술된 token들을 인식하는 program을 작성하는 도구(tool)

- 입력 : 정규표현과 실행 코드  -->  <file_name>.l

- 출력 : C 프로그램 ( lex.yy.c )

compiler의 어휘분석기, DB 질의어의 어휘분석기 등에 필요함

□ LEX 사용법(Unix에서)

$ lex <filename>.l

: 파일 lex.yy.c가 생성됨

$ cc lex.yy.c -o scanner -ll

: 리눅스에서는 □-ll□ 대신에 □-fl□

$ scanner < test.pas

□ LEX 사용법(PC용 LEX)

LEX의 file top에 다음 문장들을 insert

#include <stdio.h>

#include <lex.h>	/* LEX의 라이브러리 함수 사용시 */

Usage: pclex options scanner.l

Available options:

-c : use file "yylex.c" for C output

-Cf: use file f for C output

-h : display this help message

-i : case insensitive

-n : do not generate '#line' directive in output

-pf: use skeleton f as scanner driver

-s : suppress scanner output

1) 입력 파일 test.l 작성 (LEX SPECIFICATION)

2) pclex test.1	==> lex의 출력이 test.c

pclex -Cout.c test.1	==> lex의 출력이 out.c

pclex -c test.1	==>   "     "    yylex.c

3) cl test.c

4) test.exe 실행

4.4.1 lex의 입력

□ lex input 파일의 구조

<정의부>

%%

<규칙부>

%%

<사용자 subprogram>

1. <정의부>

%{

/* lex.yy.c의 head 부분에 그대로 copy되는 부분 */

/* 자료 구조, 변수 및 상수 정의 */

%}

이름1	치환식1

이름2	치환식2

....

이름n	치환식n

※ 이름i의 정의

- 특수한 정규표현을 하나의 이름으로 정의 : 정규표현에 대한 macro 정의

이름과 치환식은 한 개 이상의 blank 또는 tab 문자로 분리되어야 함

- 이름i : 한 개 이상의 문자로 구성

- 치환식i : 특수한 정규표현

- 규칙부에서 사용할 때는 중괄호 사용 : {이름i}

( lex가 macro expansion해 줌 )

예) <정의부>

L	[a-zA-Z_]

D	[0-9]

<규칙부>

{L}({L}|{D})*	return IDENT;

2. <규칙부> --- 정규표현과 실행코드 쌍

%%

R1	{A1}

R2	{A2}

......

Rn	{An}

- Ri : 인식하고자 하는 token의 형태를 나타내는 정규표현

- {Ai} : token이 인식되었을 때 어휘분석기가 처리할 행위를 기술한

실행 코드(action)

- 예)

integer	printf("found keyword INT\n");

3. <사용자 subprogram>

- lex의 input file에서 사용되는 subprogram들을 정의

- lex.yy.c에 그대로 복사됨

4.4.2 lex의 정규표현

□ text 문자와 연산자 문자로 구성

예) a*에서 a는 text 문자이고, *는 연산자 문자

□ 연산자 문자와 그 의미

□□ \ [ ] ^ - ? . * + | ( ) $ / { } % < >

(1) □□ : 따옴표 사이에 있는 모든 문자를 text 문자로 취급할 때 사용

( 연산자 문자를 text 문자로 취급할 때 사용 )

- 예) a*b에서 *는 반복기호인 Cleen closure이고,

a□*□b에서 *는 문자 □*□를 의미한다.

(2) \ : 한 문자를 text 문자로 취급할 때 사용

- 예) XYZ□++□, □XYZ++", XYZ\+\+는 모두 동일한 의미이다.

(3) [] : 문자들의 class를 정의하는데 사용

- [abc]는 a, b, c 중에서 한 문자를 나타낸다.

- []내에 사용되는 연산자 문자 중에서 -, ^, \를 제외한 것은

그 의미를 상실

□-□는 범위를 나타내는 연산자이다.

[a-z] : a부터 z사이의 문자 중에서 한 문자

[-+0-9] : minus, plus 기호와 숫자를 포함하는 class

[A-Za-z0-9] : 영문자와 숫자

□^□은 여집합을 표현하는 연산자이다.

[^*] : □*□을 제외한 모든 문자

[^a-zA-Z] : 영문자를 제외한 모든 문자

□\□는 C 언어의 escape 문자 중의 하나

[ \t\n] : 공백, tab, 개행 문자 중의 하나

[\40-\176] : Ascii 값 40부터 176인 □~□까지의 문자

(4) * : 0번 이상의 반복

a* : a가 0번 이상 반복

[a-zA-Z][a-zA-Z0-9]*

: 첫문자는 영문자, 두번째 이하는 영문자 또는 숫자

(5) + : 한 번 이상의 반복

a+ : a가 1번 이상 반복

[a-z]+ : 모든 소문자 문자열

(6) ? : 선택을 의미하는 연산자

ab?c : b가 선택적이므로 abc 또는 ac를 의미

(7) | : 택일을 의미하는 연산자

(ab|cd) : 문자열 ab 또는 cd

(ab|cd+)?(ef)* : abefef, efefef, cdef, cddd 등

(□+□|□-□)[0-9]+ : 부호가 있는 정수

(8) ^ : line의 시작 기호

^abc : line의 처음에 나타난 abc만 인식

(9) $ : line의 끝 기호

(10) / : 접미 문맥(trailing context)을 명시할 때 사용.

ab/cd : ab 다음에 cd가 이어서 나타날 때만 ab가 인식된다.

abc$ ≡ abc/\n

(11) . : new line 문자를 제외한 모든 문자와 match

"--".* : --부터 line의 끝까지 문자열

(12) {} : 정의된 이름을 치환식으로 확장할 때 사용

4.4.3 lex의 실행코드(Actions)

- lex의 입-출력 : stdin, stdout

- Action이 필요없는 문자열 : C 언어의 null statement

[ \t\n]	;

- 동일한 실행코드가 반복될 경우

□ □ |

□\t□ |

□\n□	;

- 외부변수(external variable) yytext : 어떤 정규표현에 의해 match된 문자열 값

[a-z]+	printf("%s", yytext);

- match된 문자열을 출력하는 lex의 지정어 ECHO

[a-z]+	ECHO;

- 그외 lex에서 사용되는 변수와 함수

yyleng : match된 문자열의 길이를 저장하고 있는 변수

yymore() : 현재 match된 문자열의 끝에 다음에 인식될 문자열이 덧붙임

yyless(n) : n개의 문자만 남겨두고 나머지는 input stream으로

retract하는 함수

input() : input stream에서 다음 문자를 읽는 함수

output(c) : output stream으로 문자 c를 보내는 함수

unput(c) : 함수 input()에 의해 다시 읽혀지도록 c를 input stream으로

retract

yywrap() : lex가 입력의 끝을 만났을 때 호출되는 함수

4.4.4 scanner의 생성 및 동작

□ 파일 lex.yy.c

- 함수 yylex()

1. lex의 input file에 명시된 정규표현과 일치되는 token을 찾을 때까지

한 문자씩 읽어들인다.

2. token이 match되면 그 정규표현에 해당하는 실행코드가 실행된다.

3. EOF를 만나면 yylex()는 함수 yywrap()을 호출한다.

<사용자 subprogram> 부분에 함수 yywrap()을 정의하면 된다.

- match되는 정규표현이 두 개 이상일 경우

1. 가장 길게 인식된 token을 우선으로 한다.

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

예) 아래 규칙에 의해 integers는 identifier로 integer는 keyword로 인식

integer	printf("keyword integer\n");

[a-z]+	printf("identifier ==> %s\n", yytext);

※ lex 입력 예

/*

Ultra-mini pascal LEX input file

*/

%{

#include <stdio.h>

#include <stdlib.h>

enum tnumber {

TEOF, TIDEN, TNUM, TASSIGN, TADD,

TSEMI, TDOT, TBEGIN, TEND, TERROR

};

%}

letter	[a-zA-Z_]

digit	[0-9]

%%

begin	return(TBEGIN);

end	return(TEND);

{letter}({letter}|{digit})*	return(TIDEN);

":="	return(TASSIGN);

"+"	return(TADD);

{digit}+	return(TNUM);

";"	return(TSEMI);

\.	return(TDOT);

[ \t\n]	;

.	return(TERROR);

%%

main()

{

enum tnumber tn;

printf("Start of lex\n");

while ((tn = yylex()) != TEOF) {

switch (tn) {

case TBEGIN:	printf("\tBegin\n"); break;

case TEND:	printf("\tEnd\n"); break;

case TIDEN:	printf("\tIdentifier : %s\n", yytext); break;

case TASSIGN:	printf("\tAssign op.\n"); break;

case TADD:	printf("\tAdd op.\n"); break;

case TNUM:	printf("\tNumber : %s\n", yytext); break;

case TSEMI:	printf("\tSemicolon\n"); break;

case TDOT:	printf("\tDot\n"); break;

case TERROR:	printf("\tError : %c\n", yytext[0]); break;

}

}

}

/*

yywrap() { printf("End of Lex\n"); return 1; }

*/

※ 숙제 : 연습문제 4.6, 4.7, 4.8, 4.10, 4.11