LL(1)文法判斷程序java代碼

1、LL(1)文法判斷程序java代碼分為兩個(gè)類import java.util.ArrayList;import java.util.HashMap;import java.util.HashSet;import java.util.Stack;public class LL_1 public HashMap<Character, HashSet<Character>> firstSet = new HashMap<Character, HashSet<Character>>();public HashMap<String, HashSet&

2、lt;Character>> firstSetX = new HashMap<String, HashSet<Character>>();public Character S = 'E'public HashMap<Character, HashSet<Character>> followSet = new HashMap<Character, HashSet<Character>>();public HashSet<Character> VnSet = new HashSet<

3、;Character>();public HashSet<Character> VtSet = new HashSet<Character>();public HashMap<Character, ArrayList<String>> experssionSet = new HashMap<Character, ArrayList<String>>();public String inputExperssion = "E->TK", "K->+TK", "

4、K->", "T->FM", "M->*FM", "M->", "F->i", "F->(E)" ;public String table;public Stack<Character> analyzeStatck = new Stack<Character>();public String strInput = "i+i*i#"public String action = ""int

5、index = 0;public void Init() for (String e : inputExperssion) String str = e.split("->");char c = str0.charAt(0);ArrayList<String> list = experssionSet.containsKey(c) ? experssionSet.get(c) : new ArrayList<String>();list.add(str1);experssionSet.put(c, list);for (Character c

6、: VnSet)getFirst(c);for (Character c : VnSet) ArrayList<String> 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

7、 (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<String> list = experssionSet.get(c);HashSet<Character&

8、gt; set = firstSet.containsKey(c) ? firstSet.get(c) : new HashSet<Character>();/ c為終結(jié)符 直接添加if (VtSet.contains(c) set.add(c);firstSet.put(c, set);return;/ c為非終結(jié)符 處理其每條產(chǎn)生式for (String s : list) / c 推出空串 直接添加if (s = Character.toString('') set.add('');/ X -> Y1Y2Y3 情況else / 從左往右掃

9、描生成式右部int i = 0;while (i < s.length() char tn = s.charAt(i);/ 先處理防止未初始化getFirst(tn);HashSet<Character> tvSet = firstSet.get(tn);/ 將其first集加入左部for (Character tmp : tvSet)set.add(tmp);/ 若包含空串 處理下一個(gè)符號(hào)if (tvSet.contains('')i+;/ 否則退出 處理下一個(gè)產(chǎn)生式elsebreak;firstSet.put(c, set);public void get

10、First(String s) HashSet<Character> set = (firstSetX.containsKey(s) ? firstSetX.get(s) : new HashSet<Character>();/ 從左往右掃描該式int i = 0;while (i < s.length() char tn = s.charAt(i);HashSet<Character> tvSet = firstSet.get(tn);/ 將其非空 first集加入左部for (Character tmp : tvSet)if (tmp != 

11、9;')set.add(tmp);/ 若包含空串 處理下一個(gè)符號(hào)if (tvSet.contains('')i+;/ 否則結(jié)束elsebreak;/ 到了尾部 即所有符號(hào)的first集都包含空串 把空串加入if (i = s.length() set.add('');firstSetX.put(s, set);public void getFollow(char c) ArrayList<String> list = experssionSet.get(c);HashSet<Character> setA = followSet.

12、containsKey(c) ? followSet.get(c) : new HashSet<Character>();/ 如果是開始符 添加 #if (c = S) setA.add('#');/ 查找輸入的所有產(chǎn)生式，確定c的后跟 終結(jié)符for (Character ch : VnSet) ArrayList<String> l = experssionSet.get(ch);for (String s : l)for (int i = 0; i < s.length(); i+)if (s.charAt(i) = c &&

13、i + 1 < s.length() && VtSet.contains(s.charAt(i + 1)setA.add(s.charAt(i + 1);followSet.put(c, setA);/ 處理c的每一條產(chǎn)生式for (String s : list) int i = s.length() - 1;while (i >= 0) char tn = s.charAt(i);/ 只處理非終結(jié)符if (VnSet.contains(tn) / 都按 A->B 形式處理/ 若不存在 followA 加入 followB/ 若存在，把的非空f(shuō)irst集 加

14、入followB/ 若存在 且 first()包含空串 followA 加入 followB/ 若存在if (s.length() - i - 1 > 0) String right = s.substring(i + 1);/ 非空f(shuō)irst集 加入 followBHashSet<Character> setF = null;if (right.length() = 1 && firstSet.containsKey(right.charAt(0)setF = firstSet.get(right.charAt(0);else if (!firstSetX.

15、containsKey(right) HashSet<Character> set = new HashSet<Character>();firstSetX.put(right, set);setF = firstSetX.get(right);HashSet<Character> setX = followSet.containsKey(tn) ? followSet.get(tn): new HashSet<Character>();for (Character var : setF)if (var != '')setX.ad

16、d(var);followSet.put(tn, setX);/ 若first()包含空串 followA 加入 followBif (setF.contains('') if (tn != c) HashSet<Character> setB = followSet.containsKey(tn) ? followSet.get(tn): new HashSet<Character>();for (Character var : setA)setB.add(var);followSet.put(tn, setB);/ 若不存在 followA 加入 f

17、ollowBelse / A和B相同不添加if (tn != c) HashSet<Character> setB = followSet.containsKey(tn) ? followSet.get(tn): new HashSet<Character>();for (Character var : setA)setB.add(var);followSet.put(tn, setB);i-;/ 如果是終結(jié)符往前看 如 A->aaaBCDaaaa 此時(shí)為 CDaaaaelsei-;public void createTable() Object VtArray

18、= VtSet.toArray();Object VnArray = VnSet.toArray();/ 預(yù)測(cè)分析表初始化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

19、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<String> l = experssionSet.get(A);for (String s : l) HashS

20、et<Character> set = firstSetX.get(s);for (char a : set)insert(A, a, s);if (set.contains('') HashSet<Character> setFollow = followSet.get(A);if (setFollow.contains('#')insert(A, '#', s);for (char b : setFollow)insert(A, b, s);public void analyzeLL() System.out.prin

21、tln(" 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 (VtSe

22、t.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();fo

23、r (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,為L(zhǎng)L(1)文法");public String find(char X, char a) for (in