LL(1)文法判断程序java代码.doc

LL(1)文法判断程序java代码分为两个类import java.util.ArrayList;import java.util.HashMap;import java.util.HashSet;import java.util.Stack;public class LL_1 public HashMapCharacter, HashSet firstSet = new HashMapCharacter, HashSet();public HashMapString, HashSet firstSetX = new HashMapString, HashSet();public Character S = E;public HashMapCharacter, HashSet followSet = new HashMapCharacter, HashSet();public HashSet VnSet = new HashSet();public HashSet VtSet = new HashSet();public HashMapCharacter, ArrayList experssionSet = new HashMapCharacter, ArrayList();public String inputExperssion = E-TK, K-+TK, K-, T-FM, M-*FM, M-, F-i, F-(E) ;public String table;public Stack analyzeStatck = new Stack();public String strInput = i+i*i#;public String action = ;int index = 0;public void Init() for (String e : inputExperssion) String str = e.split(-);char c = str0.charAt(0);ArrayList list = experssionSet.containsKey(c) ? experssionSet.get(c) : new ArrayList();list.add(str1);experssionSet.put(c, list);for (Character c : VnSet)getFirst(c);for (Character c : VnSet) ArrayList l = experssionSet.get(c);for (String s : l)getFirst(s);getFollow(S);for (Character c : VnSet) getFollow(c);public void getNvNt() for (String e : inputExperssion) String str = e.split(-);VnSet.add(str0.charAt(0);for (String e : inputExperssion) String str = e.split(-);String right = str1;for (int i = 0; i right.length(); i+)if (!VnSet.contains(right.charAt(i)VtSet.add(right.charAt(i);public void getFirst(Character c) ArrayList list = experssionSet.get(c);HashSet set = firstSet.containsKey(c) ? firstSet.get(c) : new HashSet();/ c为终结符 直接添加if (VtSet.contains(c) set.add(c);firstSet.put(c, set);return;/ c为非终结符 处理其每条产生式for (String s : list) / c 推出空串 直接添加if (s = Character.toString() set.add();/ X - Y1Y2Y3 情况else / 从左往右扫描生成式右部int i = 0;while (i s.length() char tn = s.charAt(i);/ 先处理防止未初始化getFirst(tn);HashSet tvSet = firstSet.get(tn);/ 将其first集加入左部for (Character tmp : tvSet)set.add(tmp);/ 若包含空串 处理下一个符号if (tvSet.contains()i+;/ 否则退出 处理下一个产生式elsebreak;firstSet.put(c, set);public void getFirst(String s) HashSet set = (firstSetX.containsKey(s) ? firstSetX.get(s) : new HashSet();/ 从左往右扫描该式int i = 0;while (i s.length() char tn = s.charAt(i);HashSet tvSet = firstSet.get(tn);/ 将其非空 first集加入左部for (Character tmp : tvSet)if (tmp != )set.add(tmp);/ 若包含空串 处理下一个符号if (tvSet.contains()i+;/ 否则结束elsebreak;/ 到了尾部 即所有符号的first集都包含空串 把空串加入if (i = s.length() set.add();firstSetX.put(s, set);public void getFollow(char c) ArrayList list = experssionSet.get(c);HashSet setA = followSet.containsKey(c) ? followSet.get(c) : new HashSet();/ 如果是开始符 添加 #if (c = S) setA.add(#);/ 查找输入的所有产生式，确定c的后跟 终结符for (Character ch : VnSet) ArrayList l = experssionSet.get(ch);for (String s : l)for (int i = 0; i s.length(); i+)if (s.charAt(i) = c & i + 1 = 0) char tn = s.charAt(i);/ 只处理非终结符if (VnSet.contains(tn) / 都按 A-B 形式处理/ 若不存在 followA 加入 followB/ 若存在，把的非空first集 加入followB/ 若存在 且 first()包含空串 followA 加入 followB/ 若存在if (s.length() - i - 1 0) String right = s.substring(i + 1);/ 非空first集 加入 followBHashSet setF = null;if (right.length() = 1 & firstSet.containsKey(right.charAt(0)setF = firstSet.get(right.charAt(0);else if (!firstSetX.containsKey(right) HashSet set = new HashSet();firstSetX.put(right, set);setF = firstSetX.get(right);HashSet setX = followSet.containsKey(tn) ? followSet.get(tn): new HashSet();for (Character var : setF)if (var != )setX.add(var);followSet.put(tn, setX);/ 若first()包含空串 followA 加入 followBif (setF.contains() if (tn != c) HashSet setB = followSet.containsKey(tn) ? followSet.get(tn): new HashSet();for (Character var : setA)setB.add(var);followSet.put(tn, setB);/ 若不存在 followA 加入 followBelse / A和B相同不添加if (tn != c) HashSet setB = followSet.containsKey(tn) ? followSet.get(tn): new HashSet();for (Character var : setA)setB.add(var);followSet.put(tn, setB);i-;/ 如果是终结符往前看 如 A-aaaBCDaaaa 此时为 CDaaaaelsei-;public void createTable() Object VtArray = VtSet.toArray();Object VnArray = VnSet.toArray();/ 预测分析表初始化table = new StringVnArray.length + 1VtArray.length + 1;table00 = Vn/Vt;/ 初始化首行首列for (int i = 0; i VtArray.length; i+)table0i + 1 = (VtArrayi.toString().charAt(0) = ) ? # : VtArrayi.toString();for (int i = 0; i VnArray.length; i+)tablei + 10 = VnArrayi + ;/ 全部置errorfor (int i = 0; i VnArray.length; i+)for (int j = 0; j VtArray.length; j+)tablei + 1j + 1 = error;/ 插入生成式for (char A : VnSet) ArrayList l = experssionSet.get(A);for (String s : l) HashSet set = firstSetX.get(s);for (char a : set)insert(A, a, s);if (set.contains() HashSet setFollow = followSet.get(A);if (setFollow.contains(#)insert(A, #, s);for (char b : setFollow)insert(A, b, s);public void analyzeLL() System.out.println( Stack Input Action);analyzeStatck.push(#);analyzeStatck.push(E);displayLL();char X = analyzeStatck.peek();while (X != #) char a = strInput.charAt(index);if (X = a) action = 匹配 + analyzeStatck.peek();analyzeStatck.pop();index+; else if (VtSet.contains(X)return;else if (find(X, a).equals(error)return;else if (find(X, a).equals() analyzeStatck.pop();action = X + -; else String str = find(X, a);if (str != ) action = X + - + str;analyzeStatck.pop();int len = str.length();for (int i = len - 1; i = 0; i-)analyzeStatck.push(str.charAt(i); else System.out.println(error at + strInput.charAt(index) + in + index);return;X = analyzeStatck.peek();displayLL();System.out.println(Successful,为LL(1)文法);public String find(char X, char a) for (int i = 0; i VnSet.size() + 1; i+) if (tablei0.charAt(0) = X)