2장 스캐닝 scanning

token을 만든다. 논리적인 단위.

Regular expression - 문자열의 패턴

Regular expression 연산

1) choice : L(a|b|c|d) = {a,b,c,d}

2) concatenation : L((a|b)c) = {ac,bc}

3) repetition : L((a|bb)*) = {ε,a,bb,aa,abb,bba,bbbb,...}

우선순위 : repetition > concatenation > choice

a|bc* = a|(b(c*))

regular definition(정규정의)

정규 표현식이 기니까 이름 부여

digit = 0|1|2|...|9

정규표현식 extention

    1) 최소 한번이상 반복 '+'

    (0|1)+ = (0|1)(0|1)*

    2) 임의의문자 '.'

    .*b.*

    3) 문자의범위 [0-9]

    [a-zA-Z] 모든 영어 대문자, 소문자

    4) 주어진 집합에 속하지 않는 임의의 문자

    [^abc]  a또는 b또는 c가 아닌 임의의 문자

    5) 선택적 부분표현식 '?'

    signedNatural = (+|-)? natural

    signedNatural = natural | +natural | -natural이랑 의미가 같다.

프로그래밍언어의 토큰의 범주

Number 

reserved word(keyword) : if, while, do

special symbol : <,> :=, ++

identifier : 연문자로 시작하는 영문자와 숫자의 나열

literal : 문자열 리터널, ‘Hello world’

constant : 수치

disambiguating

<> 는 여러가지로 해석될 수 있다. < , > , <>

문자열이 식별자 또는 키워드일 때 일반적으로 키워드가 우선적용.

Principle of longest substring : 단일 토큰을 구성할 수 있는 가장 긴 문자열을 토큰으로 한다. 

Whitespace

token delimiter ( 토큰 분리자) 역할

newline, blank, tab, comment

lookahead

분리자가 토큰에 포함되어서는 안된다.

xtemp=ytemp에서 =는 다음 토큰을 위해 입력에 남아 있어야 한다.

backup이 필요.

Finite automata(유한 오토마타)

알고리즘 기술 방법.

패턴을 인식하는 과정을 표현하는데 이용.

Deterministic Finite Automata (DFA)

하나의 상태와 symbol(문자)가 주어지면 다음 상태는 유일하다.

Nondeterministic finite Autumata(NFA)

하나의 상태와 symbol이 주어지더라도 다음 상태는 유일하지 않은 것.

주석은 regular expression으로 표현하려면 복잡한데, DFA로 쉽게 표현할 수 있다.

longest substring 원리에 따라 토큰 생성. lookahead를 해서 분리자(delimiting)은 다시 입력 문자열로 돌려준다.

DFA는 각 token 마다 하나씩 있다. 이 DFA를 합칠 수 있다.

하지만 체계적인 방법이 아니다.

체계적인 방법

Regular expression -> NFA -> DFA

NFA에는 ε전이가 있다.입력문자열을 안보고 가는 전이.

ε로 각 automata를 합칠 수 있다.

DNF 구현방법

이중 case문 써서 바깥 case는 상태, 안쪽 case는 transition(전이)에 따른 상태변화.

테이블 방식(table-driven), 테이블이 주어지면 코드를 만들 수 있다.

정규표현식을 DFA로 변환

1) 정규표현식 -> NFA

2) NFA -> DFA

ε를 없애야 한다. 그리고 하나의 상태와 하나의 문자로 상태 여러개를 나타낼 수 없도록.

Ε-closer이용 - 상태집합. 한 상태에서 0이상의  ε-transitions로 갈 수 있는 모든 상태의 집합.

두 상태집합을 Union 한 것은 그 상태에서 갈 수 있는 모든 상태들의 집합이다.

symbol이 하나 들어올 때마다 나오는 subset이 state가 된다.

DFA의 상태의 수 최소화하기

처음엔 최상의 시나리오로  전체 nonaacepting, accepting끼리 묶는다. 

nonaccepting집합에 있는 모든 상태가 그 상태집합의 모든 전이에 의해 nonaccepting 집합에 있는 상태로 간다면 그 집합을 새로운 상태로 정의할 수 있다.

accepting도 비슷함.

만족하지 않는 상태들은 따로  분리.

이 과정을 집합이 하나의 상태만 가지고 있을 때까지 반복.

Lex는 lex 문법에 맞게 정규표현식을 구현하면 scanner를 자동으로 생성해주는 프로그램이다.