# 从零写一个编译器（六）：语法分析之表驱动语法分析

## reduce信息

reduce信息在ProductionsStateNode各自的节点里完成，只要遍历节点里的产生式，如果符号“.”位于表达式的末尾，那么该节点即可根据该表达式以及表达式对应的lookAhead set得到reduce信息

reduce信息用一个map来表示，key是可以进行reduce的符号，也就是lookahead sets中的符合，value则是进行reduce操作的产生式

public HashMap<Integer, Integer> makeReduce() {
HashMap<Integer, Integer> map = new HashMap<>();
reduce(map, this.productions);
reduce(map, this.mergedProduction);

return map;
}

private void reduce(HashMap<Integer, Integer> map, ArrayList<Production> productions) {
for (int i = 0; i < productions.size(); i++) {
if (productions.get(i).canBeReduce()) {
ArrayList<Integer> lookAhead = productions.get(i).getLookAheadSet();
for (int j = 0; j < lookAhead.size(); j++) {
map.put(lookAhead.get(j), (productions.get(i).getProductionNum()));
}
}
}
}

## 语法分析表的构建

1. 第一个Integer表示当前节点的编号
2. 第二个Integer表示输入字符
3. 第三个Integer表示，如果大于0则是做shift操作，小于0则根据推导式做reduce操作
public HashMap<Integer, HashMap<Integer, Integer>> getLrStateTable() {
File table = new File("lrStateTable.sb");
if (table.exists()) {
return loadTable();
}

Iterator it;
if (isTransitionTableCompressed) {
it = compressedStateList.iterator();
} else {
it = stateList.iterator();
}

while (it.hasNext()) {
ProductionsStateNode state = (ProductionsStateNode) it.next();
HashMap<Integer, ProductionsStateNode> map = transitionMap.get(state);
HashMap<Integer, Integer> jump = new HashMap<>();

if (map != null) {
for (Map.Entry<Integer, ProductionsStateNode> item : map.entrySet()) {
jump.put(item.getKey(), item.getValue().stateNum);
}
}

HashMap<Integer, Integer> reduceMap = state.makeReduce();
if (reduceMap.size() > 0) {
for (Map.Entry<Integer, Integer> item : reduceMap.entrySet()) {

jump.put(item.getKey(), -(item.getValue()));
}
}

lrStateTable.put(state.stateNum, jump);
}

storageTableToFile(lrStateTable);

return lrStateTable;
}

## 表驱动的语法分析

public LRStateTableParser(Lexer lexer) {
this.lexer = lexer;
statusStack.push(0);
valueStack.push(null);
lexer.advance();
lexerInput = Token.EXT_DEF_LIST.ordinal();
lrStateTable = StateNodeManager.getInstance().getLrStateTable();
}

• 拿到当前节点和当前字符所对应的下一个操作，也就是action > 0是shift操作，action < 0是reduce操作
• 如果进入action > 0，也就是shift操作
1. 把当前状态节点和输入字符分别压入堆栈
2. 这里要区分如果当前的字符是终结符，这时候就可以直接读入下一个字符
3. 但是这里如果是非终结符，就应该直接用当前字符跳转到下一个状态。这里是一个需要注意的一个点，这里需要把当前的这个非终结符，放入到下一个节点的对应输入堆栈中，这样它进行reduce操作时弹出退栈的符号才是正确的
• 如果action > 0，也就是reduce操作
1. 拿到对应的产生式
2. 把产生式右边对应的状态节点弹出堆栈
3. 把完成reduce的这个符号放入输入堆栈
public void parse() {
while (true) {
Integer action = getAction(statusStack.peek(), lexerInput);

if (action == null) {
ConsoleDebugColor.outlnPurple("Shift for input: " + Token.values()[lexerInput].toString());
System.err.println("The input is denied");
return;
}

if (action > 0) {
statusStack.push(action);
text = lexer.text;

// if (lexerInput == Token.RELOP.ordinal()) {
//     relOperatorText = text;
// }

parseStack.push(lexerInput);

if (Token.isTerminal(lexerInput)) {
ConsoleDebugColor.outlnPurple("Shift for input: " + Token.values()[lexerInput].toString() + "   text: " + text);

// Object obj = takeActionForShift(lexerInput);

lexer.advance();
lexerInput = lexer.lookAhead;
// valueStack.push(obj);
} else {
lexerInput = lexer.lookAhead;
}
} else {
if (action == 0) {
ConsoleDebugColor.outlnPurple("The input can be accepted");
return;
}

int reduceProduction = -action;
Production product = ProductionManager.getInstance().getProductionByIndex(reduceProduction);
ConsoleDebugColor.outlnPurple("reduce by product: ");
product.debugPrint();

// takeActionForReduce(reduceProduction);

int rightSize = product.getRight().size();
while (rightSize > 0) {
parseStack.pop();
// valueStack.pop();
statusStack.pop();
rightSize--;
}

lexerInput = product.getLeft();
parseStack.push(lexerInput);
// valueStack.push(attributeForParentNode);
}
}
}

private Integer getAction(Integer currentState, Integer currentInput) {
HashMap<Integer, Integer> jump = lrStateTable.get(currentState);
return jump.get(currentInput);
}

## 小结

• 利用有限状态自动机和reduce信息完成语法解析表
• 利用语法解析表实现表驱动的语法解析