原理
数据结构
// GO
private static Map<Map<Integer,String>,Integer> GO
= new HashMap<Map<Integer,String>,Integer>(); // 规范族集 C
private static Map<Integer,Map<String,List<String>>> C
= new HashMap<Integer, Map<String, List<String>>>(); // 文法 G
private static Map<String,List<String>> G = new HashMap<String, List<String>>(); // 文法 G’
private static List<String> Gc = new ArrayList<String>(); // 文法的项目
private static Map<String,List<String>> GItems = new HashMap<String, List<String>>(); // ACTION 表
private static Map<Map<Integer,String>,String> ACTION
= new HashMap<Map<Integer,String>,String>(); // GOTO 表
private static Map<Map<Integer,String>,Integer> GOTO
= new HashMap<Map<Integer,String>,Integer>();
这个结构很清晰，不解释
算法步骤
在每个文法适当位置插入特殊字符圈，构成新的文法的项目GItems,这一步可以在输入的时候完成
例如有文法产生式为
E=[aA, bB]
则得到的文法的项目应该是，这里用*号代表圈
E=[*aA, a*A, aA*, *bB, b*B, bB*]
根据文法的项目构造识别活前缀的有限自动机DFA，如图
构造文法的规范族集
按图以对其中的每一项编号即可得到规范族集C={I0,I1,I2,....,In}
输入
S'->E
E->aA|bB
A->cA|d
B->cB|d
完整算法
package org.lyh.app; import java.io.*;
import java.util.*; public class Main { private static Integer I = 0;
// GO
private static Map<Map<Integer,String>,Integer> GO
= new HashMap<Map<Integer,String>,Integer>(); // 规范族集 C
private static Map<Integer,Map<String,List<String>>> C
= new HashMap<Integer, Map<String, List<String>>>(); // 文法 G
private static Map<String,List<String>> G = new HashMap<String, List<String>>(); // 文法 G’
private static List<String> Gc = new ArrayList<String>(); // 文法的项目
private static Map<String,List<String>> GItems = new HashMap<String, List<String>>(); // ACTION 表
private static Map<Map<Integer,String>,String> ACTION
= new HashMap<Map<Integer,String>,String>(); // GOTO 表
private static Map<Map<Integer,String>,Integer> GOTO
= new HashMap<Map<Integer,String>,Integer>(); public static void main(String[] args) throws Exception { FileReader fr = new FileReader("main.in");
BufferedReader br = new BufferedReader(fr); String line = null;
while((line = br.readLine()) != null){ // 构造文法 String [] pLine = line.split("->");
List<String> pLineValues = G.get(pLine[0]);
if(null == pLineValues) pLineValues = new ArrayList<String>();
pLineValues.addAll(Arrays.asList(pLine[1].split("\\|")));
G.put(pLine[0], pLineValues); for (String val : pLineValues){
String pStr = pLine[0]+"->"+val;
if(!Gc.contains(pStr)) Gc.add(pStr);
}
// 构造文法的项目，这里以*代替书上的圆点 List<String> pItemValues = GItems.get(pLine[0]);
if(null == pItemValues) pItemValues = new ArrayList<String>();
for(Iterator<String> iterator = pLineValues.iterator();iterator.hasNext();){
String pValueItem = iterator.next();
for (int i=0;i<pValueItem.length();i++){
String newItem = new StringBuilder(pValueItem).insert(i, "*").toString();
pItemValues.add(newItem);
}
pItemValues.add(pValueItem+"*");
}
GItems.put(pLine[0], pItemValues);
}
fr.close();
br.close(); System.out.println("文法G：" + G);
System.out.println("文法G'："+Gc);
System.out.println("文法G的项目："+GItems); // 构造项目集规范族
// 这里将问题稍稍简化，假设S'对应的第一个项目为初态
initC("S'", "*E");
System.out.println("C："+C);
System.out.println("GO："+GO); // 构造ACTION表和GOTO表
// 首先考虑最开始的情况
Map<Integer,String> acKey = new HashMap<Integer,String>();
acKey.put(0,"#");
ACTION.put(acKey,"acc");
// 遍历 项目集规范族 C
for(Iterator<Map.Entry<Integer,Map<String,List<String>>>> iterator
= C.entrySet().iterator();
iterator.hasNext();){
Map.Entry<Integer,Map<String,List<String>>> CI
= iterator.next();
//System.out.println(iterator.next());
// 扫描 CI ,switch判断每条文法
int k = CI.getKey();
Map<String,List<String>> values = CI.getValue();
for (Iterator<Map.Entry<String,List<String>>> mapIterator
= values.entrySet().iterator();mapIterator.hasNext();){
Map.Entry<String,List<String>> value = mapIterator.next();
String pLeft = value.getKey();
List<String> pRightValues = value.getValue();
for(int x = 0;x<pRightValues.size();x++){
String pRightVal = pRightValues.get(x);
System.out.println("K:"+k+" "+pLeft+"->"+pRightVal);
String a = null;
Integer GOka = 0;
Map<Integer,String> ka = new HashMap<Integer,String>(); if(pRightVal.matches("\\w*\\*[a-z]{1}\\w*")){
// 形如 A-> 。。。。 书上第一种情况
a = pRightVal.charAt(pRightVal.indexOf("*")+1)+"";
// System.out.println(a);
ka.put(k, a);
int j = GO.get(ka);
// System.out.println(j);
Map<Integer,String> key = new HashMap<Integer,String>();
key.put(k,a);
ACTION.put(key,"S"+j);
}
else if(pRightVal.matches("\\w*\\*$")){
// 形如书上第二种情况
// 扫描这个文法串
int j = 0;
j = Gc.indexOf(pLeft+"->"
+pRightVal.substring(0,pRightVal.length()-1));
for(int r = 0;r<pRightVal.length();r++){
char vti = pRightVal.charAt(r);
if(vti >= 'a' && vti <= 'z'){
// 是非终结符
// 置ACTION[k,a] 为 rj
Map<Integer,String> key = new HashMap<Integer,String>();
key.put(k,vti+"");
// 在G‘中查找A->r 得到j if(j>=0) ACTION.put(key,"r"+j);
}
}
Map<Integer,String> key = new HashMap<Integer,String>();
key.put(k,"#");
ACTION.put(key,"r"+j);
}
}
} } // GOTO表
// 判断 GO（Ik,A） == Ij
// 扫描 GO 表
for (Iterator<Map.Entry<Map<Integer,String>,Integer>> goit = GO.entrySet().iterator();
goit.hasNext();){
Map.Entry<Map<Integer,String>,Integer> goi = goit.next();
Map<Integer,String> gKey = goi.getKey();
//System.out.println("gKey:"+gKey);
int k =((Integer) gKey.keySet().toArray()[0]);
char A = ((String)gKey.values().toArray()[0]).charAt(0);
// System.out.println(A);
if(A >= 'A' && A <= 'Z'){
Map<Integer,String> gotoKey = new HashMap<Integer,String>();
gotoKey.put(k,A+"");
GOTO.put(gotoKey,goi.getValue());
}
} System.out.println("ACTION 表："+ACTION);
System.out.println("GOTO 表："+GOTO);
} private static void initC(String start, String pValue) { Map<String,List<String>> CI = new HashMap<String,List<String>>();
//List<String> pValues = GItems.get(start);
List<String> startCIValues = new ArrayList<String>();
startCIValues.add(pValue);
CI.put(start, startCIValues); System.out.println(start + "->" + pValue); int new_index = pValue.indexOf("*") + 1;
if(new_index != pValue.length()){
// 找到key为E（newStart）的右部以*a(这里a是终结符)的产生式，一并加到CI中
String newStart = pValue.substring(new_index,new_index+1);
List<String> seValues = GItems.get(newStart); List<String> newStartCIValues = newStart.equals(start)
? startCIValues : new ArrayList<String>(); //System.out.println(seValues);
for (String value : seValues){
if(value.matches("^\\*[a-z]{1}\\w*")){
newStartCIValues.add(value);
System.out.println(newStart+"->"+value);
}
} CI.put(newStart, newStartCIValues); C.put(I,CI);
int curI = I;
I++; String VC = ""+pValue.charAt(new_index);
Map<Integer,String> GOI = new HashMap<Integer,String>();
GOI.put(curI,VC);
GO.put(GOI,I); System.out.println("------------");
// 将第一条程式的圆点移动到下一位
StringBuilder sb = new StringBuilder(pValue);
sb.deleteCharAt(new_index-1).insert(new_index, "*");
String newPValue = sb.toString();
// 对第一条程式进行递归查找
initC(start, sb.toString()); // 将下面程式的原点移动到下一位
for(String value : newStartCIValues){ sb.delete(0, sb.length());
sb.append(value);
int x_index = sb.indexOf("*"); VC = ""+value.charAt(x_index+1);
GOI = new HashMap<Integer,String>();
GOI.put(curI,VC);
// 下移一位
sb.deleteCharAt(x_index).insert(x_index + 1, "*");
if(!pValue.equals(sb.toString())){
// 判断C当中是否已经存在这个程式
Map<String,List<String>> _this = new HashMap<String,List<String>>();
List<String> v = new ArrayList<String>();
v.add(sb.toString());
_this.put(newStart,v);
// 查找是否已经存在这个CI了
boolean has = false;
int exist_key = 0;
Set<Integer> keys = C.keySet();
for (Integer key : keys){
// 找到这个ID
if(C.get(key).equals(_this)){
//System.out.println("存在重复");
has = true;
exist_key = key;
break;
}
}
if(has){
//System.out.println("存在重复");
// 将 GO 的值 指向这个已经存在的
GO.put(GOI,exist_key);
}
else{
// 正常新建一个CI
GO.put(GOI,I);
initC(newStart, sb.toString());
}
}else{
// 指向自身
//System.out.println("指向自身");
GO.put(GOI,curI);
}
}
}
else{
System.out.println("------------");
C.put(I,CI);
I++;
} } }
运行结果
文法G：{E=[aA, bB], S'=[E], A=[cA, d], B=[cB, d]}
文法G'：[S'->E, E->aA, E->bB, A->cA, A->d, B->cB, B->d]
文法G的项目：{E=[*aA, a*A, aA*, *bB, b*B, bB*], S'=[*E, E*], A=[*cA, c*A, cA*, *d, d*], B=[*cB, c*B, cB*, *d, d*]}
S'->*E
E->*aA
E->*bB
------------
S'->E*
------------
E->a*A
A->*cA
A->*d
------------
E->aA*
------------
A->c*A
A->*cA
A->*d
------------
A->cA*
------------
A->d*
------------
E->b*B
B->*cB
B->*d
------------
E->bB*
------------
B->c*B
B->*cB
B->*d
------------
B->cB*
------------
B->d*
------------
C：{0={E=[*aA, *bB], S'=[*E]}, 1={S'=[E*]}, 2={E=[a*A], A=[*cA, *d]}, 3={E=[aA*]}, 4={A=[c*A, *cA, *d]}, 5={A=[cA*]}, 6={A=[d*]}, 7={E=[b*B], B=[*cB, *d]}, 8={E=[bB*]}, 9={B=[c*B, *cB, *d]}, 10={B=[cB*]}, 11={B=[d*]}}
GO：{{2=d}=6, {7=B}=8, {4=c}=4, {4=A}=5, {0=E}=1, {7=c}=9, {0=b}=7, {7=d}=11, {4=d}=6, {2=c}=4, {2=A}=3, {0=a}=2, {9=d}=11, {9=c}=9, {9=B}=10}
K:0 E->*aA
K:0 E->*bB
K:0 S'->*E
K:1 S'->E*
K:2 E->a*A
K:2 A->*cA
K:2 A->*d
K:3 E->aA*
K:4 A->c*A
K:4 A->*cA
K:4 A->*d
K:5 A->cA*
K:6 A->d*
K:7 E->b*B
K:7 B->*cB
K:7 B->*d
K:8 E->bB*
K:9 B->c*B
K:9 B->*cB
K:9 B->*d
K:10 B->cB*
K:11 B->d*
ACTION 表：{{1=#}=r0, {2=d}=S6, {5=c}=r3, {0=#}=acc, {4=c}=S4, {7=c}=S9, {3=#}=r1, {6=d}=r4, {0=b}=S7, {3=a}=r1, {5=#}=r3, {7=d}=S11, {4=d}=S6, {6=#}=r4, {0=a}=S2, {2=c}=S4, {11=d}=r6, {8=#}=r2, {11=#}=r6, {10=#}=r5, {9=d}=S11, {9=c}=S9, {8=b}=r2, {10=c}=r5}
GOTO 表：{{0=E}=1, {4=A}=5, {7=B}=8, {2=A}=3, {9=B}=10}
Process finished with exit code 0