正规式、NFA、DFA、MFA的转换

1、word计算机专业软件类课程实验报告课程名称：编译原理实验题目：正规式、NFA、DFA、MFA的转换实验小组成员：实验小组组长：任课教师：专业名称：计算机科学与技术班级名称：计科1班实验起止时间：2022-5-192022-5-29一、实验目的1、理解什么是正规式2、理解NFA、DFA、MFA的概念；3、掌握正规式和NFA之间的等价变换；4、掌握NFA和DFA之间的等价变换；5、掌握DFA和MFA之间的等价变换；6、了解程序设计语言Java的语言机制。2、 实验内容程序的流程图如下所示：1、 根据用户输入的表达式，验证是否为合法的正规式2、根据正规式，将其转换为NFA3、根据NFA，将其转换为

2、DFA4、根据DFA，将其转换为MFA3、 实验需求1、 正规式验证对输入的表达式能够做出正确的判断，如果是合法的正规式，那么激活正规式转为NFA的功能；如果不是合法的正规式，那么会弹出消息框进行提示2、 正规式转为NFA对经过验证的正规式，根据算法，将其转换为NFA，得出开始符号集、终结符号集以及符号集，并激活NFA转为DFA的功能；也可以点击翻开按钮，选择一个格式符合标准的NFA文件，同时激活NFA转为DFA的功能；也可以对得到的NFA进行保存3、 NFA转为DFA对第一个文本框中的NFA，根据算法，将其转换为DFA，得出开始符号集、终结符号集以及符号集，并激活DFA转为MFA的功能；也可

3、以点击翻开按钮，选择一个格式符合标准的DFA文件，同时激活DFA转为MFA的功能；也可以对得到的DFA进行保存4、 DFA转为MFA对第二个文本框中的DFA，根据算法，将其转换为MFA，得出开始符号集、终结符号集以及符号集；也可以点击翻开按钮，选择一个格式符合标准MFA文件；也可以对得到的MFA进行保存4、 主要数据结构介绍1、 自定义一个JavaBean，这个类里只有三个属性，节点的开始符号，接受符号，终结符号，并有他们的get()、set()方法，将类名定义为Node2、 整个程序涉及到的NFA、DFA、MFA都存放在ArrayList<Node>中，每次通过迭代器Iterat

4、or<Node>进行迭代3、 在正规式转为NFA时，将创立一个开始符号栈和一个终结符号栈，分别用来存储开始符号和终结符号4、 在NFA转换为DFA时，创立一个对象数组Object2，每个数组单元第一列为ArrayList<String>，存放的是节点号，第二列是一个Boolean，标记该状态T是否被访问过5、 在DFA转换为MFA时，创立一个对象数组Object，每个数组单元为ArrayList<String>，存放的是每次划分的节点信息5、 主要模块算法介绍1、 正规式验证将输入的正规式使用toCharArray()转换成一个一个字符，然后对字符进行处理，

5、主要是验证左右括号是否匹配正确，以及|，.，*等符号位置是否合法，输入的表达式中是否含有非法字符2、正规式转为NFA对经过验证的正规式进行一个字符一个字符的判断，其中*的优先级最高，其次是.，最后是|。在转换过程中，构造两个栈，一个栈是开始符号栈，用来存放创立的开始符号，一个是终结符号栈，用来存放创立的终结符号。通过对|，.，*优先级的的不同，对两个栈进行不同的处理，将产生的结点存入ArrayList<Node>中3、NFA转为DFA将从第一个文本框中读出的NFA节点信息存入ArrayList<Node>，由迭代器进行迭代，算法的流程如下列图所示：开始求开始状态闭包标记

6、令它为集合C中的唯一成员集合C中存在尚未被标记子集标记对子集中的每个输入字母求a子集将参加中结束语是否4、 DFA转为MFA化简DFA的根本思想是指导它的状态分成一些互不相交的子集，每一个子集中的状态都不是等价的，不同子集中的状态可以由某个输入串来区别，最后将不能区别的每个子集用一个状态来做代表，这种方法称为“分割法。具体过程是：1将M的所有状态分成两个子集终态集和非终态集；2考察每一个子集，假设发现某子集中的状态不等价，将其划分为两个集合；3重复第2步，继续考察已得到的每一个子集，直到没有任何一个子集需要继续划分为止。这时DFA的状态被分成假设干个互不相交的子集。4从每个子集中选出一个状态做

7、代表即可得到最简的DFA。6、 程序实现环境及使用说明本次实验采用Eclipse进行代码的编写、编译及运行；编写语言为java语言；程序的运行环境为jdk1.8；系统为windows 8.17、 实验测试用例设计说明1、 正规式验证（1） 输入，这是一个错误的输入（2） 输入ab|b，这是一个正确的输入2、 正规式转为NFA（1） 输入ab|b，这是一个不含闭包的例子（2） 输入(a*|b)*，这是一个含有闭包的例子3、 NFA转为DFA1输入ab|b，这是一个不含闭包的例子2输入(a*|b)*，这是一个含有闭包的例子4、 DFA转为MFA1输入ab|b，这是一个不含闭包的例子2输入

8、(a*|b)*，这是一个含有闭包的例子八、实验结果测试情况9、 小组对实验结果的自我评价通过这次实验，我对正规式、NFA、DFA、MFA有了一定的了解，进一步的稳固了这局部的知识。懂得了他们之间转化的原理。在编程过程中，遇到了不少的问题，在同学的帮助下，问题一步一步的得到了解决。同时，实验期间，老师也对程序进行了测试评价，发现了一些错误，比方，在将正规式转为NFA时，连接运算符与或运算符之间的处理出现了一些问题；还有，在最后将DFA转为MFA时，在MFA中出现了没有对相同的两项进行冗余处理。这些问题也在实验后期进行了一一解决。由于编程能力和时间的缺乏，这个转换器还有待完善，可能还有没有测试出来

9、的错误。对于出错处理也考虑得不够周到。望老师多多指教。十、任课教师对实验结果的评分源码FrameView.javapackage view;import java.awt.BorderLayout;import java.awt.Event;import java.awt.FileDialog;import ;import java.awt.Font;import java.awt.GridLayout;import java.awt.ScrollPane;import java.awt.datatransfer.Clipboard;import java.awt.datatransfer.D

10、ataFlavor;import java.awt.datatransfer.StringSelection;import java.awt.datatransfer.Transferable;import java.awt.event.ActionEvent;import java.awt.event.ActionListener;import java.awt.event.KeyEvent;import java.awt.event.MouseAdapter;import java.awt.event.MouseEvent;import java.awt.event.WindowAdapt

11、er;import java.awt.event.WindowEvent;import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.File;import java.io.FileReader;import java.io.FileWriter;import java.io.IOException;import javax.swing.JDialog;import javax.swing.JFrame;import javax.swing.JMenu;import javax.swing.JMenuBa

12、r;import javax.swing.JMenuItem;import javax.swing.JOptionPane;import javax.swing.JPanel;import javax.swing.JPopupMenu;import javax.swing.JTextArea;import javax.swing.KeyStroke;import javax.swing.event.DocumentEvent;import javax.swing.event.DocumentListener;import javax.swing.event.UndoableEditEvent;

13、import javax.swing.event.UndoableEditListener;import javax.swing.undo.UndoManager;public class FrameView extends JFrame implements ActionListener,DocumentListener, UndoableEditListener JFrame f = new JFrame("词法分析器");ScrollPane jspa = new ScrollPane();ScrollPane jspb = new ScrollPane();Scro

14、llPane jspc = new ScrollPane();JPopupMenu pop = new JPopupMenu();JTextArea ta = new JTextArea();JTextArea tb = new JTextArea();JTextArea tc = new JTextArea();JPanel pa = new JPanel();JPanel pb = new JPanel();JOptionPane jop = new JOptionPane();UndoManager um = new UndoManager();JMenuBar bar = new JM

15、enuBar();JMenu file = new JMenu("文件");JMenu edit = new JMenu("编辑");JMenu analysis = new JMenu("词法分析");JMenu help = new JMenu("帮助");JMenuItem open = new JMenuItem("翻开");JMenuItem save = new JMenuItem("保存");JMenuItem saveNew = new JMenuItem(&

16、quot;另存为");JMenuItem exit = new JMenuItem("退出");JMenuItem back = new JMenuItem("撤销");JMenuItem cut = new JMenuItem("剪切");JMenuItem copy = new JMenuItem("复制");JMenuItem paste = new JMenuItem("粘贴");JMenuItem del = new JMenuItem("删除");JMe

17、nuItem all = new JMenuItem("全选");JMenuItem lexical = new JMenuItem("词法分析器");JMenuItem nfadfamfa = new JMenuItem("NFA_DFA_MFA");JMenuItem sHelp = new JMenuItem("查看帮助");JMenuItem about = new JMenuItem("关于");JMenuItem back1 = new JMenuItem("撤销"

18、;);JMenuItem cut1 = new JMenuItem("剪切");JMenuItem copy1 = new JMenuItem("复制");JMenuItem paste1 = new JMenuItem("粘贴");JMenuItem del1 = new JMenuItem("删除");JMenuItem all1 = new JMenuItem("全选");FileDialog openDia = new FileDialog(f, "翻开", File

19、Dialog.LOAD);FileDialog saveDia = new FileDialog(f, "保存", FileDialog.SAVE);AboutFile prompta;File fe;Clipboard clipboard = null;boolean isSave, change, isLine;String select;public FrameView() isSave = false;change = false;isLine = true;setup();f.addWindowListener(new WindowAdapter() public

20、 void windowClosing(WindowEvent we) if (isSave = false) && (change = true) Prompt dg = new Prompt(f, "词法分析器", true); elseSystem.exit(0););ta.setFont(new Font("宋体", 0, 20);ta.setLineWrap(true);tb.setEditable(false);tc.setEditable(false);pack();f.setBounds(300, 100, 750, 55

21、0);f.setVisible(true);public void setup() setLayout(new BorderLayout();f.setJMenuBar(bar);jspa.add(ta);jspb.add(tb);jspc.add(tc);pb.setLayout(new GridLayout(2, 1);pb.add(jspb);pb.add(jspc);pa.setLayout(new GridLayout(1, 2);pa.add(jspa);pa.add(pb);f.add(pa);bar.add(file);bar.add(edit);bar.add(analysi

22、s);bar.add(help);file.add(open);file.add(save);file.add(saveNew);file.addSeparator();file.add(exit);edit.add(back);edit.addSeparator();edit.add(cut);edit.add(copy);edit.add(paste);edit.add(del);edit.addSeparator();edit.addSeparator();edit.add(all);edit.addSeparator();analysis.add(lexical);analysis.a

23、dd(nfadfamfa);help.add(sHelp);help.add(about);pop.add(back1);pop.addSeparator();pop.add(cut1);pop.add(copy1);pop.add(paste1);pop.add(del1);pop.addSeparator();pop.add(all1);open.setMnemonic('O');open.setAccelerator(KeyStroke.getKeyStroke(KeyEvent.VK_O,Event.CTRL_MASK);save.setMnemonic('S&

24、#39;);save.setAccelerator(KeyStroke.getKeyStroke(KeyEvent.VK_S,Event.CTRL_MASK);saveNew.setMnemonic('A');saveNew.setAccelerator(KeyStroke.getKeyStroke(KeyEvent.VK_A,Event.SHIFT_MASK);exit.setMnemonic('X');exit.setAccelerator(KeyStroke.getKeyStroke(KeyEvent.VK_X,Event.SHIFT_MASK);back

25、.setMnemonic('Z');back.setAccelerator(KeyStroke.getKeyStroke(KeyEvent.VK_Z,Event.CTRL_MASK);cut.setMnemonic('X');cut.setAccelerator(KeyStroke.getKeyStroke(KeyEvent.VK_X,Event.CTRL_MASK);copy.setMnemonic('C');copy.setAccelerator(KeyStroke.getKeyStroke(KeyEvent.VK_C,Event.CTRL_

26、MASK);paste.setMnemonic('V');paste.setAccelerator(KeyStroke.getKeyStroke(KeyEvent.VK_V,Event.CTRL_MASK);del.setMnemonic('L');del.setAccelerator(KeyStroke.getKeyStroke(KeyEvent.VK_DELETE, 0);all.setMnemonic('A');all.setAccelerator(KeyStroke.getKeyStroke(KeyEvent.VK_A,Event.CTR

27、L_MASK);lexical.setMnemonic('L');lexical.setAccelerator(KeyStroke.getKeyStroke(KeyEvent.VK_L,Event.CTRL_MASK);nfadfamfa.setMnemonic('N');nfadfamfa.setAccelerator(KeyStroke.getKeyStroke(KeyEvent.VK_N,Event.CTRL_MASK);sHelp.setMnemonic('H');sHelp.setAccelerator(KeyStroke.getKey

28、Stroke(KeyEvent.VK_H,Event.SHIFT_MASK);about.setMnemonic('B');about.setAccelerator(KeyStroke.getKeyStroke(KeyEvent.VK_B,Event.SHIFT_MASK);back1.setMnemonic('Z');back1.setAccelerator(KeyStroke.getKeyStroke(KeyEvent.VK_Z,Event.CTRL_MASK);cut1.setMnemonic('X');cut1.setAccelerato

29、r(KeyStroke.getKeyStroke(KeyEvent.VK_X,Event.CTRL_MASK);copy1.setMnemonic('C');copy1.setAccelerator(KeyStroke.getKeyStroke(KeyEvent.VK_C,Event.CTRL_MASK);paste1.setMnemonic('V');paste1.setAccelerator(KeyStroke.getKeyStroke(KeyEvent.VK_V,Event.CTRL_MASK);del1.setMnemonic('L');

30、del1.setAccelerator(KeyStroke.getKeyStroke(KeyEvent.VK_DELETE, 0);all1.setMnemonic('A');all1.setAccelerator(KeyStroke.getKeyStroke(KeyEvent.VK_A,Event.CTRL_MASK);open.addActionListener(this);save.addActionListener(this);saveNew.addActionListener(this);exit.addActionListener(this);back.addAct

31、ionListener(this);cut.addActionListener(this);copy.addActionListener(this);paste.addActionListener(this);del.addActionListener(this);all.addActionListener(this);lexical.addActionListener(this);nfadfamfa.addActionListener(this);about.addActionListener(this);sHelp.addActionListener(this);back1.addActi

32、onListener(this);cut1.addActionListener(this);copy1.addActionListener(this);paste1.addActionListener(this);del1.addActionListener(this);all1.addActionListener(this);ta.getDocument().addDocumentListener(this);ta.getDocument().addUndoableEditListener(this);ta.addMouseListener(new MouseAdapter() public

33、 void mousePressed(MouseEvent me) if (me.getButton() = me.BUTTON3) pop.show(ta, me.getX(), me.getY(););public void openFile() openDia.setVisible(true);String dirPath = openDia.getDirectory();String fileName = openDia.getFile();if (dirPath = null | fileName = null)return;ta.setText("");fe =

34、 new File(dirPath, fileName);try BufferedReader in = new BufferedReader(new FileReader(fe);String line = null;while (line = in.readLine() != null)ta.append(line + "rn");in.close();ta.setCaretPosition(0); catch (IOException ioe) System.err.println(ioe);public void saveFile() if (fe = null)

35、saveDia.setVisible(true);String dirPath = openDia.getDirectory();String fileName = openDia.getFile();if (dirPath = null | fileName = null)return;ta.setText("");File fe = new File(dirPath, fileName);isSave = true;change = false;try BufferedWriter out = new BufferedWriter(new FileWriter(fe);

36、String text = ta.getText();out.write(text);out.flush();out.close(); catch (IOException ioe) System.err.println(ioe);public void undoableEditHappened(UndoableEditEvent ue) um.addEdit(ue.getEdit();public void changedUpdate(DocumentEvent e) change = true;public void insertUpdate(DocumentEvent e) change

37、 = true;public void removeUpdate(DocumentEvent e) change = true;public void actionPerformed(ActionEvent ae) if (ta.getText().equals("")change = false;if (ae.getSource() = open) openFile();change = false;if (ae.getSource() = save) if (isSave = false)saveFile();if (ae.getSource() = saveNew)

38、saveFile();if (ae.getSource() = exit) if (isSave = false) && (change = true) Prompt dg = new Prompt(f, "词法分析器", true); elseSystem.exit(0);if (ae.getSource() = back | ae.getSource() = back1) if (um.canUndo() um.undo();if (ae.getSource() = cut | ae.getSource() = cut1) try clipboard =

39、 getToolkit().getSystemClipboard();select = ta.getSelectedText();if (select.length() != 0) StringSelection text = new StringSelection(select);clipboard.setContents(text, null);ta.replaceRange("", ta.getSelectionStart(),ta.getSelectionEnd(); catch (Exception e) System.err.println(e);if (ae.

40、getSource() = copy | ae.getSource() = copy1) try clipboard = getToolkit().getSystemClipboard();select = ta.getSelectedText();if (select.length() != 0) StringSelection text = new StringSelection(select);clipboard.setContents(text, null); catch (Exception e) System.err.println(e);if (ae.getSource() =

41、paste | ae.getSource() = paste1) Transferable contents = clipboard.getContents(this);DataFlavor flavor = DataFlavor.stringFlavor;if (contents.isDataFlavorSupported(flavor)try String str;str = (String) contents.getTransferData(flavor);ta.insert(str, ta.getCaretPosition(); catch (Exception e) System.e

42、rr.println(e);if (ae.getSource() = del | ae.getSource() = del1) ta.replaceSelection(null);if (ae.getSource() = all | ae.getSource() = all1) ta.selectAll();if (ae.getSource() = lexical) lexical.setEnabled(false);if (ae.getSource() = nfadfamfa) try NDMdialog dialog = new NDMdialog("NFA_DFA_MFA&qu

43、ot;);dialog.setDefaultCloseOperation(JDialog.DISPOSE_ON_CLOSE);dialog.setVisible(true); catch (Exception e) e.printStackTrace();if (ae.getSource() = sHelp) jop.setBounds(300, 300, 250, 150);jop.showMessageDialog(null, "无法启动“Windows帮助和支持", "查看",jop.ERROR_MESSAGE);if (ae.getSource(

44、) = about) AboutFile af = new AboutFile(f, "词法分析器", true);public static void main(String args) FrameView fv = new FrameView();Prompt.javapackage view;import java.awt.BorderLayout;import java.awt.Color;import java.awt.FlowLayout;import java.awt.Frame;import java.awt.event.ActionEvent;import

45、 java.awt.event.ActionListener;import java.awt.event.WindowAdapter;import java.awt.event.WindowEvent;import javax.swing.JButton;import javax.swing.JDialog;import javax.swing.JLabel;import javax.swing.JPanel;public class Prompt extends JDialog implements ActionListener JButton ok = new JButton("

46、保存");JButton no = new JButton("不保存");JButton cancel = new JButton("取消");public Prompt(Frame parent, String title, Boolean d) super(parent, title, true);addWindowListener(new WindowAdapter() public void windowClosing(WindowEvent we) dispose(););JLabel lb = new JLabel("是否

47、需要将更改保存？", JLabel.CENTER);setLayout(new BorderLayout();setBackground(Color.WHITE);JPanel pl = new JPanel();add("South", pl);add("Center", lb);pl.setLayout(new FlowLayout();pl.setBackground(Color.LIGHT_GRAY);pl.add(ok);pl.add(no);pl.add(cancel);ok.setBackground(Color.WHITE);n

48、o.setBackground(Color.WHITE);cancel.setBackground(Color.WHITE);setBounds(450, 300, 250, 150);ok.addActionListener(this);no.addActionListener(this);cancel.addActionListener(this);setVisible(true);public void actionPerformed(ActionEvent e) if (e.getSource() = ok) FrameView my = new FrameView();my.save

49、File();if (e.getSource() = no)System.exit(0);if (e.getSource() = cancel)this.dispose();AboutFile.javapackage view;import java.awt.BorderLayout;import java.awt.Color;import java.awt.Frame;import java.awt.GridLayout;import java.awt.event.ActionEvent;import java.awt.event.ActionListener;import java.awt

50、.event.WindowAdapter;import java.awt.event.WindowEvent;import javax.swing.JButton;import javax.swing.JDialog;import javax.swing.JLabel;import javax.swing.JPanel;import javax.swing.JTextArea;public class AboutFile extends JDialog implements ActionListener public AboutFile(Frame parent, String title,

51、Boolean k) super(parent, title, true);addWindowListener(new WindowAdapter() public void windowClosing(WindowEvent we) dispose(););JPanel pla = new JPanel();JPanel plb = new JPanel();JLabel lba = new JLabel("感谢老师和各位队友的帮助", JLabel.CENTER);JLabel lbb = new JLabel("版权人：崔立志", JLabel.C

52、ENTER);JLabel lbc = new JLabel("出版日期：2022年", JLabel.CENTER);lba.setOpaque(true);setLayout(new BorderLayout();setBackground(Color.WHITE);plb.setLayout(new GridLayout(3, 1);plb.add(lba);plb.add(lbb);plb.add(lbc);add("South", pla);add("Center", plb);JButton confirm = new J

53、Button("确定");pla.add(confirm);JTextArea t = new JTextArea();t.setEditable(false);setBounds(490, 300, 250, 150);confirm.addActionListener(this);setVisible(true);public void actionPerformed(ActionEvent e) dispose();NDMdialog.javapackage view;import java.awt.BorderLayout;import java.awt.FileDialog;import java.awt.FlowLayout;import javax.swing.JButton;import javax.swing.JDialog;import javax.swing.JFileChooser;import ;import javax.swing.JOptionPane;import javax.swing.JPanel;import javax.swing.border.EmptyBorder;import java.awt.event.ActionListen