AI 助理
备案控制台
开发者社区 人工智能 文章 正文

编译原理：正规式转变成DFA算法

2016-04-28 1915
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 

//将正规式转变成NFA
package hjzgg.formal_ceremony_to_dfa;

import java.util.ArrayList;

class Edge{
    public int u, v;
    public char key;
    public Edge(int u, int v, char key) {
        super();
        this.u = u;
        this.v = v;
        this.key = key;
    }
    @Override
    public String toString() {
        return u + "->" + v + " " + key;
    }
    
    @Override
    public boolean equals(Object arg0) {
        Edge tmp = (Edge)arg0;
        return tmp.u==this.u && tmp.v==this.v && tmp.key==this.key;
    }
    @Override
    public int hashCode() {
        return u+v+key;
    }
}

class NFA{
    public static final int MAX_NODE = 100;
    private boolean finalState[] = new boolean[MAX_NODE];//记录每一个节点是否为终态
    private String formal_ceremony;//正规式字符串
    private int cnt_node=1;//记录节点的个数
    private Map<Integer, Integer> endNode = new TreeMap<Integer, Integer>();//每一个开始节点对应的终端节点
    private ArrayList<Edge> nodeAl = new ArrayList<Edge>();
    private Vector<Pair>[] g = new Vector[MAX_NODE];//NFA图
    private Set<Character> st = new TreeSet<Character>();//正规式中出现的字符的集合
    public NFA(String formal_ceremony) {
        super();
        this.formal_ceremony = formal_ceremony;
    }
    
    private void addEdge(int u, int v, char ch){
        nodeAl.add(new Edge(u, v, ch));
        if(g[u] == null) 
            g[u] = new Vector<Pair>();
        g[u].add(new Pair(v, ch));
        if(ch!='$')
            st.add(ch);
    }
    
    public boolean    kernel_way(int fa, int ld, int rd, boolean isClosure){//fa表示区间的开始点，正规式的区间[ld, rd], isClosure表示这段区间查是否存在闭包 
        if(ld < 0 || rd >= formal_ceremony.length()){
            System.out.println("正规式不正确---发生数组越界!");
            return false;
        }
        int pre_node = fa;
        int inBracket = 0;//判断'|'是否在括弧内
        for(int i=ld; i<=rd; ++i){
            if(formal_ceremony.charAt(i)=='(') ++inBracket;
            else if(formal_ceremony.charAt(i)==')') --inBracket;
            else if(formal_ceremony.charAt(i)=='|' && 0==inBracket){
                if(!kernel_way(fa, ld, i-1, isClosure)) return false;
                if(!kernel_way(fa, i+1, rd, isClosure)) return false;
                return true;
            }
        }
        for(int i=ld; i<=rd; ++i){
            if(formal_ceremony.charAt(i)=='('){//又是一个子区间
                //寻找和 该 '('相匹配的')'
                int cntLeftBracket = 0;//统计遍历过程中'('出现的次数，遇到')'减去1
                int posRightBracket = -1;//记录相匹配的')'的位置
                int posLeftBracket = i;
                for(int j=i+1; j<=rd; ++j){
                    if(formal_ceremony.charAt(j)=='(')
                        ++cntLeftBracket;
                    else if(formal_ceremony.charAt(j)==')'){
                        if(cntLeftBracket == 0){
                            posRightBracket = j;
                            break;
                        }
                        --cntLeftBracket;
                    }
                }
                if(posRightBracket == -1){//出错
                    System.out.println("正规式出错----括弧不匹配!");
                    return false;
                }
                int nodeFather = 0;//括弧内正则式的开始节点
                if(posRightBracket+1 <= rd && formal_ceremony.charAt(posRightBracket+1)=='*'){
                    i = posRightBracket+1;//过滤掉"()*"
                    addEdge(pre_node, ++cnt_node, '$');//表示这一条边为空
                    pre_node = cnt_node;
                    nodeFather = cnt_node;
                    addEdge(pre_node, ++cnt_node, '$');//表示这一条边为空
                    pre_node = cnt_node;
                    //处理()*括弧内的正规式
                    if(!kernel_way(nodeFather, posLeftBracket+1, posRightBracket-1, true)) return false;
                } else {
                    nodeFather = pre_node;
                    if(!kernel_way(nodeFather, posLeftBracket+1, posRightBracket-1, false))//对于"(101)"， 看成101
                        return false;
                    i = posRightBracket;
                }
                
            } else {//单个字符
                if(formal_ceremony.charAt(i)==')') continue;
                if(i+1 <= rd && formal_ceremony.charAt(i+1)=='*'){
                    addEdge(pre_node, ++cnt_node, '$');//表示这一条边为空
                    pre_node = cnt_node;
                    addEdge(pre_node, pre_node, formal_ceremony.charAt(i));
                    if(i+1==rd  && isClosure)
                        addEdge(pre_node, fa, '$');//表示这一条边为空并且是连接到父亲节点
                    else{
                        if(endNode.containsKey(fa))
                            addEdge(pre_node, endNode.get(fa), '$');
                        else{
                            addEdge(pre_node, ++cnt_node, '$');//表示这一条边为空
                            if(i==rd) endNode.put(fa, cnt_node);//记录非闭包状态下 第一个节点对应的最后一个节点
                        }
                    }
                    pre_node = cnt_node;
                    ++i;//过滤*
                } else {
                    if(i==rd && isClosure){//是闭包的情况
                        addEdge(pre_node, fa, formal_ceremony.charAt(i));
                    } else{
                        if(endNode.containsKey(fa))
                            addEdge(pre_node, endNode.get(fa), formal_ceremony.charAt(i));
                        else{
                            addEdge(pre_node, ++cnt_node, formal_ceremony.charAt(i));
                            if(i==rd) endNode.put(fa, cnt_node);//记录非闭包状态下 第一个节点对应的最后一个节点
                        }
                    }
                    pre_node = cnt_node;
                }
            }
        }
        return true;
    }
    
    private void checkFinalState(){//检查哪一个节点是终态
        for(int i=1; i<=cnt_node; ++i){
            int cc = 0;
            if(g[i] == null){//表明是终态
                finalState[i] = true;
                continue;
            }
            for(int j=0; j<g[i].size(); ++j)
                if(g[i].elementAt(j).v != i)
                    ++cc;
            if(cc == 0)//表明是终态
                finalState[i] = true;
        }
    }
    
    public boolean[] getFinalState(){
        return finalState;
    }
    
    public Vector<Pair>[] getNFAGraphics(){
        if(kernel_way(1, 0, formal_ceremony.length()-1, false)){
//            for(Edge e : nodeAl)//打印NFA
//                System.out.println(e);
            checkFinalState();
            return g;
        }
        return null;
    }
    
    public Set<Character> getCharacterSet(){
        return st;
    }
    
    public void outputNFA(){
        if(kernel_way(1, 0, formal_ceremony.length()-1, false)){
            checkFinalState();
            for(Edge e : nodeAl)
                System.out.println(e);
        }
    }
}


/*
 * 将正规式转换成NFA
 * */
public class ToNFA {
    
    public static void main(String[] args){
        String formal_ceremony = "0*(100*)*0*";
//        String formal_ceremony = "1(1010*|1(010)*1)*0";
//        String formal_ceremony = "1(0|1)*101";
//        String formal_ceremony = "0*1*(010)0*1*";
//        String formal_ceremony = "(0|1|2)*";
//        String formal_ceremony = "0|1";
//        String formal_ceremony = "0|1|2|3";
//        String formal_ceremony = "(0|1|6)|(2|3)|(4|5)";
//        String formal_ceremony = "(0|1)*|(2|3)*";
//        String formal_ceremony = "((10)|(01)*|(0|1))";
        NFA nfa = new NFA(formal_ceremony);
        nfa.outputNFA();
    }
}


//将NFA转变成确定化DFA
package hjzgg.formal_ceremony_to_dfa;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.Vector;

class Pair {
    public int v;
    public char ch;
    public Pair(int v, char ch) {
        super();
        this.v = v;
        this.ch = ch;
    }
    
}

class MyHashSet extends HashSet<Integer>{//重写 set 集合的 hashcode()和equals()方法
    private int state;
    public void setState(int state){
        this.state = state;
    }
    public int getState(){
        return state;
    }
    @Override
    public boolean equals(Object arg0) {
        MyHashSet tmp = (MyHashSet)arg0;
        if(tmp.size() != this.size()) return false;
        Iterator<Integer> it = this.iterator();
        while(it.hasNext()){
            if(!tmp.contains(it.next())) return false;
        }
        return true;
    }

    @Override
    public int hashCode() {
         int sum = 0;
         Iterator<Integer> it = this.iterator();
         while(it.hasNext())
             sum += (((java.lang.Integer)it.next()).intValue());
         return sum;
    }
}

class DefinedNFA{
    private int dfaNode = 0;//defined DFA节点的个数
    private boolean[] finalState = null;//表示NFA中哪一个节点是终态
    private boolean[] newFinalState = new boolean[NFA.MAX_NODE] ;
    private Vector<Pair>[] g = null;//NFA 图
    private Set<Edge>edgeSet = new HashSet<Edge>(); //标记图中的边是否被访问过
    private MyHashSet st = null; //集合,表示每一个子集状态
    private Queue<MyHashSet> queue = new LinkedList<MyHashSet>();//存放要执行的子集状态
    private Set<MyHashSet> sst = new HashSet<MyHashSet>();
    private Set<Character> characterSet = null;//正规式中的字符的集合
    private ArrayList<Edge> nodeAl = new ArrayList<Edge>();//NFA边的集合
    public DefinedNFA(Vector<Pair>[] g, Set<Character> characterSet, boolean[] finalState) {
        super();
        this.g = g;
        this.characterSet = characterSet;
        this.finalState = finalState;
    }
    
    public Set<Character> getCharacterSet(){
        return characterSet;
    }
    public int getDfaNode(){
        return dfaNode;
    }
    public boolean[] getNewFinalState(){
        return newFinalState;
    }
    public ArrayList<Edge> getNodeAl(){
        return nodeAl;
    }
    private void dfs(int u, char ch){
        if(g[u]==null) return ;
        int len = g[u].size();
        for(int i=0; i<len; ++i){
            Pair pair = g[u].elementAt(i);
            Edge edge = new Edge(u, pair.v, pair.ch);
            if(!edgeSet.contains(edge) && pair.ch==ch){
                edgeSet.add(edge);
                st.add(pair.v);
                dfs(pair.v, '$');
            }
        }
            
    }
    
    public void checkIsFinalState(Set<Integer> st, int state){
        Iterator<Integer> it = st.iterator();
        while(it.hasNext()){
            int val = it.next();
            if(finalState[val])
                newFinalState[state] = true;
        }
    }
    
    private void initFirstSet(){
        edgeSet.clear();
        st = new MyHashSet();
        st.add(1);
        st.setState(++dfaNode);
        dfs(1, '$');
        checkIsFinalState(st, dfaNode);
        sst.add(st);
        queue.add(st);
    }
    private void addEdge(int u, int v, char ch){
        nodeAl.add(new Edge(u, v, ch));
    }
    
    public void ToStateMatrix(){
        initFirstSet();
        while(!queue.isEmpty()){
            MyHashSet myset = queue.poll();
            for(Character ch : characterSet){
                st = new MyHashSet();
                for(Integer i : myset){
                    edgeSet.clear();
                    dfs(i, ch);
                }
                if(st.size()>0){
                    if(!sst.contains(st)){
                        sst.add(st);
                        queue.add(st);
                        st.setState(++dfaNode);
                        checkIsFinalState(st, dfaNode);
                    } else {
                        Iterator<MyHashSet> it = sst.iterator();
                        while(it.hasNext()){
                            MyHashSet tmp = it.next();
                            if(tmp.equals(st)){
                                st = tmp;
                                break;
                            }
                        }
                    }
                    addEdge(myset.getState(), st.getState(), ch);
                } 
            }
        }
    }
    
    public void outputDFA(){
        ToStateMatrix();//有状态转换矩阵得到defined NFA
        for(Edge e : nodeAl)
            System.out.println(e);
    }
    
}

public class ToDefinedDFA {

    public static void main(String[] args) {
//        String formal_ceremony = "((10)|(01)*|(0|1))";
//        String formal_ceremony = "(0|1|6)|(2|3)|(4|5)";
//        String formal_ceremony = "1(0|1)*101";
        String formal_ceremony = "0*(100*)*0*";
        NFA nfa = new NFA(formal_ceremony);
        DefinedNFA definedDFA = new DefinedNFA(nfa.getNFAGraphics(), nfa.getCharacterSet(), nfa.getFinalState());
        definedDFA.outputDFA();
    }

}


//将确定化DFA最小化
package hjzgg.formal_ceremony_to_dfa;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

class MinimumDFA{
    private boolean[] newFinalState = null;//由确定化DFA得到
    private ArrayList<Edge> nodeAl = null;//由确定化DFA得到
    private int dfaNode;//确定化DFA节点的个数
    private Set<Character> characterSet = null;//正规式中的字符的集合
    private ArrayList<Set<Integer>> setList = new ArrayList<Set<Integer>>();    
    public MinimumDFA(boolean[] newFinalState, ArrayList<Edge> nodeAl, int dfaNode, Set<Character> characterSet) {
        super();
        this.newFinalState = newFinalState;
        this.nodeAl = nodeAl;
        this.dfaNode = dfaNode;
        this.characterSet = characterSet;
    }
    private void init(){//利用分割法将集合分成终态和非终态
        Set<Integer> finalStateSet = new HashSet<Integer>();
        Set<Integer> NofinalStateSet = new HashSet<Integer>();
        for(int i=1; i<=dfaNode; ++i)
            if(newFinalState[i])//终态
                finalStateSet.add(i);
            else 
                NofinalStateSet.add(i);
        setList.add(finalStateSet);
        setList.add(NofinalStateSet);
    }
    
    public void toMinimumDfa(){
        init();
        boolean flag = true;
        ArrayList<Set<Integer>> tmpSetList = new ArrayList<Set<Integer>>();
        while(flag){
            flag = false;
            hjzgg:
            for(int k=0; k<setList.size(); ++k){
                Set<Integer> st = setList.get(k);
                if(st.size()<=1) continue;
                for(Character ch : characterSet){
                    Map<Integer, Integer> mp = new HashMap<Integer, Integer>();
                    for(int i=0; i<nodeAl.size(); ++i){//st集合(也就是map的val值)在 ch这个点对应的集合 {st}a = {...}
                        Edge edge = nodeAl.get(i);
                        if(edge.key == ch && st.contains(edge.u))
                            mp.put(edge.u, edge.v);
                    }

 　　　　　　　　　　　　for(Integer i : st)
						　　　　　　　　　　　　　　if(!mp.containsKey(i))//表明i节点对应的是一条空边
							　　　　　　　　　　　　　　　　mp.put(i, -1);
//将st集合拆分成两个不想交的集合
                    Set<Integer> firstSet = new HashSet<Integer>();
                    Set<Integer> secondSet = new HashSet<Integer>();
                    for(int j=0; j<setList.size(); ++j){
                        firstSet.clear();
                        secondSet.clear();
                        Set<Integer> tmpSt = setList.get(k);
                        for(Entry<Integer, Integer> entry : mp.entrySet()){//返回此映射中包含的映射关系的 set 视图。返回的 set 中的每个元素都是一个 Map.Entry
                              if(tmpSt.contains(entry.getValue()))
                                  firstSet.add(entry.getKey());
                              else secondSet.add(entry.getKey());
                        }
                        if(firstSet.size()!=0 && secondSet.size()!=0){
                            flag = true;//如果发现可以拆分的集合，则继续最顶层的while循环
                            for(Integer i : tmpSt){//将firstSet 和 secondSet中都没有的元素添加到firstSet中
                                if(!firstSet.contains(i) && !secondSet.contains(i))
                                    firstSet.add(i);
                            }
                            setList.remove(k);
                            setList.add(firstSet);
                            setList.add(secondSet);
                            break hjzgg;
                        }
                    }
                }
            }
        }
//        for(int k=0; k<setList.size(); ++k)//输出最终的集合划分
//            System.out.println(setList.get(k));
//        System.out.println("&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&");
        for(int k=0; k<setList.size(); ++k){
            Set<Integer> st = setList.get(k);
            if(st.size() > 1){//看成是一个等价的状态，选择第一个元素当作代表
                int first=0;
                for(Integer i : st){//取得第一个元素
                    first = i;
                    break;
                }
                ArrayList<Edge> tmpList = new ArrayList<Edge>();
                for(int i=0; i<nodeAl.size(); ++i){//遍历所有的边，找到不是first
                    Edge edge = nodeAl.get(i);
                    if(st.contains(edge.u) && edge.u!=first){
                        nodeAl.remove(i);
                        --i;
                    } else if(st.contains(edge.v) && edge.v!=first){
                        nodeAl.remove(i);
                        --i;
                        tmpList.add(new Edge(edge.u, first, edge.key));
                    }
                }
                nodeAl.addAll(tmpList);
            }
        }
    }
    
    public void outputMinimumDFA(){
//        for(int i=0; i<nodeAl.size(); ++i)//输出未确定化的DFA
//            System.out.println(nodeAl.get(i));
        toMinimumDfa();
        for(int i=0; i<nodeAl.size(); ++i)
            System.out.println(nodeAl.get(i));
    }
}

public class ToMinimumDFA {

    public static void main(String[] args) {
//        String formal_ceremony = "1(0|1)*101";
        String formal_ceremony = "0*(100*)*0*";
        NFA nfa = new NFA(formal_ceremony);
        DefinedNFA definedDFA = new DefinedNFA(nfa.getNFAGraphics(), nfa.getCharacterSet(), nfa.getFinalState());
        definedDFA.ToStateMatrix();
        MinimumDFA minimumDFA = new MinimumDFA(definedDFA.getNewFinalState(), definedDFA.getNodeAl(), definedDFA.getDfaNode(), definedDFA.getCharacterSet());
        minimumDFA.outputMinimumDFA();
    }

}

文章标签：
云数据库 ClickHouse
算法
hjzgg
目录
相关文章
₍ᐢ..ᐢ₎王
|
7月前
|
算法 C语言
【专业解码】递归求和在C语言中的神操作！只需1秒，你也能轻松开挂
【专业解码】递归求和在C语言中的神操作！只需1秒，你也能轻松开挂
₍ᐢ..ᐢ₎王
100 0
热烈的马
|
7月前
|
自然语言处理 算法 编译器
编译原理复习一：正则表达式-NFA NFA-DFA DFA最小化（附题目与答案 超详细）
编译原理复习一：正则表达式-NFA NFA-DFA DFA最小化（附题目与答案 超详细）
热烈的马
369 0
hnrk7epeorhrk
|
6月前
|
机器学习/深度学习 资源调度
技术经验解读：【常用】数学符号及读法大全
技术经验解读：【常用】数学符号及读法大全
hnrk7epeorhrk
66 0
泡沫o0
|
7月前
|
算法 C++
【软件设计师备考 专题 】数学基础知识：命题逻辑、谓词逻辑、形式逻辑与数值计算
【软件设计师备考 专题 】数学基础知识：命题逻辑、谓词逻辑、形式逻辑与数值计算
泡沫o0
86 0
北溪入江流
编译原理实验：NFA转化为DFA
编译原理实验：NFA转化为DFA
北溪入江流
198 0
demo123567
|
算法 搜索推荐 程序员
C语言第十六练——数字组合匹配
C语言第十六练——数字组合匹配
demo123567
129 0
marsCatXDU_李经纬@西电
|
存储 自然语言处理 算法
编译原理笔记5：从正规式到词法分析器（2）：NFA 记号识别、确定化、并行算法、子集法构造DFA
marsCatXDU_李经纬@西电
1411 0
ZhangBlossom
|
存储 Java C语言
C语言哈夫曼编码实现细则(附代码以及详细实现解释)
C语言哈夫曼编码实现细则(附代码以及详细实现解释)
ZhangBlossom
253 0
angel_kitty
|
存储 自然语言处理 算法
简单的词法设计——DFA模拟程序
简单的词法设计——DFA模拟程序
angel_kitty
277 0
简单的词法设计——DFA模拟程序
自由
|
算法
重温算法之有效的括号
这个题为什么借助栈会变得很容易呢，因为都是在利用栈先进先出的特点，然后匹配左右括号，如果只有其中之一则不满足，不满足的从栈里取出，剩下的就是满足条件的。
自由
114 0
重温算法之有效的括号

热门文章

最新文章

  • 1
    天猫精灵开放平台-之小百科测评
  • 2
    语义检索系统：基于Milvus 搭建召回系统抽取向量进行检索，加速索引
  • 3
    3D立方体图片切换动画
  • 4
    模态对话框和非模态对话框
  • 5
    java03
  • 6
    冒泡排序
  • 7
    Windows XP客户端加域操作手册上
  • 8
    微信 6.5.1 for iOS发布 可以在朋友圈分享相册中的视频
  • 9
    Chapter 1: Creating the GUI Form and Adding Widgets
  • 10
    【Mockplus教程】帐号和购买
  • 1
    「Mac畅玩鸿蒙与硬件42」UI互动应用篇19 - 数字键盘应用
    34
  • 2
    赋能加速AI应用交付，F5 BIG-IP Next for Kubernetes方案解读
    30
  • 3
    RAG分块策略：主流方法（递归、jina-seg）+前沿推荐（Meta-chunking、Late chunking、SLM-SFT）
    28
  • 4
    Python学习的自我理解和想法（2）
    30
  • 5
    Transformer图解
    36
  • 6
    API安全专题：如何有效应对新型Bot攻击？
    18
  • 7
    Selenium IDE：Web自动化测试的得力助手
    34
  • 8
    《docker高级篇（大厂进阶）：5.Docker-compose容器编排》包括是什么能干嘛去哪下、Compose核心概念、Compose使用三个步骤、Compose常用命令、Compose编排微服务
    51
  • 9
    24/7全时守护：AI视频监控技术的深度实现与应用分享
    43
  • 10
    《docker高级篇（大厂进阶）：6.Docker轻量级可视化工具Portainer》
    27

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法
  • 相册服务中的故事生成算法介绍
  • 智能运维赛（复赛）：利用数据和算法，快速定位系统异常并进行根因分析
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 图解算法小抄
  • 超全算法笔试-模拟题精解合集

    • 相关实验场景

    更多
  • 使用Swing算法实现商品推荐
  • RSA密码算法设计与实现
  • 欧拉图的构造性证明与算法实现
  • 推荐系统入门之使用ALS算法实现打分预测
    • 下一篇
    阿里云无影云电脑免费试用，最长可试用3个月