前言
在上一篇，已经成功的构建了有限状态自动机，但是这个自动机还存在两个问题：
- 无法处理shift/reduce矛盾
- 状态节点太多，导致自动机过大，效率较低
这一节就要解决这两个问题
shift/reduce矛盾
看上一节那个例子的一个节点
e -> t .
t -> t . * f这时候通过状态节点0输入t跳转到这个节点，但是这时候状态机无法分清是根据推导式1做reduce还是根据推导式2做shift操作，这种情况就称之为shift / reduce矛盾。
SLR(1)语法
FOLLOW(s) = {EOI}
FOLLOW(e) = {EOI, },+}
FOLLOW(t) = {EOI, }, + , * }
FOLLOW(f) = {EOI, }, +, * }也就是说如果当前的输入字符属于e的FOLLOW SET，那么就可以根据第一个推导式做reduce操作
如果构建的状态机，出现reduce / shift矛盾的节点都可以根据上面的原则处理的话，那么这种语法，我们称之为SLR(1)语法。
LR(1)语法
当我们根据一个输入符号来判断是否可以进行reduce操作时，只需要判断在我们做完了reduce操作后，当前的输入符号是否能够合法的跟在reduce后的非终结符的后面，也就是只要收集只要该符号能够被reduce到退回它的节点的所有路径的能跟在后面的终结符
这种能合法的跟在某个非终结符后面的符号集合，我们称之为look ahead set, 它是FOLLOW set的子集。
在给出LookAhead Set的算法前要先明确两个个概念：
First Set
nullable
nullable在之前SyntaxProductionInit里的初始化时已经赋值了
First Set的构建
First Set构建算法
- 如果A是一个终结符，那么FIRST(A)={A}
- 对于以下形式的语法推导:
s -> A a
s是非终结符，A是终结符，a 是零个或多个终结符或非终结符的组合，那么A属于FIRST(s). - 对于推导表达式：
s -> b a
s和b是非终结符，而且b不是nullable的，那么first(s) = first(b) - 对于推导表达式:
s -> a1 a2 … an b
如果a1, a2 … an 是nullable 的非终结符，b是非终结符但不是nullable的，或者b是终结符，那么
first(s) 是 first(a1)… first(an) 以及first(b)的集合。
FirstSetBuilder类
这些就是用代码将上面的逻辑实现而已
这时候之前在SyntaxProductionInit初始化用到的symbolMap、symbolArray两个数据结构终于派上用场了
public void buildFirstSets() {
while (runFirstSetPass) {
runFirstSetPass = false;
Iterator<Symbols> it = symbolArray.iterator();
while (it.hasNext()) {
Symbols symbol = it.next();
addSymbolFirstSet(symbol);
}
}
ConsoleDebugColor.outlnPurple("First sets :");
debugPrintAllFirstSet();
ConsoleDebugColor.outlnPurple("First sets end");
}
private void addSymbolFirstSet(Symbols symbol) {
if (Token.isTerminal(symbol.value)) {
if (!symbol.firstSet.contains(symbol.value)) {
symbol.firstSet.add(symbol.value);
}
return ;
}
ArrayList<int[]> productions = symbol.productions;
for (int[] rightSize : productions) {
if (rightSize.length == 0) {
continue;
}
if (Token.isTerminal(rightSize[0]) && !symbol.firstSet.contains(rightSize[0])) {
runFirstSetPass = true;
symbol.firstSet.add(rightSize[0]);
} else if (!Token.isTerminal(rightSize[0])) {
int pos = 0;
Symbols curSymbol;
do {
curSymbol = symbolMap.get(rightSize[pos]);
if (!symbol.firstSet.containsAll(curSymbol.firstSet)) {
runFirstSetPass = true;
for (int j = 0; j < curSymbol.firstSet.size(); j++) {
if (!symbol.firstSet.contains(curSymbol.firstSet.get(j))) {
symbol.firstSet.add(curSymbol.firstSet.get(j));
}
}
}
pos++;
} while (pos < rightSize.length && curSymbol.isNullable);
}
}
}LookAhead Set的算法
[S -> a .r B, C]
r -> r1 r是一个非终结符，a, B是0个或多个终结符或非终结符的集合。
在自动机进入r -> r1所在的节点时，如果采取的是reduce操作，那么自动机的节点将会退回[S -> a .r B, C]这个推导式所在的节点，所以要正确的进行reduce操作就要保证当前的输入字符，必须属于FIRST(B)
所以推导式2的look ahead集合就是FIRST(B),如果B是空，那么2的look ahead集合就等于C, 如果B是nullable的，那么推导式2的look ahead集合就是FIRST(B) ∪ C
computeFirstSetOfBetaAndc
public ArrayList<Integer> computeFirstSetOfBetaAndc() {
ArrayList<Integer> set = new ArrayList<>();
for (int i = dotPos + 1; i < right.size(); i++) {
set.add(right.get(i));
}
ProductionManager manager = ProductionManager.getInstance();
ArrayList<Integer> firstSet = new ArrayList<>();
if (set.size() > 0) {
for (int i = 0; i < set.size(); i++) {
ArrayList<Integer> lookAhead = manager.getFirstSetBuilder().getFirstSet(set.get(i));
for (int s : lookAhead) {
if (!firstSet.contains(s)) {
firstSet.add(s);
}
}
if (!manager.getFirstSetBuilder().isSymbolNullable(set.get(i))) {
break;
}
if (i == lookAhead.size() - 1) {
//beta is composed by nulleable terms
firstSet.addAll(this.lookAhead);
}
}
} else {
firstSet.addAll(lookAhead);
}
return firstSet;
}竟然计算了Lookahead Set，那么在计算闭包时，每个节点里的推导式都要加上LookAhead Set以便之后求语法分析表
private void makeClosure() {
ConsoleDebugColor.outlnPurple("==== state begin make closure sets ====");
Stack<Production> productionStack = new Stack<>();
for (Production production : productions) {
productionStack.push(production);
}
while (!productionStack.isEmpty()) {
Production production = productionStack.pop();
ConsoleDebugColor.outlnPurple("production on top of stack is : ");
production.debugPrint();
production.debugPrintBeta();
if (Token.isTerminal(production.getDotSymbol())) {
ConsoleDebugColor.outlnPurple("Symbol after dot is not non-terminal, ignore and process next item");
continue;
}
int symbol = production.getDotSymbol();
ArrayList<Production> closures = productionManager.getProduction(symbol);
ArrayList<Integer> lookAhead = production.computeFirstSetOfBetaAndc();
Iterator<Production> it = closures.iterator();
while (it.hasNext()) {
Production oldProduct = it.next();
Production newProduct = oldProduct.cloneSelf();
newProduct.addLookAheadSet(lookAhead);
if (!closureSet.contains(newProduct)) {
closureSet.add(newProduct);
productionStack.push(newProduct);
removeRedundantProduction(newProduct);
} else {
ConsoleDebugColor.outlnPurple("the production is already exist!");
}
}
}
debugPrintClosure();
ConsoleDebugColor.outlnPurple("==== make closure sets end ====");
}removeRedundantProduction是处理冗余的产生式，比如
1. [t -> . t * f, {* EOI}]
2. [t -> .t * f {EOI}]这样就可以认为产生式1可以覆盖产生式2
private void removeRedundantProduction(Production product) {
boolean removeHappended = true;
while (removeHappended) {
removeHappended = false;
Iterator it = closureSet.iterator();
while (it.hasNext()) {
Production item = (Production) it.next();
if (product.isCover(item)) {
removeHappended = true;
closureSet.remove(item);
break;
}
}
}
}有限状态自动机的压缩
在我们之前构造的LR(1)有限自动机里，如果根据C语言的推导式，应该会产生600多个状态节点，但是是因为之前在构造状态节点时，如果相同的推导式但是它的lookAhead Sets不一样，就认为这是两个不一样的产生式。
下面是对状态节点的equals的重写
@Override
public boolean equals(Object obj) {
return checkProductionEqual(obj, false);
}
public boolean checkProductionEqual(Object obj, boolean isPartial) {
ProductionsStateNode node = (ProductionsStateNode) obj;
if (node.productions.size() != this.productions.size()) {
return false;
}
int equalCount = 0;
for (int i = 0; i < node.productions.size(); i++) {
for (int j = 0; j < this.productions.size(); j++) {
if (!isPartial) {
if (node.productions.get(i).equals(this.productions.get(j))) {
equalCount++;
break;
}
} else {
if (node.productions.get(i).productionEquals(this.productions.get(j))) {
equalCount++;
break;
}
}
}
}
return equalCount == node.productions.size();
}所以对这些推导式相同但是LookAhead Sets不同的节点，就可以进行合并，以达到压缩节点数量的目的
合并相似的节点最好的地方，自然就是在添加节点和节点之间的跳转关系的时候了
public void addTransition(ProductionsStateNode from, ProductionsStateNode to, int on) {
/* Compress the finite state machine nodes */
if (isTransitionTableCompressed) {
from = getAndMergeSimilarStates(from);
to = getAndMergeSimilarStates(to);
}
HashMap<Integer, ProductionsStateNode> map = transitionMap.get(from);
if (map == null) {
map = new HashMap<>();
}
map.put(on, to);
transitionMap.put(from, map);
}getAndMergeSimilarStates的逻辑也很简单，遍历当前的所有节点，找出相似，把编号大的合并到小的节点上
private ProductionsStateNode getAndMergeSimilarStates(ProductionsStateNode node) {
Iterator<ProductionsStateNode> it = stateList.iterator();
ProductionsStateNode currentNode = null, returnNode = node;
while (it.hasNext()) {
currentNode = it.next();
if (!currentNode.equals(node) && currentNode.checkProductionEqual(node, true)) {
if (currentNode.stateNum < node.stateNum) {
currentNode.stateMerge(node);
returnNode = currentNode;
} else {
node.stateMerge(currentNode);
returnNode = node;
}
break;
}
}
if (!compressedStateList.contains(returnNode)) {
compressedStateList.add(returnNode);
}
return returnNode;
}public void stateMerge(ProductionsStateNode node) {
if (!this.productions.contains(node.productions)) {
for (int i = 0; i < node.productions.size(); i++) {
if (!this.productions.contains(node.productions.get(i)) && !mergedProduction.contains(node.productions.get(i))
) {
mergedProduction.add(node.productions.get(i));
}
}
}
}小结
这一节的贴的代码应该是到现在五篇里最多，但是主要的就是
解决shift/reduce矛盾
主要在于构造一个lookahead sets，也就是当前的输入符号是否能够合法的跟在reduce后的非终结符的后面压缩有限状态自动机节点
压缩节点在于合并推导式一样但是lookahead sets不一样的节点
下一篇的内容比较少，也就是可以正式构造出语法分析表和根据表驱动的语法分析，也就代表语法分析阶段的结束
另外的github博客：https://dejavudwh.cn/