语法设计——基于LL(1)文法的预测分析表法

package python;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet; 
import java.util.Stack;
/**
 * @author Angel_Kitty
 * @createTime 2018年11月24日 上午0:46:33
 */
class TextUtil {
  /**
   * (3)B->aA,=Follow(B)
   * 
   * @param nvSet
   * @param itemCharStr
   * @param a
   * @param expressionMap
   * @return
   */
  public static boolean containsbA(TreeSet<Character> nvSet, String itemCharStr, Character a,
      HashMap<Character, ArrayList<String>> expressionMap) {
    String aStr = a.toString();
    String lastStr = itemCharStr.substring(itemCharStr.length() - 1);
    if (lastStr.equals(aStr)) {
      return true;
    }
    return false;
  }
  /**
   * 形如aBb,b=空
   * 
   * @param nvSet
   * @param itemCharStr
   * @param a
   * @param expressionMap
   * @return
   */
  public static boolean containsbAbIsNull(TreeSet<Character> nvSet, String itemCharStr, Character a,
      HashMap<Character, ArrayList<String>> expressionMap) {
    String aStr = a.toString();
    if (containsAB(nvSet, itemCharStr, a)) {
      Character alastChar = getAlastChar(itemCharStr, a);
      System.out.println("----------------+++++++++++++++++++--" + expressionMap.toString());
      ArrayList<String> arrayList = expressionMap.get(alastChar);
      if (arrayList.contains("ε")) {
        System.out.println(alastChar + "  contains('ε')" + aStr);
        return true;
      }
    }
    return false;
  }
  /**
   * 是否包含这种的字符串<Br>
   * (2)Ab,=First(b)-ε,直接添加终结符
   * 
   * @param str
   * @param a
   * @return
   */
  public static boolean containsAb(TreeSet<Character> ntSet, String itemCharStr, Character a) {
    String aStr = a.toString();
    if (itemCharStr.contains(aStr)) {
      int aIndex = itemCharStr.indexOf(aStr);
      String findStr;
      try {
        findStr = itemCharStr.substring(aIndex + 1, aIndex + 2);
      } catch (Exception e) {
        return false;
      }
      if (ntSet.contains(findStr.charAt(0))) {
        return true;
      } else {
        return false;
      }
    } else {
      return false;
    }
  }
  /**
   * 是否包含这种的字符串<Br>
   * (2).2Ab,=First(b)-ε
   * 
   * @param str
   * @param a
   * @return
   */
  public static boolean containsAB(TreeSet<Character> nvSet, String itemCharStr, Character a) {
    String aStr = a.toString();
    if (itemCharStr.contains(aStr)) {
      int aIndex = itemCharStr.indexOf(aStr);
      String findStr;
      try {
        findStr = itemCharStr.substring(aIndex + 1, aIndex + 2);
      } catch (Exception e) {
        return false;
      }
      if (nvSet.contains(findStr.charAt(0))) {
        return true;
      } else {
        return false;
      }
    } else {
      return false;
    }
  }
  /**
   * 获取A后的字符
   * 
   * @param itemCharStr
   * @param a
   * @return
   */
  public static Character getAlastChar(String itemCharStr, Character a) {
    String aStr = a.toString();
    if (itemCharStr.contains(aStr)) {
      int aIndex = itemCharStr.indexOf(aStr);
      String findStr = "";
      try {
        findStr = itemCharStr.substring(aIndex + 1, aIndex + 2);
      } catch (Exception e) {
        return null;
      }
      return findStr.charAt(0);
    }
    return null;
  }
  /**
   * 是否为ε开始的
   * 
   * @param selectExp
   * @return
   */
  public static boolean isEmptyStart(String selectExp) {
    char charAt = selectExp.charAt(0);
    if (charAt == 'ε') {
      return true;
    }
    return false;
  }
  /**
   * 是否是终结符开始的
   * 
   * @param ntSet
   * @param selectExp
   * @return
   */
  public static boolean isNtStart(TreeSet<Character> ntSet, String selectExp) {
    char charAt = selectExp.charAt(0);
    if (ntSet.contains(charAt)) {
      return true;
    }
    return false;
  }
  /**
   * 是否是非终结符开始的
   * 
   * @param nvSet
   * @param selectExp
   * @return
   */
  public static boolean isNvStart(TreeSet<Character> nvSet, String selectExp) {
    char charAt = selectExp.charAt(0);
    if (nvSet.contains(charAt)) {
      return true;
    }
    return false;
  }
  /**
   * 查找产生式
   * 
   * @param selectMap
   * @param peek
   *            当前Nv
   * @param charAt
   *            当前字符
   * @return
   */
  public static String findUseExp(TreeMap<Character, HashMap<String, TreeSet<Character>>> selectMap, Character peek,
      char charAt) {
    try {
      HashMap<String, TreeSet<Character>> hashMap = selectMap.get(peek);
      Set<String> keySet = hashMap.keySet();
      for (String useExp : keySet) {
        TreeSet<Character> treeSet = hashMap.get(useExp);
        if (treeSet.contains(charAt)) {
          return useExp;
        }
      }
    } catch (Exception e) {
      return null;
    }
    return null;
  }
}
class Analyzer {
  public Analyzer() {
    super();
    analyzeStatck = new Stack<Character>();
    // 结束符进栈
    analyzeStatck.push('#');
  }
  private ArrayList<AnalyzeProduce> analyzeProduces;
  /**
   * LL（1）文法
   */
  private Gs ll1Gs;
  public Gs getLl1Gs() {
    return ll1Gs;
  }
  public void setLl1Gs(Gs ll1Gs) {
    this.ll1Gs = ll1Gs;
  }
  /**
   * 开始符
   */
  private Character startChar;
  /**
   * 分析栈
   */
  private Stack<Character> analyzeStatck;
  /**
   * 剩余输入串
   */
  private String str;
  /**
   * 推导所用产生或匹配
   */
  private String useExp;
  public ArrayList<AnalyzeProduce> getAnalyzeProduces() {
    return analyzeProduces;
  }
  public void setAnalyzeProduces(ArrayList<AnalyzeProduce> analyzeProduces) {
    this.analyzeProduces = analyzeProduces;
  }
  public Character getStartChar() {
    return startChar;
  }
  public void setStartChar(Character startChar) {
    this.startChar = startChar;
  }
  public Stack<Character> getAnalyzeStatck() {
    return analyzeStatck;
  }
  public void setAnalyzeStatck(Stack<Character> analyzeStatck) {
    this.analyzeStatck = analyzeStatck;
  }
  public String getStr() {
    return str;
  }
  public void setStr(String str) {
    this.str = str;
  }
  public String getUseExp() {
    return useExp;
  }
  public void setUseExp(String useExp) {
    this.useExp = useExp;
  }
  /**
   * 分析
   */
  //进栈 flag is here
  public void analyze() {
    analyzeProduces = new ArrayList<AnalyzeProduce>();
    // 开始符进栈
    analyzeStatck.push(startChar);
    System.out.println("开始符:" + startChar);
    System.out.println("步骤\t\t\t " + "符号栈\t\t        " + "\t输入串 \t\t\t" + "所用产生式 ");
    int index = 0;
    // 开始分析
    // while (analyzeStatck.peek() != '#' && str.charAt(0) != '#') {
    while (!analyzeStatck.empty()) {
      index++;
      //返回栈顶元素
      if (analyzeStatck.peek() != str.charAt(0)) {
        // 到分析表中找到这个产生式
        String nowUseExpStr = TextUtil.findUseExp(ll1Gs.getSelectMap(), analyzeStatck.peek(), str.charAt(0));
        System.out.println(index + "\t\t\t" + analyzeStatck.toString() + "\t\t\t" + str + "\t\t\t"
            + analyzeStatck.peek() + "->" + nowUseExpStr);
        AnalyzeProduce produce = new AnalyzeProduce();
        produce.setIndex(index);
        produce.setAnalyzeStackStr(analyzeStatck.toString());
        produce.setStr(str);
        if (null == nowUseExpStr) {
          produce.setUseExpStr("无法匹配!");
        } else {
          produce.setUseExpStr(analyzeStatck.peek() + "->" + nowUseExpStr);
        }
        analyzeProduces.add(produce);
        // 将之前的分析栈中的栈顶出栈
        analyzeStatck.pop();
        // 将要用到的表达式入栈,反序入栈
        if (null != nowUseExpStr && nowUseExpStr.charAt(0) != 'ε') {
          for (int j = nowUseExpStr.length() - 1; j >= 0; j--) {
            char currentChar = nowUseExpStr.charAt(j);
            analyzeStatck.push(currentChar);
          }
        }
        continue;
      }
      // 如果可以匹配,分析栈出栈，串去掉一位
      if (analyzeStatck.peek() == str.charAt(0)) {
        System.out.println(index + "\t\t\t" + analyzeStatck.toString() + "\t\t\t" + str + "\t\t\t" + "“"
            + str.charAt(0) + "”匹配");
        AnalyzeProduce produce = new AnalyzeProduce();
        produce.setIndex(index);
        produce.setAnalyzeStackStr(analyzeStatck.toString());
        produce.setStr(str);
        produce.setUseExpStr("“" + str.charAt(0) + "”匹配");
        analyzeProduces.add(produce);
        analyzeStatck.pop();
        str = str.substring(1);
        continue;
      }
    }
  }
}
class AnalyzeProduce implements Serializable{
  private static final long serialVersionUID = 10L;
  private Integer index;
  private String analyzeStackStr;
  private String str;
  private String useExpStr;
  public Integer getIndex() {
    return index;
  }
  public void setIndex(Integer index) {
    this.index = index;
  }
  public String getAnalyzeStackStr() {
    return analyzeStackStr;
  }
  public void setAnalyzeStackStr(String analyzeStackStr) {
    this.analyzeStackStr = analyzeStackStr;
  }
  public String getStr() {
    return str;
  }
  public void setStr(String str) {
    this.str = str;
  }
  public String getUseExpStr() {
    return useExpStr;
  }
  public void setUseExpStr(String useExpStr) {
    this.useExpStr = useExpStr;
  }
}
class Gs implements Serializable {
  /**
   * 
   */
  private static final long serialVersionUID = 1L;
  public Gs() {
    super();
    gsArray = new ArrayList<String>();
    nvSet = new TreeSet<Character>();
    ntSet = new TreeSet<Character>();
    firstMap = new HashMap<Character, TreeSet<Character>>();
    followMap = new HashMap<Character, TreeSet<Character>>();
    selectMap = new TreeMap<Character, HashMap<String, TreeSet<Character>>>();
  }
  private String[][] analyzeTable;
  /**
   * Select集合
   */
  private TreeMap<Character, HashMap<String, TreeSet<Character>>> selectMap;
  /**
   * LL（1）文法产生集合
   */
  private ArrayList<String> gsArray;
  /**
   * 表达式集合
   */
  private HashMap<Character, ArrayList<String>> expressionMap;
  /**
   * 开始符
   */
  private Character s;
  /**
   * Vn非终结符集合
   */
  private TreeSet<Character> nvSet;
  /**
   * Vt终结符集合
   */
  private TreeSet<Character> ntSet;
  /**
   * First集合
   */
  private HashMap<Character, TreeSet<Character>> firstMap;
  /**
   * Follow集合
   */
  private HashMap<Character, TreeSet<Character>> followMap;
  public String[][] getAnalyzeTable() {
    return analyzeTable;
  }
  public void setAnalyzeTable(String[][] analyzeTable) {
    this.analyzeTable = analyzeTable;
  }
  public TreeMap<Character, HashMap<String, TreeSet<Character>>> getSelectMap() {
    return selectMap;
  }
  public void setSelectMap(TreeMap<Character, HashMap<String, TreeSet<Character>>> selectMap) {
    this.selectMap = selectMap;
  }
  public HashMap<Character, TreeSet<Character>> getFirstMap() {
    return firstMap;
  }
  public void setFirstMap(HashMap<Character, TreeSet<Character>> firstMap) {
    this.firstMap = firstMap;
  }
  public HashMap<Character, TreeSet<Character>> getFollowMap() {
    return followMap;
  }
  public void setFollowMap(HashMap<Character, TreeSet<Character>> followMap) {
    this.followMap = followMap;
  }
  public HashMap<Character, ArrayList<String>> getExpressionMap() {
    return expressionMap;
  }
  public void setExpressionMap(HashMap<Character, ArrayList<String>> expressionMap) {
    this.expressionMap = expressionMap;
  }
  public ArrayList<String> getGsArray() {
    return gsArray;
  }
  public void setGsArray(ArrayList<String> gsArray) {
    this.gsArray = gsArray;
  }
  public Character getS() {
    return s;
  }
  public void setS(Character s) {
    this.s = s;
  }
  public TreeSet<Character> getNvSet() {
    return nvSet;
  }
  public void setNvSet(TreeSet<Character> nvSet) {
    this.nvSet = nvSet;
  }
  public TreeSet<Character> getNtSet() {
    return ntSet;
  }
  public void setNtSet(TreeSet<Character> ntSet) {
    this.ntSet = ntSet;
  }
  /**
   * 获取非终结符集与终结符集
   * 
   * @param gsArray
   * @param nvSet
   * @param ntSet
   */
  public void getNvNt() {
    for (String gsItem : gsArray) {
      String[] nvNtItem = gsItem.split("->");
      String charItemStr = nvNtItem[0];
      char charItem = charItemStr.charAt(0);
      // nv在左边
      nvSet.add(charItem);
    }
    for (String gsItem : gsArray) {
      String[] nvNtItem = gsItem.split("->");
      // nt在右边
      String nvItemStr = nvNtItem[1];
      // 遍历每一个字
      for (int i = 0; i < nvItemStr.length(); i++) {
        char charItem = nvItemStr.charAt(i);
        if (!nvSet.contains(charItem)) {
          ntSet.add(charItem);
        }
      }
    }
  }
  /**
   * 初始化表达式集合
   */
  public void initExpressionMaps() {
    expressionMap = new HashMap<Character, ArrayList<String>>();
    for (String gsItem : gsArray) {
      String[] nvNtItem = gsItem.split("->");
      String charItemStr = nvNtItem[0];
      String charItemRightStr = nvNtItem[1];
      char charItem = charItemStr.charAt(0);
      if (!expressionMap.containsKey(charItem)) {
        ArrayList<String> expArr = new ArrayList<String>();
        expArr.add(charItemRightStr);
        expressionMap.put(charItem, expArr);
      } else {
        ArrayList<String> expArr = expressionMap.get(charItem);
        expArr.add(charItemRightStr);
        expressionMap.put(charItem, expArr);
      }
    }
  }
  /**
   * 获取First集
   */
  public void getFirst() {
    // 遍历所有Nv,求出它们的First集合
    Iterator<Character> iterator = nvSet.iterator();
    while (iterator.hasNext()) {
      Character charItem = iterator.next();
      ArrayList<String> arrayList = expressionMap.get(charItem);
      for (String itemStr : arrayList) {
        boolean shouldBreak = false;
        // Y1Y2Y3...Yk
        for (int i = 0; i < itemStr.length(); i++) {
          char itemitemChar = itemStr.charAt(i);
          TreeSet<Character> itemSet = firstMap.get(charItem);
          if (null == itemSet) {
            itemSet = new TreeSet<Character>();
          }
          shouldBreak = calcFirst(itemSet, charItem, itemitemChar);
          if (shouldBreak) {
            break;
          }
        }
      }
    }
  }
  /**
   * 计算First函数
   * 
   * @param itemSet
   * @param charItem
   * @param itemitemChar
   * @return
   */
  private boolean calcFirst(TreeSet<Character> itemSet, Character charItem, char itemitemChar) {
    // get ago
    // TreeSet<Character> itemSet = new TreeSet<Character>();
    // 将它的每一位和Nt判断下
    // 是终结符或空串,就停止，并将它加到FirstMap中
    if (itemitemChar == 'ε' || ntSet.contains(itemitemChar)) {
      itemSet.add(itemitemChar);
      firstMap.put(charItem, itemSet);
      // break;
      return true;
    } else if (nvSet.contains(itemitemChar)) {// 这一位是一个非终结符
      ArrayList<String> arrayList = expressionMap.get(itemitemChar);
      for (int i = 0; i < arrayList.size(); i++) {
        String string = arrayList.get(i);
        char tempChar = string.charAt(0);
        calcFirst(itemSet, charItem, tempChar);
      }
    }
    return true;
  }
  /**
   * 获取Follow集合
   */
  public void getFollow() {
    for (Character tempKey : nvSet) {
      TreeSet<Character> tempSet = new TreeSet<Character>();
      followMap.put(tempKey, tempSet);
    }
    // 遍历所有Nv,求出它们的First集合
    Iterator<Character> iterator = nvSet.descendingIterator();
    // nvSet.descendingIterator();
    while (iterator.hasNext()) {
      Character charItem = iterator.next();
      System.out.println("charItem:" + charItem);
      Set<Character> keySet = expressionMap.keySet();
      for (Character keyCharItem : keySet) {
        ArrayList<String> charItemArray = expressionMap.get(keyCharItem);
        for (String itemCharStr : charItemArray) {
          System.out.println(keyCharItem + "->" + itemCharStr);
          TreeSet<Character> itemSet = followMap.get(charItem);
          calcFollow(charItem, charItem, keyCharItem, itemCharStr, itemSet);
        }
      }
    }
  }
  /**
   * 计算Follow集
   * 
   * @param putCharItem
   *            正在查询item
   * @param charItem
   *            待找item
   * @param keyCharItem
   *            节点名
   * @param itemCharStr
   *            符号集
   * @param itemSet
   *            结果集合
   */
  private void calcFollow(Character putCharItem, Character charItem, Character keyCharItem, String itemCharStr,
      TreeSet<Character> itemSet) {
    ///////
    // （1）A是S（开始符)，加入#
    if (charItem.equals(s)) {
      itemSet.add('#');
      System.out.println("---------------find S:" + charItem + "   ={#}+Follow(E)");
      followMap.put(putCharItem, itemSet);
      // return;
    }
    // (2)Ab,=First(b)-ε,直接添加终结符
    if (TextUtil.containsAb(ntSet, itemCharStr, charItem)) {
      Character alastChar = TextUtil.getAlastChar(itemCharStr, charItem);
      System.out.println("---------------find Ab:" + itemCharStr + "    " + charItem + "   =" + alastChar);
      itemSet.add(alastChar);
      followMap.put(putCharItem, itemSet);
      // return;
    }
    // (2).2AB,=First(B)-ε,=First(B)-ε，添加first集合
    if (TextUtil.containsAB(nvSet, itemCharStr, charItem)) {
      Character alastChar = TextUtil.getAlastChar(itemCharStr, charItem);
      System.out.println(
          "---------------find AB:" + itemCharStr + "    " + charItem + "   =First(" + alastChar + ")");
      TreeSet<Character> treeSet = firstMap.get(alastChar);
      itemSet.addAll(treeSet);
      if (treeSet.contains('ε')) {
        itemSet.add('#');
      }
      itemSet.remove('ε');
      followMap.put(putCharItem, itemSet);
      ///////////////////////
      if (TextUtil.containsbAbIsNull(nvSet, itemCharStr, charItem, expressionMap)) {
        char tempChar = TextUtil.getAlastChar(itemCharStr, charItem);
        System.out.println("tempChar:" + tempChar + "  key" + keyCharItem);
        if (!keyCharItem.equals(charItem)) {
          System.out.println("---------------find tempChar bA: " + "tempChar:" + tempChar + keyCharItem
              + "   " + itemCharStr + "    " + charItem + "   =Follow(" + keyCharItem + ")");
          Set<Character> keySet = expressionMap.keySet();
          for (Character keyCharItems : keySet) {
            ArrayList<String> charItemArray = expressionMap.get(keyCharItems);
            for (String itemCharStrs : charItemArray) {
              calcFollow(putCharItem, keyCharItem, keyCharItems, itemCharStrs, itemSet);
            }
          }
        }
      }
    }
    // (3)B->aA,=Follow(B),添加followB
    if (TextUtil.containsbA(nvSet, itemCharStr, charItem, expressionMap)) {
      if (!keyCharItem.equals(charItem)) {
        System.out.println("---------------find bA: " + keyCharItem + "   " + itemCharStr + "    " + charItem
            + "   =Follow(" + keyCharItem + ")");
        Set<Character> keySet = expressionMap.keySet();
        for (Character keyCharItems : keySet) {
          ArrayList<String> charItemArray = expressionMap.get(keyCharItems);
          for (String itemCharStrs : charItemArray) {
            calcFollow(putCharItem, keyCharItem, keyCharItems, itemCharStrs, itemSet);
          }
        }
      }
    }
  }
  /**
   * 获取Select集合
   */
  public void getSelect() {
    // 遍历每一个表达式
    // HashMap<Character, HashMap<String, TreeSet<Character>>>
    Set<Character> keySet = expressionMap.keySet();
    for (Character selectKey : keySet) {
      ArrayList<String> arrayList = expressionMap.get(selectKey);
      // 每一个表达式
      HashMap<String, TreeSet<Character>> selectItemMap = new HashMap<String, TreeSet<Character>>();
      for (String selectExp : arrayList) {
        /**
         * 存放select结果的集合
         */
        TreeSet<Character> selectSet = new TreeSet<Character>();
        // set里存放的数据分3种情况,由selectExp决定
        // 1.A->ε,=follow(A)
        if (TextUtil.isEmptyStart(selectExp)) {
          selectSet = followMap.get(selectKey);
          selectSet.remove('ε');
          selectItemMap.put(selectExp, selectSet);
        }
        // 2.Nt开始,=Nt
        // <br>终结符开始
        if (TextUtil.isNtStart(ntSet, selectExp)) {
          selectSet.add(selectExp.charAt(0));
          selectSet.remove('ε');
          selectItemMap.put(selectExp, selectSet);
        }
        // 3.Nv开始，=first(Nv)
        if (TextUtil.isNvStart(nvSet, selectExp)) {
          selectSet = firstMap.get(selectKey);
          selectSet.remove('ε');
          selectItemMap.put(selectExp, selectSet);
        }
        selectMap.put(selectKey, selectItemMap);
      }
    }
  }
  /**
   * 生成预测分析表
   */
  public void genAnalyzeTable() throws Exception {
    Object[] ntArray = ntSet.toArray();
    Object[] nvArray = nvSet.toArray();
    // 预测分析表初始化
    analyzeTable = new String[nvArray.length + 1][ntArray.length + 1];
    // 输出一个占位符
    System.out.print("Nv/Nt" + "\t\t");
    analyzeTable[0][0] = "Nv/Nt";
    // 初始化首行
    for (int i = 0; i < ntArray.length; i++) {
      if (ntArray[i].equals('ε')) {
        ntArray[i] = '#';
      }
      System.out.print(ntArray[i] + "\t\t");
      analyzeTable[0][i + 1] = ntArray[i] + "";
    }
    System.out.println("");
    for (int i = 0; i < nvArray.length; i++) {
      // 首列初始化
      System.out.print(nvArray[i] + "\t\t");
      analyzeTable[i + 1][0] = nvArray[i] + "";
      for (int j = 0; j < ntArray.length; j++) {
        String findUseExp = TextUtil.findUseExp(selectMap, Character.valueOf((Character) nvArray[i]),
            Character.valueOf((Character) ntArray[j]));
        if (null == findUseExp) {
          System.out.print("\t\t");
          analyzeTable[i + 1][j + 1] = "";
        } else {
          System.out.print(nvArray[i] + "->" + findUseExp + "\t\t");
          analyzeTable[i + 1][j + 1] = nvArray[i] + "->" + findUseExp;
        }
      }
      System.out.println();
    }
  }
}
/*主程序*/
public class LL1_modify {
  public static void main(String[] args) throws Exception {
    // TODO Auto-generated method stub
    // // LL（1）文法产生集合
        ArrayList<String> gsArray = new ArrayList<String>();
        // // Vn非终结符集合
        // TreeSet<Character> nvSet = new TreeSet<Character>();
        // // Vt终结符集合
        // TreeSet<Character> ntSet = new TreeSet<Character>();
        Gs gs = new Gs();
        initGs(gsArray);
        gs.setGsArray(gsArray);
        // getNvNt(gsArray, gs.getNvSet(), gs.getNtSet());
        gs.getNvNt();
        gs.initExpressionMaps();
        gs.getFirst();
        // 设置开始符
        gs.setS('E');
        gs.getFollow();
        gs.getSelect();
        // 创建一个分析器
        Analyzer analyzer = new Analyzer();
        analyzer.setStartChar('E');
        analyzer.setLl1Gs(gs);
        analyzer.setStr("i+i*i#");
        analyzer.analyze();
        gs.genAnalyzeTable();
        System.out.println("");
      }
      /**
       * 获取非终结符集与终结符集
       * 
       * @param gsArray
       * @param nvSet
       * @param ntSet
       */
      private static void getNvNt(ArrayList<String> gsArray, TreeSet<Character> nvSet, TreeSet<Character> ntSet) {
        for (String gsItem : gsArray) {
          String[] nvNtItem = gsItem.split("->");
          String charItemStr = nvNtItem[0];
          char charItem = charItemStr.charAt(0);
          // nv在左边
          nvSet.add(charItem);
        }
        for (String gsItem : gsArray) {
          String[] nvNtItem = gsItem.split("->");
          // nt在右边
          String nvItemStr = nvNtItem[1];
          // 遍历每一个字
          for (int i = 0; i < nvItemStr.length(); i++) {
            char charItem = nvItemStr.charAt(i);
            if (!nvSet.contains(charItem)) {
              ntSet.add(charItem);
            }
          }
        }
      }
      /**
       * 初始化LL(1)文法
       * 
       * @param gsArray
       */
      private static void initGs(ArrayList<String> gsArray) {
        // Z相当于E',Y相当于T'
        gsArray.add("E->TZ");
        gsArray.add("Z->+TZ");
        gsArray.add("Z->ε");
        gsArray.add("Z->+TZ");
        gsArray.add("T->FY");
        gsArray.add("Z->+TZ");
        gsArray.add("Y->*FY");
        gsArray.add("Y->ε");
        gsArray.add("F->i");
        gsArray.add("F->(E)");
      }
}