Simple lexical design – DFA simulation procedures

Experiment one, simple lexical design — DFA simulation program

I. Purpose of the experiment

Through experimental teaching, students can deepen their understanding of the theoretical knowledge about compilation, enhance their comprehensive application ability of the knowledge they have learned, and verify the knowledge they have learned through practice. Through the DFA simulation program experiment, let the students master the realization technology of lexical analysis, and the concrete realization method. Through this experiment to deepen the understanding of the function and implementation of lexical analysis program.

2. Experimental environment

For Windows PC, it can be written by C++, C#, Java and other programming tools.

3. Experiment content

1. Define your own DFA or a right linear normal grammar

Example (for reference only) G [S] : S – aU | bV U – bV | aQ

V – aU | bQ Q – aQ | bQ | e

2. Use appropriate data structures to store automata, such as

3. Use finite deterministic automata M=(K, σ, F, S,Z) behavior simulation program algorithm to stop and answer “yes” after a finite number of calculations for any given string if it belongs to the language, or stop and answer “no” if it does not.

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 ')Copy the code

4. Experimental methods and requirements

1, the design of the automatic program to have universality, computer programming to achieve;

2, experimental report format requirements writing key points: summary design (overall design idea); Detailed design (program main flow, automaton storage format, flow chart of key functions); Results analysis (input and output results, existing problems and areas for improvement, experimental experience);

3. The experiment report is limited to 4 pages.

Design idea: We mainly use Java language to realize the lexical analysis process, need to deal with DFA and NFA two states, so at the end of the article we give the test sample and test screenshots, part of the code to give detailed notes.

The experimental code is as follows:

package python;
import java.util.List;
import java.util.ArrayList;
import java.util.Scanner;
/ * * *@author Angel_Kitty
 * @createTimeNovember 21, 2018, 2:23:33 */
/** State transition constructor class */
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(a) {
		return "edge [PriorityState=" + PriorityState + ", ch=" + ch + ", NextState=" + NextState + "]"; }}/**DFA */
public class DFA {
	static List<edge> listEdge = new ArrayList<edge>();/ / state
	//static HashMap<edge, Character> mapEdge = new HashMap<>();
	static String S;/ / set initial state
	static String Z;/ / final set
	//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(a) {
		Scanner in = new Scanner(System.in);
		String instr = null;
		String subStr[] = null;
		System.out.println("Please enter the start character:");
		S = in.next();
		System.out.println("Please enter the endstate set (a string of endsets) :");
		Z = in.next();
		System.out.println("Please enter normal grammar to end with end (as shown below) :");
		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];// Read a line of f(conversion function)
			for(int i=1; i<subStr.length; i++){
				edge e = null;
				if(subStr[i].length()==2) {char c = subStr[i].charAt(0);// There is a finite symbol table
					char n = subStr[i].charAt(1);/ / state
					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){
				returnlistEdge.get(i).NextState; }}return '0';
	}
	
	static void judeDFA(a){
		Scanner in = new Scanner(System.in);
		System.out.println("Please enter the string to judge :");
		while(in.hasNext()){
			String str = in.next();
			if(str.equals("#")){
				System.out.println("Program has exited, welcome to use next time!");
				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("This string" belongs "to the text method!");
			else System.out.println("This string" does not belong to "text method!");
			System.out.println("Judge again please enter string (exit program type #):"); }}/*main*/
	public static void main(String[] args) {
		// TODO Auto-generated method stubDFA.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. * * */
Copy the code

The test results are as follows: