Compiler 2 - Lexical analyzer & DFA

 token의 pattern을 서술하는 것은 regular language를 사용하고, Finite automata가 이 언어를 받아 해석하는 알고리즘이 된다.

Regular language를 사용하는 이유는 가장 간단하면서 필요한 것을 나타낼 수 있기 때문이다. (Context Free Language 등을 사용해도 되지만, 이 경우 해석하는 알고리즘이 더 복잡해지고, 컴파일러도 복잡해지므로 프로그램도 느려지게 된다.)

Language는 set of string이므로 각 token (ID, num, op) 에 속하는 것들을 모두 받아들일 수 있어야 한다. 예를 들어 ID를 정의하는 language L은 a, b, i, count 등등의 이름을 모두 받아들여야 한다.
이를 위해 해당 token에 알맞은 것을 받을 수 있도록 pattern을 정해야 한다. (by regular expression)

Regular expression : notation to describe pattern of regular languages. regular expression의 조합으로 나타낼 수 있는 언어는 regular language이다.

- Epsilon
- Single alphabet
- Union
- concatenation
- Kleene closure(*)

이 다섯개가 basic regular expression이다. Language와 마찬가지로 이 기본 regular 의 조합으로 나타낼 수 있어야만 regular expression이 된다.

단, Lexical analysis는 Regular Language를 사용하므로 무한 언어를 받아들일 수 없어 syntax error를 찾아낼 수 없다. 그러나 해당 부분의 역할은 그저 token으로 분리하는 것 뿐이므로 충분하다.
이후 Syntax analyzer가 context free language를 사용해 이런 에러를 찾아낸다.

각 토큰을 모두 분리하여 regular expression으로 나타낸 후에는, input string을 해당 token에 알맞는지 아닌지 확인하고 lexeme 단위로 분리해 낼 수 있다.

이렇게 input string을 regular expression으로 판별하는 작업은 앞서 오토마타에서 배운 것 처럼 finite automata를 사용하여 쉽게 해결할 수 있다.

Finite Automata : implementation for recognization tokens
given input string을 주어진 regular expression에 대해 accept or reject하는 machine.

M = { Q, sigma, delta, q0, F}
epsilon move : 아무런 input symbol을 읽지 않고도 state 이동을 할 수 있는 경로(NFA에서만 가능)

lexical analyzer는 transition table을 사용한 자료구조를 참고하여 만들어진다.

DFA & NFA

DFA의 경우, 하나의 symbol에 대해 반드시 하나의 move가 만들어져야 한다. 그러나 NFA는 e-move를 허용하므로 multiple move(transition) for each state/symbol을 허용한다.

각각의 장단을 알아보면, DFA는 모든 경로를 하나로 한정하여 표현해야 하므로 나타내기가 어렵지만, accept 가능하다면 반드시 성공하는 하나의 path만 존재하므로 빠른 실행이 가능하다. 그러나 NFA는 가능한 경로의 move를 그냥 나타내면 되므로 표현하기가 훨씬 편하지만, accepted 일 때도 여러 개의 경로가 가능해 실패할 수 있기 때문에 시간이 좀 더 걸린다.

Lexical analyzer는 NFA와 DFA를 모두 사용한다. Lexical specification - Regular expression - NFA - DFA(transition table form) 의 순으로 구성된다.

Regular expression to NFA (Thomson's construction algorithm) : expression을 sub expression으로 반복적으로 나눈 후 merge 하는 방식으로 작동. (Divide & conquer)

앞서 배운 것 처럼 basic regular expression으로 이루어져야 regular language/expression이 되므로 이를 이용.
여러 regular expression을 분해하여 NFA로 간단히 표현한 후에는, 해당 basic regular expression을 나타내는 각 NFA를 epsilon move를 이용하여 이어주면 된다. (concatenation, Union, Kleene)
단, 이 때 합쳐진 NFA의 start/final state를 알맞게 변경/추가해주어야 한다.

이 단순한 알고리즘은 항상 옳다는 것이 증명되었으므로 일반적으로 간단하게 주어진 regular expression을 NFA로 변경하는데 사용할 수 있다.
그러나 NFA의 특성상 Possible path가 여러 개 발생하고, 필요하지 않은 epsilon move가 많기 때문에 속도가 느려진다.

NFA to DFA
NFA의 필요없는 move, epsilon move를 모두 없앰
- Subset construction algorithm : grouping NFA states that is reachable with input string
오토마타에서 배운 것 처럼, NFA의 state에서 갈 수 있는 state의 집합체를 하나의 state 처럼 생각하여 나타내면 DFA로 바꿀 수 있다. 앞선 알고리즘과 동일하게, 이것도 항상 옳음을 증명한다.

epsilon closure (q^N) : NFA의 state qN에서 epsilon move로 갈 수 있는 모든 state의 set.
이를 확장하여 하나의 state qN 뿐 아니라, 주어진 state의 집합 T에서 갈 수 있는 모든 state의 set을 나타낼 수도 있다. (개별 qN의 Union과 같다)

이런 과정을 통해 생성한 state의 집합 T를 하나의 state로 보고 transition table을 만들면 NFA에서 DFA를 만들어 낼 수 있다.
이 때 NFA의 final state를 포함하는 모든 집합 T가 DFA의 final state가 된다.
이런 과정을 통해 만들어진 DFA는 Lexeme을 token으로 판별하는 lexical analyzer에서 사용된다.

transition table의 특정 state와 특정 token은 compiler design에 의해 분리되고 input string을 분리하여 토큰으로 만들어낼 수 있다. 이런 작업은 별로 복잡한 것이 아니기 때문에 DFA에 의해 이런 transition rule을 만드는 것이 가장 중요하다.