[Compiler] 5. Lexical analysis

Lexical analysis (Scanning)

source code를 읽고 token으로 나눈다.

• token : 집합적 의미를 갖는 문자 sequence
• token은 컴파일러의 parser에 의해 처리된다.

- Token categories

• Reserved words : IF, THEN 등
• Special symbols : +, - 등
• Integers, doubles, floats, delimiters 등

- 입력 문자열에서 token을 식별한다.

• lexeme(string value) : token을 구성하는 실제 문자 시퀀스
• token의 실제 text : "137", "int" 등
• token : lexeme이 속한 general class

- 오류가 거의 감지되지 않는다.

• 유효한 토큰, 잘못된 토큰
• 위치가 잘못된 토큰, 선언되지 않은 식별자, 철자가 잘못된 키워드 등을 찾을 수 없다.
• ex :
  int a double } switch b[2] = ;
  int_type identifier double_type } reserved identifier [number];
  
  • Scanner는 input에 대해 어떠한 에러도 발생시키지 않는다.
  • Syntax analyzer가 에러를 잡을것이다.

 

Scanning a source file

ex)
while (i > 12)
    ++i;

w

h

i

l

e

(

i

>

1

2

)

\n

\t

+

+

i

;

• 앞에서부터 순차적으로 인식한다.

w

h

i

l

e

(

i

>

1

2

)

\n

\t

+

+

i

;

• Reserved word 인식
• Token 인식
• Lexeme (string value)

w

h

i

l

e

(

i

>

1

2

)

\n

\t

+

+

i

;

• Reserved word                         ( identifier  Bigger than       number      )                     +      +  identifier ;
• Lexical analysis가 위에처럼 인식하는 것이다.

 

Extension to regular expressions

- 한 번 이상 반복

• (0 + 1)(0 + 1)* || (0 | 1)(0 | 1)* => 이렇게 표현하기 불편, 아래와 같이 정의
• (0 | 1)+ -> {0, 1, 01, 00, 10, 11, ...}

- 모든 문자

• 일반적인 상황은 알파벳의 모든 문자와 일치해야 한다는 것이다.
• metacharacter
• . (period) : 모든 문자로 매칭 가능
• 모든 문자열은 최소 하나의 b를 표현한다. -> .*b.*

- 문자열의 범위

• Lower case letter : a | b | c | ... | z -> [a-z]
• Digit : [0-9]
• a | b | c -> [abc]
• 여러 범위 가능 : [a-zA-Z], [a-z0-9], [a-zA-Z0-9]

- 지정된 집합에 없는 문자

• 일치시킬 문자 집합에서 단일 문자를 제외할 수 있으면 유용하다.
• not a -> ~a
• a | b | c가 아닌 문자 -> ~(a | b | c)
• 또 다른 표기법 : [^a], [^abc] -> 하지만 비추하는 편

- Optional subexpressions

• 있어도 되고 없어도 된다.
• 예를들어 123, +123, -123은 숫자라는 Token 인식을 위한 것이기 때문에 부호는 optinal하다.
• natural = [0-9]+
• signedNatural = natural | +natural | -natural
• Metacharater ?
  • r? : r의 optional을 표현하는 문자
• signedNatural = (+ | -)? natural

 

Regular expressions for Programming Language tokens

- Number

• A sequence of digits : ex) 113424
• Decimal numbers : ex) 0.34233, 0.34
• Numbers with a exponent (indicate by an E) : ex) 2.7E-2 => E-2 == 10^(-2)
• nat = [0-9]+
• signedNat = (+ | -)? nat
• number = signedNat("."nat)?(E signedNat)?

- Reserved words(예약어)

• 가장 간단한 정규표현식
• reserved = if | while | do | ...

- Identifiers

• 고정되지 않은 문자열
• letter = [a-zA-Z]
• digit = [0-9]
• identifier = letter(letter | digit)*
  => 숫자로 시작하지 않는다.

 

Ambiguity

일부 문자열은 여러 가지 다른 정규 표현식과 일치할 수 있다.

• 예를 들어, reserved와 identifier 둘 모두에 매칭될 경우 무엇을 선택할 것인가?
• Regular expressions 만으로 알 수 없다.

언어의 정의는 disambiguation rules(모호성 규칙)을 제공해야한다.

1. Reserved word : identifier가 될 수 없다.
2. 가장 긴 하위 문자열의 원리 (최대 뭉크의 원리)
   • 문자열이 단일 token이거나 여러 token의 sequence가 될 수 있는 경우, 일반적으로 단일 토큰 해석이 선호된다.
   • variable을 인식할 때 몇개씩 묶어 인식할 것인가? -> 최대한 길게 인식하겠다는 원리
   • ex)
     while -> w, h, i, l, e, while
     variable -> v, a, r, i, a, b, l, e, vari, able, variable
   • Token은 구분 기호 또는 문자다.
     • xtemp = ytemp -> '='는 identifier xtemp를 구분한다. 왜? 
     • 공백, 새 줄, 탭 문자는 일반적으로 구분자로 간주된다.

 

White space

Scanner는 일반적으로 구문 분석에 기여하지 않는 "관심 없는" Token을 폐기한다.

• ex : whitespace, comments 등
• whitespace = (newline | blank | tab | comment)+

+ int ab/**/cd; => error => 주석은 whitespace 취급하기 때문

 

Lookahead

미리 다음에 뭐가 나오는지 보는 것

구분자가 token 문자열을 보내지만 token 자체의 일부가 아니다.

하나의 토큰이 끝나고 다음 토큰이 시작되는 위치를 결정하기 위해 "예측"이 필요할 수 있다.

• ex) xtemp=ytemp
• identifier xtemp의 끝은 =가 발견될 때다.
• =는 인식될 다음 토큰을 나타내므로 입력에 남아있어야 한다.

때로는 한 글자 이상의 사전 검색이 필요할 수 있다. => 한 개만 볼것인가? 여러개 볼 것인가?