有了前面一系列的铺垫和准备后，我们终于能走到至关重要的一刻。在本节，我们将用C语言开发快速排序算法，然后利用我们的编译器把它编译成java字节码，让C语言编写的快速排序算法能在java虚拟机上顺利执行，完成本节内容后，编译器可以正确的将下列代码编译成java字节码：
1void quicksort(int A[10], int p, int r) { 2 int x; 3 int i; 4 i = p - 1; 5 int j; 6 int t; 7 int v; 8 v = r - 1; 9 if (p < r) { 10 x = A[r]; 11 12 for (j = p; j <= v; j++) { 13 if (A[j] <= x) { 14 i++; 15 t = A[i]; 16 A[i] = A[j]; 17 A[j] = t; 18 } 19 } 20 21 v = i + 1; 22 t = A[v]; 23 A[v] = A[r]; 24 A[r] = t; 25 26 t = v - 1; 27 quicksort(A, p, t); 28 t = v + 1; 29 quicksort(A, t, r); 30 } 31 32} 33 34void main () { 35 int a[10]; 36 int i; 37 int t; 38 printf("before quick sort:"); 39 for(i = 0; i < 10; i++) { 40 t = (10 - i); 41 a[i] = t; 42 printf("value of a[%d] is %d", i, a[i]); 43 } 44 45 46 quicksort(a, 0, 9); 47 48 printf("after quick sort:"); 49 for (i = 0; i < 10; i++) { 50 printf("value of a[%d] is %d", i, a[i]); 51 } 52 53}
上面的C代码是根据《算法导论》所编写的实现快速排序的算法，主函数先初始化一个乱序的数组，然后通过调用quicksort函数实现排序。我一直把编译器能够解释编译C语言快速排序的代码作为章节的终点，一来快速排序算法的实现包含了循环，ifelse分支判断，递归等编程语言的关键要素，能正确解释和编译它意味着编译器达到了一定的成熟度。而本节完成后，我们的编译器能正确编译快速排序的C语言实现后，整个编译器实现课程经历两年时光，也该画上句号了。
我们看看代码的实现，这次代码与前面代码的一大不同之处就是函数的递归调用。quicksort函数中会调用它自己，因此编译器在实现时，需要注意这个特点。原来我们实现函数的编译时，编译器会解读代码，直到函数第一次被调用时，才会把被调函数编译成字节码，但这里，被调函数在执行时会调用它自己，如果对原来的逻辑不加处理，那么编译器会反复的为quicksort函数生成代码，陷入到一种死循环的状态。负责函数调用的代码处于UnaryNodeExecutor中，代码修改如下：
1case CGrammarInitializer.Unary_LP_RP_TO_Unary: 2 case CGrammarInitializer.Unary_LP_ARGS_RP_TO_Unary: 3 //先获得函数名 4 boolean reEntry = false; 5 String funcName = (String)root.getChildren().get(0).getAttribute(ICodeKey.TEXT); 6 //change here 7 /* 8 * 如果函数名被记录过，那表明现在的函数调用其实是递归调用 9 */ 10 if (funcName != "" && funcName.equals(BaseExecutor.funcName)) { 11 reEntry = true; 12 } 13 14 15 ArrayList<Object> argList = null; 16 ArrayList<Object> symList = null; 17 18 if (production == CGrammarInitializer.Unary_LP_ARGS_RP_TO_Unary) { 19 ICodeNode argsNode = root.getChildren().get(1); 20 argList = (ArrayList<Object>)argsNode.getAttribute(ICodeKey.VALUE); 21 symList = (ArrayList<Object>)argsNode.getAttribute(ICodeKey.SYMBOL); 22 FunctionArgumentList.getFunctionArgumentList().setFuncArgList(argList); 23 FunctionArgumentList.getFunctionArgumentList().setFuncArgSymbolList(symList); 24 } 25 26 //找到函数执行树头节点 27 ICodeNode func = CodeTreeBuilder.getCodeTreeBuilder().getFunctionNodeByName(funcName); 28 if (func != null) { 29 //change here push parameters before calling function 30 /* 31 * 函数调用时，把当前被调用的函数名记录下来，如果函数体内发送递归调用，那么编译器还会再次进入到 32 * 这里，如果进入时判断到函数名跟我们这里存储的函数名一致，那表明发生了递归调用。 33 */ 34 BaseExecutor.funcName = funcName; 35 int count = 0; 36 while (count < argList.size()) { 37 Object objVal = argList.get(count); 38 Object objSym = symList.get(count); 39 if (objSym != null) { 40 Symbol param = (Symbol)objSym; 41 int idx = generator.getLocalVariableIndex(param); 42 if (param.getDeclarator(Declarator.ARRAY) != null) { 43 generator.emit(Instruction.ALOAD, "" + idx); 44 } else { 45 generator.emit(Instruction.ILOAD, ""+idx); 46 } 47 } else { 48 int v = (int)objVal; 49 generator.emit(Instruction.SIPUSH, ""+v); 50 } 51 52 count++; 53 } 54 //problem here handle reentry 55 if (BaseExecutor.isCompileMode == true && reEntry == false) { 56 /* 57 * 在编译状态下，遇到函数自我递归调用则不需要再次为函数生成代码，只需要生成invoke指令即可 58 */ 59 Executor executor = ExecutorFactory.getExecutorFactory().getExecutor(func); 60 ProgramGenerator.getInstance().setInstructionBuffered(true); 61 executor.Execute(func); 62 symbol = (Symbol)root.getChildren().get(0).getAttribute(ICodeKey.SYMBOL); 63 emitReturnInstruction(symbol); 64 ProgramGenerator.getInstance().emitDirective(Directive.END_METHOD); 65 ProgramGenerator.getInstance().setInstructionBuffered(false); 66 ProgramGenerator.getInstance().popFuncName(); 67 } 68 compileFunctionCall(funcName); 69 70 71 Object returnVal = func.getAttribute(ICodeKey.VALUE); 72 if (returnVal != null) { 73 System.out.println("function call with name " + funcName + " has return value that is " + returnVal.toString()); 74 root.setAttribute(ICodeKey.VALUE, returnVal); 75 } 76 77 } else { 78 ClibCall libCall = ClibCall.getInstance(); 79 if (libCall.isAPICall(funcName)) { 80 Object obj = libCall.invokeAPI(funcName); 81 root.setAttribute(ICodeKey.VALUE, obj); 82 } 83 } 84 85 86 break;
当编译器解析到代码中发生函数调用时，它会把被调函数的名字记录下来，然后判断这个名字是否被记录过，如果前面有过记录，那么这次进入表明函数发生了递归调用，于是就不再执行函数对应的执行树，如果函数是第一次被调用，那么就执行函数对应的执行树，在执行过程中就可以把函数编译成字节码。
除了上面的改动之后，还有不少地方需要相应的修改，具体的调试演示过程请点击‘阅读额原文'查看视频。上面代码完成后，运行编译器，给定的C语言代码编译出的java汇编代码如下：
1.class public CSourceToJava 2.super java/lang/Object 3 4.method public static main([Ljava/lang/String;)V 5 sipush 10 6 newarray int 7 astore 1 8 sipush 0 9 istore 2 10 sipush 0 11 istore 0 12 getstatic java/lang/System/out Ljava/io/PrintStream; 13 ldc "before quick sort:" 14 invokevirtual java/io/PrintStream/print(Ljava/lang/String;)V 15 getstatic java/lang/System/out Ljava/io/PrintStream; 16 ldc " 17" 18 invokevirtual java/io/PrintStream/print(Ljava/lang/String;)V 19 sipush 0 20 istore 2 21 22loop0: 23 iload 2 24 sipush 10 25if_icmpge branch0 26 sipush 10 27 iload 2 28 isub 29 istore 0 30 aload 1 31 iload 2 32 iload 0 33 iastore 34 aload 1 35 iload 2 36 iaload 37 istore 3 38 iload 2 39 istore 4 40 getstatic java/lang/System/out Ljava/io/PrintStream; 41 ldc "value of a[" 42 invokevirtual java/io/PrintStream/print(Ljava/lang/String;)V 43 getstatic java/lang/System/out Ljava/io/PrintStream; 44 iload 4 45 invokevirtual java/io/PrintStream/print(I)V 46 getstatic java/lang/System/out Ljava/io/PrintStream; 47 ldc "] is " 48 invokevirtual java/io/PrintStream/print(Ljava/lang/String;)V 49 getstatic java/lang/System/out Ljava/io/PrintStream; 50 iload 3 51 invokevirtual java/io/PrintStream/print(I)V 52 getstatic java/lang/System/out Ljava/io/PrintStream; 53 ldc " 54" 55 invokevirtual java/io/PrintStream/print(Ljava/lang/String;)V 56 iload 2 57 sipush 1 58 iadd 59 istore 2 60goto loop0 61branch0: 62 aload 1 63 sipush 0 64 sipush 9 65 invokestatic CSourceToJava/quicksort([III)V 66 getstatic java/lang/System/out Ljava/io/PrintStream; 67 ldc "after quick sort:" 68 invokevirtual java/io/PrintStream/print(Ljava/lang/String;)V 69 getstatic java/lang/System/out Ljava/io/PrintStream; 70 ldc " 71" 72 invokevirtual java/io/PrintStream/print(Ljava/lang/String;)V 73 sipush 0 74 istore 2 75 76loop2: 77 iload 2 78 sipush 10 79if_icmpge branch4 80 aload 1 81 iload 2 82 iaload 83 istore 3 84 iload 2 85 istore 4 86 getstatic java/lang/System/out Ljava/io/PrintStream; 87 ldc "value of a[" 88 invokevirtual java/io/PrintStream/print(Ljava/lang/String;)V 89 getstatic java/lang/System/out Ljava/io/PrintStream; 90 iload 4 91 invokevirtual java/io/PrintStream/print(I)V 92 getstatic java/lang/System/out Ljava/io/PrintStream; 93 ldc "] is " 94 invokevirtual java/io/PrintStream/print(Ljava/lang/String;)V 95 getstatic java/lang/System/out Ljava/io/PrintStream; 96 iload 3 97 invokevirtual java/io/PrintStream/print(I)V 98 getstatic java/lang/System/out Ljava/io/PrintStream; 99 ldc " 100" 101 invokevirtual java/io/PrintStream/print(Ljava/lang/String;)V 102 iload 2 103 sipush 1 104 iadd 105 istore 2 106goto loop2 107branch4: 108 return 109.end method 110.method public static quicksort([III)V 111 sipush 0 112 istore 7 113 sipush 0 114 istore 6 115 iload 1 116 sipush 1 117 isub 118 istore 6 119 sipush 0 120 istore 5 121 sipush 0 122 istore 4 123 sipush 0 124 istore 3 125 iload 2 126 sipush 1 127 isub 128 istore 3 129 iload 1 130 iload 2 131if_icmpge branch1 132 133 aload 0 134 iload 2 135 iaload 136 istore 7 137 iload 1 138 istore 5 139 140loop1: 141 142 iload 5 143 iload 3 144if_icmpgt ibranch1 145 146 aload 0 147 iload 5 148 iaload 149 iload 7 150if_icmpgt ibranch2 151 152 iload 6 153 sipush 1 154 iadd 155 istore 6 156 aload 0 157 iload 6 158 iaload 159 istore 4 160 aload 0 161 iload 6 162 aload 0 163 iload 5 164 iaload 165 iastore 166 aload 0 167 iload 5 168 iload 4 169 iastore 170ibranch2: 171 172 iload 5 173 sipush 1 174 iadd 175 istore 5 176goto loop1 177 178ibranch1: 179 180 iload 6 181 sipush 1 182 iadd 183 istore 3 184 aload 0 185 iload 3 186 iaload 187 istore 4 188 aload 0 189 iload 3 190 aload 0 191 iload 2 192 iaload 193 iastore 194 aload 0 195 iload 2 196 iload 4 197 iastore 198 iload 3 199 sipush 1 200 isub 201 istore 4 202 aload 0 203 iload 1 204 iload 4 205 invokestatic CSourceToJava/quicksort([III)V 206 iload 3 207 sipush 1 208 iadd 209 istore 4 210 aload 0 211 iload 4 212 iload 2 213 invokestatic CSourceToJava/quicksort([III)V 214branch1: 215 216 return 217.end method 218 219.end class
上面的代码转换成jvm字节码运行后结果如下：
编译原理几乎是计算机专业中最晦涩难懂的课程。很多学生学这门课只不过是为了通过考试，学完后对编译原理之精妙仍然是摸不着头脑。而很多教这门课的老师，也只不过是混口饭吃，他自己未必对编译原理有多少深入的了解和把握，于是与其昏昏，使人昭昭。毕业多年后，回过头来反省我所承受的教育，我发现我们的教育总是流于表面的肤浅，给学生展示的始终是冰山的一角，对冰山下的巨大形体去置若罔闻，于是整个系统虽然培养出大量的计算机专业人员，但有能力对计算机知识具备深入见解的人凤毛麟角，很多人其实是走上工作岗位后，通过大量的生产实践才开始对计算机知识有了一定程度的深入窥探的，我就是其中之一。
计算机始终是一门理论结合实践的科学。光有理论却不能实践，那么理论看起来晦涩难懂，听起来虚儿巴脑，于是美妙的智慧结晶在应试教育体制下变成了虚张声势的怪兽，让学习它的人惊恐不慌，以为自己要被这只巨大的怪兽所吞灭。我是过来人，知道这种关说不练假把式的巨大危害，那种理论讲起来头头是道，搞得我晕头转向，处处受挫的煎熬感真是不忍回忆，我真心希望通过动手实践，能够让那些有志于在科技行业大展身手的年轻人不要再走我的老路。
如果人类只会谈情说爱，那么早就灭绝了。因此爱的核心在做不在说，科学技术的理解和掌握更是如此，动手吧！Just Fuck It!
本文分享自微信公众号 - Coding迪斯尼（gh_c9f933e7765d）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。