##// END OF EJS Templates
sync
cin -
r167:96681e9d0cea ref20160224
parent child
Show More
@@ -4,14 +4,14 using System.Collections.Generic;
4 using System.Linq;
4 using System.Linq;
5
5
6 namespace Implab.Automaton {
6 namespace Implab.Automaton {
7 public class DFATransitionTable<TTag> : IDFATableBuilder {
7 public class DFATransitionTable : IDFATableBuilder {
8 DFAStateDescriptior[] m_dfaTable;
8 DFAStateDescriptior[] m_dfaTable;
9
9
10 int m_stateCount;
10 int m_stateCount;
11 int m_symbolCount;
11 int m_symbolCount;
12 int m_initialState;
12 int m_initialState;
13
13
14 readonly Dictionary<int, TTag[]> m_finalStates = new Dictionary<int, TTag[]>();
14 readonly HashSet<int> m_finalStates = new HashSet<int>();
15 readonly HashSet<AutomatonTransition> m_transitions = new HashSet<AutomatonTransition>();
15 readonly HashSet<AutomatonTransition> m_transitions = new HashSet<AutomatonTransition>();
16
16
17
17
@@ -32,10 +32,10 namespace Implab.Automaton {
32 public bool IsFinalState(int s) {
32 public bool IsFinalState(int s) {
33 Safe.ArgumentInRange(s, 0, m_stateCount, "s");
33 Safe.ArgumentInRange(s, 0, m_stateCount, "s");
34
34
35 return m_finalStates.ContainsKey(s);
35 return m_dfaTable != null ? m_dfaTable[s].final : m_finalStates.Contains(s);
36 }
36 }
37
37
38 public IEnumerable<KeyValuePair<int,TTag[]>> FinalStates {
38 public IEnumerable<int> FinalStates {
39 get {
39 get {
40 return m_finalStates;
40 return m_finalStates;
41 }
41 }
@@ -55,8 +55,8 namespace Implab.Automaton {
55
55
56 #endregion
56 #endregion
57
57
58 protected virtual DFAStateDescriptior<TTag>[] ConstructTransitionTable() {
58 protected virtual DFAStateDescriptior[] ConstructTransitionTable() {
59 var dfaTable = new DFAStateDescriptior<TTag>[m_stateCount];
59 var dfaTable = new DFAStateDescriptior[m_stateCount];
60
60
61 foreach (var pair in m_finalStates) {
61 foreach (var pair in m_finalStates) {
62 var idx = pair.Key;
62 var idx = pair.Key;
@@ -1,22 +1,14
1 using System;
1 using System;
2 using System.Collections.Generic;
2
3
3 namespace Implab.Automaton {
4 namespace Implab.Automaton {
4 public interface IDFATableBuilder : IDFATable {
5 public interface IDFATableBuilder : IDFATable, ICollection<AutomatonTransition> {
5 /// <summary>
6 /// <summary>
6 /// Marks the state as final.
7 /// Marks the state as final.
7 /// </summary>
8 /// </summary>
8 /// <param name="state">State.</param>
9 /// <param name="state">State.</param>
9 void MarkFinalState(int state);
10 void MarkFinalState(int state);
10
11
11 /// <summary>
12 /// Defines the transition from <paramref name="s1"/> to
13 /// <paramref name="s2"/> with input <paramref name="symbol"/>.
14 /// </summary>
15 /// <param name="s1">S1.</param>
16 /// <param name="s2">S2.</param>
17 /// <param name="symbol">Symbol.</param>
18 void DefineTransition(int s1, int s2, int symbol);
19
20 void SetInitialState(int s);
12 void SetInitialState(int s);
21
13
22 }
14 }
@@ -8,6 +8,11 namespace Implab.Automaton {
8 /// <summary>
8 /// <summary>
9 /// Indexed alphabet is the finite set of symbols where each symbol has a zero-based unique index.
9 /// Indexed alphabet is the finite set of symbols where each symbol has a zero-based unique index.
10 /// </summary>
10 /// </summary>
11 /// <remarks>
12 /// Indexed alphabets are usefull in bulting efficient translations from source alphabet
13 /// to the input alphabet of the automaton. It's assumed that the index to the symbol match
14 /// is well known and documented.
15 /// </remarks>
11 public abstract class IndexedAlphabetBase<T> : IAlphabetBuilder<T> {
16 public abstract class IndexedAlphabetBase<T> : IAlphabetBuilder<T> {
12 int m_nextId = 1;
17 int m_nextId = 1;
13 readonly int[] m_map;
18 readonly int[] m_map;
General Comments 0
You need to be logged in to leave comments. Login now