Lexical Analysis 1 컴파일러 입문 제 4 장 어휘 분석

Lexical Analysis Page 2 목 차목 차목 차목 차 4.1 서론 4.2 토큰 인식 4.3 어휘분석기의 구현 4.4 렉스 (Lex)

Lexical Analysis Page 서 론  어휘분석  원시프로그램을 하나의 긴 문자열로 보고 차례대로 문자를 검사하여 문법적으로 의미 있는 최소의 단위로 분할 해내는 것  어휘분석기  Scanner  Lexer

Lexical Analysis Page 4  토큰  문법적으로 의미 있는 최소 단위 (terminal symbol) Token Number - 토큰들을 효율적으로 처리하기 위한 고유의 내부번호. Token Value 토큰이 프로그래머가 사용한 값을 가질 때 그 값을 말한다 명칭의 토큰값은 그 자신의 스트링 값 상수의 토큰값은 그 자신의 상수 값

Lexical Analysis Page 5 ex) if ( a > 10 )... Token Number : Token Value : 0 0 ‘ a ’

Lexical Analysis Page 6  토큰의 종류 일반 형태 특수 형태 명 칭 상 수 지정어 연산자기호 구분자 : stk, ptr, exp 등 : 526, 2.3, “string” 등 : begin, end, for, goto 등 : +, -, *, /, <, := 등 : ;,,, (, [, : 등

Lexical Analysis Page 7  Lexical Analyzer 와 Parser 의 관계  Scanner 는 Parser 가 token 이 필요할 때 호출하는 서브루틴 L.A.  Finite Automata. S.A.  Pushdown Automata.  Token type  scanner 가 parser 에게 넘겨주는 토큰 형태. (token number, token value) ex) if ( x > y ) x = 10 ; (32,0) (7,0) (4,x) (25,0) (4,y) (8,0) (4,x) (23,0) (5,10) (20,0)

Lexical Analysis Page 8  Symbol table  L.A 와 S.A 시 identifier 에 관한 정보를 수집하여 저장.  Semantic analysis 와 Code generation 시에 사용.  name + attributes ex) Hashed symbol table  chapter 12 참조

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

Lexical Analysis Page 10  Character classification  letter : a | b | c... | z | A | B | C | … | Zl  digit : 0 | 1 | 2... | 9 d  special character : + | - | * | / |. |, |...

Lexical Analysis Page 명칭의 인식  Transition diagram  Regular grammar S  lA | _A A  lA | dA | _A | ε  Regular expression S = lA + _A = (l + _)A A = lA + dA + _A + ε = (l + d + _)A + ε = (l + d + _) *  S = (l + _)( l + d + _) *

Lexical Analysis Page 정수 상수의 인식  Form : 10 진수, 8 진수, 16 진수로 구분되어진다. 10 진수 : 0 이 아닌 수 시작 8 진수 : 0 으로 시작, 16 진수 : 0x, 0X 로 시작  Transition diagram n : non-zero digit o : octal digit h : hexa digit

Lexical Analysis Page 13  Regular grammar S  nA | 0B A  dA | ε B  oC | xD | XD | ε C  oC | ε D  hE E  hE | ε  Regular expression E = hE + ε = h*ε = h* D = hE = hh* = h + C = oC + ε = o* B = oC + xD + XD + ε = o + + (x + X)D = o + + (x + X)h + + ε A = dA + ε = d* S = nA + 0B = nd* + 0(o + + (x + X)h + + ε) = nd* o + + 0(x + X)h + ∴ S = nd* o + + 0(x + X)h +

Lexical Analysis Page 실수 상수의 인식  형태 : 고정소수점 수와 보동소수점 수  Transition diagram  Regular grammar S  dA D  dE | +F | -G A  dA |.B E  dE |ε B  dC F  dE C  dC | eD |ε G  dE

Lexical Analysis Page 15  Regular expression 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 + + e = 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 + 를 ‘+' 로 표기.

Lexical Analysis Page 스트링 상수의 인식  Form : a sequence of characters between a pair of double quotes.  Transition diagram where, a = char_set - {", \} and c = char_set  Regular grammar S  "A A  aA | "B | \C B  ε C  cA

Lexical Analysis Page 17  Regular expression A = aA + " B + \C = aA + " + \cA = (a + \c)A + " = (a + \c)* " S = " A = "(a + \c)*" ∴ S = "(a + \c)* "

Lexical Analysis Page 주석의 처리  Transition diagram where, a = char_set - {*} and b = char_set - {*, /}.  Regular grammar S  /A A  *B B  aB | *C C  *C | bB | /D D  ε

Lexical Analysis Page 19  Regular expression C = *C + bB + /D = * * (bB + /) B = aB + ** * (bB + /) = aB + ** * bB + ** * / = (a + ** * b)B + ** * /= (a + ** * b) * ** * / A = *B = *(a + ** * b) * ** * /  S = /A = /* (a + ** * b) * ** * /  A program which recognizes a comment statement. do { while (ch != ' * ' ) ch = getchar(); ch = getchar(); } while (ch != ' / ' );

Lexical Analysis Page 어휘분석기의 구현  어휘분석기 설계방법  범용 프로그래밍 언어를 사용.  어휘분석 생성기 LEX 를 이용.  Programming vs. Constructing

Lexical Analysis Page 21  The Tokens of Mini C  Special symbols (30 개 ) !!=%=&& ()* *=+ +++=,--- -= //=;< >= []{ ∥ }  Reserved symbols (7 개 ) const else if int return void while  State diagram for Mini C-- pp  Mini C Scanner Source-- pp

Lexical Analysis Page LEX - A Lexical Analyzer Generator M.E. Lesk Bell laboratories, Murry Hill, N.J October, 1975

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

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

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

Lexical Analysis Page 26  * : 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

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

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

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