Video & Image VIPL Processing Lab. Compiler Construction 한국방송통신대학교컴퓨터과학과출석수업 제 2012-2 공학박사김명진 (HCI & 지능형로봇연구소 ) 숭실대학교연구교수
컴파일러교재구성 2장 : 형식언어와오토마타 3장 : 어휘분석 4장 : Contex-free 언어와푸시다운오토마타 5장 : 구문분석 2
어휘분석 어휘분석이란? 원시프로그램을읽어들여토큰이라는의미있는문법단위로분리하는것 원시프로그램 : If a 10 then 토큰 (token) : if, a,, 10, then 토큰번호 : 29, 1, 20, 2, 35 3
컴파일러구조 Source Program 어휘분석기 토큰 구문분석기 중간코드생성기 코드최적화기 목적코드생성기 4 트리 중간코드 Compiler Object Program
어휘분석기 소스프로그램 (S.P) 을문법적으로 의미있는최소단위로분할 원시프로그램 어휘분석기 일련의토큰 5
어휘분석기설계 토큰의종류 (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 > = not >,= = not =.. b=blank l=letter d=digit = not = not. 예약어표검색 39 43 42 40 41 44 46 51 45 33 숫자 not found A found = ( ) + * /,. ; 3 4 식별자 예약어 38 49 50 34 35 36 37 47 45 48 3장어휘분석
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 76 29 E L E 31 77 S 78 22 N D 79 10 A A N D F 80 O 81 R 28 82 N 83 C 84 T I 85 O 86 87 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 E R 102 103 A 104 M 4 O R C 106 107 108 109 D 9 R 123 11 I E A 110 111 112 26 N 115 21 E 117 6 I 120 121 L L 126 127 E 10 27 24 T 12
어휘분석기구현방법 프로그래밍언어를이용하여직접구현 컴파일러자동화도구를이용하여구현 어휘분석기생성기종류 LEX FLEX ScanGen PCLEX POISON JLEX 11
컴파일러생성기모델 Language Description : L Machine Description : M 컴파일러생성기 Program written in L 컴파일러 Executable form on M 12
어휘분석기생성기 LEX: 1975 년에 M.E.Leak 가고안 토큰을구분하는프로그램작성도구 원시프로그램 토큰구조 ( 정규표현 ) LEX 어휘분석기 (Scanner) 일련의토큰 13
PCLEX 소개 LEX LEX 의입력 원시프로그램 상태전이표를갖는어휘분석기 LEX 의역할 일련의토큰들 14
LEX 의기능 정규표현 (*.L) LEX 어휘분석용소스프로그램 (lex.yy.c) 컴파일 원시프로그램 어휘분석기 일련의토큰 15
LEX 입력명세서 사용형식 { 정의부분 } %% // 규칙시작표시, 생략불가능 { 규칙부분 } // 규칙부분 ::= 정규표현 + 수행코드 %% { 사용자부프로그램 } 16
LEX 정규표현 ::= 텍스트문자 + 연산자문자 텍스트문자 비교대상의스트링문자로알파벳과숫자 연산자문자 \ [] ^ -?. * + () $ / {} % <> 17
LEX 수행코드 정규표현이매칭되면즉, 토큰이인식되었을때실행해야할행동을 C언어로기술하는부분 수행코드구성 전역변수 함수 I/O 루틴 ( 입출력함수 ) 18
LEX 수행코드 전역변수 yytext 정규표현과매칭된실제문자열보관변수 [a-z]+ printf( %s, yytext); yyleng 매칭된문자열의길이를저장하는변수 yytext[yyleng-1] 매칭된스트링의마지막문자 19
LEX 수행코드 함수 yylex() LEX 입력에서명시한정규표현과일치하는토큰을찾을때까지한문자씩계속읽음 yymore() 현재매칭된문자열의끝에다음에인식될문자열을덧붙이는함수 20
LEX 수행코드 함수 yyless(n) n 개의문자만을 yytext 에남겨두고나머지는다시처리하기위해 input 으로되돌려보내는함수. yywrap() Lex 가입력의끝을만났을때호출하는함수. 정상인경우 : 함수복귀값은 1 21
LEX 수행코드 I/O 루틴 input() 입력스트림으로부터다음문자를읽는함수. output(c) 출력스트림으로문자 c 를내보내는함수 unput(c) input() 에의해읽혀지도록문자 c 를입력스트림으로되돌려보내는함수 22
LEX 활용사례 원시프로그램 (datafile) ABC := E * 314 + ABC / E ; 토큰 LIST(10 개 ) ABC, :=, E, *, 314, +, ABC, /, E, ; 23
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
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
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
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 Identifier : E MUL_op Number : 314 Add_op Identifier : ABC DIV_op Identifier : E Semicolon End of LEX 토큰 10 개