13 - Lexical analysis

이번엔, analyzer를 통해 정제된 데이터중 ID를 Finite Automata로 변환해 보자.

ID (변수명)은 첫번째가 letter이여야 하고 그 이후에는 Digit 또는 letter이여야 한다.

 

 

 

ID to Automata

---

이를 오토마타로 바꾸면,

가 된다.

식으로 나타내기 위해 편의상 letter는 l로 digit은 d로 표기하도록 하자

 

S = lA

A = lA + dA + epsilon 이 된다.

 

A로 묶으면 A = (l + d)A + epsilon이 되고, 정리하면 A = (l + d)* 가 된다.

A를 S식에 대입하면 최종으로 S = l(l + d)* 이 된다.

해석해보면 처음엔 letter, 그 이후로는 l 또는 d가 무작위로 나올 수 있다는 뜻이다.

 

 

Integer to Automata

---

d는 digit

 

바로 식으로 표현하면,

S = +A + -B + dC
A = dC
b = dC
C = dC + epsilon

이다. C먼저 정리할 수 있기 때문에 정리를 하면,

C = d*가 되고, 이를 A, B에 대입하면 dd* 가 되기 때문에 d+(epsilon을 제외한 d로 구성된 집합)으로 표현할 수 있다.

 

중간정리

S = +A + -B + dC
A = B = d+

이제 대입하면, 문자 + - 와 연산자 + - 가 헷갈리지 않도록 ""로 구별한다.

S = " + "d+ + "-"d+ + d+가 된다. 이를 d+로 묶어 정리하면

(" + " + " - " + epsilon)d+가 된다.

해석하면 앞에 +가 오거나, -가 오거나, 아무것도 없이 숫자가 있으면 Integer로 인식하겠다는 뜻이다.

이렇게 오늘은 간단한 Lexical analysis에 대해 알아보았다.