EA0015: 컴파일러

Size: px

Start display at page:

Download "EA0015: 컴파일러"

병숙 영
4 years ago
Views:

1 4 Flex

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

3 강의내용 Flex 소개 Flex 파일모습 Flex 확장정규식 입력이 Pattern 과매치되는방식 주요 Flex 변수및함수 C-Minus 어휘분석기 교재 Kenneth C. Louden, Compiler Construction Principles and Practice, PWS Publishing Company, (2.6, A.1, A.4) V. Paxon, W. Estes and J Millaway, Lexical Analysis With Flex, Edition , The Regents of the University of California, ( 4 Flex 4-3

4 Flex 소개 Flex 는어휘분석기생성기 (lexical analyzer generator) 이다. Flex 는 flex 파일 (.l) 을읽어서 C 프로그램파일 lex.yy.c 를생성한다. Flex file 은확장정규식으로표현되는 pattern 과 C 코드의 list 로구성됨. 생성된프로그램 lex.yy.c 에는 C 언어함수 yylex() 가포함되어있고이함수가어휘분석작업을수행한다. 생성된프로그램 lex.yy.c 는일반 C 컴파일러에의하여컴파일된후 flex 라이브러리와링크되어 (-lfl 옵션사용 ) 수행파일인어휘분석기를생성한다 수행파일은수행하면서 flex file 에서정의한 pattern 과일치하는스트링이입력파일에서들어오면이식과쌍을이룬 C 코드를수행한다. 4 Flex 4-4

5 Flex 파일모습 Flex 파일은 %% 로구분되는 3 부분으로구성된다. %{ #include, #define 및 C 언어변수선언 %} flex macro 정의 %% lexical rule ( 확장정규식 { C 코드 } 로구성 ) %% 사용자제공 C 함수 4 Flex 4-5

6 Flex 파일모습 - 보기 %{ #include <stdio.h> int lineno = 1; %} line.*\n %% {line} { printf("%5d %s",lineno++, yytext); } %% main() { yylex(); return 0; } 4 Flex 4-6

7 Flex 확장정규식 - 1/2 x match the character x. any character except newline [xyz] x or y or z [abj-oz] a or b or any letter from j to o or Z [^A-Z] any character except A to Z r* zero or more r's r+ one or more r's r? zero or one r (optional) r{4} 4 r's r{2,5} two to five r's {name} macro expansion "[xyz]\"foo" literal string [xyz]"foo 4 Flex 4-7

8 Flex 확장정규식 - 2/2 \x ANSI-C \x for a, b, f, n, r, t, v \0 NULL character (ASCII 0) \123 character with value octal 123 \x2a character with value hexadecimal 2a (r) r for high precedence rs r followed by s (concatenation) r s either r or s ^r r at the beginning of a line r$ r at the end of a line <<EOF>> end of file 4 Flex 4-8

9 입력이 Pattern 과매치되는방식 매치되는 pattern 찾기 입력파일을읽어가면서매치되는 pattern 이있는지를찾는다. 이때가장긴스트링으로매치되는 pattern 을찾는다. 만약매치되는 pattern 이두개이상이면 flex file 에서먼저나타나는 pattern 을선택한다. yytext 및 yyleng 변경 매치된 pattern 이선택되면입력스트링을전역변수 char *yytext 가가리키는곳에복사하고이스트링의길이를전역변수 int yyleng 에저장한다. Pattern 과쌍을이루는 C 코드의수행 매치된 pattern 과쌍을이루는 C 코드를수행한다. 만약매치되는 pattern 이없으면입력을출력파일로출력한다. 4 Flex 4-9

10 Flex 변수 주요 Flex 변수및함수 FILE *yyin - 입력파일. (default로 stdin) FILE *yyout - 출력파일. (default로 stdout) char *yytext - 현재매치된스트링이저장되는곳. int yyleng - yytext의길이. Flex 함수 int input(void) - 입력함수. int ECHO(void) - yytext를 yyout에출력. int yylex(void) - 어휘분석기함수. 4 Flex 4-10

11 C-Minus 어휘분석기 : 어휘 어휘 : lexeme(token) Keywords: void(void), int(int), if(if), else(else), while(while), return(return), input(input), output(output) Special symbols: +(PLUS), -(MINUS), *(MULTIPLY), /(DIVIDE), <(LT), <=(LE), >(GT), >=(GE), ==(EQ),!=(NE), =(ASSIGN),,(COMMA), ;(SEMICOLON), ((LPAR), )(RPAR), {(LBRACE), }(RBRACE), [(LBRACKET), ](RBRACKET) Other token: 변수 (ID) 숫자 (NUM) ID=(letter _)(letter digit _)* NUM=digit digit* Whitespaces: " ", "\t", "\r", "\n" Comments: "/*... */", "//... \n" 4 Flex 4-11

12 C-Minus 어휘분석기 : scanner.l %{ #define ACCEPT(x) \ { \ } printf("line=%i, token=%s, lexeme=\"%s\"\n", source_line_no, (char *)x, yytext); \ fflush(stdout); \ int source_line_no = 1; %% "void" "int"... {digit}{digit}*... %%... ACCEPT("VOID"); ACCEPT("INT"); ACCEPT("NUM"); %} digit [0-9] letter [a-za-z] int main(int argc, char *argv[]) {... yyin=fopen(argv[1], "r"); yylex(); return 0; } 4 Flex 4-12

13 C-Minus 어휘분석기 : Makefile scanner: scanner.c gcc -O -o scanner scanner.c -lfl scanner.c: scanner.l flex scanner.l mv lex.yy.c scanner.c 4 Flex 4-13

14 C-Minus 어휘분석기 : 수행 /********************************/ int gcd(int u, int v) { int g; if (v == 0) g = u; else g = gcd(v, u - u / v * v); return g; }... /********************************/ $ scanner gcd.c line=3, token=int, lexeme="int" line=3, token=id, lexeme="gcd" line=3, token=lpar, lexeme="(" line=3, token=int, lexeme="int" line=3, token=id, lexeme="u" line=3, token=comma, lexeme="," line=3, token=int, lexeme="int" line=3, token=id, lexeme="v" line=3, token=rpar, lexeme=")" line=4, token=lbrace, lexeme="{" line=5, token=int, lexeme="int" line=5, token=id, lexeme="g" line=5, token=semicolon, lexeme=";"... $ 4 Flex 4-14

EA0015: 컴파일러

EA0015: 컴파일러 5 Context-Free Grammar 무엇을공부하나? 앞에서배운 " 정규식 " 은언어의 " 어휘 (lexeme)" 를표현하는도구로사용되었다. 언어의 " 구문 (syntax)" 은 " 정규언어 " 의범위를벗어나기때문에 " 정규식 " 으로표현이불가능하다. 본장에서배우는 " 문맥자유문법 " 은언어의 " 구문 (syntax)" 을표현할수있는도구이다. 어떤 " 문맥자유문법