从零写一个编译器（十）：编译前传之直接解释执行
- 2019 年 10 月 3 日
- 筆記
项目的完整代码在 C2j-Compiler
前言
这一篇不看也不会影响后面代码生成部分
现在经过词法分析语法分析语义分析，终于可以进入最核心的部分了。前面那部分可以称作编译器的前端，代码生成代码优化都是属于编译器后端，如今有关编译器的工作岗位主要都是对后端的研究。当然现在写的这个编译器因为水平有限，并没有优化部分。
在进行代码生成部分之前，我们先来根据AST来直接解释执行，其实就是对AST的遍历。现代解释器一般都是生成一个比较低级的指令然后跑在虚拟机上，但是简单起见我们就直接根据AST解释执行的解释器。（原本这部分是不想写的，是可以直接写代码生成的）
这次的文件在interpreter包里，这次涉及到的文件比较多，就不列举了
一个小问题
在开始说解释器的部分前我们看一下，认真观察之前在构造符号表对赋初值的推导式的处理是有问题的，但是问题不大，只要稍微改动一下
在github源代码的部分已经改了，改动如下：
case SyntaxProductionInit.VarDecl_Equal_Initializer_TO_Decl: attributeForParentNode = (Symbol) valueStack.get(valueStack.size() - 3); ((Symbol) attributeForParentNode).value = initialValue; break; case SyntaxProductionInit.Expr_TO_Initializer: initialValue = (Integer) valueStack.get(valueStack.size() - 1); System.out.println(initialValue); break;其实就是一个拿到赋的初值放到Symbol的value里
示例
先看一下这篇完成之后解释执行的效果
void swap(int arr[10], int i, int j) { int temp; temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } void quickSort(int a[10], int p, int r) { int x; int i; i = p - 1; int j; int t; int v; v = r - 1; if (p < r) { x = a[r]; for (j = p; j <= v; j++) { if (a[j] <= x) { i++; swap(a, i, j); } } v = i + 1; swap(a, v, r); t = v - 1; quickSort(a, p, t); t = v + 1; quickSort(a, t, r); } } void main () { int a[10]; int i; int t; printf("Array before quicksort:"); for(i = 0; i < 10; i++) { t = (10 - i); a[i] = t; printf("value of a[%d] is %d", i, a[i]); } quickSort(a, 0, 9); printf("Array after quicksort:"); for (i = 0; i < 10; i++) { printf("value of a[%d] is %d", i, a[i]); } }Executor接口
所有能够执行结点的类都要实现这个接口，所以以此来达到遍历AST来执行代码
解释器的启动在Interpreter类里，它也实现了Executor接口
Interpreter类的execute传入的参数就是整棵抽象语法树的头节点了，ExecutorFactory的getExecutor则是根据当前结点的TokenType返回一个可以解释当前节点的类，而其它执行节点的类都继承了BaseExecutor
@Override public Object execute(AstNode root) { if (root == null) { return null; } ExecutorFactory factory = ExecutorFactory.getInstance(); Executor executor = factory.getExecutor(root); executor.execute(root); return root; }BaseExecutor的两个主要方法就是执行它的子节点，并且可以指定执行哪个子节点。可以先忽略Brocaster，这些是用来实现执行节点类之前的通讯的，现在还没有用。reverseChildren是用来对节点的反转，因为在创建的AST的过程由于堆栈的原因，所以节点顺序的相反的。continueExecute是标志位，后面可能会执行到设置它的节点来结束运行
protected void executeChildren(AstNode root) { ExecutorFactory factory = ExecutorFactory.getInstance(); root.reverseChildren(); int i = 0; while (i < root.getChildren().size()) { if (!continueExecute) { break; } AstNode child = root.getChildren().get(i); executorBrocaster.brocastBeforeExecution(child); Executor executor = factory.getExecutor(child); if (executor != null) { executor.execute(child); } else { System.err.println("Not suitable Generate found, node is: " + child.toString()); } executorBrocaster.brocastAfterExecution(child); i++; } } protected AstNode executeChild(AstNode root, int childIdx) { root.reverseChildren(); AstNode child; ExecutorFactory factory = ExecutorFactory.getInstance(); child = (AstNode)root.getChildren().get(childIdx); Executor executor = factory.getExecutor(child); AstNode res = (AstNode)executor.execute(child); return res; }解释执行
我们可以知道一个C语言的源文件一般都是一些函数定义和一个main的函数来启动，所以在AstBuilder里返回给Interpreter的节点就是从main开始的
public AstNode getSyntaxTreeRoot() { AstNode mainNode = funcMap.get("main"); return mainNode; }执行函数ExtDefExecutor
用来执行函数的Executor是ExtDefExecutor
- 在进入execute会先执行FunctDecl节点，再执行CompoundStmt节点
- saveArgs和restoreArgs属于保护当前的环境，就是进入其它作用域的时候保证这个符号不变修改，不比如当作参数传递的时候
- returnVal也是属于由其它节点设置的属性
- root.setAttribute的作用就是对节点设置属性，把值往上传递
@Override public Object execute(AstNode root) { this.root = root; int production = (Integer) root.getAttribute(NodeKey.PRODUCTION); switch (production) { case SyntaxProductionInit.OptSpecifiers_FunctDecl_CompoundStmt_TO_ExtDef: AstNode child = root.getChildren().get(0); funcName = (String) child.getAttribute(NodeKey.TEXT); root.setAttribute(NodeKey.TEXT, funcName); saveArgs(); executeChild(root, 0); executeChild(root, 1); Object returnVal = getReturnObj(); clearReturnObj(); if (returnVal != null) { root.setAttribute(NodeKey.VALUE, returnVal); } isContinueExecution(true); restoreArgs(); break; default: break; } return root; }函数定义 FunctDeclExecutor
执行函数会先执行它的括号的前部分也就是标识符和参数那部分，对参数进行初始化，函数的传递的参数用单独一个类FunctionArgumentList来表示
@Override public Object execute(AstNode root) { int production = (Integer) root.getAttribute(NodeKey.PRODUCTION); Symbol symbol; currentNode = root; switch (production) { case SyntaxProductionInit.NewName_LP_RP_TO_FunctDecl: root.reverseChildren(); copyChild(root, root.getChildren().get(0)); break; case SyntaxProductionInit.NewName_LP_VarList_RP_TO_FunctDecl: symbol = (Symbol) root.getAttribute(NodeKey.SYMBOL); Symbol args = symbol.getArgList(); initArgumentList(args); if (args == null || argsList == null || argsList.isEmpty()) { System.err.println("generate function with arg list but arg list is null"); System.exit(1); } break; default: break; } return root; }执行语句部分 CompoundStmtExecutor
执行语句的部分就开始对树的遍历执行，但是我们来看一下这个节点的推导式
COMPOUND_STMT-> LC LOCAL_DEFS STMT_LIST RC在构建AST的时候我们并没有构建LOCAL_DEFS，并且在之前符号表也没有进行处理，所以我们直接执行第0个节点就可以了
@Override public Object execute(AstNode root) { return executeChild(root, 0); }一元操作
下面看UnaryNodeExecutor，UnaryNodeExecutor应该是所有Executor最复杂的之一了，其实对于节点执行，先执行子节点，并且向上传递执行结果的值。
只说其中的几个
-
指针
这个就是对指针的操作了，本质是对内存分配的一个模拟，再设置实现ValueSetter的DirectMemValueSetter，让它的父节点可以通过这个节点的setter对指针指向进行赋值
ValueSetter是一个可以对变量进行赋值的接口，数组、指针、简单的变量都有各自的valueSetter
case SyntaxProductionInit.Start_Unary_TO_Unary: child = root.getChildren().get(0); int addr = (Integer) child.getAttribute(NodeKey.VALUE); symbol = (Symbol) child.getAttribute(NodeKey.SYMBOL); MemoryHeap memHeap = MemoryHeap.getInstance(); Map.Entry<Integer, byte[]> entry = memHeap.getMem(addr); int offset = addr - entry.getKey(); if (entry != null) { byte[] memByte = entry.getValue(); root.setAttribute(NodeKey.VALUE, memByte[offset]); } DirectMemValueSetter directMemSetter = new DirectMemValueSetter(addr); root.setAttribute(NodeKey.SYMBOL, directMemSetter); break;-
指针和数组操作：
这是执行数组或者是指针的操作，对于数组和指针的操作会在节点中的Symbol里设置一个可以进行赋值的接口：ArrayValueSetter、PointerValueSetter，逻辑都不是很复杂。对于指针的操作其实是对于内存地址分配的一个模拟。
case SyntaxProductionInit.Unary_LB_Expr_RB_TO_Unary: child = root.getChildren().get(0); symbol = (Symbol) child.getAttribute(NodeKey.SYMBOL); child = root.getChildren().get(1); int index = (Integer) child.getAttribute(NodeKey.VALUE); try { Declarator declarator = symbol.getDeclarator(Declarator.ARRAY); if (declarator != null) { Object val = declarator.getElement(index); root.setAttribute(NodeKey.VALUE, val); ArrayValueSetter setter = new ArrayValueSetter(symbol, index); root.setAttribute(NodeKey.SYMBOL, setter); root.setAttribute(NodeKey.TEXT, symbol.getName()); } Declarator pointer = symbol.getDeclarator(Declarator.POINTER); if (pointer != null) { setPointerValue(root, symbol, index); PointerValueSetter pv = new PointerValueSetter(symbol, index); root.setAttribute(NodeKey.SYMBOL, pv); root.setAttribute(NodeKey.TEXT, symbol.getName()); } } catch (Exception e) { System.err.println(e.getMessage()); e.printStackTrace(); System.exit(1); } break;-
函数调用
函数调用也是属于一元操作，对于函数调用有两种情况：一种是自定义的函数，还有一种是解释器提供的函数
- 如果是自定义函数，就找到这个函数的头节点，从这个头节点开始执行
- 如果是解释器提供的函数，就交由ClibCall处理，比如printf就是属于库函数
case SyntaxProductionInit.Unary_LP_RP_TO_Unary: case SyntaxProductionInit.Unary_LP_ARGS_RP_TO_Unary: String funcName = (String) root.getChildren().get(0).getAttribute(NodeKey.TEXT); if (production == SyntaxProductionInit.Unary_LP_ARGS_RP_TO_Unary) { AstNode argsNode = root.getChildren().get(1); ArrayList<Object> argList = (ArrayList<Object>) argsNode.getAttribute(NodeKey.VALUE); ArrayList<Object> symList = (ArrayList<Object>) argsNode.getAttribute(NodeKey.SYMBOL); FunctionArgumentList.getInstance().setFuncArgList(argList); FunctionArgumentList.getInstance().setFuncArgSymbolList(symList); } AstNode func = AstBuilder.getInstance().getFunctionNodeByName(funcName); if (func != null) { Executor executor = ExecutorFactory.getInstance().getExecutor(func); executor.execute(func); Object returnVal = func.getAttribute(NodeKey.VALUE); if (returnVal != null) { ConsoleDebugColor.outlnPurple("function call with name " + funcName + " has return value that is " + returnVal.toString()); root.setAttribute(NodeKey.VALUE, returnVal); } } else { ClibCall libCall = ClibCall.getInstance(); if (libCall.isApiCall(funcName)) { Object obj = libCall.invokeApi(funcName); root.setAttribute(NodeKey.VALUE, obj); } } break;逻辑语句处理
逻辑语句处理无非就是根据节点值判断该执行哪些节点
-
FOR、WHILE语句
代码逻辑和语句的逻辑是一样，比如对于
for(i = 0; i < 5; i++){}就会先执行i = 0部分，在执行{}和i++部分，然后再判断条件是否符合
case SyntaxProductionInit.FOR_OptExpr_Test_EndOptExpr_Statement_TO_Statement: executeChild(root, 0); while (isLoopContinute(root, LoopType.FOR)) { //execute statement in for body executeChild(root, 3); //execute EndOptExpr executeChild(root, 2); } break; case SyntaxProductionInit.While_LP_Test_Rp_TO_Statement: while (isLoopContinute(root, LoopType.WHILE)) { executeChild(root, 1); } break;-
IF语句
if语句就是先执行判断部分，再根据判断的结果来决定是否执行{}块
@Override public Object execute(AstNode root) { AstNode res = executeChild(root, 0); Integer val = (Integer)res.getAttribute(NodeKey.VALUE); copyChild(root, res); if (val != null && val != 0) { executeChild(root, 1); } return root; }小结
这一篇写的很乱，一是解释器部分还是蛮大的，想在一篇之内写完比较难。所以省略了很多东西。但其实对于解释器实现部分对于AST的遍历才比较涉及编译原理部分，其它的主要是逻辑实现
对于解释器部分，因为没有采用虚拟机那样的实现，而是直接对AST的遍历。所以对AST的遍历是关键，主要在于遍历到该执行的子节点部分，然后处理逻辑，再把信息通过子节点传递到父节点部分。
