上一篇中实现的First函数没有考虑左递归，在这对此说明和实现
1.立即左递归
A -> Ab|a
1.两步或两步以上产生的左递归
A -> Bc|a
B -> Ab|d
前面的实现中，递归用first函数
public Set<Terminal> first(List<Symbol> tokens) {
first(token)
}
public Set<Terminal> first(Symbol token) {
first(tokens)
}
如果产生式存在左递归就会出现循环调用，得不到结果
那么需要做下面处理
1. 需要记录当前外层有没有处理这个符号，如果有则跳过
2. A -> Bc|a B->Ad | ε
1)first(A)
2)first(Bc) 并 first(a)
3)first(B) frist(c) 并 first(a)
4)first(Ad) frist(ε) first(c) 并 first(a)
5)first(A) first(d) frist(ε) first(c) 并 first(a)
可以看第5步又需要first(A)，因为外层正在处理，所以直接返回，但是返回前需要判断A是否为空，
如果不为空，则直接返回，如果为空，则继续first(d)
看两组产生式的结果
A -> Bc|a B->Ad| d | ε A的first集合是 a, d, c, B的first集合 a d c
A -> Bc|a B->Ad | d A的first集合是 a, d, B的first集合 a d
可以看出 A -> Bc 对 frist(A)集合，如果A, B可以推出 ε 那么集合就多了c，否则 A->Bc 不影响 first(A)的结果
所以需要加过一个函数专门用来判断A是否可以推导出ε
/**
* tokens是否可以推导出ε
* @param tokens
* @param expands
* @return
*/
public boolean hasEpsilon(List<Symbol> tokens, Set<Symbol> expands) {
for (Symbol token : tokens) {
if (expands.contains(token)) {
return false;
}
if (Terminal.epsilon.equals(token)) {
return true;
}
if (token instanceof Terminal) {// 终结符直接返回
return false;
}
expands.add(token);
boolean hasEpsilon = false;
List<Production> productionList = getProduction((Nonterminal) token);
for (Production production : productionList) {
if (hasEpsilon(production.getBody(), expands)) {
hasEpsilon = true;
break;
}
}
if (!hasEpsilon) {
return false;
}
expands.remove(token);
}
return true;
}
最终First集合函数修改如下
/**
* P140 FIRST(X)集合
* @param tokens 正在计算的串
* @param expands 用于记录正在计算的串是由哪个非终结符展开得到的
* @return
*/
public Set<Terminal> first(List<Symbol> tokens, Set<Symbol> expands) {
// 是否全部包含ε
boolean allContainsEpsilon = true;
Set<Terminal> result = new HashSet<>();
for (Symbol token : tokens) {
Set<Symbol> epsilonExpands = new HashSet<>();
boolean hasEpsilon = hasEpsilon(Arrays.asList(token), epsilonExpands);
Set<Terminal> firstSet = first(token, expands);
if (firstSet == null) {
if (hasEpsilon) {
continue;
} else {
return result;
}
} else {
for (Terminal terminal : firstSet) {
if (terminal.equals(Terminal.of("ε"))) {
continue;
}
result.add(terminal);
}
if (!hasEpsilon) {
allContainsEpsilon = false;
break;
}
}
}
// 如果对于所有的j=1，2，...，k，ε在FIRST(Yj)中，那么将ε加入到FIRST(X)
if (allContainsEpsilon) {
result.add(Terminal.of("ε"));
}
return result;
}
