最初のセット

LL（1）文法、最初に設定されたスタックオーバーフローエラーを尋ねる



Ll Grammar Ask First Set Stack Overflow Error



最初のセットスタックオーバーフローエラーを探しています


スタックオーバーフロー、calFirstメソッドに無限ループがあるかもしれませんが、どこに問題があるのか​​わかりません。
エラー行にエラーコメントをしました
すべてのエラーはcalFirstメソッドで報告されますが、これは理解できません
ArrayList itemArr = expression.get（S）エラーが報告されるのはなぜですか
画像import java.io.Serializable import java.util.ArrayList import java.util.HashMap import java.util.Iterator import java.util.TreeMap import java.util.TreeSet public class GS implements Serializable{ private static final long serialVersionUID = 1L //The production of string input private ArrayList<String> gsArray // private HashMap<Character, ArrayList<String>> expression //Non-terminal symbol set private TreeSet<Character> vnSet //Terminator set private TreeSet<Character> vtSet //Grammar start character private Character start //How many right parts of each nonterminal private HashMap<Character,Integer> numSet //The set of non-terminal symbols that can reach ^ private TreeSet<Character> blankSet //Cannot reach the non-terminal set of ^ private TreeSet<Character> unBlankSet //first set private HashMap<Character, TreeSet<Character>> firstMap //follow set private HashMap<Character, TreeSet<Character>> followMap //select set private TreeMap<Character, HashMap<String, TreeSet<Character>>> selectMap //Analysis Table private String[][] analyzeTable public GS() { super() gsArray=new ArrayList<String>() vnSet=new TreeSet<Character>() vtSet=new TreeSet<Character>() firstMap=new HashMap<Character, TreeSet<Character>>() followMap=new HashMap<Character, TreeSet<Character>>() selectMap=new TreeMap<Character, HashMap<String, TreeSet<Character>>>() numSet=new HashMap<Character,Integer>() blankSet=new TreeSet<Character>() unBlankSet=new TreeSet<Character>() } public void getNvNt() { for (String gsItem : gsArray) {//Separate non-terminal symbols from the left String[] temp = gsItem.split('->') String lefts = temp[0] char left = lefts.charAt(0) vnSet.add(left) } for (String gsItem : gsArray) {//Separate non-terminal symbols from the right String[] temp = gsItem.split('->') String rights = temp[1] for (int i = 0 i < rights.length() i++) { char charItem = rights.charAt(i) if (!vnSet.contains(charItem)&&charItem!='|'&&charItem!='^') { vtSet.add(charItem) } } } } public void initExpression() { Integer num=0 expression = new HashMap<Character, ArrayList<String>>() for (String gsItem : gsArray) { String[] temp = gsItem.split('->') String lefts = temp[0] String rights = temp[1] char left=lefts.charAt(0) String[] right=rights.split('|') ArrayList<String> expArr = new ArrayList<String>() for(String s:right) { expArr.add(s) num++ } numSet.put(left, num) expression.put(left, expArr) } } public void getBlank() { int done=0//Record the number of non-terminal symbols processed //First deal with the situation where there are ^ and terminator on the right for(Character c:vnSet)//Operate for each non-terminal { ArrayList<String> itemArr=expression.get(c) if(itemArr.contains('^')) {//The non-terminal symbol directly containing ^ on the right blankSet.add(c) done++ } else {//You can launch non-terminal symbols that cannot reach ^ in one go Integer i=0//Record how many right parts contain terminator for(String s:itemArr) { for(char itemChar:vtSet) if(s.indexOf(itemChar)>0) { i++ break } } Integer num=numSet.get(c) if(i==num) {//If all right parts contain terminator unBlankSet.add(c) done++ } } } //There is at least one non-terminal symbol on the right while(done<vnSet.size()) { for(Character c:vnSet) { Integer flag1=0,flag2=0//flag1 records the number of the right part of the terminator and unBlank, if it is equal to the number of all its productions, it is added to unBlankSet if(!blankSet.contains(c)&&!unBlankSet.contains(c)) { ArrayList<String> s=expression.get(c) for(String itemStr:s) { for(int i=0i<itemStr.length()i++) { char itemChar=itemStr.charAt(i) if(unBlankSet.contains(itemChar)||vtSet.contains(itemChar)) { flag1++ break } if(blankSet.contains(itemChar)) flag2++ } if(flag2==itemStr.length()) {//Only the non-terminal symbol on the right of a production can reach ^, and the production can reach ^ blankSet.add(c) done++ break } } if(flag1==numSet.get(c)) { unBlankSet.add(c) done++ } } } } } public void getFirst() { Iterator<Character> iterator=vnSet.iterator() while(iterator.hasNext()) { Character itemChar=iterator.next() if(firstMap.containsKey(itemChar)) continue calFirst(itemChar) } } public void calFirst(Character S) { TreeSet<Character> first=new TreeSet<Character>() ArrayList<String> itemArr=expression.get(S)//Report an error for(String itemStr:itemArr) { char itemChar=itemStr.charAt(0) if(itemChar=='^'||vtSet.contains(itemChar)) first.add(itemChar) else {//The first one on the right is a non-terminal symbol for(int i=0i<itemStr.length()i++) { Character temp=itemStr.charAt(i) if(vtSet.contains(temp)) { first.add(temp) if(first.contains('^')) first.remove('^') break } else { if(!firstMap.containsKey(temp)) calFirst(temp)//Report an error TreeSet<Character> x=firstMap.get(temp) for(Character temps:x) first.add(temps) if(unBlankSet.contains(temp)){ if(first.contains('^')) first.remove('^') break } } } } } firstMap.put(S, first) if(firstMap.containsKey(S)) return } public void getFollow() { Iterator<Character> iterator=vnSet.iterator() while(iterator.hasNext()) { Character itemChar=iterator.next() calFollow(itemChar) } } public void calFollow(Character S) {//For each non-terminal symbol, which production does it appear on the right TreeSet<Character> follow=new TreeSet<Character>() Iterator<Character> iterator=vnSet.iterator() while(iterator.hasNext()) {//Scan each left itemChar Character itemChar=iterator.next() if(itemChar.equals(start))//If it is a start symbol, add # to the follow set follow.add('#') ArrayList<String> itemArr=expression.get(itemChar) for(String itemStr:itemArr) { char xs=S.charValue() if(itemStr.indexOf(xs)>0) for(int i=0i<itemStr.length()i++) { if(itemStr.charAt(i)==xs)//Prevent the situation where the right part is SaSb, that is, it appears multiple times on the right part { Character temp=itemStr.charAt(i+1)//A symbol after the non-terminal s if(vtSet.contains(temp))//After the terminator follow.add(temp) else if(vnSet.contains(temp)) {//After the non-terminal symbol int j for(j=i+1j<itemStr.length()j++) { Character temps=itemStr.charAt(j) TreeSet<Character> first=firstMap.get(temps) for(Character x:first) follow.add(x) if(unBlankSet.contains(temps)) break if(vtSet.contains(temps)) break } if(j==itemStr.length()) {//The situation where all behind is blank calFollow(itemChar) TreeSet<Character> tempFollow=followMap.get(itemChar) for(Character e:tempFollow) follow.add(e) } } else { calFollow(itemChar) TreeSet<Character> tempFollow=followMap.get(itemChar) for(Character e:tempFollow) follow.add(e) } } } } } if(follow.contains('^')) follow.remove('^') followMap.put(S, follow) } public int toBlank(Character S,String itemStr) {//Directly go to ^ and return 0, and the non-terminal on the right can go to ^ and return -1, but not to ^ and return 1. if(itemStr.equals('^')) return 0 for(int i=0i<itemStr.length()i++) vtSet.contains(itemChar)) return 1 return -1 } public void getSelect() { Iterator<Character> iterator=vnSet.iterator() while(iterator.hasNext()) {//For each non-terminal symbol itemChar Character itemChar=iterator.next() HashMap<String, TreeSet<Character>> selectItemMap = new HashMap<String, TreeSet<Character>>() ArrayList<String> itemArr=expression.get(itemChar) for(String itemStr:itemArr) {//For each production right itemStr TreeSet<Character> selectSet = new TreeSet<Character>() if(toBlank(itemChar,itemStr)==1) {//No way^ for(int i=0i<itemStr.length()i++) { Character x=itemStr.charAt(i) if(vtSet.contains(x)){ selectSet.add(x) break } TreeSet<Character> first=firstMap.get(x) for(Character temp:first) selectSet.add(temp) if(unBlankSet.contains(x)) break } } else if(toBlank(itemChar,itemStr)==0) {//The right part is directly ^ TreeSet<Character> follow=followMap.get(itemChar) for(Character temp:follow) selectSet.add(temp) } else {//The right part is all non-terminals that can reach ^ for(int i=0i<itemStr.length()i++) {//First on the right Character m=itemStr.charAt(i) TreeSet<Character> first=firstMap.get(m) for(Character temp:first) selectSet.add(temp) } TreeSet<Character> follow=followMap.get(itemChar) for(Character temp:follow)//And follow on the top left selectSet.add(temp) } selectItemMap.put(itemStr, selectSet) } selectMap.put(itemChar, selectItemMap) } } public void getAnalyzeTab() { TreeSet<Character> head=new TreeSet<Character>(vtSet) head.add('^') head.add('#') int m=vnSet.size()+1 int n=head.size()+1 analyzeTable=new String[m][n] Iterator<Character> iterator=vnSet.iterator() int i=1,j=1 for(Character temp:head) {//Initialize the first line analyzeTable[0][i]=temp+'' i++ } i=1 for(Character temp:vnSet) {//Initialize the first column analyzeTable[i][0]=temp+'' } while(iterator.hasNext()) { Character itemChar=iterator.next() ArrayList<String> itemArr=expression.get(itemChar) for(Character temp:head) { for(String itemStr:itemArr) { HashMap<String, TreeSet<Character>> temp1=selectMap.get(itemChar) TreeSet<Character> temp2=temp1.get(itemStr) if(temp2.contains(temp)) { analyzeTable[i][j]=itemStr break } } j++ } i++ } } public void setGsArray(ArrayList<String> gsArray) { this.gsArray=gsArray } public ArrayList<String> getGsArray(){ return gsArray } public void setExpression(HashMap<Character, ArrayList<String>> expression) { this.expression=expression } public HashMap<Character, ArrayList<String>> getExpression() { return expression } public void setVnSet(TreeSet<Character> vnSet) { this.vnSet=vnSet } public TreeSet<Character> getVnSet(){ return vnSet } public void setVtSet(TreeSet<Character> vtSet) { this.vtSet=vtSet } public TreeSet<Character> getVtSet(){ return vtSet } public void setStart(Character s) { this.start=s } public Character getStart() { return start } public void setNumSet(HashMap<Character,Integer> numSet) { this.numSet=numSet } public HashMap<Character,Integer> getNumSet(){ return numSet } public void setBlankSet(TreeSet<Character> blankSet) { this.blankSet=blankSet } public TreeSet<Character> getBlankSet(){ return blankSet } public void setUnBlankSet(TreeSet<Character> unBlankSet) { this.unBlankSet=unBlankSet } public TreeSet<Character> getUnBlankSet(){ return unBlankSet } public void setFirstMap(HashMap<Character, TreeSet<Character>> firstMap) { this.firstMap=firstMap } public HashMap<Character, TreeSet<Character>> getFirstMap(){ return firstMap } public void setFollowMap(HashMap<Character, TreeSet<Character>> followMap) { this.followMap=followMap } public HashMap<Character, TreeSet<Character>> getFollowMap(){ return followMap } public void setSelectMap(TreeMap<Character, HashMap<String, TreeSet<Character>>> selectMap) { this.selectMap=selectMap } public TreeMap<Character, HashMap<String, TreeSet<Character>>> getSelectMap(){ return selectMap } public void setAnalyzeTable(String[][] analyzeTable) { this.analyzeTable=analyzeTable } public String[][] getAnalyzeTable(){ return analyzeTable } }