C\#품사 분석 기의 변환 DFA 상세 설명
30898 단어 C\#문법 분석 기DFA 변환
DFA 는 NFA 와 유사 하지만 간단 한 것 이 많 으 려 면 새로운 상 태 를 추가 하 는 방법 하나만 있 으 면 된다 고 밝 혔 다.Dfa 류 의 코드 는 다음 과 같다
namespace Cyjb.Compiler.Lexer {
class Dfa {
// DFA 。
DfaState NewState() {}
}
}
기호 색인 은 현재 수용 상태 에 대응 하 는 정규 표현 식 을 표시 합 니 다.그러나 DFA 의 한 상 태 는 NFA 의 여러 상태 에 대응 할 수 있 기 때문에 DFA 상태의 기호 색인 은 하나의 배열 이다.일반 상태 에서 기호 색인 은 빈 배열 입 니 다.
상태 이동 은 현재 상태 에서 다음 상태 로 어떻게 이동 하 는 지 를 나타 내 며,NFA 를 구성 할 때 문자 클래스 를 구분 하 였 기 때문에 DFA 에 서 는 서로 다른 문자 클래스 에 대응 하 는 이동 을 배열 로 직접 기록 합 니 다(DFA 에 서 는 존재 하지 않 습 니 다).ϵ 전 이 된 것 은 모든 문자 류 에 있 고 하나의 이전 만 있 습 니 다).
NFA 의 상태 정의 에 서 는 상태 유형 속성 이 하나 더 있 지만 DFA 상태 에 서 는 이 속성 이 없다.왜냐하면 Trailing 유형의 상 태 는 DFA 가 문자열 과 일치 할 때 처리 되 기 때문이다(다음 글 에서 설명 할 것 이다).TrailingHead 유형의 상 태 는 DFA 를 구성 할 때 Normal 유형의 상태 와 합 쳐 지기 때문이다(상세 한 내용 은 2.4 절 참조).
다음은 DfaState 클래스 의 정의 입 니 다
namespace Cyjb.Compiler.Lexer {
class DfaState {
// DFA。
Dfa Dfa { get; private set; }
// 。
int Index { get; set; }
// 。
int[] SymbolIndex { get; set; }
// 。
DfaState this[int charClass] { get; set; }
}
}
NFA 를 DFA 로 변환 하고 부분 집합 구조(subset construction)알고리즘 을 사용 합 니 다.이 알고리즘 은'C\#품사 분석 기(3)정규 표현 식'의 3.1 절 에서 언급 한 NFA 와 일치 하 는 과정 과 비슷 하 다.NFA 와 일치 하 는 과정 에서 NFA 의 한 상태 집합 을 사용 합 니 다.그러면 부분 집합 구조 법 은 DFA 의 한 상태 로 NFA 의 한 상태 집합,즉 DFA 가 입력 문자열 a1a 2 를 읽 은 후에 도착 하 는 상태 로 NFA 가 같은 문자열 a1a 2 를 읽 은 후에 도착 하 는 상태 에 대응 합 니 다.
부분 집합 구조 알고리즘 에 필요 한 동작 은 다음 과 같 습 니 다.
조작 하 다.
묘사 하 다.
ϵ-closure(s)
NFA 상태 s 부터 통과 할 수 있 습 니 다.ϵ 도착 할 수 있 는 NFA 상태 집합 이동
ϵ-closure(T)
T 중 어느 NFA 상태 s 부터 통과 할 수 있 습 니 다.ϵ 도착 할 수 있 는 NFA 상태 집합 을 옮 깁 니 다.즉,8746°s*8712°T 입 니 다.ϵ-closure(s)
move(T,a)
T 의 특정한 상태 s 에서 출발 하여 a 로 표 시 된 이동 을 통 해 도착 하 는 NFA 상태 로 집합 할 수 있 습 니 다.
우리 가 찾 아야 할 것 은 NFA N 이 어떤 입력 문자열 을 읽 은 후에 있 을 수 있 는 모든 상태 로 집합 하 는 것 이다.
우선,첫 번 째 문 자 를 읽 기 전에 N 은ϵ-closure(s0)의 모든 상태,그 중 s0 은 N 의 시작 상태 입 니 다.그럼,이때ϵ-closure(s0)는 DFA 의 시작 상 태 를 나타 낸다.
N 이 입력 문자열 x 를 읽 은 후에 집합 T 의 상태 에 있 을 수 있다 고 가정 하면 다음 입력 문 자 는 a 입 니 다.그러면 N 은 move(T,a)의 모든 상태 로 즉시 이동 할 수 있 고 통과 할 수 있 습 니 다.ϵ 옮기다ϵ-closure(move(T,a)의 모든 상태 에서.이런 거 하나하나 다른 거.ϵ-closure(move(T,a)는 DFA 의 상 태 를 나타 낸다.만약 이 설명 이 이해 하기 어렵다 면,뒤에 제 시 된 예 시 를 참고 할 수 있다.
이에 따라 다음 알고리즘(알고리즘 중의 T[a]=U 는 상태 T 의 문자 클래스 a 에 상태 U 의 이전 이 있 음 을 나타 낸다)을 얻 을 수 있 습 니 다
： NFA N
： NFA DFA D
，ϵ-closure(s0) D ，
while ( D T ) {
T
foreach ( a ) {
U=ϵ-closure(move(T,a))
if (U D ) {
U D ，
}
T[a]=U
}
}계산 하 다.ϵ-closure(T)의 과정 은 하나의 상태 집합 에서 시작 되 는 간단 한 그림 검색 과정 으로 DFS 를 사용 하면 이 루어 집 니 다.구체 적 인 알고리즘 은 다음 과 같 습 니 다(ϵ-closure(s)의 알고리즘 도 마찬가지 입 니 다.\epsilon\text{-}closure(\{s\}):
：NFA T
：\epsilon \text{-} closure(T)
T
\epsilon \text{-} closure(T) = T
while ( ) {
t
foreach (u : t \epsilon u) {
if (u
otin \epsilon \text{-} closure(T)) {
\epsilon \text{-} closure(T) = \epsilon \text{-} closure(T) \cup \left\{ u \right\}
u
}
}
} ：NFA T
：move(T,a)
move(T,a) = \emptyset
foreach (u \in T) {
if (u a ， t) {
move(T,a) = move(T,a) \cup \left\{ t \right\}
}
}
2.2
(a|b)*baa NFA ， DFA。 \Sigma = \{a, b\}。
1 (a|b)*baa NFA
2 DFA
3 DFA
2.3
NFA （ ）， ， ， NFA DFA ， DFA， DFA 。 ， DFA DFA ， 。
2.4 DFA
DFA NFA ， NFA 。 ， TrailingHead NFA DFA Normal NFA ， 。
，Normal ，TrailingHead ， int.MaxValue - SymbolIndex DFA ， （ ， ）。
， DFA 。 Normal TrailingHead ， ， 。
2.5
C# ， ， NFA DFA 。 NFA HashSet<NfaState> ， Dictionary<HashSet<NfaState>, DfaState> ， ， ， 。
Nfa ：
View Code
/// <summary>
/// NFA DFA， 。
/// </summary>
/// <param name="headCnt"> 。</param>
internal Dfa BuildDfa(int headCnt) {
Dfa dfa = new Dfa(charClass);
// DFA NFA ，DFA NFA 。
Dictionary<DfaState, HashSet<NfaState>> stateMap =
new Dictionary<DfaState, HashSet<NfaState>>();
// NFA DFA （ ）。
Dictionary<HashSet<NfaState>, DfaState> dfaStateMap =
new Dictionary<HashSet<NfaState>, DfaState>(SetEqualityComparer<NfaState>.Default);
Stack<DfaState> stack = new Stack<DfaState>();
// 。
for (int i = 0; i < headCnt; i++) {
DfaState head = dfa.NewState();
head.SymbolIndex = new int[0];
HashSet<NfaState> headStates = EpsilonClosure(Enumerable.Repeat(this[i], 1));
stateMap.Add(head, headStates);
dfaStateMap.Add(headStates, head);
stack.Push(head);
}
int charClassCnt = charClass.Count;
while (stack.Count > 0) {
DfaState state = stack.Pop();
HashSet<NfaState> stateSet = stateMap[state];
// 。
for (int i = 0; i < charClassCnt; i++) {
// NFA ， Move 。
HashSet<NfaState> set = Move(stateSet, i);
if (set.Count > 0) {
set = EpsilonClosure(set);
DfaState newState;
if (!dfaStateMap.TryGetValue(set, out newState)) {
// .
newState = dfa.NewState();
stateMap.Add(newState, set);
dfaStateMap.Add(set, newState);
stack.Push(newState);
// 。
newState.SymbolIndex = set.Where(s => s.SymbolIndex != Symbol.None)
.Select(s => {
if (s.StateType == NfaStateType.TrailingHead) {
return int.MaxValue - s.SymbolIndex;
} else {
return s.SymbolIndex;
}
}).OrderBy(idx => idx).ToArray();
}
// DFA 。
state[i] = newState;
}
}
}
return dfa;
}
/// <summary>
/// NFA ϵ 。
/// </summary>
/// <param name="states"> ϵ NFA 。</param>
/// <returns> ϵ 。</returns>
private static HashSet<NfaState> EpsilonClosure(IEnumerable<NfaState> states) {
HashSet<NfaState> set = new HashSet<NfaState>();
Stack<NfaState> stack = new Stack<NfaState>(states);
while (stack.Count > 0) {
NfaState state = stack.Pop();
set.Add(state);
// ϵ 。
int cnt = state.EpsilonTransitions.Count;
for (int i = 0; i < cnt; i++) {
NfaState target = state.EpsilonTransitions[i];
if (set.Add(target)) {
stack.Push(target);
}
}
}
return set;
}
/// <summary>
/// NFA 。
/// </summary>
/// <param name="states"> NFA 。</param>
/// <param name="charClass"> 。</param>
/// <returns> 。</returns>
private static HashSet<NfaState> Move(IEnumerable<NfaState> states, int charClass) {
HashSet<NfaState> set = new HashSet<NfaState>();
foreach (NfaState state in states) {
if (state.CharClassTransition != null && state.CharClassTransition.Contains(charClass)) {
set.Add(state.CharClassTarget);
}
}
return set;
}
이 실현 에서 DFA 의 시작 상태의 기호 색인 을 빈 배열 로 설정 하면 빈 문자열$\epsilon$가 일치 하지 않 습 니 다.즉,DFA 는 한 글자 가 적 게 일치 합 니 다.이러한 방법 은 어법 분석 에서 의미 가 있다.왜냐하면 어소 가 빈 문자열 이 될 수 없 기 때문이다.2.6 DFA 의 데 드 상 태 는 엄 밀 히 말 하면 상기 알고리즘 에서 얻 은 DFA 는 하나의 DFA 가 아 닐 수 있 습 니 다.DFA 는 모든 상태 가 문자 류 에 있 고 하나의 이전 만 요구 하기 때 문 입 니 다.위의 알고리즘 이 생 성 된 DFA 는 일부 문자 클래스 에서 전이 되 지 않 을 수 있 습 니 다.알고리즘 에서 이 전이 에 대응 하 는 NFA 상태 집합 이 빈 집합 이면 이 전 이 를 무시 하기 때 문 입 니 다.엄격 한 DFA 라면 이 때 는 죽은 상태$\empty set$로 이동 하 는 것 을 추가 해 야 합 니 다.그러나 어법 분석 에 서 는 이 DFA 에 의 해 받 아들 여 질 가능성 이 언제 존재 하지 않 는 지 알 아야 정확 한 어소 가 일치 하 는 지 알 수 있다.따라서 어법 분석 에서 죽은 상태 에 이 르 는 전 이 는 제거 되 고 특정한 입력 기호 에서 의 전환 을 찾 지 못 하면 이때 정확 한 어소(마지막 종결 상태 에 대응 하 는 어소)와 일치 했다 고 생각 합 니 다.3.DFA 의 간소화 3.1 DFA 는 위 에서 사용 가능 한 DFA 를 구 조 했 지만 가장 좋 은 것 이 아 닐 수 있 습 니 다.예 를 들 어 아래 의 두 등가 의 DFA 는 모두 정규 표현 식(a|b)*baa 를 식별 하지만 서로 다른 상태 수 를 가지 고 있 습 니 다
그림 4 두 등가 의 DFA 는 분명히 상태 수가 적은 DFA 일수 록 일치 할 때의 효율 이 높 기 때문에 DFA 의 상태 수 를 최소 화 하 는 알고리즘,즉 DFA 의 간소화 가 필요 하 다.DFA 를 간소화 하 는 사상 은 등가 상 태 를 찾 는 것 이다.그들 은 모두 수용 상태 이 고 임 의적 인 입력 에 대해 항상 등가 상태 로 이전 하 는 것 이다.모든 등가 의 상 태 를 찾 으 면 그것들 을 하나의 상태 로 합 쳐 DFA 상태 수 를 최소 화 할 수 있다.등가 상 태 를 찾 는 데 는 일반적으로 두 가지 방법 이 있다.분할법 과 합병 법 이다.분할법 은 먼저 모든 수용 상태 와 모든 비 수용 상 태 를 두 개의 등가 상태 로 집합 한 다음 에 안에서 부 등가 상태 부분 집합 을 나 누 어 나머지 모든 등가 상태 집합 이 재 분 리 될 때 까지 나 눌 수 없다.합병 법 은 먼저 모든 상 태 를 부 등가 로 간주 한 다음 에 그 안에서 두 개(또는 여러 개)의 등가 상 태 를 찾 아 하나의 상태 로 합병 하 는 것 이다.두 가지 방법 모두 DFA 의 간소화 가 가능 하지만 합병 법 은 비교적 복잡 하기 때문에 여기 서 나 는 분할법 으로 DFA 를 간소화 했다.DFA 최소 화 알고리즘 은 다음 과 같다.실제 구현 에서 주의해 야 할 것 은 하나의 DFA 상태 가 여러 개의 서로 다른 종결 부호 에 대응 할 수 있 기 때문에 초기 상 태 를 구분 할 때 대응 하 는 종결 부호 의 서로 다른 종결 상태 도 서로 다른 그룹 으로 나 누 어야 한 다 는 것 이다.3.2 DFA 최소 화 예시 아래 그림 4(a)를 예 로 들 어 DFA 최소 화 예 시 를 제시한다.초기 구분 은 두 그룹 을 포함 합 니 다.첫 번 째 분할 은\{A,B,C,D\}그룹 에서 문자 a,상태 A,B,C 는 모두 그룹 내 상태 로 이동 하고 상태 D 는 그룹\{E\}으로 이동 하기 때문에 상태 D 는 구분 되 어야 합 니 다.문자 b 에 대해 서 는 모든 상태 가 이 그룹 내 상태 로 옮 겨 져 구분 할 수 없습니다.\{E\}그룹 에는 한 상태 만 포함 되 어 있 으 며 더 이상 구분 할 필요 가 없습니다.이번 라운드\Pi {new} = \left\{ \{A, B, C\}, \{D\}, \{E\} \right\}。두 번 째 분할 은\{A,B,C\}그룹 에서 문자 a,상태 A,B 는 모두 그룹 내 상태 로 이동 하고 상태 C 는 그룹\{D\}으로 이동 하 며 문자 b 는 구분 할 수 없습니다.그룹\{D\}과 그룹\{E\}은 구분 하지 않 습 니 다.이번 라운드\Pi {new} = \left\{\{A, B\}, \{C\}, \{D\}, \{E\} \right\}。세 번 째 분할 은 유일 하 게 분 단 될 수 있 는 그룹\{A,B\}입 니 다.문자 a 와 문자 b 는 같은 그룹 으로 이동 하기 때문에 분할 되 지 않 습 니 다.그래서final} = \left\{ \{A, B\}, \{C\}, \{D\}, \{E\} \right\}。마지막 으로 최소 화 된 DFA 를 구성 합 니 다.\Pi {에 대응 하 는 네 가지 상태 입 니 다.final}의 네 개의 그룹.각각 A,C,D,E 를 각 조 의 대표 로 뽑 았 는데 그 중에서 A 는 시작 상태 이 고 E 는 수용 상태 이다.모든 상 태 를 B 로 옮 기 는 것 을 A 로 옮 기 는 것 으로 수정 하고 마지막 으로 받 은 DFA 변환 표 는 DFA 상태 a 의 이전 b 의 이전 AACCDCDECEAC 로 마지막 에 상 태 를 다시 정렬 하여 그림 4(b)와 같은 DFA 를 얻 었 다.3.3 문자 류 는 DFA 를 최소 화 한 후에 문자 류 도 최소 화해 야 한다.DFA 의 최소 화 과정 은 등가 상 태 를 합 칠 수 있 기 때문에 그림 5 와 같이 일부 문자 류 를 등가 로 만 들 수 있다
그림 5 등가 의 문자 류 등가 문자 류 의 찾기 는 등가 상태 보다 간단 하 다.먼저 간소 화 된 DFA 를 표 형식 으로 쓰 고 그림 5 의 DFA 를 예 로 들 면 DFA 상태 a 의 전이 b 의 전이 c 의 전이 ABB\empty setBBBCC\empty set\empty set\\empty set 표 칸 의 첫 번 째 열 은 DFA 의 상태 이다.뒤의 세 열 은 각각 서로 다른 문자 류 의 이전 을 대표 한다.표 의 두 번 째 줄 에서 네 번 째 줄 까지 각각 A,B,C 세 가지 상태의 전이 에 대응 하고 있다.그렇다면 이 표 의 두 열 이 완전히 같다 면 해당 하 는 문자 류 는 등가 이다.DFA 와 문자 류 를 간소화 하 는 실현 코드 가 비교적 많 습 니 다.여 기 는 붙 이지 않 습 니 다.Dfa 류 를 참조 하 십시오.마지막 으로 간략하게 얻 은 DFA 는 일반적으로 이전 표 형식 으로 저장 되 며,아래 세 개의 배열 을 사용 하면 DFA 를 완전 하 게 표시 할 수 있다 ： DFA $D$
： $D$ DFA $D'$
$D$ $\Pi$， ：
while (true) {
foreach ( $G \in \Pi$) {
$G$ ， $s$ $t$ ，$s$ $t$ $\Pi$
}
$\Pi _{new}$
if ($\Pi_{new}
e \Pi$) {
$\Pi = \Pi_{new}$
} else {
$\Pi _{final} = \Pi$
break;
}
}
$\Pi _{final}$ ， $D'$ 。
$D'$ $D$ 。
$D'$ $D$ 。
$s$ $\Pi_{final}$ $G$ （ ）， $D'$ $s$ ， $G$ 。
그 중에서 CharClass 는 문자 류 의 맵 표 로 길이 가 65536 인 배열 로 문 자 를 해당 하 는 문자 류 로 표시 합 니 다.Transitions 는 DFA 의 전이 표 로 줄 수 는 DFA 의 상태 수 와 같 고 열 수 는 문자 류 의 개수 이다.SymbolIndex 는 모든 상태 에 대응 하 는 기호 색인 입 니 다.물론 DFA 의 이전 표 와 기호 색인 을 압축 하여 메모 리 를 절약 할 수도 있 지만 이것 은 나중에 다시 이야기 하 자.좋은 웹페이지 즐겨찾기
