C# 利用NFA数据生成DFA文件数据

private void button7_Click(object sender, EventArgs e) { //清空listView2中的所有项 listView2.Items.Clear();

//获取NFA数据
string[] nfaData = new string[listView1.Items.Count + 2];
nfaData[0] = '开始符:' + textBox1.Text;
nfaData[1] = '终结符:' + textBox2.Text;
for (int i = 0; i < listView1.Items.Count; i++)
{
    nfaData[i + 2] = listView1.Items[i].SubItems[0].Text + '\t' + listView1.Items[i].SubItems[1].Text + '\t' + listView1.Items[i].SubItems[2].Text;
}

//利用NFA数据生成DFA数据
string[] dfaData = GenerateDFAData(nfaData);

//将DFA数据显示在listView2中
for (int i = 0; i < dfaData.Length; i++)
{
    string[] items = dfaData[i].Split('\t');
    ListViewItem lvi = new ListViewItem(items[0]);
    lvi.SubItems.Add(items[1]);
    lvi.SubItems.Add(items[2]);
    listView2.Items.Add(lvi);
}

}

private string[] GenerateDFAData(string[] nfaData) { //获取开始符和终结符 int startSymbol = int.Parse(nfaData[0].Split(':')[1]); string[] endSymbols = nfaData[1].Split(':')[1].Split(';');

//将NFA数据转换为状态转移表
Dictionary<int, Dictionary<int, List<int>>> transitionTable = new Dictionary<int, Dictionary<int, List<int>>>();
for (int i = 2; i < nfaData.Length; i++)
{
    string[] items = nfaData[i].Split('\t');
    int fromState = int.Parse(items[0]);
    int symbol = items[1] == '#' ? -1 : int.Parse(items[1]);
    int toState = int.Parse(items[2]);
    if (!transitionTable.ContainsKey(fromState))
    {
        transitionTable.Add(fromState, new Dictionary<int, List<int>>());
    }
    if (!transitionTable[fromState].ContainsKey(symbol))
    {
        transitionTable[fromState].Add(symbol, new List<int>());
    }
    transitionTable[fromState][symbol].Add(toState);
}

//利用子集构造法生成DFA
Dictionary<List<int>, int> stateMap = new Dictionary<List<int>, int>();
List<List<int>> queue = new List<List<int>>();
List<int> startState = EpsilonClosure(new List<int> { startSymbol }, transitionTable);
stateMap.Add(startState, 0);
queue.Add(startState);
int stateCount = 1;
while (queue.Count > 0)
{
    List<int> currentState = queue[0];
    queue.RemoveAt(0);
    foreach (int symbol in Enumerable.Range(0, 26))
    {
        List<int> nextState = EpsilonClosure(Move(currentState, symbol, transitionTable), transitionTable);
        if (nextState.Count == 0)
        {
            continue;
        }
        if (!stateMap.ContainsKey(nextState))
        {
            stateMap.Add(nextState, stateCount);
            queue.Add(nextState);
            stateCount++;
        }
        int fromState = stateMap[currentState];
        int toState = stateMap[nextState];
        if (fromState == toState)
        {
            continue;
        }
        string symbolStr = symbol == -1 ? '#' : ((char)('a' + symbol)).ToString();
        ListViewItem lvi = new ListViewItem(fromState.ToString());
        lvi.SubItems.Add(symbolStr);
        lvi.SubItems.Add(toState.ToString());
        for (int i = 0; i < endSymbols.Length; i++)
        {
            if (nextState.Contains(int.Parse(endSymbols[i])))
            {
                lvi.SubItems.Add(endSymbols[i]);
            }
        }
        listView2.Items.Add(lvi);
    }
}

//将状态转移表转换为DFA数据
string[] dfaData = new string[stateCount + 2];
dfaData[0] = '开始符:0;';
dfaData[1] = '终结符:';
for (int i = 0; i < endSymbols.Length; i++)
{
    dfaData[1] += endSymbols[i] + ';';
}
for (int i = 0; i < stateCount; i++)
{
    dfaData[i + 2] = i.ToString();
    foreach (int symbol in Enumerable.Range(0, 26))
    {
        if (transitionTable.ContainsKey(i) && transitionTable[i].ContainsKey(symbol))
        {
            List<int> nextStateList = transitionTable[i][symbol];
            if (nextStateList.Count > 0)
            {
                int nextState = stateMap[EpsilonClosure(nextStateList, transitionTable)];
                string symbolStr = symbol == -1 ? '#' : ((char)('a' + symbol)).ToString();
                dfaData[i + 2] += '\t' + symbolStr + '\t' + nextState;
            }
        }
    }
}

return dfaData;

}

private List EpsilonClosure(List states, Dictionary<int, Dictionary<int, List>> transitionTable) { List result = new List(states); Queue queue = new Queue(states); while (queue.Count > 0) { int currentState = queue.Dequeue(); if (transitionTable.ContainsKey(currentState) && transitionTable[currentState].ContainsKey(-1)) { List nextStateList = transitionTable[currentState][-1]; foreach (int nextState in nextStateList) { if (!result.Contains(nextState)) { result.Add(nextState); queue.Enqueue(nextState); } } } } return result; }

private List Move(List states, int symbol, Dictionary<int, Dictionary<int, List>> transitionTable) { List result = new List(); foreach (int state in states) { if (transitionTable.ContainsKey(state) && transitionTable[state].ContainsKey(symbol)) { List nextStateList = transitionTable[state][symbol]; foreach (int nextState in nextStateList) { if (!result.Contains(nextState)) { result.Add(nextState); } } } } return result;