Closed n4o847 closed 3 years ago
MakeNowJust さんから:
[x] CharSet は EpsilonNFA を構築する際に完全にばらしてください。以降のコードが複雑になっている理由の半分くらいはこのせいだと思います。 文字は string として持つことにして、 EpsilonNFA は次のようにしてみてはどうでしょうか?
CharSet
EpsilonNFA
string
export type NullableTransition = | { epsilon: false; char: string | null; destination: State; } | { epsilon: true; destination: State; };
また、その場合に . の変換をどうするかですが、 null をパターンに現れない文字を表す記号として使うことにしましょう。 例えばパターンが /ab.c/ の場合、パターンには a, b, c が現れるので、アルファベットは 'a', 'b', 'c', null になります。 そして、 . の部分の遷移は 'a', 'b', 'c', null について追加するようにします。 否定クラスの場合も同様に、 例えば /a[^b-d]/ の場合は、アルファベットは 'a', 'b', 'c', 'd', null になって、 [^b-d] の部分の遷移は 'a', null について追加します。
.
null
/ab.c/
a, b, c
'a', 'b', 'c', null
/a[^b-d]/
'a', 'b', 'c', 'd', null
[^b-d]
'a', null
[x] State も string で持つようにした方が、問題が生じにくくて良いです。
State
[x] NonEpsilonNFA 以降の遷移は Map<State, NonNullableTransition[]> ではなく Map<State, Map<string | null, State[]>> のように文字から遷移先へのMapとして持っておくと、NFAからDAFへの決定化などの実装がシンプルになると思います。
NonEpsilonNFA
Map<State, NonNullableTransition[]>
Map<State, Map<string | null, State[]>>
[x] StronglyConnectedComponentNFA や DirectProductNFA などNFAではないものにNFAとついているのが気になります。
StronglyConnectedComponentNFA
DirectProductNFA
NFAではないものにNFAとついているの直しときます
1つ目と3つ目については相談中です
一応全部できたのでissueを閉じます
MakeNowJust さんから:
[x]
CharSet
はEpsilonNFA
を構築する際に完全にばらしてください。以降のコードが複雑になっている理由の半分くらいはこのせいだと思います。 文字はstring
として持つことにして、EpsilonNFA
は次のようにしてみてはどうでしょうか?また、その場合に
.
の変換をどうするかですが、null
をパターンに現れない文字を表す記号として使うことにしましょう。 例えばパターンが/ab.c/
の場合、パターンにはa, b, c
が現れるので、アルファベットは'a', 'b', 'c', null
になります。 そして、.
の部分の遷移は'a', 'b', 'c', null
について追加するようにします。 否定クラスの場合も同様に、 例えば/a[^b-d]/
の場合は、アルファベットは'a', 'b', 'c', 'd', null
になって、[^b-d]
の部分の遷移は'a', null
について追加します。[x]
State
もstring
で持つようにした方が、問題が生じにくくて良いです。[x]
NonEpsilonNFA
以降の遷移はMap<State, NonNullableTransition[]>
ではなくMap<State, Map<string | null, State[]>>
のように文字から遷移先へのMapとして持っておくと、NFAからDAFへの決定化などの実装がシンプルになると思います。[x]
StronglyConnectedComponentNFA
やDirectProductNFA
などNFAではないものにNFAとついているのが気になります。