import hjzgg.first.First;
import hjzgg.follow.Follow;
import hjzgg.tablenode.TableNode;
import hjzgg.treenode.TreeNode; import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;
import java.util.Stack;
import java.util.TreeMap;
import java.util.TreeSet; public class AnalysisTable {
private final int noFinalCharacterCount = 100;
private Map<String, Integer>stringToInt = new TreeMap<String, Integer>();//分析表行 列 字母映射到数字
private Map<Integer, String>tableRow = new TreeMap<Integer, String>();//分析表 行列 数字 映射到字母
private Map<Integer, String>tableCol = new TreeMap<Integer, String>();
private String[][] table = new String[noFinalCharacterCount][];//分析表
private Set<Character>terminalCharacters = new TreeSet<Character>();//终结符集合
private Map<String, Set<Character>> first = null;
private Map<String, Set<Character>> follow = null;
private Map<String, String[]> mp = null;
private int nodeCntRow = 0, nodeCntCol=0; public static final int treeNodeCnt = 200;//树最多节点的个数
private int cntTreeNode = 0;
private ArrayList<String> usedProduction = new ArrayList<String>();//预测分析中所用到的产生式
private int fatherNode;//treeGraphic搜素是的开始节点
private TreeNode[] treeGraphic = new TreeNode[treeNodeCnt]; private String[] analysisStack = null;
public String[] getAnalysisStack(){
return analysisStack;
} public Map<String, Integer> getStringToInt(){
return stringToInt;
}
public Set<Character> getTerminalCharacters(){
return terminalCharacters;
} public int getFatherNode(){
return fatherNode;
} public TreeNode[] getTreeGraphic(){
return treeGraphic;
} public AnalysisTable(Map<String, Set<Character>> first,
Map<String, Set<Character>> follow, Map<String, String[]> mp) {
super();
this.first = first;
this.follow = follow;
this.mp = mp;
init();
} private void init(){
for(String leftNode : mp.keySet()){
stringToInt.put(leftNode, ++nodeCntRow);
tableRow.put(nodeCntRow, leftNode);
String[] rightNodes = mp.get(leftNode);
for(int i=0; i<rightNodes.length; ++i){//枚举每一个产生式
for(int j=0; j<rightNodes[i].length(); ++j)
if(!mp.containsKey(""+rightNodes[i].charAt(j)) && rightNodes[i].charAt(j)!='\'' && rightNodes[i].charAt(j)!='$'){//每一个终结符
if(!stringToInt.containsKey(""+rightNodes[i].charAt(j))){
stringToInt.put(""+rightNodes[i].charAt(j), ++nodeCntCol);
terminalCharacters.add(rightNodes[i].charAt(j));
tableCol.put(nodeCntCol, ""+rightNodes[i].charAt(j));
}
}
}
}
stringToInt.put("#", ++nodeCntCol);
tableCol.put(nodeCntCol, "#");
terminalCharacters.add('#');
} public ArrayList<TableNode> analysisTableKernealCode(){
for(String leftNode : mp.keySet()){
String[] rightNodes = mp.get(leftNode);
for(int i=0; i<rightNodes.length; ++i){//枚举每一个产生式
for(Character terminal : terminalCharacters){//每一个终结符
char finalCharacter = terminal;
Set<Character> productionFirstSet = new TreeSet<Character>();//产生式对应first集
for(int k=0; k<rightNodes[i].length(); ++k){
String node = ""+rightNodes[i].charAt(k);
if(k+1 < rightNodes[i].length() && rightNodes[i].charAt(k+1)=='\''){
node += '\'';
++k;
}
if(mp.containsKey(node)){//非终结符
productionFirstSet.addAll(first.get(node));
if(!first.get(node).contains('$')) break;
} else {//终结符
productionFirstSet.add(node.charAt(0));
break;
}
} if(productionFirstSet.contains(finalCharacter)){//A->@ 对于每一个终结符 a属于FIRST(@),加入M[A, a]
int col = stringToInt.get(""+finalCharacter);
int row = stringToInt.get(leftNode);
if(table[row]==null)
table[row] = new String[nodeCntCol+1];
table[row][col] = leftNode + "->" + rightNodes[i];
} /***********************************************************************/
else if(productionFirstSet.contains('$')){//A->@ 对于$属于First（@）,对任何b属于Follow(A)则把A->@加入
if(follow.get(leftNode).contains(finalCharacter)){
int col = stringToInt.get(""+finalCharacter);
int row = stringToInt.get(leftNode);
if(table[row]==null)
table[row] = new String[nodeCntCol+1];
table[row][col] = leftNode + "->" + rightNodes[i];
}
}
}
}
}
return printTalbe();
} public ArrayList<TableNode> printTalbe(){
ArrayList<TableNode> tableNodeAl = new ArrayList<TableNode>();
System.out.println("分析表如下:");
for(int i=1; i<=nodeCntRow; ++i){
for(int j=1; j<=nodeCntCol; ++j)
if(table[i]!=null && table[i][j]!=null){
tableNodeAl.add(new TableNode(i, j, table[i][j]));
System.out.println(tableRow.get(i) + ":" + tableCol.get(j) + " " + table[i][j]);
}
}
return tableNodeAl;
} public boolean predictiveAnalysis(String formula){
ArrayList<String>stringStack = new ArrayList<String>();
System.out.println("开始进行预测分析,分析栈如下:");
Stack<String> stack = new Stack<String>();
stack.push("#");
stack.push(tableRow.get(1));
int formulaIndex = 0;
char a = formula.charAt(formulaIndex++);
boolean flag = false;
while(true){
if(stack.size() == 0){
//error
break;
}
stringStack.add(stack.toString());
System.out.println(stack);
String x = stack.pop();
if(!mp.containsKey(x)){//终结符
if(x.charAt(0)==a){
if(a=='#'){
flag = true;
break;
}
a = formula.charAt(formulaIndex++);
} else {
//error
}
} else {//非终结符
if(table[stringToInt.get(x)] != null){
String production = table[stringToInt.get(x)][stringToInt.get(""+a)];
if(production != null){
usedProduction.add(production);
if(!production.contains("$")){//X->X1X2X3....Xk 中 Xk....X3X2X1压入栈中
for(int i=production.length()-1; i>=0; --i){
if(production.charAt(i)=='>') break;
if(production.charAt(i)=='\''){
stack.push(""+production.charAt(i-1)+production.charAt(i));
--i;
} else{
stack.push(""+production.charAt(i));
}
}
}
} else {
//error
}
} else {
//error
}
}
}
analysisStack = stringStack.toArray(new String[stringStack.size()]);
return flag;
} private int produceAnalysisTree(int curRow, String preNode){
String curProduction = usedProduction.get(curRow);
String splits[] = curProduction.split("->");
if(preNode != null && !preNode.equals(splits[0]))
return produceAnalysisTree(curRow+1, preNode);
TreeNode treeNode = new TreeNode();
treeNode.content = splits[0];
for(int i=0; i<splits[1].length(); ++i){//右部的产生式
String node = "" + splits[1].charAt(i);
if(i+1<splits[1].length() && splits[1].charAt(i+1)=='\''){
node += '\'';
++i;
}
if(!mp.containsKey(node)){//不是 非终结点
TreeNode tmpTreeNode = new TreeNode();
tmpTreeNode.content = node;
treeNode.child.add(cntTreeNode);//加入孩子节点
treeGraphic[cntTreeNode++] = tmpTreeNode;
} else {//非终结点
int childNodeCnt = produceAnalysisTree(curRow+1, node);//得到这个孩子的节点
treeNode.child.add(childNodeCnt);
}
}
treeGraphic[cntTreeNode] = treeNode;
return cntTreeNode++;
} private void printAnalysisTree(int curNode){
System.out.print(" " + treeGraphic[curNode].content);
for(int i=0; i<treeGraphic[curNode].child.size(); ++i)
printAnalysisTree(treeGraphic[curNode].child.get(i));
} public void AnalysisTree(){
fatherNode = produceAnalysisTree(0, null);
System.out.println("分析树的先序遍历如下:");
printAnalysisTree(fatherNode);
} public static void main(String[] args) { // String[] rightLinearGrammar ={
// "S->iCtSA|a",
// "A->$|eS",
// "C->b"
// }; String[] rightLinearGrammar = {
"E->TE\'",
"E\'->+TE\'|$",
"T->FT\'",
"T\'->*FT\'|$",
"F->(E)|i"
}; // String[] rightLinearGrammar = {
// "S->ABc",
// "A->a|$",
// "B->b|$"
// }; Map<String, String[]> mp = new LinkedHashMap<String, String[]>();
try{
for(int i=0; i<rightLinearGrammar.length; ++i){
String split1[] = rightLinearGrammar[i].split("->");
String split2[] = split1[1].split("\\|");
mp.put(split1[0], split2);
} } catch(Exception e){
e.printStackTrace();
System.out.println("右线性文法错误!");
}
First first = new First(mp);
first.firstKernealCode();
Follow follow = new Follow(mp, first.getFirstSet());
follow.followKernealCode();
AnalysisTable analysisTable = new AnalysisTable(first.getFirstSet(), follow.getFollowSet(), mp);
analysisTable.analysisTableKernealCode(); analysisTable.predictiveAnalysis("i+i#");
analysisTable.AnalysisTree();
} }