编译原理LL1文法Follow集算法实现
2023-09-27 14:20:24 时间
import hjzgg.first.First; import java.util.LinkedHashMap; import java.util.Map; import java.util.Set; import java.util.TreeMap; import java.util.TreeSet; public class Follow { private Map<String, Set<Character>> first = null; private Map<String, Set<Character>> follow = new TreeMap<String, Set<Character>>(); private Map<String, String[]> mp = null; public Follow(Map<String, String[]> mp, Map<String, Set<Character>> first) { super(); this.first = first; this.mp = mp; } public Map<String, Set<Character>> getFollowSet(){ return follow; } private void getFirstSet(Set<Character> st, String node, int k){ if(k >= node.length()) return; if(node.charAt(k)=='\'') --k; String nextNode = "" + node.charAt(k); if(k+1<node.length() && node.charAt(k+1)=='\''){ nextNode += '\''; ++k; } if(!mp.containsKey(nextNode)){//终结点 st.add(nextNode.charAt(0)); } else { st.addAll(first.get(nextNode)); if(first.get(nextNode).contains('$')) getFirstSet(st, node, k+1); } } private void findFollow(String curNode){ Set<Character> st = null; for(String leftNode : mp.keySet()){ String rightNodes[] = mp.get(leftNode); for(int i=0; i<rightNodes.length; ++i){ int index = rightNodes[i].indexOf(curNode, 0); while(index != -1){ int nextIndex = index + 1; if(curNode.length()==1 && index+1<rightNodes[i].length() && rightNodes[i].charAt(index+1)=='\''){ index = rightNodes[i].indexOf(curNode, nextIndex); continue; } index = index+curNode.length(); if(index == rightNodes[i].length()){//末尾的非终结点, A->@B if(follow.get(leftNode) == null) findFollow(leftNode); if(follow.get(curNode) == null){ st = new TreeSet<Character>(); st.addAll(follow.get(leftNode)); follow.put(curNode, st); } else follow.get(curNode).addAll(follow.get(leftNode)); } else { String nextNode = ""+rightNodes[i].charAt(index); if(index+1 < rightNodes[i].length() && rightNodes[i].charAt(index+1)=='\''){ nextNode += '\''; ++index; } if(mp.containsKey(nextNode)){//非终结符 if(first.get(nextNode).contains(new Character('$'))){//A->@B&, 而 &->$ if(follow.get(leftNode) == null) findFollow(leftNode); if(follow.get(curNode) == null){ st = new TreeSet<Character>(); st.addAll(follow.get(leftNode)); follow.put(curNode, st); } else follow.get(curNode).addAll(follow.get(leftNode)); } //好特殊的情况啊.... {//A->@B&, First(&)^$ 放入follow(B) Set<Character> tmpSt = new TreeSet<Character>(); getFirstSet(tmpSt, rightNodes[i], index); tmpSt.remove('$'); if(follow.get(curNode) == null){ st = new TreeSet<Character>(); st.addAll(tmpSt); follow.put(curNode, st); } else follow.get(curNode).addAll(tmpSt); } } else {//终结符 if(follow.get(curNode) == null){ st = new TreeSet<Character>(); st.add(nextNode.charAt(0)); follow.put(curNode, st); } else follow.get(curNode).add(nextNode.charAt(0)); } } index = rightNodes[i].indexOf(curNode, nextIndex); } } } } public String followKernealCode(){ String content = ""; boolean flag = true; for(String leftNode : mp.keySet()){ if(flag){ Set<Character> st = new TreeSet<Character>(); st.add('#'); follow.put(leftNode, st); flag = false; } findFollow(leftNode); } //打印first集合 System.out.println("Follow 集合如下:"); for(Map.Entry<String, Set<Character>> entry : follow.entrySet()){ content += entry.getKey() + " : " + entry.getValue() + "\n"; System.out.println(entry.getKey() + " : " + entry.getValue()); } return content; } public static void main(String[] args) { String[] rightLinearGrammar = { "E->TE\'", "E\'->+TE\'|$", "T->FT\'", "T\'->*FT\'|$", "F->(E)|i" }; // String[] rightLinearGrammar = { // "S->ABc", // "A->a|$", // "B->b|$" // }; Map<String, String[]> mp = new LinkedHashMap<String, String[]>(); try{ for(int i=0; i<rightLinearGrammar.length; ++i){ String split1[] = rightLinearGrammar[i].split("->"); String split2[] = split1[1].split("\\|"); mp.put(split1[0], split2); } } catch(Exception e){ e.printStackTrace(); System.out.println("右线性文法错误!"); } First first = new First(mp); first.firstKernealCode(); new Follow(mp, first.getFirstSet()).followKernealCode(); } }
相关文章
- 机器学习:逻辑回归模型算法原理(附案例实战)
- 【梯度下降法】详解优化算法之梯度下降法(原理、实现)
- python svm原理和实现,svm相关算法
- Python bm25短文本分类,相似度识别,BM25算法相似度匹配,疾病相似度匹配gensim实现,bm25算法原理和实现实例
- 【数据结构与算法】归并排序的原理及算法实现
- 由Photoshop高反差保留算法原理联想到的一些图像增强算法。
- o(1)复杂度之双边滤波算法的原理、流程、实现及效果。
- 机器学习笔记之梯度下降算法原理讲解
- KCF跟踪算法原理 入门详解
- 【数据结构与算法】K 近邻算法—— KD 树 算法原理讲解和C语言实现代码
- 【数据结构与算法】编译原理基础知识 / 禅与计算机程序设计艺术 & ChatGPT
- 【人工智能AI】第一章 神经网络基础 《深度学习算法原理》 / By 禅与计算机程序设计艺术&ChatGPT
- 【大数据&AI人工智能】图文详解 ChatGPT、文心一言等大模型背后的 Transformer 算法原理
- 增强现实:原理算法与应用 第一章增强现实概论笔记
- 【算法】选择排序
- 嵌入式操作系统内核原理和开发(改进的链表内存分配算法)
- 一篇文章带你了解Paxos算法
- 教你如何利用算法原理,让TA对你一见钟情
- 【Java 虚拟机原理】垃圾回收算法 ( 标记-清除算法 | 复制算法 | 标记-整理算法 )
- Gamma原理及快速实现算法(C/C++)(转)
- 【算法基础】(一)基础算法 --- 离散化
- 机器学习:维数约减算法PCA(主成分分析法)原理、实现与应用
- Hash算法及java HashMap底层实现原理理解(含jdk 1.7以及jdk 1.8)