编译原理：java实现求first集

求first集合的思路还是非常清晰的，按照书上的算法。
定义：first(A)={a| A ==>+ aβ }

• 对于终结符而言，first集就是他本身。first(a)={a}
• 对于非终结符，有以下三种情况：
  1. if (A ==>+ ε) then add ε to first(A)
  2. 有产生式A ==> αβ if (α ∈ Vt) then add α to first(A)
  3. 有产生式A ==> Bβ add first(B) to first(A)
     重复应用这几条规则，直到所有集合都没有增长。

代码说明：
first:Map<String,List<String>> key:Vn,Vt value:对应var的first集
terminals:Set<String>终结符集合
nonTerminals:Set<String>非终结符集合

实现思路：
直接看代码就好啦～
额外需要说的一点是！这里一定要注意深拷贝问题，因为哪怕是用putAll也并没有完全深拷贝，因为我的map的value是Set,仍然是引用，所以一定要自己手动new一个set，然后add进去。才真正实现了深拷贝。

public void generateFirstCollection() {
    //所有终结符的first集合就是自己
    for (String ter : terminals) {
      Set<String> set = new HashSet<>();
      set.add(ter);
      first.put(ter, set);
    }
    //非终结符注册，避免判断first.containsKey，更简洁
    for (String non : nonTerminals) {
      Set<String> set = new HashSet<>();
      first.put(non, set);
    }

    while (true) {
      //手动深拷贝
      Map<String, Set<String>> firstClone = new HashMap<>();
      for(Entry<String,Set<String>>entry:first.entrySet()){
        Set<String>set=new HashSet<>();
        for(String s:entry.getValue() ){
          set.add(s);
        }
        firstClone.put(entry.getKey(),set);
      }

     for (Production p : productions) {
        String rightHead = p.getRights().get(0);
        // * - 有产生式A ==> αβ if (α ∈ VT) then add α to first(A)
        if (terminals.contains(rightHead)) {
          Set<String> set = firstClone.get(p.getLeft());
          set.add(rightHead);
          firstClone.replace(p.getLeft(), set);
        }
        if (nonTerminals.contains(rightHead) && firstClone.containsKey(rightHead)) {
          Set<String> set = firstClone.get(p.getLeft());
          set.addAll(firstClone.get(rightHead));
          firstClone.replace(p.getLeft(), set);
        }
      }
      //判断有无改变
      if (isSameMap(first, firstClone)) {
        return;
      } else {
        first = firstClone;
      }
    }
  }