编译原理实验辅助教学系统

目录

一.系统介绍

二.运行结果展示

三.源代码 

一.系统介绍

        本系统是基于C#开发的一个编译原理实验辅助教学系统，包含了词法分析器设计、自动机系统、NFA_DFA_MFA转换、LL(1)分析、LR(0)分析、SLR(1)分析等主要功能的实现。

二.运行结果展示

三.源代码 

namespace work_1
{public partial class Form1 : Form{static List keys = new List() { "int","float","double","char","struct","if","else","for","while","do","return","break","continue","auto","short","long","union","enum","typedef","const","unsigned","signed","extern","register","static","void","switch","case","goto","continue","break","sizeof","default"};static List arithmetics = new List() { "+","-","*","/","++","+="};static List relations = new List() { "<", "<=", "=", "==", ">", ">=", "!=","&","|","&&","||" };static List borders = new List() { ',',';','{','}','(',')','[',']' };//static List labels = new List();static List consts = new List();public Form1(){InitializeComponent();}private void toolStripMenuItem1_Click(object sender, EventArgs e){}private void panel1_Paint(object sender, PaintEventArgs e){}private void menuStrip2_ItemClicked(object sender, ToolStripItemClickedEventArgs e){}private void richTextBox2_TextChanged(object sender, EventArgs e){richTextBox2.ReadOnly = true;}//打开按钮响应private void toolStripButton1_Click(object sender, EventArgs e){OpenFileDialog openFileDialog1 = new OpenFileDialog();DialogResult dr = openFileDialog1.ShowDialog();//获取所打开文件的文件名string filename = openFileDialog1.FileName;if (dr == System.Windows.Forms.DialogResult.OK && !string.IsNullOrEmpty(filename)){StreamReader sr = new StreamReader(filename);richTextBox1.Text = sr.ReadToEnd();sr.Close();}}private void richTextBox1_TextChanged(object sender, EventArgs e){}//打开菜单响应private void 打开ToolStripMenuItem_Click(object sender, EventArgs e){OpenFileDialog openFileDialog1 = new OpenFileDialog();DialogResult dr = openFileDialog1.ShowDialog();//获取所打开文件的文件名string filename = openFileDialog1.FileName;if (dr == System.Windows.Forms.DialogResult.OK && !string.IsNullOrEmpty(filename)){StreamReader sr = new StreamReader(filename);richTextBox1.Text = sr.ReadToEnd();sr.Close();}}保存按钮响应private void toolStripButton2_Click(object sender, EventArgs e){SaveFileDialog saveFileDialog1 = new SaveFileDialog();DialogResult dr = saveFileDialog1.ShowDialog();string filename = saveFileDialog1.FileName;if (dr == System.Windows.Forms.DialogResult.OK && !string.IsNullOrEmpty(filename)){StreamWriter sw = new StreamWriter(filename, true, System.Text.Encoding.UTF8);sw.Write(richTextBox1.Text);sw.Close();}}private void 保存ToolStripMenuItem_Click(object sender, EventArgs e){SaveFileDialog saveFileDialog1 = new SaveFileDialog();DialogResult dr = saveFileDialog1.ShowDialog();string filename = saveFileDialog1.FileName;if (dr == System.Windows.Forms.DialogResult.OK && !string.IsNullOrEmpty(filename)){StreamWriter sw = new StreamWriter(filename, true, System.Text.Encoding.UTF8);sw.Write(richTextBox1.Text);sw.Close();}}//退出按钮响应private void toolStripButton3_Click(object sender, EventArgs e){System.Environment.Exit(0);}//退出菜单响应private void 退出ToolStripMenuItem_Click(object sender, EventArgs e){System.Environment.Exit(0);}//允许编辑private void toolStripButton4_Click(object sender, EventArgs e){//richTextBox1.ReadOnly=false;richTextBox1.Enabled = true;richTextBox2.Enabled = true;richTextBox3.Enabled = true;}//退出编辑（只读）private void toolStripButton5_Click(object sender, EventArgs e){richTextBox1.Enabled=false;richTextBox2.Enabled = false;richTextBox3.Enabled = false;}private void toolStripButton6_Click(object sender, EventArgs e){richTextBox3.Text = null;int a = 89;int b = 90;int num = 0;richTextBox2.Text = string.Format("标识符整数码为{0};常量整数码为{1}\n", a,b);richTextBox2.AppendText("______________________________________________________\n");richTextBox2.AppendText("行号\t单词\t类型\t是否合法\t单词码\n");richTextBox2.AppendText("______________________________________________________\n");string[] str = richTextBox1.Text.Split('\n');//richTextBox2.AppendText(#"{Word}\t关键字\t合法\n");//逐行分析for (int i = 0; i < str.Length; i++){char[] chars = str[i].ToCharArray();List word = new List();//临时保存分解出来的变量,关键字，字符等for (int j = 0; j < chars.Length; ){char ch = chars[j];  //ch=iwhile (ch <= 32 && ch > 0)//跳过不可见字符(空格){if (j < chars.Length - 1){ch = chars[++j];}else{break;}}if (ch >= 'a' && ch <= 'z' || ch >= 'A' && ch <= 'Z')//若以字母开头，判断是关键字还是变量{while (true){word.Add(ch);//保存下来if (j < chars.Length - 1)//是否达到字符数组末尾{ch = chars[++j];}else{string Word = new string(word.ToArray());//判断是关键字还是变量if (keys.Contains(Word))//关键字{//richTextBox2.Text = string.Format("标识符整数码为{0};常量整数码为{1}\n", a,b);richTextBox2.AppendText(String.Format("{0}\t", i + 1));richTextBox2.AppendText($"{Word}\t保留字\t合法\t\t2\n");}else{/*if (!labels.Contains(Word)){labels.Add(Word);}*/richTextBox2.AppendText(String.Format("{0}\t", i + 1));richTextBox2.AppendText($"{Word}\t标识符\t合法\t\t89\n");}word.Clear();j++;break;}if (!(ch >= 'a' && ch <= 'z' || ch >= 'A' && ch <= 'Z' || ch >= '0' && ch <= '9'))//当出现非字母或数字的字符，即到达变量或关键字的结尾{string Word = new string(word.ToArray());if (keys.Contains(Word)){richTextBox2.AppendText(String.Format("{0}\t", i + 1));richTextBox2.AppendText($"{Word}\t保留字\t合法\t\t2\n");}else{/*if (!labels.Contains(Word)){labels.Add(Word);}*/richTextBox2.AppendText(String.Format("{0}\t", i + 1));richTextBox2.AppendText($"{Word}\t标识符\t合法\t\t89\n");}word.Clear();break;}}}else if (ch >= '0' && ch <= '9')//遇到数字开头{int flag = 0;List numbers = new List();while (true){numbers.Add(ch);ch = chars[++j];if (!(ch >= 'a' && ch <= 'z'||ch>='A'&&ch<='Z'|| ch >= '0' && ch <= '9' || ch == '.')){break;}}//分析numbersfor(int k = 0; k < numbers.Count; k++){if (numbers[k] >= 'a' && numbers[k] <= 'z' || numbers[k] >= 'A' && numbers[k] <= 'Z'){string numbers_Word = new string(numbers.ToArray());richTextBox2.AppendText(String.Format("{0}\t", i + 1));//richTextBox2.AppendText(#"{numbers_Word}\t变量\t非法\nrichTextBox2.AppendText($"{numbers_Word}\t标识符\t非法\t\t-1\t<-(错误行)\n");richTextBox3.AppendText(String.Format("{0}行\t", i + 1));richTextBox3.AppendText($"{numbers_Word}\t\t标识符命名错误\n");num++;numbers.Clear();flag = 1;break;}}if (flag == 0){string numbers_Word = new string(numbers.ToArray());richTextBox2.AppendText(String.Format("{0}\t", i + 1));richTextBox2.AppendText($"{numbers_Word}\t常量\t合法\t\t90\n");numbers.Clear();}}else if (ch == '+' || ch == '-' || ch == '*' || ch == '/')//遇到运算符号{string Word;word.Add(ch);ch = chars[++j];if (chars[j - 1] == '-' && ch >= '0' && ch <= 9)//是负数还是-运算符{while (true){word.Add(ch);ch = chars[++j];if (!(ch >= '0' && ch <= '9')){Word = new string(word.ToArray());if (!consts.Contains(Word)){consts.Add(Word);}richTextBox2.AppendText(String.Format("{0}\t", i + 1));richTextBox2.AppendText($"{Word}\t常量\t合法\t\t90\n");word.Clear();break;}}}else if (ch == '+' || ch == '-' || ch == '*' || ch == '/')//判断是否是++、--等运算符{word.Add(ch);ch = chars[++j];}Word = new string(word.ToArray());word.Clear();if (arithmetics.Contains(Word)){richTextBox2.AppendText(String.Format("{0}\t", i + 1));richTextBox2.AppendText($"{Word}\t运算符\t合法\t\t60\n");}}else if (ch == '>' || ch == '<' || ch == '=' || ch == '!')//判断是否是关系运算符{word.Add(ch);ch = chars[++j];if (ch == '='){word.Add(ch);ch = chars[++j];}string Word = new string(word.ToArray());word.Clear();if (relations.Contains(Word)){richTextBox2.AppendText(String.Format("{0}\t", i + 1));richTextBox2.AppendText($"{Word}\t运算符\t合法\t\t40\n");}}else if (borders.Contains(ch))//是否是边界符{//richTextBox2.AppendText("*******************\n");word.Add(ch);if (j < chars.Length - 1){ch = chars[++j];}else{j++;}string Word = new string(word.ToArray());word.Clear();richTextBox2.AppendText(String.Format("{0}\t", i + 1));richTextBox2.AppendText($"{Word}\t界符\t合法\t\t64\n");}else{//richTextBox2.AppendText("*******************\n");j++;}}}richTextBox3.AppendText("____________________________________________\n");richTextBox3.AppendText(String.Format("{0} errors", num));//richTextBox3.Text = String.Format("{0} errors", num);}private void richTextBox3_TextChanged(object sender, EventArgs e){//richTextBox3.ReadOnly = true;}private void 允许编辑ToolStripMenuItem_Click(object sender, EventArgs e){//richTextBox1.ReadOnly = false;}private void 退出编辑ToolStripMenuItem_Click(object sender, EventArgs e){richTextBox1.ReadOnly = true;}private void 词法分析ToolStripMenuItem_Click(object sender, EventArgs e){toolStripButton6_Click(sender, e);}private void 自动机系统ToolStripMenuItem_Click(object sender, EventArgs e){//new Form2().Show();}private void nFADFAMFAToolStripMenuItem_Click(object sender, EventArgs e){new Form2().Show();}private void lL1分析ToolStripMenuItem_Click(object sender, EventArgs e){new Form3().Show();}private void lR0分析ToolStripMenuItem_Click(object sender, EventArgs e){new Form4().Show();}private void sLR1ToolStripMenuItem_Click(object sender, EventArgs e){new SLR_1().Show();}private void Form1_Load(object sender, EventArgs e){}}
}

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
using System.Text.RegularExpressions;
using System.Collections;namespace work_1
{public partial class Form2 : Form{public Form2(){InitializeComponent();button4.Enabled = false;button7.Enabled = false;button9.Enabled = false;}string nfa;string dfa;string re;//正规式private void toolStripContainer1_TopToolStripPanel_Click(object sender, EventArgs e){}private void richTextBox1_TextChanged(object sender, EventArgs e){}private void label5_Click(object sender, EventArgs e){}public bool rep(char x, string s)//判断是否重复{int i = 0;if (s.Length == 0){return true;}while (i < s.Length){if (s[i] == x)return false;i++;}return true;}string s3 = "";public int countap(string s)//统计字母个数{int i = 0;while (i < s.Length){if (s[i] <= 'z' && s[i] >= 'a'){if (rep(s[i], s3))s3 = s3 + s[i];}i++;}return s3.Length;}private void button1_Click(object sender, EventArgs e){//MessageBox.Show("正确的输入");/** Regex r = new Regex("[\\(|\\)|\\*|\\||[a-z]|\\d#949]+");string a = textBox1.Text;bool t = r.IsMatch(a);if (t == false){MessageBox.Show("表达式错误", "提示", MessageBoxButtons.OK, MessageBoxIcon.Error);}else{MessageBox.Show("正确", "提示", MessageBoxButtons.OK, MessageBoxIcon.Information);}*/string Regular;//正规式int i, count = 0;//count用来标记（和）Regular = textBox1.Text;//用户输入的内容为正规式countap(Regular);//统计字母个数if (Regular == "")//如果输入为空白{MessageBox.Show("请输入一个正规式！");return;}if (Regular[0] == '|' || Regular[0] == '*' || Regular[Regular.Length - 1] == '|' || Regular[Regular.Length - 1] == '(')//不能以|、*开头，也不能以|、（结尾{// MessageBox.Show("错误的输入!");MessageBox.Show("表达式错误", "提示", MessageBoxButtons.OK, MessageBoxIcon.Error);return;}for (i = 0; i < Regular.Length; i++)//做循环判断{if ((Regular[i] >= 'a' && Regular[i] <= 'z') || (Regular[i] >= 'A' && Regular[i] <= 'Z') || Regular[i] == '*' || Regular[i] == '|' || Regular[i] == '(' || Regular[i] == ')')//当前为大写（小写）字母或者*、|、（、）{switch (Regular[i]){case '('://if ((i + 1) < Regular.Length){if (Regular[i + 1] == '*' || Regular[i + 1] == '|')//（）内开头也不可以是闭包 {//MessageBox.Show("正规式格式错误!\n (" + Regular[i + 1] + " 不符合要求");MessageBox.Show("表达式错误", "提示", MessageBoxButtons.OK, MessageBoxIcon.Error);return;}if (Regular[i + 1] == ')'){//MessageBox.Show("正规式格式错误!\n （) 不符合要求");MessageBox.Show("表达式错误", "提示", MessageBoxButtons.OK, MessageBoxIcon.Error);return;}}count++;break;case '|'://if ((i + 1) < Regular.Length){if (Regular[i + 1] == '*' || Regular[i + 1] == '|' || Regular[i + 1] == ')'){//MessageBox.Show("正规式格式错误!\n |" + Regular[i + 1] + " 不符合要求");MessageBox.Show("表达式错误", "提示", MessageBoxButtons.OK, MessageBoxIcon.Error);return;}}break;case '*':if ((i + 1) < Regular.Length){if (Regular[i + 1] == '*'){//MessageBox.Show("正规式格式错误!\n **不符合要求");MessageBox.Show("表达式错误", "提示", MessageBoxButtons.OK, MessageBoxIcon.Error);return;}}break;case ')':count--;break;}}else{//MessageBox.Show("正规式格式错误!\n" + Regular[i] + "不符合要求!");MessageBox.Show("表达式错误", "提示", MessageBoxButtons.OK, MessageBoxIcon.Error);return;}if (count < 0)//只要出现）数量大于（时，一定是错误情况{//MessageBox.Show("正规式格式错误!\n括号不匹配!");MessageBox.Show("表达式错误", "提示", MessageBoxButtons.OK, MessageBoxIcon.Error);return;}}if (count != 0)//最终循环结束时，count=0才是括号匹配{//MessageBox.Show("正规式格式错误!\n括号不匹配!");MessageBox.Show("表达式错误", "提示", MessageBoxButtons.OK, MessageBoxIcon.Error);return;}//CreateNFA.Enabled = true;button4.Enabled = true;button7.Enabled = true;button9.Enabled = true;//MessageBox.Show("表达式正确！");MessageBox.Show("表达式正确", "提示", MessageBoxButtons.OK, MessageBoxIcon.Information);}private String addConnect(String s){ // 为表达式加上连接符Stack stack = new Stack();char[] chr = s.ToCharArray();int point = 0;while (point != chr.Length){//Regex r = new Regex("[\\(|\\)|\\*|\\||[a-z]]+");Regex r = new Regex("[(|)|*|||[a-z]]+");   //正则表达式，用来验证正规式Regex r1 = new Regex("[a-z]");// 对*[a-z]的情况在中间加上连接符后入栈if (chr[point] == '*' && point != chr.Length - 1&& r1.IsMatch(chr[point + 1] + "")){stack.push(chr[point]);stack.push('.');}// 对)(、*(、[a-z](的情况在中间加上连接符后入栈else if (chr[point] == '(' && point != 0 && chr[point - 1] != '|'){stack.push('.');stack.push('(');}//[a-z][a-z] 或 )[a-z]else if (point != 0 && r1.IsMatch(chr[point] + "")&& (r1.IsMatch(chr[point - 1] + "") || chr[point - 1] == ')')){stack.push('.');stack.push(chr[point]);}else{stack.push(chr[point]);}point++;}return stack.getString(); //stack:(a*|b)*}private String change(String s){ // 生成后缀表达式char[] chr = s.ToCharArray();int point = 0;Stack stack = new Stack();String str = "";while (point != chr.Length){switch (chr[point]){case '(':stack.push(chr[point]);point++;break;case ')':   //在栈内匹配(，匹配成功则(出栈while (stack.peek() != '(' && !stack.isEmpty()){str += stack.pop();}if (!stack.isEmpty() && stack.peek() == '(')stack.pop();point++;break;case '*':str += chr[point];point++;break;case '|':case '.':while (!stack.isEmpty() && stack.peek() != '('&& stack.peek() != ')'&& !compare(chr[point], stack.peek())){str += stack.pop();}stack.push(chr[point]);point++;break;default:  //[a-z]str += chr[point];point++;break;}}while (!stack.isEmpty()){if (stack.peek() == ')' || stack.peek() == ')')return "";elsestr += stack.pop();}return str;  //str="a*b*}private bool compare(char a, char b){ //比较操作符的优先级if (a == b)return false;if (a == '*')return true;if (a == '.'){if (b == '*')return false;elsereturn true;}return false;}private bool check(String str){ // 对后缀表达式做消除运算Stack stack = new Stack();Stack result = new Stack();char[] chr = str.ToCharArray();Regex r1 = new Regex("[a-z]");for (int i = chr.Length - 1; i >= 0; i--)stack.push(chr[i]);while (!stack.isEmpty()){switch (stack.peek()){case '*':if (!r1.IsMatch(result.peek() + ""))return false;stack.pop();break;case '.':case '|':if (result.length() < 2 || !r1.IsMatch(result.pop() + "")|| !r1.IsMatch(result.peek() + ""))return false;stack.pop();break;default:result.push(stack.peek());stack.pop();break;}}return result.length() == 1 && r1.IsMatch(result.peek() + "");}int x = 1;Stack list = new Stack();Stack res = new Stack();Stack res_T = new Stack();private int getFacoter(){int s = x;x++;return s;}public int[] getElement(Stack stack, int position){int[] result = stack.Pop();if (stack.Count == position){return result;}else{int[] element = getElement(stack, position);stack.Push(element);return element;}}public int[] getfactor(){return getElement(list, 0);}public Stack getlist(){return res;}public void ToNFA(String str){// TODO Auto-generated constructor stubchar[] chr = str.ToCharArray();for (int i = 0; i < chr.Length; i++){char ch = chr[i];int[] a = new int[2];int[] b = new int[2];int[] c = new int[2];switch (ch){case '.':String[] st = new String[3];// 取出list中上面的两个关系a = list.Peek();Console.WriteLine(a);list.Pop();b = list.Peek();Console.WriteLine(b);list.Pop();// 创建新的关系c = new int[2];c[0] = b[0];c[1] = a[1];// 将上面的两个关系替换成新的关系list.Push(c);// 添加新的NFA项st[0] = b[1] + "";st[1] = "#";st[2] = a[0] + "";res.Push(st);break;case '|':c[0] = getFacoter();c[1] = getFacoter();a = list.Peek();list.Pop();b = list.Peek();list.Pop();list.Push(c);String[] st1 = new String[3];String[] st2 = new String[3];String[] st3 = new String[3];String[] st4 = new String[3];st1[0] = c[0] + "";st1[1] = "#";st1[2] = a[0] + "";res.Push(st1);st2[0] = c[0] + "";st2[1] = "#";st2[2] = b[0] + "";res.Push(st2);st3[0] = a[1] + "";st3[1] = "#";st3[2] = c[1] + "";res.Push(st3);st4[0] = b[1] + "";st4[1] = "#";st4[2] = c[1] + "";res.Push(st4);break;case '*':String[] st5 = new String[3];String[] st6 = new String[3];String[] st7 = new String[3];String[] st8 = new String[3];c[0] = getFacoter();c[1] = getFacoter();a = list.Peek();list.Pop();list.Push(c);st5[0] = c[0] + "";st5[1] = "#";st5[2] = c[1] + "";res.Push(st5);st6[0] = c[0] + "";st6[1] = "#";st6[2] = a[0] + "";res.Push(st6);st7[0] = a[1] + "";st7[1] = "#";st7[2] = a[0] + "";res.Push(st7);st8[0] = a[1] + "";st8[1] = "#";st8[2] = c[1] + "";res.Push(st8);break;default:String[] st9 = new String[3];c[0] = getFacoter();c[1] = getFacoter();list.Push(c);st9[0] = c[0] + "";st9[1] = ch + "";st9[2] = c[1] + "";res.Push(st9);break;}}}private void textBox1_TextChanged(object sender, EventArgs e){}private void button2_Click(object sender, EventArgs e){textBox1.Text = "";listView1.Items.Clear();listView2.Items.Clear();listView3.Items.Clear();textBox2.Text = "";textBox3.Text = "";textBox4.Text = "";textBox5.Text = "";textBox6.Text = "";textBox7.Text = "";}private void richTextBox1_TextChanged_1(object sender, EventArgs e){}private void button3_Click(object sender, EventArgs e){listView1.Items.Clear();StreamReader vStreamReader = new StreamReader(@"F:\dfa_read.txt", Encoding.Default);string vLine;while ((vLine = vStreamReader.ReadLine()) != null){string[] vItems = vLine.Split(new char[] { (char)9, ' ' },StringSplitOptions.RemoveEmptyEntries); // 文本的格式得规范用空格还是制表符分隔？这里可以根据情况调整if (vItems.Length <= 0) continue;ListViewItem vListViewItem = new ListViewItem();vListViewItem.Text = vItems[0];for (int i = 1; i < vItems.Length; i++){vListViewItem.SubItems.Add(vItems[i]);}listView1.Items.Add(vListViewItem);}vStreamReader.Close();button4.Enabled = true;button7.Enabled = true;button9.Enabled = true;}private void button6_Click(object sender, EventArgs e){listView2.Items.Clear();StreamReader vStreamReader = new StreamReader(@"F:\todfa2.txt", Encoding.Default);string vLine;while ((vLine = vStreamReader.ReadLine()) != null){string[] vItems = vLine.Split(new char[] { (char)9, ' ' },StringSplitOptions.RemoveEmptyEntries); // 文本的格式得规范用空格还是制表符分隔？这里可以根据情况调整if (vItems.Length <= 0) continue;ListViewItem vListViewItem = new ListViewItem();vListViewItem.Text = vItems[0];for (int i = 1; i < vItems.Length; i++){vListViewItem.SubItems.Add(vItems[i]);}listView2.Items.Add(vListViewItem);}vStreamReader.Close();textBox4.Text = "1";textBox5.Text = "5";button4.Enabled = true;button7.Enabled = true;button9.Enabled = true;}private void button5_Click(object sender, EventArgs e){using (var tw = new StreamWriter(@"F:\t2.txt")){StringBuilder sb;if (listView1.Items.Count > 0){// the actual dataforeach (ListViewItem lvi in listView1.Items){sb = new StringBuilder();foreach (ListViewItem.ListViewSubItem listViewSubItem in lvi.SubItems){sb.Append(string.Format("{0}\t", listViewSubItem.Text));}tw.WriteLine(sb.ToString());}tw.WriteLine();}}MessageBox.Show("保存成功", "提示", MessageBoxButtons.OK, MessageBoxIcon.Information);}private void button8_Click(object sender, EventArgs e){using (var tw = new StreamWriter(@"F:\dfa_save.txt")){StringBuilder sb;if (listView1.Items.Count > 0){// the actual dataforeach (ListViewItem lvi in listView1.Items){sb = new StringBuilder();foreach (ListViewItem.ListViewSubItem listViewSubItem in lvi.SubItems){sb.Append(string.Format("{0}\t", listViewSubItem.Text));}tw.WriteLine(sb.ToString());}tw.WriteLine();}}MessageBox.Show("保存成功", "提示", MessageBoxButtons.OK, MessageBoxIcon.Information);}private void button4_Click(object sender, EventArgs e){/*listView1.Items.Clear(); //清空数据List ch1 = new List();List ch2 = new List();string st = textBox1.Text;string ss = addConnect(st);string ss1 = change(ss);string ss2;if (check(ss1)){ss2 = ss1;}else{ss2 = "";}ToNFA(ss2);foreach (string[] ch in res){String[] st_t = new String[3];st_t[0] = ch[0];st_t[1] = ch[1];st_t[2] = ch[2];res_T.Push(st_t);}int cnt1 = 0, cnt2 = 0;int flag = 0;string t=null;foreach (string[] ch in res_T){ListViewItem item = new ListViewItem();item.Text = ch[0];//记录ch[0]以便判断初始状态集if (!ch1.Contains(ch[0])){ch1.Add(ch[0]);cnt1++;}item.SubItems.Add(ch[1]);item.SubItems.Add(ch[2]);//记录ch[2]以便判断初始状态集if (!ch2.Contains(ch[2])){ch2.Add(ch[2]);cnt2++;}listView1.Items.Add(item);flag++;t = ch[2];}int i, j, flag2 = 0;//flag2用来标记初始终态集for(i = 0; i < cnt1; i++){for(j = 0; j < cnt2; j++){if (ch1[i] == ch2[j]){//ch1.Remove(ch1[i]);//ch2.Remove(ch2[j]);flag2 = 1;break;}}if(flag2 == 0) //找到了初始集{textBox2.AppendText(ch1[i]+" ");//textBox2.Text = ch1.ToString();}flag2 = 0;}int flag3 = 0;for (i = 0; i < cnt2; i++){for (j = 0; j < cnt1; j++){if (ch2[i] == ch1[j]){//ch1.Remove(ch1[i]);//ch2.Remove(ch2[j]);flag3 = 1; break;}}if (flag3 == 0) //找到了终态{textBox3.AppendText(ch2[i] + " ");//textBox2.Text = ch1.ToString();}flag3 = 0;}*///textBox3.Text = t;if (textBox1.Text != ""){string str = textBox1.Text;NFA nFA = new NFA();nFA.SetStr(str);nFA.ExptoNFA();nfa = "开始符:" + nFA.start_state.ToString() + '\n' +"终结符:" + nFA.end_state.ToString() + '\n' +"符号集:";for (int i = 0; i < nFA.list_ch.Count; i++){nfa += nFA.list_ch[i].ToString() + ' ';}nfa += '\n';nfa += nFA.result;string[] ss = nFA.result.Split('\n');listView1.Items.Clear();// 在listViewNFA.Items中显示for (int i = 0; i < ss.Length; i++){string[] sss = ss[i].Split('\t', '\n');ListViewItem list = new ListViewItem(sss[0]);list.SubItems.Add(sss[1]);list.SubItems.Add(sss[2]);listView1.Items.Add(list);}// 输出开始状态集、终态集textBox2.Text = nFA.start_state.ToString();textBox3.Text = nFA.end_state.ToString();button7.Enabled = true;}else{//DialogResult dia = MessageBox.Show("正规式为空！", "提示");//button7.Enabled = false;//buttonMFA.Enabled = false;}listView2.Items.Clear();listView3.Items.Clear();}private void listView1_SelectedIndexChanged(object sender, EventArgs e){}private void listView1_SelectedIndexChanged_1(object sender, EventArgs e){}private void textBox2_TextChanged(object sender, EventArgs e){}private void button7_Click(object sender, EventArgs e){if (nfa != ""){DFA dFA = new DFA(nfa);string str_dfa_result = dFA.NFAtoDFA();string[] str_dfa_splited = str_dfa_result.Split('\n');listView2.Items.Clear();for (int i = 0; i < str_dfa_splited.Length; i++){string[] every_base_state = str_dfa_splited[i].Split('\t', '\n');ListViewItem list = new ListViewItem(every_base_state[0]);list.SubItems.Add(every_base_state[1]);list.SubItems.Add(every_base_state[2]);listView2.Items.Add(list);}textBox4.Text = "0";textBox5.Text = dFA.end_state;dfa = "开始符:0;\n结束符:" + textBox5.Text + "\n" + "最大状态数:" + dFA.count + "\n" + "符号集:";for (int i = 0; i < dFA.to_list.Count; i++){dfa += dFA.to_list[i] + " ";}dfa += "\n" + str_dfa_result;//richTextBox1.Text = dfa;//buttonMFA.Enabled = true;}else{//DialogResult dia = MessageBox.Show("NFA为空！", "提示");//buttonMFA.Enabled = false;}listView3.Items.Clear();}private void textBox4_TextChanged(object sender, EventArgs e){}private void button9_Click(object sender, EventArgs e){if (dfa != ""){MFA Mfa = new MFA(dfa);Mfa.Needless();Mfa.Sameless();listView3.Items.Clear();for (int i = 0; i < Mfa.mfa_list.Count; i++){ListViewItem list = new ListViewItem(Mfa.mfa_list[i].start.ToString());list.SubItems.Add(Mfa.mfa_list[i].to.ToString());list.SubItems.Add(Mfa.mfa_list[i].end.ToString());listView3.Items.Add(list);}textBox6.Text = Mfa.start.ToString();textBox7.Text = Mfa.num_end.ToString();}else{DialogResult dia = MessageBox.Show("DFA为空！", "提示");}}private void Form2_Load(object sender, EventArgs e){}}
}public class Stack
{private int maxSize;// 栈的大小private int top;private char[] arr;public Stack(){maxSize = 30;top = -1;arr = new char[maxSize];}public void push(char value){ // 压入数据arr[++top] = value;}public char pop(){ // 弹出数据return arr[top--];}public char peek(){ // 访问栈顶元素return arr[top];}public bool isFull(){ // 栈是否满了return maxSize - 1 == top;}public bool isEmpty(){ // 栈是否为空return top == -1;}public int length(){ // 栈内元素个数return top + 1;}public String getString(){if (top == -1)return "";String s = "";int point = 0;while (point <= top){s += arr[point];point++;}return s;}
}public class NFA
{public struct FA{public int start;public char to;public int end;}public string str;public string result;public int start_state;         // 记录开始状态public int end_state;           // 记录结束状态// 构造函数public NFA(string str){this.str = str;}public NFA(){}public void SetStr(string str){this.str = str;}// 定义两个list作存储数组public List list_nfa = new List();public List list_ch = new List();public void ExptoNFA()      // 正规式转NFA{string exp_end = ExptoEnd();int state_num = 0;Stack stack_startstate = new Stack();Stack stack_endstate = new Stack();for (int i = 0; i < exp_end.Length; i++){if (char.IsLetter(exp_end[i])){FA nfa1 = new FA();nfa1.start = state_num;stack_startstate.Push(state_num);nfa1.to = exp_end[i];nfa1.end = state_num + 1;stack_endstate.Push(state_num + 1);state_num += 2;list_nfa.Add(nfa1);if (!list_ch.Contains(exp_end[i])){list_ch.Add(exp_end[i]);}}else{if (exp_end[i] == '.'){FA nFA_temp = new FA();int s1, s2, e1, e2;s2 = stack_startstate.Pop();s1 = stack_startstate.Pop();e2 = stack_endstate.Pop();e1 = stack_endstate.Pop();nFA_temp.start = e1;nFA_temp.to = '#';nFA_temp.end = s2;list_nfa.Add(nFA_temp);stack_startstate.Push(s1);stack_endstate.Push(e2);}else if (exp_end[i] == '*'){int s1, e1;s1 = stack_startstate.Pop();e1 = stack_endstate.Pop();FA nFA_temp = new FA();nFA_temp.start = state_num;nFA_temp.to = '#';nFA_temp.end = s1;list_nfa.Add(nFA_temp);nFA_temp.start = e1;nFA_temp.to = '#';nFA_temp.end = state_num + 1;list_nfa.Add(nFA_temp);nFA_temp.start = state_num;nFA_temp.to = '#';nFA_temp.end = state_num + 1;list_nfa.Add(nFA_temp);nFA_temp.start = e1;nFA_temp.to = '#';nFA_temp.end = s1;list_nfa.Add(nFA_temp);stack_startstate.Push(state_num);stack_endstate.Push(state_num + 1);state_num += 2;}else if (exp_end[i] == '|'){FA nFA_temp = new FA();int s1, s2, e1, e2;s2 = stack_startstate.Pop();s1 = stack_startstate.Pop();e2 = stack_endstate.Pop();e1 = stack_endstate.Pop();nFA_temp.start = state_num;nFA_temp.to = '#';nFA_temp.end = s1;list_nfa.Add(nFA_temp);nFA_temp.start = state_num;nFA_temp.to = '#';nFA_temp.end = s2;list_nfa.Add(nFA_temp);nFA_temp.start = e1;nFA_temp.to = '#';nFA_temp.end = state_num + 1;list_nfa.Add(nFA_temp);nFA_temp.start = e2;nFA_temp.to = '#';nFA_temp.end = state_num + 1;list_nfa.Add(nFA_temp);stack_startstate.Push(state_num);stack_endstate.Push(state_num + 1);state_num += 2;}}if (stack_startstate.Count == 1){start_state = stack_startstate.Peek();end_state = stack_endstate.Peek();}}result = NFAtoString(list_nfa);list_ch.Sort();}//public string NFAtoString(List n){string str = "";int i = 0;for (i = 0; i < n.Count - 1; i++){str += n[i].start.ToString() + '\t' + n[i].to + '\t' + n[i].end.ToString() + '\n';}str += n[i].start.ToString() + '\t' + n[i].to + '\t' + n[i].end.ToString();return str;}// 表达式转后缀表达式public string ExptoEnd(){string str_temp = "";string str_result = "";int i = 0;for (i = 0; i < str.Length - 1; i++){str_temp += str[i];if ((char.IsLetter(str[i]) && (char.IsLetter(str[i + 1]) || str[i + 1] == '('))|| (str[i].Equals(')') && char.IsLetter(str[i + 1]))|| (str[i].Equals(')') && str[i + 1].Equals('('))|| (str[i].Equals('*') && (str[i + 1].Equals('(') || char.IsLetter(str[i + 1])))){// 添加 .表示连接运算str_temp += '.';}}str_temp += str[str.Length - 1];Stack op_youxianji_stack = new Stack();        // 判断操作符优先级的栈i = 0;string sign = "(|.*)";      // 处理后的操作符//操作符优先级判断  ) > * > . > | > ( while (i < str_temp.Length){if (char.IsLetter(str_temp[i])){str_result += str_temp[i];      // 字母直接加入}else{if (op_youxianji_stack.Count == 0)     // 栈空，操作符直接加入op_youxianji_stack.Push(str_temp[i]);else{if (str_temp[i] == '(')op_youxianji_stack.Push('(');else if (str_temp[i] == ')'){while (op_youxianji_stack.Peek() != '('){str_result += op_youxianji_stack.Peek();op_youxianji_stack.Pop();}op_youxianji_stack.Pop();}else if (sign.IndexOf(str_temp[i]) > sign.IndexOf(op_youxianji_stack.Peek())){op_youxianji_stack.Push(str_temp[i]);}else{while (op_youxianji_stack.Count > 0 && sign.IndexOf(str_temp[i]) <= sign.IndexOf(op_youxianji_stack.Peek())){str_result += op_youxianji_stack.Peek();op_youxianji_stack.Pop();}op_youxianji_stack.Push(str_temp[i]);}}}i++;}while (op_youxianji_stack.Count != 0){str_result += op_youxianji_stack.Peek();op_youxianji_stack.Pop();}return str_result;}
}public class DFA
{public struct FA{public int start;public char to;public int end;}public List start = new List();//开始状态集public List end = new List();//结束状态集public List to_list = new List();//符号集public int count = 0;//状态数List nfa = new List();public String end_state;public DFA(string str_nfa_rslt)    // 对前一部分的结果进行处理{string[] str1 = str_nfa_rslt.Split('\n');int i = 0;while (i < str1.Length){if (i == 0){string[] str_temp1 = str1[0].Split(':');string[] str_temp2 = str_temp1[1].Split(' ');for (int j = 0; j < str_temp2.Length; j++){start.Add(int.Parse(str_temp2[j]));}}else if (i == 1){string[] str_temp3 = str1[1].Split(':');string[] str_temp4 = str_temp3[1].Split(' ');for (int j = 0; j < str_temp4.Length; j++){end.Add(int.Parse(str_temp4[j]));}}else if (i == 2){string[] str_temp5 = str1[2].Split(':');string[] str_temp6 = str_temp5[1].Split(' ');for (int j = 0; j < str_temp6.Length - 1; j++){to_list.Add(char.Parse(str_temp6[j]));}}else{string[] str = str1[i].Split('\t', '\n', '\r');FA fa_temp = new FA();fa_temp.start = int.Parse(str[0]);fa_temp.to = str[1][0];fa_temp.end = int.Parse(str[2].ToString());nfa.Add(fa_temp);}i++;}}//NFApublic String NFAtoDFA(){List> closure_list = new List>();List list_FA = new List();int index = 0;closure_list.Add(closure(start));while (index < closure_list.Count){List list_t = new List();list_t = closure_list[index];for (int i = 0; i < to_list.Count; i++){if (move(list_t, to_list[i]).Count != 0){List res = new List();res = closure(move(list_t, to_list[i]));int NO = locate(closure_list, res);if (NO == -1){closure_list.Add(res);FA n = new FA();n.start = index;n.to = to_list[i];n.end = closure_list.Count - 1;list_FA.Add(n);}else{FA n = new FA();n.start = index;n.to = to_list[i];n.end = NO;list_FA.Add(n);}}}index++;}count = StatuesNum(list_FA);end_state = end_with(closure_list, end);return NFAtoString(list_FA);}//NFAtoDFApublic List closure(List list){Queue state_queue = new Queue();List closure_result_list = new List();for (int i = 0; i < list.Count; i++){state_queue.Enqueue(list[i]);closure_result_list.Add(list[i]);}while (state_queue.Count != 0){int now_state = state_queue.Peek();state_queue.Dequeue();for (int i = 0; i < nfa.Count; i++){if (nfa[i].start == now_state && nfa[i].to == '#' && find(closure_result_list, nfa[i].end) == -1){state_queue.Enqueue(nfa[i].end);closure_result_list.Add(nfa[i].end);}}}closure_result_list.Sort();return closure_result_list;}public int find(List list_t, int x)     // find函数{for (int i = 0; i < list_t.Count; i++){if (list_t[i] == x)return 1;}return -1;}public List move(List state_list, char to){List move_result_list = new List();for (int i = 0; i < state_list.Count; i++){for (int j = 0; j < nfa.Count; j++){if (state_list[i] == nfa[j].start && nfa[j].to == to){move_result_list.Add(nfa[j].end);}}}move_result_list.Sort();return move_result_list;}//movepublic int locate(List> C, List x)       // 查找x在C中的位置{for (int i = 0; i < C.Count; i++){if (C[i].Count == x.Count){int j;for (j = 0; j < x.Count; j++){if (C[i][j] != x[j])break;}if (j >= x.Count)return i;}}return -1;}public string NFAtoString(List n)       // 转换为固定格式的string{string str = "";int i = 0;for (i = 0; i < n.Count - 1; i++){str += n[i].start.ToString() + '\t' + n[i].to + '\t' + n[i].end.ToString() + '\n';}str += n[i].start.ToString() + '\t' + n[i].to + '\t' + n[i].end.ToString();return str;}public String end_with(List> C, List end){String result = "";for (int i = 0; i < C.Count; i++){for (int j = 0; j < end.Count; j++){if (C[i].Contains(end[j])){result += i.ToString() + ' ';break;}}}return result;}public int StatuesNum(List n){List num_list = new List();for (int i = 0; i < n.Count; i++){if (!num_list.Contains(n[i].start)){num_list.Add(n[i].start);}if (!num_list.Contains(n[i].end)){num_list.Add(n[i].end);}}return num_list.Count;}
}class MFA
{public struct FA{public int start;public char to;public int end;}string Origin;List dfa_list = new List();public List mfa_list = new List();public int start;//开始状态集List end_list = new List();//结束状态集public int num_end;int max_state_count;//最大状态数List sign_list = new List();//符号集public MFA(string str){this.Origin = str;string[] str1 = str.Split('\n');for (int i = 0; i < str1.Length; i++){if (i == 0){string[] str2 = str1[0].Split(':');string[] str3 = str2[1].Split(';');start = int.Parse(str3[0]);}else if (i == 1){string[] str2 = str1[1].Split(':');string[] str3 = str2[1].Split(' ');for (int j = 0; j < str3.Length - 1; j++){end_list.Add(int.Parse(str3[j]));}}else if (i == 2){string[] str2 = str1[2].Split(':');max_state_count = int.Parse(str2[1]);}else if (i == 3){string[] str2 = str1[3].Split(':');string[] str3 = str2[1].Split(' ');for (int j = 0; j < str3.Length - 1; j++){sign_list.Add(str3[j][0]);}}else{string[] str2 = str1[i].Split('\t', '\n');FA fa_temp = new FA();fa_temp.start = int.Parse(str2[0]);fa_temp.to = str2[1][0];fa_temp.end = int.Parse(str2[2]);dfa_list.Add(fa_temp);}}end_list.Sort();sign_list.Sort();}//MFApublic void Needless(){int max_new = max_state_count;List new_count_list = new List();for (int i = 0; i < max_new; i++){new_count_list.Add(0);}Stack stack = new Stack();stack.Push(0);new_count_list[0] = 1;while (stack.Count != 0){int x = stack.Peek();stack.Pop();for (int i = 0; i < dfa_list.Count; i++){if (dfa_list[i].start == x){if (new_count_list[dfa_list[i].end] == 0){stack.Push(dfa_list[i].end);new_count_list[dfa_list[i].end] = 1;}}}}List dfa_new = new List();List end_new = new List();for (int i = 0; i < new_count_list.Count; i++){if (new_count_list[i] == 1){if (end_list.Contains(i)){end_new.Add(i);}for (int j = 0; j < dfa_list.Count; j++){if (dfa_list[j].start == i){dfa_new.Add(dfa_list[j]);}}}}dfa_list.Clear();end_list.Clear();dfa_list = dfa_new;end_list = end_new;}public void Sameless(){List> result = new List>();List e = new List();for (int i = 0; i < dfa_list.Count; i++){if (!end_list.Contains(dfa_list[i].start) && !e.Contains(dfa_list[i].start)){e.Add(dfa_list[i].start);}}e.Sort();if (e.Count != 0)result.Add(e);result.Add(end_list);int count = 0;while (count < result.Count){List E = new List();E = result[count];if (count == result.Count - 1)//终结状态{num_end = findtype(result, E[0]);}List L = new List();for (int i = 0; i < sign_list.Count; i++){int x = findtype(result, findlast(E[0], sign_list[i]));for (int j = 0; j < E.Count; j++){if (findlast(E[j], sign_list[i]) != -1 && findtype(result, findlast(E[j], sign_list[i])) != x && !L.Contains(E[j])){L.Add(E[j]);}}}if (L.Count == 0){count++;}else{List J = new List();for (int x = 0; x < E.Count; x++){if (!L.Contains(E[x])){J.Add(E[x]);}}result.RemoveAt(count);result.Insert(count, J);result.Insert(count + 1, L);}}for (int i = 0; i < result.Count; i++){for (int j = 0; j < dfa_list.Count; j++){if (dfa_list[j].start == result[i][0]){FA fa = new FA();fa.start = findtype(result, dfa_list[j].start);fa.to = dfa_list[j].to;fa.end = findtype(result, dfa_list[j].end);if (!mfa_list.Contains(fa))mfa_list.Add(fa);}}}}public int findlast(int s, char a){for (int i = 0; i < dfa_list.Count; i++){if (dfa_list[i].start == s && dfa_list[i].to == a){return dfa_list[i].end;}}return -1;}public int findtype(List> result, int type){for (int i = 0; i < result.Count; i++){if (result[i].Contains(type))return i;}return -1;}public string FAtoString(List n){string str = "";int i = 0;for (i = 0; i < n.Count - 1; i++){str += n[i].start.ToString() + '\t' + n[i].to + '\t' + n[i].end.ToString() + '\n';}str += n[i].start.ToString() + '\t' + n[i].to + '\t' + n[i].end.ToString();return str;}//public string Test(){string res = "";for (int i = 0; i < sign_list.Count; i++){res += sign_list[i] + " ";}return res;}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！