4. 어휘 분석(Lexical analysis)

Presentation on theme: "4. 어휘 분석(Lexical analysis)"— Presentation transcript:

1 4. 어휘 분석(Lexical analysis)
4-1. 정 의 토큰 인식 4-3. 어휘분석기의 구현 렉스(Lex)

2 1-3. 컴파일러 논리적 구조 (phase) Source code 전 단 부(front-end)
1) Lexical analysis (어휘분석) LL(7장) LR(8장) 2) Syntax analysis (구문분석) Symbol table 3) Semantic analysis (의미분석) Error handle 4) Intermediate code generation (중간코드생성) 5) Code optimization (코드 최적화) 6) Code generation (코드 생성) 후 단 부(back-end) Object code

3 4-1. 정 의 정의 스캐너 (Scanner) = 어휘 분석기(lexical analyzer)
4-1. 정 의 정의 원시 프로그램을 하나의 긴 문자열로 보고 차례대로 문자를 검조(scanning)하여 문법적으로 의미있는 최소의 단위로 분할해 내는 것 token 스캐너 (Scanner) = 어휘 분석기(lexical analyzer) 원시 프로그램을 토큰으로 분리하는 부분

4 Interaction of lexical analyzer with parser
token은 유한 오토마타에 의해 인식 token의 구조는 프로그래밍 언어 설계자나 컴파일러 구현자에 의해 결정 스캐너(scanner) token Source program lexical analyzer Parser (구문분석기) Get next token Symbol table

5 토큰(Token) 문법적 최소단위, terminal symbol 형태 일반 형태 명 칭
명 칭 : l(l+d)* , stk, ptr, sum1 등 상 수 : 526, 2.3, ‘string’ 등 특수 형태 지정어 : begin, end, for, goto 등 연산자기호 : + , - , * , / , < , := 등 구분자 : ; , , , ( , [ , : 등

6 ex) if ( a > 10 )… 토큰 번호(Token number) 토큰 값 (Token value)
토큰들을 효율적으로 처리하기 위한 고유의 내부 번호 즉, 토큰을 대표하는 정수 번호 토큰 값 (Token value) 토큰이 프로그래머가 사용한 값을 가질 때 그 값을 말한다 명칭의 토큰 값은 그 명칭의 스트링 값 상수의 토큰 값은 그 자신의 상수 값 어휘 분석기  구문 분석기 토큰 번호와 토큰 값의 순서쌍 <예 1 > p125 | p131 ex) if ( a > )… Token Number : Token Value : ‘a’

7 Symbol table L.A와 S.A시 identifier에 관한 정보를 수집하여 저장
Semantic analysis와 Code generation시에 사용 name + attributes ex) Hashed symbol table chapter 12 참조 attributes name symbol table bucket F(x) x

8 4-2. 토큰 인식 어휘 분석기 설계 시 주의사항 상태전이도 1. 정규표현을 알고 있어야 함
프로그래밍 언어의 각 토큰 구조를 기술할 때 이용 2. 인식기 설계에 상태 전이도와 유한 오토마타를 사용 상태전이도 유한 오토마타를 그림으로 표현한 흐름도 어떤 모양의 토큰을 인식할 수 있는지를 쉽게 알 수 있는 그림

9 S = nA + 0B = nd* + 0(o+ + (x + X)h* +  )
1) 명칭의 인식(p127~ | p134~) l, d, _ l, _ S A start S = (l + _)(l + d + _)* 2) 정수의 인식 (p128~ | p135~) d S n A start o o B C h x, X h D E S = nA + 0B = nd* + 0(o+ + (x + X)h* +  ) = nd* o+ + 0(x + X)h+

10 3) 실수 상수의 인식(p130~ | p137~) 형태 : 고정소수점 수와 부동소수점 수 Transition diagram
형태 : 고정소수점 수와 부동소수점 수 Transition diagram Regular grammar S  dA D  dE | +F | −G A  dA | .B E  dE |ε B  dC F  dE C  dC | eD |ε G  dE S = d+.d+ + d+.d+e(+’+’+– )d+

11 Regular expression(p131 | p138)
E = dE + ε = d* F = dE = dd* = d G = dE = dd* = d+ D = dE + '+'F + −G = dd* + '+'d+ + − d + = d+ + '+'d+ + − d+ = (ε + '+' + −)d + C = dC + eD + ε = dC+ e(ε + '+' + −)d+ + ε = d*(e(ε + '+' + −) d+ + ε) B = dC=dd*(e(ε + '+' + −)d+ +ε) = d+(e(ε + '+' + −) d+ +ε) A = dA + .B = d*.d+(e(ε + '+' + −)d+ + ε) S = dA = dd*. d+(e(ε + '+' + −) d+ +ε) = d+.d+(e(ε + '+' + −) d+ + ε) = d+.d++ d+.d+e(ε + '+' + −) d+  참고 Terminal +를 `+` 로 표기.

12 4) 스트링 상수의 인식(p132| p139) 형태 : 일련의 문자를 “(double quote)와 “ 사이에 나타냄
Transition diagram where, a = char_set ― {", \} and c = char_set Regular grammar S  "A ∙ ∙ ∙ (1) A  aA | "B | \C ∙ ∙ ∙ (2) B  ε ∙ ∙ ∙ (3) C  cA ∙ ∙ ∙ (4)

13 Regular expression (2)식 A = aA + " B + \C = aA + " + \cA
(3), (4)를 (2)식에 (2)식 A = aA + " B + \C = aA + " + \cA = (a + \c)A + " = (a + \c)* " (1)식 S = " A = "(a + \c)*" ∴ S = "(a + \c)* "

14 5) 주석의 처리(p132~ | p140~) Transition diagram Regular grammar
where, a = char_set ― {  } and b = char_set ― { , /} Regular grammar S  /A ∙ ∙ ∙(1) A  *B ∙ ∙ ∙(2) B  aB | *C ∙ ∙ ∙(3) C  *C | bB | /D ∙ ∙ ∙(4) D  ε ∙ ∙ ∙ (5)

15 A program which recognizes a comment statement. do {
Regular expression (4)식 C = *C + bB + /D = **(bB + /) (3)식 B = aB + *C = aB + ***(bB + /) = aB + ***bB + ***/ = (a + *** b)B + ***/ = (a + ***b)****/ (2)식 A = *B = *(a + ***b)****/ (1)식  S = /A = /* (a + ***b)*** */ A program which recognizes a comment statement. do { while (ch != '*') ch = getchar(); ch = getchar(); } while (ch != '/');

16 Programming vs. Constructing
4.3 어휘분석기의 구현(p134~ | p142~ ) 어휘분석기 설계방법 범용 프로그래밍 언어를 사용. 어휘분석기 생성기 LEX를 이용. Programming vs. Constructing 부록 A( p572~ | p611~) .

17 State diagram for Mini C(p135~136 | p143~144)
The Tokens of Mini C Special symbols (30개) ! != % %= && ( ) * *= + ++ += , - -- -= / /= ; < <= = == > >= [ ] { ∥ } Reserved symbols (7개) const else if int return void while State diagram for Mini C(p135~136 | p143~144) Mini C Scanner Source(p137~140 | p145~148)

18 1) 문법 표현으로부터 terminal symbol들의 형태인
어휘분석기 구현 1) 문법 표현으로부터 terminal symbol들의 형태인 token의 구조 결정 2) token들을 인식할 수 있는 프로그램 작성 i ) 범용 프로그램 언어 사용(C언어 사용) ii ) 어휘분석기 생성기 (Lex를 이용) 어휘분석기를 범용 프로그래밍 언어로 구현 방법 1) 토큰들을 인식하기 위한 유한 오토마타를 상태전이도로 나타냄 2) 그 상태전이도로부터 실제 프로그래밍 언어로 작성

19 4 23 20 1 6 2 24 21 8 5 50 54 3 51 17 9 53 18 22 19 52 36 7 Look up keyword Table A B 출발 b l,d,_ l,_ not l,d,- not found found nonzero d ident exit keyword exit hexa ! = not = % & + : < ) [ ] { }  미니 C의 상태전이도 25 26 27 * not= octal x, X

20 4-4. 렉스(Lex) : A Lexical Analyzer Generator
정의 1975년에 레스크(Lesk, M. E.)에 의해 발표된 어휘분석기 생성기 기능 사용자가 정의한 정규 표현과 실행코드를 입력받아 C언어로 쓰여진 프로그램 출력 렉 스 렉스 입력 (정규표현과 실행코드) (C언어 프로그램) 어휘 분석기 입력 스트림 일련의 토큰들 lex.yy.c

21 렉스(Lex)의 입력 : Lex의 source
렉스의 정규 표현(p145~ |p154~) 렉스의 실행 코드(p148~ |p156~) 스캐너의 생성 및 동작(p150~ |p158~)

22 1) 렉스(Lex)의 입력 : Lex의 source
<정의부분> <예 3> p144|p152 %{ 실행코드를 C언어로 기술할 때 필요한 자료구조, 변수 상수 정의 }% 이름 정의 부분 : 특정한 정규표현을 하나의 이름으로 정의하여 그 형태의 정규표현이 필요 할 때만 쓸 수 있도록 해주는 부분 %% <규칙부분> <예4> p145|p153 :토큰의 형태를 표현하는 정규표현과 그 토큰이 인식되었을 때 처리할 행위를 기술하기 위한 부분인 실행코드 <사용자 부 프로그램 부분> : 렉스의 입력 작성 시 사용되는 부 프로그램들을 정의

23 2) 렉스의 정규 표현(p145~ |p154~) : 토큰의 형태를 정형하게 표현 렉스의 정규 표현 텍스트 문자(text character) 연산자 문자(operator character) Lex regular expression := text character operator character <예> 정규 표현 a* 연산자 문자 text 문자(일반적으로 영문자와 숫자)

24 <예 5> 토큰의 구조를 렉스의 정규 표현으로 나타낸 예 (p148|p156)
 C 언어에서 허용하는 명칭의 정규 표현 (l + _)(l + d + _)* lex의 정규표현 [az AZ_] [az AZ09_]*  정수 상수 : [19][09]*|0([07]+|(x|X)[09AFaf]*)?  실수 : [09]+”.”[09]+(e[+ –]?[09]+)?  주석 : “/*”([^*] | “*”+[^*/])*”*”+”/”

25 렉스에서 사용되는 연산자 – 1(p146~ 147|p154~156) “ \ [ ] ^  ? . * + | ( ) $ / { } % < > “ : “ 사이에 있는 모든 문자는 텍스트 문자로 취급 예) ( a“*”b = a * b )  ( a * b = a*b ) \ : 한 개의 문자를 에스케이프하기 위하여 사용 예) XYZ“++”, “XYZ++”, XYZ\+\+ [ ] : 문자들의 클래스를 정의하는데 사용 예) [abc] : a, b, c중에서 한문자  : 범위를 나타내는 연산자 문자 예) [az] : a부터 z사이의 문자 중에 한 문자 ^ : 여집합을 표현 예) [^*] : *를 제외한 모든 문자

26 렉스에서 사용되는 연산자 - 2 * : 0번 이상 반복을 의미
\ : C언어의 에스케이프 문자열로 간주 예) [ \t\n] : 공백, 탭, 개행 문자 중의 하나 * : 0번 이상 반복을 의미 예) [azAZ][azAZ09]* : 변수 인식을 위한 정규표현 + : 한번 이상 반복할 수 있음을 의미 예) [az]+ : 모든 소문자 문자열을 인식하는 정규표현 ? : 선택을 의미 예) ab?c : abc 또는 ac | : 택일을 위한 연산자 예) (ab | cd) : ab 또는 cd (ab | cd+)?(ef)* : abefef, efefef, cdef, cddd

27 렉스에서 사용되는 연산자 - 3 ^ : 라인의 시작을 인식 예) ^abc : 라인의 시작에서 abc가 있을 때만 토큰으로 처리
$ : 라인의 끝에서만 인식 / : 접미 문맥을 명시할 때 사용 예) ab/cd : ab다음에 cd가 이어서 있을때만 ab를 토큰으로 처리 . : .(dot)는 newline문자를 제외한 모든 문자들 예) “- -” . 는 - -부터 한 라인의 끝까지와 부합 { } : 정의된 이름을 치환식으로 확장할 때 사용

28 <예 6> 렉스의 정규 표현과 실행 코드의 예(p149|p158)
%{ #include <stdio.h>  정의 부분 %} %% int printf(“integer”); { printf(“begin”);  규칙 부분 } printf(“end”);

29 전역변수(p149| p157) 함수 입출력 함수 yytext : 입력 스트림에서 정규 표현하고 매칭된 실제 문자열
yyleng : 매칭된 문자열의 길이를 저장하고 있는 변수 함수 yymore( ) : 현재 매칭된 문자열의 끝에 다음에 인식될 문자열이 덧붙여 지도록 하는 함수 yyless(n) : n개의 문자만을 yytext에 남겨두고 나머지는 다시 처리하기 위하여 입력 스트림으로 되돌려 보내는 함수 yywrap( ) : 렉스가 입력의 끝을 만났을 때 호출하는 함수 정상적인 경우에 복귀 값은 1이다. 입출력 함수 input( ) : 입력 스트림으로부터 다음 문자를 읽는 함수 output(c) : 출력 스트림으로부터 문자 c를 내보내는 함수 unput(c) : 함수 input()에 의해 다시 읽혀지도록 문자c를 입력 스트림으로 되돌려 보내는 기능을 하는 함수

30 스캐너의 생성 및 동작(p150~ | p158~) 스캐너의 생성 과정 렉스의 선택 규칙 lex
토큰을 가장 길게 인식할 수 있는 정규 표현을 선택한다. 인식될 수 있는 토큰의 길이가 같은 경우, 먼저 나타난 규칙의 정규 표현으로 인식한다. <예> integer printf(“Keyword integer\n”); [a z]+ printf(“Identifier = > %s\n”, yytext); 렉스 입력 lex lex.yy.c C compiler 스캐너 *.l lex library