package curriculumdesign;
import org.junit.Test;
import javax.swing.*;
import java.util.*;
/**
* @author 李天翔
* @date 2022/06/13
**/
@SuppressWarnings({"all"})
public class Priority {
static char[][] table;
// E->E+T|T#T->T*F|F#F->(E)|i i+i#
//E->E+T|T#T->F*F|F#F->(E)|i i+i*i#
//V->N#V->N[E]#E->V#E->V+E#N->i [i+i+i]#
static String[] grammar = {"V->N", "V->N[E]", "E->V", "E->V+E", "N->i"};
static HashSet<Character> vtSet = new HashSet<>();//终结符
static HashSet<Character> vnSet = new HashSet<>();//非终结符
static HashMap<Character, ArrayList<String>> productionMap = new HashMap<>();//产生式Map
static HashMap<Character, HashSet<Character>> firstVtMap = new HashMap<>();//任意非终结符的firstVt集
static HashMap<Character, HashSet<Character>> lastVtMap = new HashMap<>();//任意非终极符的lastVt集
static int row;
static int col;
static ArrayList<Step> steps = new ArrayList<>();
static String inString;
static Stack<Character> charStack = new Stack<>();
static boolean right = true;
static String errorMes="出错";
/**
* 用来得到终结符集和非终结符集
*/
@Test
public static void init() {
steps.clear();
vtSet.clear();
vnSet.clear();
firstVtMap.clear();
lastVtMap.clear();
productionMap.clear();
charStack.clear();
right=true;
//生成终结符和非终结符集
for (int i = 0; i < grammar.length; i++) {
char[] temp = grammar[i].replace("->", "").replace("|", "").toCharArray();//去除->
for (int j = 0; j < temp.length; j++) {
if (temp[j] >= 'A' && temp[j] <= 'Z') {
vnSet.add(temp[j]);//大写字母为非终结符
} else {
vtSet.add(temp[j]);
}
}
}
vtSet.add('#');
//生成每个非终结符对应的产生式
for (String str : grammar) {
String[] strings = str.split("->")[1].split("\\|");
char ch = str.charAt(0);
ArrayList<String> list = productionMap.containsKey(ch) ? productionMap.get(ch) : new ArrayList<String>();
for (String S : strings) {
list.add(S);
}
productionMap.put(str.charAt(0), list);
//System.out.println(str.charAt(0) + "\t" + list);
}
//System.out.println(vnSet + "***" + vnSet);
}
/**
* 该函数用于得到两个终结符之间的优先级关系
*
* @param x1
* @param x2
* @return 返回值为优先关系表中的优先关系
*/
public static char getPriority(char x1, char x2) {
for (int i = 0; i < row; i++) {
if (x1 == table[i][0]) {
for (int j = 0; j < col; j++) {
if (x2 == table[0][j]) {
return table[i][j];
}
}
}
}
return ' ';
}
/**
* 构建firstVt集
*/
public static void getFirstVt() {
HashSet<Character> hs = null;
//用两个栈同步完成非终结符对应一个终结符，即在栈中相同位置处的非终结符的firstVt包含该终结符
Stack<Character> stackVn = new Stack<>();
Stack<Character> stackVt = new Stack<>();
Set<Character> charVnSet = productionMap.keySet();
for (Character charVn : charVnSet) {//进行一个初始化操作，遍历所有产生式，把产生式中所有P->a....或P->Qa.... 把a添加到P的firstVt中
ArrayList<String> arrayList = productionMap.get(charVn);
hs = firstVtMap.containsKey(charVn) ? firstVtMap.get(charVn) : new HashSet<Character>();//如果不存在则创建，存在则取出
for (String s : arrayList) {
if (vtSet.contains(s.charAt(0))) {//P->a...
hs.add(s.charAt(0));
} else if (s.length() >= 2 && vtSet.contains(s.charAt(1))) {//P->Qa...
hs.add(s.charAt(1));
}
}
for (Character h : hs) {//把P和它的firstVt集添加到栈中
stackVn.push(charVn);
stackVt.push(h);
}
firstVtMap.put(charVn, hs);
}
while (!stackVn.isEmpty()) {//如果栈STACK不空，就将顶项逐出，记此项为(Q，a).对于每个形如P->Q...的产生式,若P的fistvt集不包含a,则fistVt添加a并将(P,a)推进stack栈
//取出栈顶
Character peekVn = stackVn.peek();
Character peekVt = stackVt.peek();
stackVn.pop();
stackVt.pop();
for (Character charVn : charVnSet) {//遍历产生式
ArrayList<String> arrayList = productionMap.get(charVn);
hs = firstVtMap.containsKey(charVn) ? firstVtMap.get(charVn) : new HashSet<Character>();
for (String s : arrayList) {
if (s.charAt(0) == peekVn) {//找到P->Q....
hs = firstVtMap.containsKey(charVn) ? firstVtMap.get(charVn) : new HashSet<Character>();
if (!hs.contains(peekVt)) {//如果不含a则入栈并添加
hs.add(peekVt);
stackVn.push(charVn);
stackVt.push(peekVt);
firstVtMap.put(charVn, hs);
}
break;
}
}
}
}
// Set<Character> characters = firstVtMap.keySet();
// for (Character character : characters) {
// System.out.println(firstVtMap.get(character));
// }
}
/**
* 构建lastVt集，算法和firstVt集类似，只不过是找P->.....a或P->.....aQ
*/
public static void getLastVt() {
//用两个栈同步完成非终结符对应一个终结符，即在栈中相同位置处的非终结符的lastVt包含该终结符
HashSet<Character> hs = null;
Set<Character> charVnSet = productionMap.keySet();
Stack<Character> stackVn = new Stack<>();
Stack<Character> stackVt = new Stack<>();
for (Character charVn : charVnSet) {//进行一个初始化操作，遍历所有产生式，把产生式中所有P->....a或P->....aQ 把a添加到P的lastVt中
ArrayList<String> arrayList = productionMap.get(charVn);
hs = lastVtMap.containsKey(charVn) ? lastVtMap.get(charVn) : new HashSet<Character>();
for (String s : arrayList) {
if (vtSet.contains(s.charAt(s.length() - 1))) {
hs.add(s.charAt(s.length() - 1));
} else if (s.length() >= 2 && vtSet.contains(s.charAt(s.length() - 2))) {
hs.add(s.charAt(s.length() - 2));
}
}
for (Character h : hs) {//把P和它的lastVt集添加到栈中
stackVn.push(charVn);
stackVt.push(h);
}
lastVtMap.put(charVn, hs);
}
while (!stackVn.isEmpty()) {//如果栈STACK不空，就将顶项逐出，记此项为(Q，a).对于每个形如P->Q...的产生式,若P的fistvt集不包含a,则fistVt添加a并将(P,a)推进stack栈
//取出栈顶
Character peekVn = stackVn.peek();
Character peekVt = stackVt.peek();
stackVn.pop();
stackVt.pop();
for (Character charVn : charVnSet) {//遍历产生式
ArrayList<String> arrayList = productionMap.get(charVn);
hs = lastVtMap.containsKey(charVn) ? lastVtMap.get(charVn) : new HashSet<Charact
评论0