实验一、简单的词法设计——DFA模拟程序
一、实验目的
通过实验教学，加深学生对所学的关于编译的理论知识的理解，增强学生对所学知识的综合应用能力，并通过实践达到对所学的知识进行验证。通过对 DFA 模拟程序实验，使学生掌握词法分析的实现技术，及具体实现方法。通过本实验加深对词法分析程序的功能及实现方法的理解 。
二、实验环境
供 Windows 系统的 PC 机，可用 C++/C#/Java 等编程工具编写，语言不限。
三、实验内容
1、自己定义一个 DFA 或者一个右线性正规文法
示例如(仅供参考) G[S]：S→aU|bV U→bV|aQ
V→aU|bQ Q→aQ|bQ|e
2、利用合适数据结构存储自动机，如
3、利用有穷确定自动机M=(K,Σ,f, S,Z）行为模拟程序算法，来对于任意给定的串，若属于该语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”
K:=S； c:=getchar; while c<>eof do {K:=f(K,c); c:=getchar; }; if K is in Z then return (‘yes’) else return (‘no’)
四、实验方式与要求
1、设计的自动机程序要具有通用性，上机编程实现；
2、实验报告格式要求书写要点：概要设计（总体设计思想）；详细设计（程序主流程、自动机的存储格式、关键函数的流程图）；结果分析（输入与输出结果、存在问题及有待改进善的地方、实验心得）；
3、实验报告限4页内。
设计思路：我们主要是用 Java 语言实现词法分析的过程，需要处理 DFA 和 NFA 两种状态，所以在文末我们给出了测试样例以及测试截图，部分代码给出了详细的注释。
实验代码如下：
package python; import java.util.List; import java.util.ArrayList; import java.util.Scanner; /** * @author Angel_Kitty * @createTime 2018年11月21日 上午2:23:33 */ /**状态转换式构造类*/ class edge { char PriorityState; char ch; char NextState; edge(char p,char c, char n){ PriorityState = p; ch = c; NextState = n; } @Override public String toString() { return "edge [PriorityState=" + PriorityState + ", ch=" + ch + ", NextState=" + NextState + "]"; } } /**DFA的构造*/ public class DFA { static List<edge> listEdge = new ArrayList<edge>();//状态集 //static HashMap<edge, Character> mapEdge = new HashMap<>(); static String S;//初态集 static String Z;//终态集 //flag is here static boolean judeZ(char ch){ int j=0; for(; j<Z.length(); j++){ if(Z.charAt(j)==ch) return true; } return false; } static void input() { Scanner in = new Scanner(System.in); String instr = null; String subStr[] = null; System.out.println("请输入开始符："); S = in.next(); System.out.println("请输入终态集(终集符组成的一个字符串)："); Z = in.next(); System.out.println("请输入正规文法以end结尾(形式如下图)："); System.out.println("----------"); System.out.println("| S-aU |"); System.out.println("| S-bV |"); System.out.println("| U-bV |"); System.out.println("| .... |"); System.out.println("| end |"); System.out.println("----------"); while(in.hasNext()){ instr = in.next(); if("end".equals(instr)) break; subStr = instr.split("-|\\|"); String s = subStr[0];//读取一行f(转换函数) for(int i=1; i<subStr.length; i++){ edge e = null; if(subStr[i].length()==2){ char c = subStr[i].charAt(0);//有穷符号表 char n = subStr[i].charAt(1);//状态集 listEdge.add(new edge(s.charAt(0),c,n));//f(S,a)=U } if(subStr[i].length()==1){ char c = subStr[i].charAt(0); listEdge.add(new edge(s.charAt(0),c,Z.charAt(0))); } } } } static char judeNextState(char s,char ch){ for(int i=0; i<listEdge.size(); i++){ if(s==listEdge.get(i).PriorityState && ch==listEdge.get(i).ch){ return listEdge.get(i).NextState; } } return '0'; } static void judeDFA(){ Scanner in = new Scanner(System.in); System.out.println("请输入要判断的字符串:"); while(in.hasNext()){ String str = in.next(); if(str.equals("#")){ System.out.println("程序已退出，欢迎下次使用!"); return; } char temp = S.charAt(0); int i=0; //System.out.println(temp+" "+mapEdge.get(e)); for(; i<str.length(); i++){ //System.out.println("temp="+temp); if(str.charAt(i)=='a'){ temp = judeNextState(temp, 'a'); } else if(str.charAt(i)=='b'){ temp = judeNextState(temp, 'b'); } else break; } //flag is here if(i>=str.length() && judeZ(temp)) System.out.println("此字符串“属于”该文法！"); else System.out.println("此字符串“不属于”该文法！"); System.out.println("再次判断请输入字符串(退出程序输入#):"); } } /*main*/ public static void main(String[] args) { // TODO Auto-generated method stub DFA.input(); DFA.judeDFA(); } } /*test example*/ /* * //start symbol S //end symbol Q //Regular Grammar1 S-aU S-bV U-bV U-aQ V-aU V-bQ Q-aQ Q-bQ end //judge string ->test sample1: baab ->test sample2: abab //start symbol S //end symbol Q,V //Regular Grammer2 S-aU S-bV U-bV U-aQ Q-aQ Q-bQ end //judge string -> test sample1: ab -> test sample2: abb if you input '#',The program will exit. * * */
测试结果如下：
