컴퓨터/컴파일러

2. Lexical Analysis

sidedoor 2024. 7. 10. 15:31

Lexical Analysis는 영어에 비유하자면 단어들을 분리하는 과정을 뜻한다.

즉, program stream을 token들로 분리한다.

예를 들어 Character Stream이 x = (y + 4.0); 으로 주어졌다고 하면 이를 각각의 Token Stream으로 ID, ASSIGN, LPAREN. ID, PLUS, REAL, RPAREN, SEMICOLON으로 토큰으로 구분해 준다.

이때 ID가 함수를 나타내는지 변수를 나타내는지는 알 수 없고 단순히 어떤 것인지 분류만 진행하다. 그리고 나중에 판별할 수 있게 정보를 추가적으로 저장하여 위의 경우의 x는 ID(x)이런 식으로 저장을 해준다.

또한 NUM의 경우도 1:n 대응을 하기 때문에 1개의 type에 해당하는 값이 여러개가 될 수 있어 NUM(100)과 같이 저장되는 정보도 같이 저장해줘야한다.

그리고 이 과정에서 공백은 white space로 제거되고 comments도 동일하게 제거가 된다.

 

TOKEN

Token은 sequence of characters로 유닛 단위로 다뤄진다.

그리고 이는 사용하는 언어마다 다른데 실제로 c언어에서 사용하는 ;기호는 python에 없기 때문에 이에대한 토큰이 없다.

 

LAXER

lexer는 lexical analyzer를 하는 프로그램으로 정규식을 통해서 token에 대한 정의를 하면 lexer generator를 통해 자동으로 lexer가 finite automata로 변환한다.

다만 DFA(deterministic finite automata)로 바로 변환이 힘들기 때문에 NFA(nondeterministic finite automata)로 정규식을 먼저 변환한 뒤 DFA로 변환을 진행한다.

 

RE(regualer expression)

string이 유한개의 알파벳을 가지고 있는 유한한 기호들의 나열이면 정규식은 이러한것들의 집합을 나타낸다.

 

 - 정규식의 기본 표기

- Symbol : 알파벳 1개만 가지고 있는 것으로 a -> {a}, 1 -> {1} 이다.
- Epsilon ϵ : 아무것도 없는 empty expression을 표현하는 것이다.
- Alternation M | N : string의 합집합으로 a -> M, b -> N일때 M|N = {a, b}이다.

- Concatenation MN : 두 string을 연결하는 것으로 (a|b) -> M, (a|c) -> N일때 MN = {a, b}{a, c} = {aa, ac, ba, bc}이다.
- Repetition M* : Kleene clousre로 M을 반복해서 얻을 수 있는 모든 집합을 의미한다. 이때 공집합도 가능하다.

 

- 추가적인 표기

▪ [abcd] : (a | b | c | d)
▪ [b-g] : [bcdefg]
▪ [b-gM-Qkr]: [bcdefgMNOPQkr]
▪ M? : (M | ϵ)
▪ M+ : MM*
▪ . : newline을 제외한 모든 1자리 문자

▪ “a.+*” : 문자 그대로의 의미를 쓰고 싶을 때 

 

사용 예시

a, b로 이루어진 string중에서 a, b가 번갈아 나오는 것

(ab)*(ϵ|a)|(ba)*(ϵ|b)

 

다만 유한개의 사건으로 결정을 할 수 없는 조건의 경우 정규식으로 표현할 수 없다.

 

Finite Automata

유한개의 메모리를 가지고 있는 계산하는 모델로 1개의 start state를 가지고 1개 혹은 그 이상의 final states를 가진다.

그리고 각각의 state들을 edge들로 연결을 하는데 이때 edge들이 각각 1개의 symbol로 표현 된다.

 

- Non-deterministic Finite Automata(NFA)

노드를 떠난 edge에 같은 label이 붙을 수 있고 edge가 ϵ으로 라벨링 될 수 있는 유한 오토마타이다.

NFA의 경우 accept으로 이어지는 경로가 있는 모든 경우에 대해서 accept이 된다

NFA 예시

 

 

- Deterministic Finite Automata (DFA)

edge들이 유일하게 라벨 된 것으로 start state에서 시작하여 input string에 있는 문자들을 다 집어넣은 다음에 정확히 1개의 edge를 따라서 다음 state로 이동한다.

이렇게 모든 문자가 끝난 뒤에 final state에 있다면 accept이고 없으면 reject가 된다.

그리고 중간에 넘어갈 edge가 없는 경우도 reject으로 처리가 된다.

 

DFA예시

 

NFA to DFA

edge(s, c): 1개의 edge를 통해서 도달할 수 있는 모든 state로 s는 state를 의미하고 c는 label을 의미한다.closure(s): 어떤 input없이 도달할 수 있는 NFA state로 ϵ으로만 연결된 모든 state를 의미한다.DFAedge(d, c): c와 ϵ을 사용해서 도달 가능한 모든 state를 의미한다. 즉, 𝐷𝐹𝐴𝑒𝑑𝑔𝑒𝑑,𝑐=𝑐𝑙𝑜𝑠𝑢𝑟𝑒(∪𝑠∈𝑑𝑒𝑑𝑔𝑒𝑠,𝑐)

 

변환 알고리즘은 다음과 같다.

𝑠𝑡𝑎𝑡𝑒𝑠[0] ← { } # 전부 새로 할당해야 하기 때문에 새로운 state만든다
𝑠𝑡𝑎𝑡𝑒𝑠[1] ← 𝑐𝑙𝑜𝑠𝑢𝑟𝑒({𝑠1}) # start state의 coloure

𝑝 ← 1, 𝑗 ← 0

while 𝑗 ≤ 𝑝
	foreach 𝑐 ∈ Σ
        𝑒 ← 𝐷𝐹𝐴𝑒𝑑𝑔𝑒(𝑠𝑡𝑎𝑡𝑒𝑠[𝑗],𝑐)
        if 𝑒 = 𝑠𝑡𝑎𝑡𝑒𝑠[𝑖] for some 𝑖 ≤ 𝑝 # 이미 있는것은 추가 안한다
            then 𝑡𝑟𝑎𝑛𝑠[𝑗,𝑐] ← 𝑖
        else 𝑝 ← 𝑝 + 1 # 없는 경우 새로 만든다.
            𝑠𝑡𝑎𝑡𝑒𝑠[𝑝] ← 𝑒
            𝑡𝑟𝑎𝑛𝑠[𝑗,𝑐] ← 𝑝
    𝑗 ← 𝑗 + 1

 

이러한 알고리즘을 거쳐도 아직 중복되는 state들이 남을 수 있어 동일한 state들을 제거해줘야 한다.

만약 두 노드의 상태가 모두 final이거나 non-final로 동일하고, 어떤 symbol c에 대해서도 trans[node1, c] = trans[node2, c]로 같은 곳으로 trans되는 경우 두 노드가 동일하다고 할 수 있다. 따라서 이러한 노드는 합쳐서 하나로 써주면 된다.

동일한 노드 예시

애매한 것에 대한 규칙

- Longest match: 정규식과 일치하는 가장 긴 초기 부분 문자열이 다음 토큰으로 사용된다.

if8과 같은 입력이 주어진다면 이를 ID("if8")로 인식이 되고 IF()와 NUM(8)이 되지 않는다.

 

- Rule priority: 같은 길이의 정규식이 주어진 경우 사용자가 먼저 정의한 규칙을 따른다.

따라서 만약 ID("IF")가 아니라 IF()와 매치하고 싶으면 IF()에 대한 정의를 먼저 배치해야한다.