4. 어휘 분석(Lexical analysis)

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

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

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

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

4 토큰번호 토큰값 lexeme 각 토큰들을 효율적인 처리하기 위해서 고유의 내부번호
토큰이 프로그래머가 사용한 값을 가질 때 그 값을 말한다 명칭의 토큰값은 그 자신의 스트링 값 상수의 토큰값은 그 자신의 상수 값 예제 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,10) : X (1,20) : Y lexeme Symbol table

5 4-2. 토큰 인식 설계 시 주의사항 상태전이도 프로그래밍 언어의 각 토큰의 구조를 기술 할 때 이용되는
방법인 정규표현을 알고 있어야 하며, 이것들을 식별하기 위한 인식기가 필요한데, 인식기를 설계하는 방법인 상태 전이도와 유한 오토마타를 사용 상태전이도 유한 오토마타를 그림으로 표현한 흐름도로 어떤 모양의 토큰을 인식 할 수 있는지를 쉽게 알 수 있는 그림

6 S A start l, d l  명칭의 인식 S = l(l+d)*  정수의 인식 C B + - d S = ‘+’d+ + -d+ + dd* = (‘+’+ - + )d+

7  실수의 인식 A S B C F G D E start d . e + - S = d+.d+ + d+.d+e(+’+’+ - )d+  스트링의 인식 c S = ´(c + ´ ´)*´

8 4-3. 어휘분석기의 구현 미니 파스칼에 대한 어휘분석기 구현 특수 심벌 단어 심벌

9 4 25 21 18 12 7 1 6 2 22 19 8 11 5 28 32 26 3 13 29 23 15 24 9 31 16 20 14 17 30 27 10 Look up keyword Table A B 출발 b l/d l not l/d not found found d not d ident exit keyword exit number exit ( * not * ) not) and not* not* < > = not >,= not = : . not . + - ; , [ ]  미니 파스칼의 상태전이도

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

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

12 렉스의 정규표현 렉스에서 사용되는 연산자 “ \ [ ] ^ - ? . * + | ( ) $ / { } % < >
“ \ [ ] ^ - ? . * + | ( ) $ / { } % < > “ : “ 사이에 있는 모든 문자는 텍스트문자로 취급 예) ( a“*”b = a * b )  ( a * b = a*b ) \ : 한 개의 문자를 에스케이프 하기 위하여 사용 예) XYZ“++”, “XYZ++”, XYZ\+\+ [] : 문자들의 클래스를 정의하는데 사용 예) [abc] : a, b, c중에서 한문자 - : 범위를 나타내는 연산자 문자 예) [a-z] : a부터 z사이의 문자 중에 한문자 ^ : 여집합을 표현 예) [^*] : *를 제외한 모든 문자 \ : C언어의 에스케이프 문자열로 간주 예) [ \t\n] : 공백, 탭, 개행 문자중의 하나

13 예) [a-zA-Z][a-zA-Z0-9]* : 변수 인식을 위한 정규표현 + : 한번 이상 반복 할 수 있음을 의미
* : 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 ^ : 라인의 시작을 인식 예) ^abc : 라인의 시작에서 abc가 있을 때만 토큰으로 처리 $ : 라인의 끝에서만 인식 / : 접미 문맥을 명시할 때 사용 예) ab/cd : ab다음에 cd가 이어서 있을 때만 ab를 토큰으로 처리 . : .는 newline문자를 제외한 모든 문자들 예) “- -”.* : - -부터 한 라인의 끝까지와 부합 {} : 정의된 이름을 치환식으로 확장 할 때 사용

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

15 스캐너의 생성 및 동작 lex cc 스캐너의 생성과정 렉스의 선택규칙 lex.yy.c 렉스 입력 스캐너 lex library
가장 길게 인식된 토큰을 우선으로 한다. 인식될 수 있는 토큰의 길이가 같은 경우 먼저 나타난 규칙의 정규 표현으로 인식한다. lex cc lex.yy.c 렉스 입력 스캐너 lex library