1. 과제 소개
Scanner 는 입력 Character Stream 을 Token Stream 으로 변환하는 역할을 컴파일러 내에서 수행합니다. 각각의 토큰들을 식별하기 위한 Recognizer 들을 내부적으로 가지며, 각각의 Recognizer 는 Scanner Generator 가 RE(Regular Expression)을 바탕으로 생성한 DFA 를 통해 각각의 토큰을 식별합니다.
Scanner Generator 가 RE 를 바탕으로 한 DFA 의 생성은 다음과 같은 과정으로 이루어집니다.
- RE to NFA w/ε-move
- NFA w/ε-moves to DFA
- DFA → Minimized DFA
- DFA→RE
이번 과제는 위 네가지 과정 중 첫번째 단계, RE to NFA w/ε-move 과정에 집중합니다.
본 과제로 (A|B)*ABB 를 NFA 로 변환하는 과정 중 아래 NFA 의 빈칸을 채워보도록 하겠습니다.
2. RE to NFA w/ε-move 패턴
Recognizer 는 DFA 를 통해 RE 로부터 토큰을 식별합니다. 다만, DFA RE 로부터 바로 생성하기 난이도가 상당하기에 먼저 패턴 매칭을 통해 주어진 RE 로부터 NFA 를 생성해내고, 이를 다시 DFA 로 변환하여 Recognizer 를 완성합니다.패턴 매칭은 다음과 같은 패턴들을 이용해 수행됩니다.
1. N(ε)
ε-movement 는 위 그림과 같이 매칭됩니다. ε-movement 는 아무런 입력 character 를 소비하지 않고 다른 상태로 전이 될 수 있음을 의미합니다. ε-movement 를 이용해 연산 우선순위에 따라 상태간 연결하여 여러 RE 조합을 NFA 로 표기할 수 있습니다.
2. N(A)
N(A)는 위 그림과 같이 매칭됩니다. S0 상태에서 A 입력을 받으면 S1 으로의 상태전이가 이루어집니다.
3. N(AB)
N(AB)는 위 그림과 같이 N(A) 와 N(B) 를 ε-move 로 연결하여 만듭니다.
4. N(A|B)
N(A|B)는 위와 같이 매칭될 수 있습니다.
5. N((A|B)*)
(A|B)* 와 같은 RE 는 위 그림과 같이 ε-movement 를 구성하여 만들 수 있습니다.
3.과제결과
위 패턴들을 이용하여 이번 과제 RE, (A|B)*abb를 NFA로 변환하면 다음과 같은 NFA를 얻을 수 있었습니다.
N((A|B)*ABB)
감사합니다.