专栏首页小樱的经验随笔简单的词法设计——DFA模拟程序

简单的词法设计——DFA模拟程序

实验一、简单的词法设计——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 语言实现词法分析的过程,需要处理 DFANFA 两种状态,所以在文末我们给出了测试样例以及测试截图,部分代码给出了详细的注释。

实验代码如下:

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. 
 * 
 * */

测试结果如下:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 设计一个有getMin功能的栈

    【题目】   实现一个特殊的栈,在实现栈的基本功能的基础上,再实现返回栈中的最小元素的操作。 【要求】   1.pop、push、getMin操作的时间复杂度都...

    Angel_Kitty
  • 【经验总结】Java在ACM算法竞赛编程中易错点

    一、Java之ACM易错点 1. 类名称必须采用public class Main方式命名 2. 在有些OJ系统上,即便是输出的末尾多了一个“ ”,程序可能会输...

    Angel_Kitty
  • 【Java学习笔记之十四】Java中this用法小节

    用类名定义一个变量的时候,定义的只是一个引用,外面可以通过这个引用来访问这个类里面的属性和方法。     那们类里面是够也应该有一个引用来访问自己的属性和方法纳...

    Angel_Kitty
  • FileInput(Output)Stream

    mathor
  • macOS png制作icns图标

    小贝壳
  • 鲜为人知的Python功能

    每当我了解到Python中的新功能,或者我注意到其他一些人没有注意到的某个功能时,我就会把它记录下来。

    人工智能小咖
  • Java基础19(01)总结IO流,异常try…catch,throws,File类

    1:异常(理解) (1)程序出现的不正常的情况。 (2)异常的体系 Throwable |--Error 严重问题,我们不处理。 |--Excepti...

    Java帮帮
  • 应用层-day01

    主流应用程序体系结构:CS结构、P2P结构。 CS结构:客户-服务器体系结构。有一台总是打开的主机称为服务器,它服务来自其他许多称为客户的主机的请求。 P2P体...

    用户1134788
  • ESP8266固件升级至1.4.0版本方法(ESP8266-12F模组)

    使用AT命令查询当前版本信息,可以看到AT固件是2016年的,处于1.3.0版本,所以要对ESP8266模组进行固件升级:

    Mculover666
  • 39-序列对象方法2

    凯茜的老爸

扫码关注云+社区

领取腾讯云代金券