Scanner

Word 인식 방법

상태 머신을 사용하고, 정규 표현식으로 구문을 분석한다.

정규 표현식
- Formal language(형식적인 언어)이다.
  - 규칙에 의해 명시된 Symbol의 집합이다.
  - 애매한 부분이 있으면 안된다.

복잡한 Scanner개발 과정을 간소화 하기 위해, Scanner Generator를 사용하여 개발할 수도 있다.

예제

while

fee | fie

while | fee | fie

Transition table

레지스터 : r0, r1, …, r31

Recognizer(인식기)

언어 인식기는 문자열 x를 입력으로 하였을때, x가 언어의 문장인지 여부에 따라 yes 또는 no를 출력으로 하는 프로그램이다.

우리는 전환 다이어그램(DFA)을 구성하여 RE(정규 표현식)를 인식기로 컴파일 할 수 있다.

Scanner는 정규 표현식과 유사한 것을 통해서 자동으로 생성될 수 있다.

DFA를 구성한다.
- RE → NFA → DFA 변환 과정이 중요하다.
상태 최소화 기법을 사용한다.
Scanner에 대한 코드를 내보낸다.

예제

현재 상태에 따라 다음이 정해진다.

Identifier

letter

…

)

digit
- (0 1 2 … 9)
id
- letter(letter digit)*

NFA(비결정론적 유한 오토마타), DFA(결정론적 유한 오토마타)

DFA는 NFA의 특별한 경우이다.

DFA 특징
- 어떠한 상태에도 ε-전환은 없다.
  - NFA는 ε-전환을 가진다.
  - DFA와 NFA의 대표적인 차이점이다.
- 각 상태 s와 입력 기호 a에 대해서 a로 표시된 edge는 최대 하나이다.
- 시작 상태인 S0에서 x로 표시된 edge를 따라 표시된 허용된 상태까지에 대해서 전환 그래프내에 고유한 경로가 존재하면 x를 허용한다.
DFA와 NFA의 공통점
- DFA는 NFA로 시뮬레이션 가능하다.
- NFA는 DFA로 변환이 가능하다.
비결정론적이란
- 하나의 상태에서 값이 들어왔을때, 어떤 상태로 갈지 모르는 것을 의미한다.

NFA 예제

(a|b)*abb

state	a	b
S0	{S0, S1}	{S0}
S1		{S2}
S2		{S3}

S0는 a!에서 여러 전환을 한다.

RE → DFA

RE → NFA w/ε-moves
- 각각의 항을 NFA로 빌드한다.
- 그것들을 ε-moves로 묶는다.
NFA w/ε-moves 를 DFA로 만든다.
- NFA를 시뮬레이션 하기 위해 DFA를 만든다.
- 하위 집합을 만드는 것.
DFA → Minimized DFA
- 호환 가능한 상태를 병합한다.
DFA → RE
- 모든 쌍과 모든 경로들의 문제
- S0 부터 마지막 상태까지의 경로들을 합친다.

이 과정을 반복한다.
RE → NFA w/ε-moves → DFA → Minimized DFA → RE ..

1. RE to NFA

Thompson’s construction(정규 표현식을 NFA로 변환하는 알고리듬)을 보통 사용한다.
NFA 패턴을 사용한다.
각 연산에 대해서, NFA하위 그래프를 생성하여 전체 NFA를 구성한다.

N(A+)를 만드는 방법은 N(A*)에서 S0에서 마지막 상태로 가는 ε을 제거하면 된다.

2. NFA → DFA(Subset construction)

NFA를 시뮬레이션 해야한다.

두 가지 핵심 함수가 있다.
- move(s_i, a)
  - 상태 s_i에서 입력 기호(심볼) a에 대해 가능한 모든 다음 상태들의 집합을 반환한다.
  - NFA에서 전환 규칙에 따라 각 상태와 입력 기호 쌍에 대해 일어날 수 있는 상태 전환을 결정한다.
- ε-closure(s_i)
  - 상태 s_i에서 ε-전환만을 사용하여 도달 가능한 모든 상태들의 집합을 반환한다.
  - move(s_i, ε)처럼 추가 입력이 없을 경우에 바로 다음 상태로 전환이 가능할 때 사용한다.
알고리즘
1. 시작 상태 설정
  - NFA의 시작 상태 s₀에서 ε-전환에 의해 도달 가능한 모든 상태들의 집합을 DFA의 시작 상태로 설정한다.
  - ε-closure 함수를 사용해서 상태를 찾는 것이다.
2. 새로운 상태 집합 생성
  - DFA의 상태에서 입력 기호에 대해 move 함수를 통해 가능한 상태 집합을 찾는다.
  - 찾은 상태 집합에 대해서 ε-closure 함수를 통해, 가능한 상태 집합을 찾는다.
  - S₀ = ε-closure({s₀})
3. 최종적으로 찾은 상태 집합을 DFA에 추가한다.
  - DFA에 대한 전환 테이블에 집합을 추가한다.
4. 추가적인 상태가 나오지 않을 때 까지 이 과정을 반복한다.

예제

states		ε-closure(move(s, *))
DFA	NFA	a	b	c
s₀	q₀	q₁, q₂, q₃, q₄, q₆, q₉	none	none
s₁	q₁, q₂, q₃, q₄, q₆, q₉	none	q₅, q₈, q₉, q₃, q₄, q₆	q₇, q₈, q₉, q₃, q₄, q₆
s₂	q₅, q₈, q₉, q₃, q₄, q₆	none	s₂	s₃
s₃	q₇, q₈, q₉, q₃, q₄, q₆	none	s₂	s₃

s₁, s₂, s₃는 종료 상태이다.

NFA를 DFA로 바꾼 결과

ε-전환이 없기 때문에, NFA보다 작다.
모든 전환은 결정론적이다.
Use same code skeleton as before

	a	b	c
s₀	s₁	none	none
s₁	none	s₂	s₃
s₂	none	s₂	s₃
s₃	none	s₂	s₃

3. DFA → Minimized DFA

DFA에서 동일한 상태 집합을 찾아서 각 집합을 단일 상태로 나타낸다.

알고리즘
1. 서로 동일하지 않은 모든 상태를 찾는다.
- 상태 X와 Y는 다음과 같은 경우에 서로 다른 상태이다.
  - X가 종료 상태, Y는 종료 상태가 아닐 때
  - 서로 같은 입력 기호를 가지더라도 그 이전 상태가 다를 때
    1. 서로 동등하지 않은 쌍은 제거한다.

축소 결과 | | 동일한 상태 | a | b | c | | :—: | :—: | :—: | :—: | :—: | s₀ | {s₀} | s₁ | s₁ | none | none | s₁ | {s₁, s₂, s₃} | none | s₂ | s₃ |

s₁과 s₂, s₂과 s₃는 동일하다.

정규 표현식의 장점

패턴을 지정하는 단순하고 강력한 표기법이다.
많은 종류의 구문을 정규 표현식으로 지정할 수 있다.

Regular language의 한계점

정규 표현식은 균형있고 중첩된 구성을 기술하는데 사용할 수 없다.
- 균형잡힌 괄호 문자열의 집합은 정규 표현식으로 기술할 수 없다.
- 이러한 집합은 Context-free 문법으로 처리할 수 있다.
L = {p^k q^k} (k는 임의의 수이다.)
- 정규 표현식으로 이 내용을 처리할 수 없다.
- Parser로 처리한다.
정규 표현식은 오직 정해진 반복 횟수와 지정되지 않은 반복 횟수만 나타내는데 사용될 수 있다.
- (ε 1)(01)*(ε 0)
- (01 10)+

Lex and Yacc

Scanner와 Parser의 소스 코드를 만드는 데 사용된다.
또 다른 Flex(Lex와 같은 역할), Bison(Yacc과 같은 역할)도 같은 역할을 한다.