3장 어휘분석

Size: px

Start display at page:

Download "3장 어휘분석"

용환 반
7 years ago
Views:

1 Video & Image VIPL Processing Lab. Compiler Construction 한국방송통신대학교컴퓨터과학과출석수업 제 공학박사김명진 (HCI & 지능형로봇연구소 ) 숭실대학교연구교수

2 컴파일러교재구성 2장 : 형식언어와오토마타 3장 : 어휘분석 4장 : Contex-free 언어와푸시다운오토마타 5장 : 구문분석 2

3 어휘분석 어휘분석이란? 원시프로그램을읽어들여토큰이라는의미있는문법단위로분리하는것 원시프로그램 : If a 10 then 토큰 (token) : if, a,, 10, then 토큰번호 : 29, 1, 20, 2, 35 3

4 컴파일러구조 Source Program 어휘분석기 토큰 구문분석기 중간코드생성기 코드최적화기 목적코드생성기 4 트리 중간코드 Compiler Object Program

5 어휘분석기 소스프로그램 (S.P) 을문법적으로 의미있는최소단위로분할 원시프로그램 어휘분석기 일련의토큰 5

6 어휘분석기설계 토큰의종류 (1) 식별자 (identifier) (2) 상수 (constant) (3) 예약어 (reserved word) (4) 연산자 (operator) (5) 구분자 (delimiter) 6

start 1 A b l d < > : l d 2 32 52 53 54 55 not l d d not d >

예약어표검색 39 43 42 40 41 44 46 51 45 33 숫자 not found A found =

7 start 1 A b l d < > : l d not l d d not d > = not >,= = not =.. b=blank l=letter d=digit = not = not. 예약어표검색 숫자 not found A found = ( ) + * /,. ; 3 4 식별자 예약어 장어휘분석

8 b 1 l l d 2 not l d not found 식별자 예약어표검색 3 d 32 d not d 33 숫자 found 4 예약어 8

start 56 57 58 15 R R A Y 59 60 61 7 B G I N 62 E 63 64 65 18 C S 66 A 67 68 E 23 O S 69 N 70 71 T 5 D V 72 I 73 13 O W N T O 25 74 75

9 start R R A Y B G I N 62 E C S 66 A E 23 O S 69 N T 5 D V 72 I O W N T O E L E S N D A A N D F 80 O 81 R N 83 C 84 T I 85 O N 17 I U 88 F 20 M 89 O 90 D 14 N 91 O 92 T 19 9

A O 93 F 8 R 16 P R T 94 R 95 O C 96 97 P H 114 E O 30 Y 116 P U N T 118 119 V 105 E 113 122 A W H 124 125 G E U 98 D 99 100 R 101

10 A O 93 F 8 R 16 P R T 94 R 95 O C P H 114 E O 30 Y 116 P U N T V 105 E A W H G E U 98 D R 101 E R A 104 M 4 O R C D 9 R I E A N E I L L E T 12

11 어휘분석기구현방법 프로그래밍언어를이용하여직접구현 컴파일러자동화도구를이용하여구현 어휘분석기생성기종류 LEX FLEX ScanGen PCLEX POISON JLEX 11

12 컴파일러생성기모델 Language Description : L Machine Description : M 컴파일러생성기 Program written in L 컴파일러 Executable form on M 12

13 어휘분석기생성기 LEX: 1975 년에 M.E.Leak 가고안 토큰을구분하는프로그램작성도구 원시프로그램 토큰구조 ( 정규표현 ) LEX 어휘분석기 (Scanner) 일련의토큰 13

14 PCLEX 소개 LEX LEX 의입력 원시프로그램 상태전이표를갖는어휘분석기 LEX 의역할 일련의토큰들 14

15 LEX 의기능 정규표현 (*.L) LEX 어휘분석용소스프로그램 (lex.yy.c) 컴파일 원시프로그램 어휘분석기 일련의토큰 15

16 LEX 입력명세서 사용형식 { 정의부분 } %% // 규칙시작표시, 생략불가능 { 규칙부분 } // 규칙부분 ::= 정규표현 + 수행코드 %% { 사용자부프로그램 } 16

17 LEX 정규표현 ::= 텍스트문자 + 연산자문자 텍스트문자 비교대상의스트링문자로알파벳과숫자 연산자문자 \ [] ^ -?. * + () $ / {} % <> 17

18 LEX 수행코드 정규표현이매칭되면즉, 토큰이인식되었을때실행해야할행동을 C언어로기술하는부분 수행코드구성 전역변수 함수 I/O 루틴 ( 입출력함수 ) 18

19 LEX 수행코드 전역변수 yytext 정규표현과매칭된실제문자열보관변수 [a-z]+ printf( %s, yytext); yyleng 매칭된문자열의길이를저장하는변수 yytext[yyleng-1] 매칭된스트링의마지막문자 19

20 LEX 수행코드 함수 yylex() LEX 입력에서명시한정규표현과일치하는토큰을찾을때까지한문자씩계속읽음 yymore() 현재매칭된문자열의끝에다음에인식될문자열을덧붙이는함수 20

21 LEX 수행코드 함수 yyless(n) n 개의문자만을 yytext 에남겨두고나머지는다시처리하기위해 input 으로되돌려보내는함수. yywrap() Lex 가입력의끝을만났을때호출하는함수. 정상인경우 : 함수복귀값은 1 21

22 LEX 수행코드 I/O 루틴 input() 입력스트림으로부터다음문자를읽는함수. output(c) 출력스트림으로문자 c 를내보내는함수 unput(c) input() 에의해읽혀지도록문자 c 를입력스트림으로되돌려보내는함수 22

23 LEX 활용사례 원시프로그램 (datafile) ABC := E * ABC / E ; 토큰 LIST(10 개 ) ABC, :=, E, *, 314, +, ABC, /, E, ; 23

24 LEX 활용사례 정의부분 %{ /* 생성된프로그램에그대로 copy 됨 */ #include <stdio.h> #include <stdlib.h> enum tnumber {TEOF, TIDEN, TNUM, TASSIGN, TADD, TPOINT, TMUL, TDIV, TSEMI, TDOT, TBEGIN, TEND, TERROR}; %} /* 이름n 치환식 */ letter [a-za-z] digit [0-9] 24

$return(tadd); * return(tmul); / return(tdiv); {digit}+ return(tnum); ; return(tsemi); \. return(tdot); [ \t\n] ;.$

25 LEX 활용사례 규칙부분 %% begin return(tbegin); end return(tend); {letter}({letter} {digit})* return(tiden); := return(tassign); + return(tadd); * return(tmul); / return(tdiv); {digit}+ return(tnum); ; return(tsemi); \. return(tdot); [ \t\n] ;. return(terror); 25

26 LEX 활용사례 사용자부프로그램부분 %% main() { enum tnumber tn; /* token number */ printf( Start of LEX \n ); 숭실대학교 HCI& 지능형로봇연구소 교수김명진 ( 공학박사 ) while ((tn = yylex()!= TEOF) switch (tn) { case TBEGIN : printf( Begin \n ); break; case TEND : printf( End \n ); break; case TIDEN : printf( Identifier : %s\n, yytext); break; case TASSIGN : printf( Assign_op \n ); break; case TADD : printf( Add_op \n ); break; case TMUL : printf( Mul_op \n ); break; case TDIV : printf( Div_op \n ); break; case TNUM : printf( Number: %s\n, atoi(yytext)); break; case TSEMI : printf( Semicolon \n ); break; case TDOT : printf( Dot \n ); break; case TERROR : printf( Error \n ); break; } yywrap() {printf( End of LEX \=n ); return 1; } } 26

27 LEX 실행절차 LEX 명세 (TEST.L) LEX Lex.yy.c cc a.out PC 환경에서실행법 C > PCL32 -i TEST.L library C > cc -c -o test.c C > TEST < datafile 27

LEX 실행결과 datafile 실행결과 ABC := E * 314 + ABC / E ; Start of LEX Identifier : ABC Assign_op

28 LEX 실행결과 datafile 실행결과 ABC := E * ABC / E ; Start of LEX Identifier : ABC Assign_op Identifier : E MUL_op Number : 314 Add_op Identifier : ABC DIV_op Identifier : E Semicolon End of LEX 토큰 10 개

EA0015: 컴파일러

EA0015: 컴파일러 4 Flex 무엇을공부하나? " 어휘분석기 (lexical analyzer 혹은 scanner)" 는다음과같은과정을거쳐서프로그램된다. 1 토큰정의, 2 정규식으로표현, 3 NFA로변환, 4 DFA로변환, 5 프로그램작성 위과정은앞장에서배운바와같이기계적으로이루어질수있다. "Flex(Fast Lexical Analyzer)" 는컴파일러개발자를위하여위과정을자동으로처리해주는도구이다.